Задача линейного программирования онлайн в целых числах

Основные моменты

В рукописи описываются сложные реальные проблемы планирования. Возникающие в современной полиграфической промышленности.

В качестве первого солидного шага к его разрешению представлены смешанные модели целочисленного линейного программирования и программирования ограничений.

Рассмотрены обширные численные эксперименты с крупногабаритными экземплярами размера реальных экземпляров.

Численные эксперименты показывают. Что готовый решатель может быть альтернативой на практике.

Абстрактный

В данной работе рассматривается проблема планирования работы интернет-типографии.

Эту сложную реальную проблему. Которая появляется в современной полиграфической промышленности. Можно рассматривать как гибкую задачу планирования рабочего цеха с гибкостью последовательности. В которой ограничения приоритета между операциями задания задаются произвольным направленным ациклическим графом. Кроме того, в рассматриваемой задаче также присутствует ряд усложняющих особенностей. Таких как периоды недоступности машин. Возобновляемые операции. Зависящее от последовательности время настройки. Частичное перекрытие операций с ограничениями приоритета. Время выпуска и фиксированные операции.

В настоящей работе представлены модели смешанного целочисленного линейного программирования и программирования ограничений для минимизации макеспана. Задача моделирования состоит из двух частей. С одной стороны. Проблема четко определена. С другой стороны. Анализируются возможности и ограничения коммерческого программного обеспечения для решения этих моделей. Представлены обширные численные эксперименты с мелкими. Средними и крупными экземплярами. Численные эксперименты показывают. Что коммерческий решатель способен оптимально решить только часть небольших экземпляров при рассмотрении смешанной модели целочисленного линейного программирования; в то время как все малые и часть средних экземпляров оптимально решаются при рассмотрении формулировки задачи программирования ограничений.

Более того, коммерческий решатель способен предоставить выполнимые решения для крупногабаритных экземпляров. Которые имеют размер экземпляров. Появляющихся на практике.

Ключевые слова

Гибкое планирование работы цеха с гибкостью последовательности

Возобновляемые операции

Отсутствие машин

Время настройки в зависимости от последовательности

Смешанное целочисленное линейное программирование

Программирование ограничений

MSC[2010]

90B35

90С11

90С59

Просмотр полного текста

© 2020 Elsevier Ltd. Все права защищены.