Проблема машинного планирования

Question

у меня есть комбинаторная проблема как таковая:

Вам дано N тестеров.

Каждый тестер относится к разным типам M.

Каждый тестер может быть настроен на использование одного из P различных конфигов. .

У вас есть L продуктов для тестирования,

Каждый продукт может быть протестирован только на определенном типе тестера,

Каждый продукт может быть протестирован только тестером, настроенным с определенными настройками. Некоторые из конфигураций могут быть применены к нескольким продуктам. Любой тестер может изменить свою конфигурацию во время производства, но каждое изменение в конфигурации тестера потребует дополнительного времени. Каждый лот имеет размер лота, который определяет его время тестирования, Q.

Теперь мне нужно разработать алгоритм планирования лотов, чтобы время для завершения тестирования всех лотов было минимальным.

Каковы наилучшие подходы для решения такого рода проблем?

Answer 1

Это можно смоделировать как проблему Job-Shop (JSP) с временем установки, когда размер задания равен 1. К сожалению, найти оптимальное решение довольно сложно, когда количество заданий> 10.

Существует множество бесплатных реализаций решателя, которые содержат Job-Shop в качестве примера проблемы: Если вы используете C ++, Gecode - это хорошо. Если вы можете выбирать, ECLiPSe Prolog содержит исходный код для JSP.

Если вы можете сделать с хорошим решением (вместо оптимального), я предлагаю использовать жадный алгоритм (для JSP жадные алгоритмы обычно дают решения в пределах 10% от оптимального - у меня было некоторый опыт с этим). Я подумаю об одном и вернусь сюда (проблема в том, что называется «временными ограничениями настройки», то есть ограничениями, возникающими в результате изменения конфигурации тестера).