Дизъюнктивный граф

Способ представления проблем планирования путем демонстрации задач и правил расчета времени, которым они должны следовать.

В математическом моделировании задач планирования в цехе дизъюнктивные графы являются способом моделирования системы задач, которые должны быть запланированы, и ограничений по времени, которые должны соблюдаться расписанием. Это смешанные графы , в которых вершины (представляющие задачи, которые должны быть выполнены) могут быть соединены как направленными, так и ненаправленными ребрами (представляющими ограничения по времени между задачами). Два типа ребер представляют ограничения двух разных типов:

• Если одна задача x должна быть выполнена раньше, чем вторая задача y , это ограничение представлено направленным ребром от x к y .
• С другой стороны, если две задачи x и y могут быть выполнены в любом порядке, но не одновременно (возможно, потому что они обе требуют использования одного и того же оборудования или другого ресурса), это ограничение неодновременности представлено ненаправленным ребром, соединяющим x и y .

Пары задач, не имеющие ограничений на порядок выполнения (они могут выполняться в любом порядке или даже одновременно), на графике отделены друг от друга. ^{[1] [2] [3]}

Допустимое расписание для дизъюнктивного графа может быть получено путем нахождения ациклической ориентации неориентированных ребер — то есть, решая для каждой пары неодновременных задач, которая должна быть первой, без введения каких-либо циклических зависимостей — и затем упорядочивая полученный направленный ациклический граф . В частности, предположим, что все задачи имеют одинаковую длину, и цель состоит в том, чтобы найти расписание, которое минимизирует makespan, общее время до завершения всех задач. В этом случае makespan можно вычислить из самого длинного пути в ориентированном графе, который можно найти за полиномиальное время для направленных ациклических графов. Однако этап ориентации решения намного сложнее: NP -трудно найти ациклическую ориентацию, которая минимизирует длину самого длинного пути. В частности, по теореме Галлаи–Хассе–Роя–Витавера , если все ребра изначально неориентированы, то их ориентация для минимизации самого длинного пути эквивалентна нахождению оптимальной раскраски исходного неориентированного графа.

Ссылки

1. Грёфлин, Х.; Клинкерт, А. (2002), «Планирование с обобщенными дизъюнктивными графами: вопросы осуществимости», XV конференция Европейской секции по комбинаторной оптимизации (ECCO XV), 30 мая - 1 июня 2002 г., Лугано, Швейцария.
2. Олсон, Ларс Э. (август 2003 г.), Запросы к дизъюнктивным базам данных за полиномиальное время (PDF) , магистерская диссертация, Университет имени Бригама Янга, кафедра компьютерных наук.
3. Рой, С.; Сассман, Б. (декабрь 1964 г.), Les Issuees d'ordonnancement avec contraintes disjonctives , Примечание DS № 9 bis, SEMA.

Дальнейшее чтение

• Балас, Эгон (апрель 1969 г.), Машинное секвенирование: дизъюнктивные графы и подграфы с ограниченной степенью , отчет № 320–2971, IBM, Нью-Йоркский научный центр.
• Балас, Эгон (1969), «Машинное секвенирование с помощью дизъюнктивных графов: неявный алгоритм перечисления», Operations Research , 17 : 941–957, doi :10.1287/opre.17.6.941, MR  0250770.
• Блажевич, Яцек; Пеш, Эрвин; Стерна, Малгожата (2000), «Представление задачи планирования рабочего цеха с помощью дизъюнктивной графовой машины», Европейский журнал операционных исследований , 127 (2): 317–331, doi :10.1016/S0377-2217(99)00486-5.
• Мейсон, Скотт Дж.; Ой, Касин (2003), «Планирование сложных цехов с использованием дизъюнктивных графов: процедура исключения цикла», Международный журнал исследований производства , 41 (5): 981–994, doi :10.1080/00207540210163009