Черных К.А. Сервах В.В.
Исследование комбинаторной структуры оптимальных решений задачи одного станка
Докладчик: Черных К.А.
Рассматривается задача минимизации средневзвешенного времени выполнения работ
одинаковой длительности на одном станке при заданных временах поступления работ и возможности их прерывания. Эта одна из немногих задач, вычислительная сложность которой до сих пор неизвестна. В данной статье исследуется комбинаторная структура возможных оптимальных решений задачи.
Предлагается следующий подход. Для задачи с заданной длительностью и временами поступлений работ веса работ задаются параметрически. Разработанным в работе алгоритмом строится конечное подмножество расписаний, которое заведомо содержит оптимальное решение. Для каждого построенного расписания с помощью задачи линейного программирования определяется набор весов, при которых оно оптимально, либо доказывается, что такого набора нет. Тем самым можно исследовать структуры оптимальных расписаний и причины, по которым некоторые расписания не могут быть оптимальными.
В работе исследовано несколько ключевых примеров, получены основные комбинаторные
свойства оптимальных решений, сделан соответствующий анализ, выделены полиномиально разрешимые случаи.
К списку докладов