График работы открытого цеха

Планирование открытого цеха или проблема планирования открытого цеха ( OSSP ) — это задача оптимизации в информатике и исследовании операций . Это вариант оптимального планирования работы . В общей задаче планирования заданий нам даны n заданий J ₁ , J ₂ , ..., J _n с различным временем обработки, которые необходимо запланировать на m машинах с различной вычислительной мощностью, пытаясь при этом минимизировать время выполнения : общая продолжительность расписания (то есть время, когда все задания завершили обработку). В конкретном варианте, известном как планирование открытого цеха , каждое задание состоит из набора операций O ₁ , O ₂ , ..., O _n , которые необходимо обрабатывать в произвольном порядке. Проблема была впервые изучена Теофило Ф. Гонсалесом и Сартаджем Сахни в 1976 году.

В стандартной записи трех полей для задач оптимального планирования работ вариант открытого цеха обозначается буквой O в первом поле. Например, проблема, обозначенная « O3| $p_{ij}$| $C_{\max }$« — это задача цеха с тремя станками и единичным временем обработки, цель которой — минимизировать максимальное время завершения.

Определение

Входные данные для задачи планирования открытого цеха состоят из набора из n заданий, другого набора из m рабочих станций и двумерной таблицы количества времени, которое каждое задание должно провести на каждой рабочей станции (возможно, ноль). Каждое задание может обрабатываться только на одной рабочей станции одновременно, и каждая рабочая станция может обрабатывать только одно задание за раз. Однако, в отличие от задачи цеха , порядок выполнения этапов обработки может свободно меняться. Цель состоит в том, чтобы назначить время для обработки каждого задания на каждой рабочей станции, чтобы никакие два задания не были назначены на одну и ту же рабочую станцию ​​одновременно, ни одно задание не было назначено двум рабочим станциям одновременно, и каждое задание было назначено. на каждую рабочую станцию ​​в течение желаемого периода времени. Обычной мерой качества решения является его длительность , количество времени от начала расписания (первое назначение задания на рабочую станцию) до его завершения (время завершения последнего задания на последней рабочей станции).

Вычислительная сложность

Задача планирования открытого цеха может быть решена за полиномиальное время для случаев, когда имеется только две рабочие станции или только два рабочих места. Ее также можно решить за полиномиальное время, когда все ненулевые времена обработки равны: в этом случае проблема становится эквивалентной раскраске , ребер двудольного графа вершинами которого являются задания и рабочие станции, и который имеет ребро для каждой пары задание-рабочая станция. который имеет ненулевое время обработки. Цвет ребра в раскраске соответствует сегменту времени, на который запланирована обработка пары задание-рабочая станция. Поскольку линейные графы являются двудольных графов совершенными графами , двудольные графы могут быть раскрашены по краям за полиномиальное время.

Для трех и более рабочих станций или трех и более заданий с разным временем обработки планирование открытого цеха является NP-сложным .

Связанные проблемы

• Планирование цеха представляет собой аналогичную проблему, но с дополнительным ограничением: операции должны выполняться в определенном порядке.
• Поточно-цеховое планирование — это поточно-цеховое планирование, но с дополнительным ограничением потока — каждая операция должна выполняться на конкретной машине.