Disjunctive graph
In the mathematical modeling of 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, in which vertices (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. A valid schedule for the disjunctive graph may be obtained by finding an 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 – and then ordering the resulting 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 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 to find the acyclic orientation that minimizes the length of the longest path. In particular, by the Gallai–Hasse–Roy–Vitaver theorem, if all edges are initially undirected, then orienting them to minimize the longest path is equivalent to finding an optimal graph coloring of the initial undirected graph.
In the mathematical modeling of 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, in which vertices (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 of the undirected edges – that is, deciding for each pair of non-simultaneous tasks which is to be first, without introducing any circular dependencies – and then ordering the resulting 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 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 to find the acyclic orientation that minimizes the length of the longest path. In particular, by the Gallai–Hasse–Roy–Vitaver theorem, if all edges are initially undirected, then orienting them to minimize the longest path is equivalent to finding an optimal graph coloring of the initial undirected graph.
References
[edit]- ^ Gröflin, H.; Klinkert, A. (2002), "Scheduling with generalized disjunctive graphs: Feasibility issues", XV Conference of the European Chapter on Combinatorial Optimization (ECCO XV), May 30 - June 1, 2002, Lugano, Switzerland.
- ^ Olson, Lars E. (August 2003), Querying Disjunctive Databases in Polynomial Time (PDF), Master's thesis, Brigham Young University, Department of Computer Science.
- ^ Roy, S.; Sussman, B. (December 1964), Les problemes d'ordonnancement avec contraintes disjonctives, Note D.S. No. 9 bis, SEMA.
Further reading
[edit]- 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