Дизъюнктивный граф
При математическом моделировании задач планирования цеха представляют собой способ моделирования системы задач, которые необходимо запланировать , дизъюнктивные графы и временных ограничений, которые должны соблюдаться графиком.Это смешанные графы , в которых вершины (представляющие задачи, которые необходимо выполнить) могут быть соединены как направленными, так и неориентированными ребрами (представляющими временные ограничения между задачами). Два типа ребер представляют ограничения двух разных типов:
- Если одна задача x должна быть выполнена раньше, чем вторая задача y , это ограничение представлено направленным ребром от x до y .
- Если, с другой стороны, две задачи x и y могут выполняться в любом порядке, но не одновременно (возможно, потому, что обе они требуют использования одного и того же оборудования или другого ресурса), это ограничение неодновременности представлено ненаправленным ребром. соединяя х и у .
Пары задач, у которых нет ограничений на их порядок — они могут выполняться в любом порядке или даже одновременно — в графе отключены друг от друга. [1] [2] [3]
Допустимое расписание для дизъюнктивного графа можно получить, найдя ациклическую ориентацию ненаправленных ребер – то есть решая для каждой пары неодновременных задач, которая должна быть первой, без введения каких-либо циклических зависимостей – и затем упорядочивая полученные направленные ациклический граф . В частности, предположим, что все задачи имеют одинаковую длину и цель состоит в том, чтобы найти расписание, которое минимизирует время выполнения, общее время до завершения всех задач. В этом случае длина пути может быть вычислена по самому длинному пути в ориентированном графе, который можно найти за полиномиальное время для ориентированных ациклических графов. Однако этап ориентации решения гораздо сложнее: NP-трудно найти ациклическую ориентацию, минимизирующую длину самого длинного пути. В частности, по теореме Галлаи–Хассе–Роя–Витавера , если все ребра изначально неориентированные, то ориентация их так, чтобы минимизировать самый длинный путь, эквивалентна поиску оптимальной раскраски исходного неориентированного графа.
Ссылки
[ редактировать ]- ^ Грефлин, Х.; Клинкерт, А. (2002), «Планирование с использованием обобщенных дизъюнктивных графов: вопросы осуществимости», XV конференция Европейского отделения комбинаторной оптимизации (ECCO XV), 30 мая - 1 июня 2002 г., Лугано, Швейцария .
- ^ Олсон, Ларс Э. (август 2003 г.), Запрос к дизъюнктивным базам данных за полиномиальное время (PDF) , магистерская диссертация, Университет Бригама Янга, факультет компьютерных наук .
- ^ Рой, С.; Сассман, Б. (декабрь 1964 г.), Проблемы планирования с дизъюнктивными ограничениями , Примечание DS № 9 bis, SEMA .
Дальнейшее чтение
[ редактировать ]- Балас, Эгон (апрель 1969 г.), Машинное секвенирование: дизъюнктивные графы и подграфы со степенью ограничения , отчет № 320–2971, IBM, Нью-Йоркский научный центр .
- Балас, Эгон (1969), «Машинное секвенирование с помощью дизъюнктивных графов: неявный алгоритм перечисления», Operations Research , 17 : 941–957, doi : 10.1287/opre.17.6.941 , MR 0250770 .
- Блажевич, Яцек; Пеш, Эрвин; Стерна, Малгожата (2000), «Представление задачи планирования цеха на дизъюнктивной графовой машине», European Journal of Operational Research , 127 (2): 317–331, doi : 10.1016/S0377-2217(99)00486-5 .
- Мейсон, Скотт Дж.; Оуи, Касин (2003), «Планирование сложных цехов с использованием дизъюнктивных графов: процедура исключения цикла», International Journal of Production Research , 41 (5): 981–994, doi : 10.1080/00207540210163009