Планирование в открытом цехе или задача планирования в открытом цехе ( OSSP ) — это задача оптимизации в информатике и исследовании операций . Это вариант оптимального планирования заданий . В общей задаче планирования заданий нам даны n заданий J 1 , J 2 , ..., J n с различным временем обработки, которые необходимо запланировать на m машинах с различной вычислительной мощностью, при этом пытаясь минимизировать время выполнения — общую длину расписания (то есть время, когда все задания закончат обработку). В конкретном варианте, известном как планирование в открытом цехе , каждое задание состоит из набора операций O 1 , O 2 , ..., O n , которые необходимо обработать в произвольном порядке. Впервые эту задачу изучили Теофило Ф. Гонсалес и Сартадж Сахни в 1976 году . [1]
В стандартной трехполевой нотации для задач оптимального планирования заданий вариант с открытым цехом обозначается как O в первом поле. Например, задача, обозначенная как " O3| | ", представляет собой задачу с тремя станками и единичным временем обработки, где целью является минимизация максимального времени завершения.
Входные данные для задачи планирования открытого цеха состоят из набора из n заданий, другого набора из m рабочих станций и двумерной таблицы количества времени, которое каждое задание должно провести на каждой рабочей станции (возможно, ноль). Каждое задание может обрабатываться только на одной рабочей станции за раз, и каждая рабочая станция может обрабатывать только одно задание за раз. Однако, в отличие от задачи рабочего цеха , порядок, в котором происходят этапы обработки, может свободно меняться. Цель состоит в том, чтобы назначить время для обработки каждого задания каждой рабочей станцией, так, чтобы никакие два задания не были назначены на одну и ту же рабочую станцию в одно и то же время, никакие задания не были назначены на две рабочие станции в одно и то же время, и каждое задание было назначено на каждую рабочую станцию на желаемое количество времени. Обычной мерой качества решения является его makespan , количество времени от начала расписания (первого назначения задания рабочей станции) до его конца (времени окончания последнего задания на последней рабочей станции).
Задача планирования open-shop может быть решена за полиномиальное время для экземпляров, имеющих только две рабочие станции или только две работы. Она также может быть решена за полиномиальное время, когда все ненулевые времена обработки равны: в этом случае задача становится эквивалентной раскраске ребер двудольного графа , вершинами которого являются работы и рабочие станции, и который имеет ребро для каждой пары работа-рабочая станция, имеющей ненулевое время обработки. Цвет ребра в раскраске соответствует отрезку времени, на который запланирована обработка пары работа-рабочая станция. Поскольку линейные графы двудольных графов являются идеальными графами , двудольные графы могут быть раскрашены по ребрам за полиномиальное время.
Для трех или более рабочих станций или трех или более заданий с различным временем обработки планирование в открытом цехе является NP-трудным . [2]
