Disjunctive graph
 | This article may be too technical for most readers to understand. (October 2012) |
 | The topic of this article may not meet Wikipedia's general notability guideline. (September 2012) |
A Disjunctive Graph is a special graph structure, frequently used in Job Shop scheduling (kind of) problems.[1] A disjunctive graph is defined as a graph containing disjunctive edges. The disjunctive edge represents an edge which can connect any two vertices from the possible set of vertices.[2]
The disjunctive graph [3] is a directed graph G(V,C U D), where V denotes a set of vertices corresponding to tasks of jobs. This set contains two additional vertices: a source and a sink, which represent the start and the end of a schedule. The source is equivalent to a dummy task T0 preceding all other tasks and the sink to a dummy task T(n+1) succeeding all other tasks. Both dummy tasks have zero processing time. C is a set of conjunctive arcs 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)
3. E. BALAS, "Machine Sequencing: Disjunctive Graphs and Degree-Constrained Subgraphs," IBM, New York Scientific Center Report No. 320-2971 (April 1969).
 | This article has not been added to any content categories. Please help out by adding categories to it so that it can be listed with similar articles. (September 2012) |