| Аннотацiя: | Описан генетический алгоритм для решения задачи job-shop, характеризующейся наличием альтернативных приборов. Рассматриваемая задача является одной из самых сложных среди задач комбинаторной оптимизации и относится к числу NP-трудных. В статье раскрываются идеи представления расписаний и преобразования невыполнимых расписаний в выполнимые. Вычислительные эксперименты показали, что предложенный метод позволяет находить близкие к оптимальным решения для стандартных вычислительных тестов и имеет полиномиальную сложность.
Ключевые слова: задачи составления расписаний, генетические алгоритмы, альтернативные приборы, job-shop
|