Disjunctive graph

A Disjunctive Graph is a special graph structure, frequently used in Job Shop scheduling (kind of) problems.

The disjunctive graph 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

3. E. BALAS, "Machine Sequencing: Disjunctive Graphs and Degree-Constrained Subgraphs," IBM, New York Scientific Center Report No. 320-2971 (April 1969).