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

Question

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

Вам даны тестеры N.

Каждый тестер является одним из М различных типов.

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

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

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

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

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

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

Answer 1

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

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

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