Abstract: Рассматривается цеховая задача составления расписаний открытого типа [3] (open-shop) с точки зрения вычислительной сложности и подходов к решению. Обсуждаются точные и приближенные конструктивные алгоритмы для классического варианта задачи и выявляются новые комбинаторные свойства формируемых ими расписаний. Доказывается, что свойства расписаний и нижних оценок на целевую функцию позволяют обобщить результаты на варианты задачи с учетом ресурсов возобновимого и невозобновимого типов [1, 2], в том числе, когда потребление ресурса и длительность операции имеют нелинейную зависимость. Устанавливаются новые полиномиально разрешимые и NP-трудные частные случаи.

Cite: Захарова Ю.В.
О комбинаторных методах решения одной цеховой задачи составления расписаний открытого типа
Комбинаторно-вычислительные методы алгебры и логики 15-19 июл. 2024