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:

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

  1. ↑ 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.
  2. ↑ Olson, Lars E. (August 2003), Querying Disjunctive Databases in Polynomial Time (PDF), Master's thesis, Brigham Young University, Department of Computer Science.
  3. ↑ Roy, S.; Sussman, B. (December 1964), Les problemes d'ordonnancement avec contraintes disjonctives, Note D.S. No. 9 bis, SEMA.

Additional reading

This article is issued from Wikipedia - version of the Tuesday, December 22, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.