Jump to content

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

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

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

Определение

[ редактировать ]

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

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

[ редактировать ]

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

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

[ редактировать ]
  • Планирование цеха представляет собой аналогичную проблему, но с дополнительным ограничением: операции должны выполняться в определенном порядке.
  • Поточно-цеховое планирование — это поточно-цеховое планирование, но с дополнительным ограничением потока — каждая операция должна выполняться на конкретной машине.
  1. ^ Гонсалес, Теофило; Сахни, Сартадж (1976), «Планирование открытых цехов для минимизации времени завершения», Journal of the ACM , 23 (4): 665–679, CiteSeerX   10.1.1.394.1507 , doi : 10.1145/321978.321985 , MR   0429089 , S2CID   164277 5 .
  2. ^ Уильямсон, ДП ; Холл, Луизиана; Хугевен, ДА; Хюркенс, CAJ; Ленстра, JK ; Севастьянов С.В.; Шмойс, Д.Б. (1997), «Краткие графики цехов», Operations Research , 45 (2): 288–294, doi : 10.1287/opre.45.2.288 , JSTOR   171745 , MR   1644998
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: cf4230ceb4470f23e121671e8c924e01__1679897700
URL1:https://arc.ask3.ru/arc/aa/cf/01/cf4230ceb4470f23e121671e8c924e01.html
Заголовок, (Title) документа по адресу, URL1:
Open-shop scheduling - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)