Дизъюнктивный граф
В математическом моделировании по вопросам планирования работ на производстве или предприятии дизъюнктивные графы представляют собой способ представления поставленных задач и временных ограничений, которые должны соблюдаться планом работ. Это смешанные графы, в которых вершины (представляющие задачи, которые должны быть выполнены) могут быть соединены как направленными, так и неориентированными ребрами (представляющими временные ограничения между задачами). Эти два типа ребер представляют ограничения двух разных типов:
- Если одна задача x должна быть выполнена раньше, чем вторая задача y, это ограничение представлено направленным ребром от x до y.
- Если, с другой стороны, две задачи x и y могут выполняться в любом порядке, но не одновременно (возможно, потому, что они оба требуют использования одного и того же оборудования или другого ресурса), это ограничение одновременности представлено неориентированным ребром, соединяющим x и y.
Пары задач, которые не имеют ограничений по порядку их выполнения — могут осуществляться в любом порядке или даже одновременно — не связаны друг с другом на графе[1][2][3].
Правильное планирование для дизъюнктивного графа может быть получено путем нахождения ациклической ориентации ненаправленных ребер, то есть решения для каждой пары несовпадающих задач, какая из них должна быть первой, не вводя никаких циклических зависимостей[англ.], а затем упорядочив полученный ориентированный ациклический граф. В частности, предположим, что все задачи имеют одинаковую продолжительность, и цель состоит в том, чтобы найти такое расписание, которое минимизирует время выполнения, общее время до завершения всех задач. В этом случае время выполнения может быть вычислено по самому длинному пути в ориентированном графе, который может быть найден за полиномиальное время для направленных ациклических графов. Однако этап решения проблемы ориентации намного сложнее: NP — трудная задача для нахождения ациклической ориентации, которая минимизирует длину самого длинного пути. В частности, по теореме Галлая-Хассе-Роя-Витавер, если все ребра изначально не ориентированы, то их ориентация для минимизации самого длинного пути эквивалентна нахождению оптимальной разметки исходного неориентированного графа.
Дальнейшее чтение[править | править код]
- Balas, Egon (April 1969), Machine Sequencing: Disjunctive Graphs and Degree-Constrained Subgraphs, Report No. 320–2971, IBM, New York Scientific Center.
- Balas, Egon (1969), "Machine sequencing via disjunctive graphs: An implicit enumeration algorithm", Operations Research, 17: 941-957, doi: 10.1287/opre.17.6.941, MR 0250770.
- Błażewicz, Jacek; Pesch, Erwin; Sterna, Małgorzata (2000), "The disjunctive graph machine representation of the job shop scheduling problem", European Journal of Operational Research, 127 (2): 317-331, doi: 10.1016/S0377-2217(99)00486-5.
- Mason, Scott J.; Oey, Kasin (2003), "Scheduling complex job shops using disjunctive graphs: A cycle elimination procedure", International Journal of Production Research, 41 (5): 981-994, doi: 10.1080 / 00207540210163009
Примечания[править | править код]
- ↑ Gröflin, H.; Klinkert, A. "Scheduling with generalized disjunctive graphs: Feasibility issues" // XV Conference of the European Chapter on Combinatorial Optimization (ECCO XV). — Lugano, Switzerland., 2002. — 30 мая.
- ↑ Olson, Lars E. Querying Disjunctive Databases in Polynomial Time (PDF) // Brigham Young University, Department of Computer Science. : Master's thesis. — 2003. — Август. Архивировано 1 июля 2022 года.
- ↑ Roy, S.; Sussman, B. Les problemes d'ordonnancement avec contraintes disjonctives // SEMA : Note D.S.. — 1964. — Декабрь (вып. 9).