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

 Если одна задача x должна быть выполнена раньше, чем вторая задача y, это ограничение представлено направленным ребром от x до y.

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

Пары задач, которые не имеют ограничений по порядку их выполнения — могут осуществляться в любом порядке или даже одновременно — не связаны друг с другом на графе.

Правильное планирование для дизъюнктивного графа может быть получено путем нахождения ациклической ориентации ненаправленных ребер, то есть решения для каждой пары несовпадающих задач, какая из них должна быть первой, не вводя никаких , а затем упорядочив полученный ориентированный ациклический граф. В частности, предположим, что все задачи имеют одинаковую продолжительность, и цель состоит в том, чтобы найти такое расписание, которое минимизирует время выполнения, общее время до завершения всех задач. В этом случае время выполнения может быть вычислено по самому длинному пути в ориентированном графе, который может быть найден за полиномиальное время для направленных ациклических графов. Однако этап решения проблемы ориентации намного сложнее: 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

Примечания 

Приложения теории графов