Disjunctive graph
 | This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these messages)
|
A disjunctive graph is a mixed graph, frequently used in problems resembling job shop scheduling problems.[1] A disjunctive graph is defined as a graph containing disjunctive edges. The disjunctive edge represents an edge that can connect any two vertices from the possible set of vertices.[2]
The disjunctive graph [3] is a directed graph G=(V, C ,D), where V denotes a set of vertices corresponding to tasks of jobs. C is a set of conjunctive arcs (directed edges) which reflect the precedence constraints initially connecting every two consecutive tasks of the same job. Undirected disjunctive edges belonging to set D connect mutually unordered tasks which require the same machine for their execution (a disjunctive edge can be represented by two opposite directed arcs). Each arc is labelled with the positive weight equal to the processing time of the task where the arc begins.
The job shop scheduling problem requires to find an optimal order of all tasks on the machines, resulting in a schedule with the minimal length. In the disjunctive graph model, this is equivalent to select one arc in each disjunction, i.e. to turn each undirected disjunctive edge into a directed conjunctive one. By fixing directions of all disjunctive edges, the execution order of all conflicting tasks requiring the same machine is determined and a complete schedule is obtained. Moreover, the resulting graph has to be acyclic and if it is optimal, the length of the longest path from the source to the sink is minimum. This longest path determines the makespan, it is the duration of the longest chain of tasks in a job shop.
References
- ^ http://www.idp.zhaw.ch/fileadmin/user_upload/engineering/_Institute_und_Zentren/IDP/pdfs/Publikationen/klinkert_ecco_2002.pdf
- ^ Querying Disjunctive Databases in Polynomial Time; Lars E. Olson, David W. Embley
- ^ S. ROY AND B. SUSSMAN, "Les problemes d'ordonnancement avec contraintes disjonctives," SEMA, Note D.S. No. 9 bis (decembre 1964)
4. E. BALAS, "Machine Sequencing: Disjunctive Graphs and Degree-Constrained Subgraphs," IBM, New York Scientific Center Report No. 320–2971 (April 1969).
5. Balas, Egon. "Machine sequencing via disjunctive graphs: an implicit enumeration algorithm." Operations research 17.6 (1969): 941-957.
6. Bl̶ażewicz, Jacek, Erwin Pesch, and Malgorzata Sterna. "The disjunctive graph machine representation of the job shop scheduling problem." European Journal of Operational Research 127.2 (2000): 317-331.
7. Mason, Scott J., and Kasin Oey. "Scheduling complex job shops using disjunctive graphs: a cycle elimination procedure." International journal of production research 41.5 (2003): 981-994.