# Disjunctive graph

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Disjunctive_graph
> Markdown URL: https://mediated.wiki/source/Disjunctive_graph.md
> Source: https://en.wikipedia.org/wiki/Disjunctive_graph
> Source revision: 1329550644
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

Mathematical concept

In the [mathematical modeling](/source/Mathematical_modeling) of [job shop scheduling](/source/Job_shop_scheduling) problems, **disjunctive graphs** are a way of modeling a system of tasks to be scheduled and timing constraints that must be respected by the schedule. They are [mixed graphs](/source/Mixed_graph), in which [vertices](/source/Vertex_(graph_theory)) (representing tasks to be performed) may be connected by both directed and undirected edges (representing timing constraints between tasks). The two types of edges represent constraints of two different types:

- If one task *x* must be performed earlier than a second task *y*, this constraint is represented by a directed edge from *x* to *y*.

- If, on the other hand, two tasks *x* and *y* can be performed in either order, but not simultaneously (perhaps because they both demand the use of the same equipment or other resource), this non-simultaneity constraint is represented by an undirected edge connecting *x* and *y*.

Pairs of tasks that have no constraint on their ordering – they can be performed in either order or even simultaneously – are disconnected from each other in the graph.[1][2][3]

A valid schedule for the disjunctive graph may be obtained by finding an [acyclic orientation](/source/Acyclic_orientation) of the undirected edges – that is, deciding for each pair of non-simultaneous tasks which is to be first, without introducing any [circular dependencies](/source/Circular_dependency) – and then ordering the resulting [directed acyclic graph](/source/Directed_acyclic_graph). In particular, suppose that all tasks have equal length and the goal is to find a schedule that minimizes the makespan, the total time until all tasks have been completed. In this case, the makespan can be computed from the [longest path](/source/Longest_path) in the oriented graph, which can be found in polynomial time for directed acyclic graphs. However, the orientation stage of the solution is much more difficult: it is [NP-hard](/source/NP-hard) to find the acyclic orientation that minimizes the length of the longest path. In particular, by the [Gallai–Hasse–Roy–Vitaver theorem](/source/Gallai%E2%80%93Hasse%E2%80%93Roy%E2%80%93Vitaver_theorem), if all edges are initially undirected, then orienting them to minimize the longest path is equivalent to finding an optimal [graph coloring](/source/Graph_coloring) of the initial undirected graph.

## References

1. **[^](#cite_ref-1)** Gröflin, H.; Klinkert, A. (2002), "Scheduling with generalized disjunctive graphs: Feasibility issues", *XV Conference of the [European Chapter on Combinatorial Optimization](/source/European_Chapter_on_Combinatorial_Optimization) (ECCO XV), May 30 - June 1, 2002, Lugano, Switzerland*.

1. **[^](#cite_ref-2)** Olson, Lars E. (August 2003), [*Querying Disjunctive Databases in Polynomial Time*](http://www.deg.byu.edu/papers/lars_thesis.pdf) (PDF), Master's thesis, Brigham Young University, Department of Computer Science.

1. **[^](#cite_ref-3)** Roy, S.; Sussman, B. (December 1964), *Les problemes d'ordonnancement avec contraintes disjonctives*, Note D.S. No. 9 bis, SEMA.

## Further reading

- 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](/source/Doi_(identifier)):[10.1287/opre.17.6.941](https://doi.org/10.1287%2Fopre.17.6.941), [MR](/source/MR_(identifier)) [0250770](https://mathscinet.ams.org/mathscinet-getitem?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](/source/Doi_(identifier)):[10.1016/S0377-2217(99)00486-5](https://doi.org/10.1016%2FS0377-2217%2899%2900486-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](/source/Doi_(identifier)):[10.1080/00207540210163009](https://doi.org/10.1080%2F00207540210163009)

---
Adapted from the Wikipedia article [Disjunctive graph](https://en.wikipedia.org/wiki/Disjunctive_graph) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Disjunctive_graph?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.