In the

mathematical modeling A mathematical model is a description of a system using mathematical concepts and language. The process of developing a mathematical model is termed mathematical modeling. Mathematical models are used in the natural sciences (such as physics, ...

job shop scheduling Job-shop scheduling, the job-shop problem (JSP) or job-shop scheduling problem (JSSP) is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. In a general job scheduling problem, we are giv ...

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 graph In graph theory, a mixed graph is a graph consisting of a set of vertices , a set of (undirected) edges , and a set of directed edges (or arcs) . Definitions and notation Consider adjacent vertices u,v \in V. A directed edge, called an arc, ...

s, 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 In software engineering, a circular dependency is a relation between two or more modules which either directly or indirectly depend on each other to function properly. Such modules are also known as mutually recursive. Overview Circular depen ...

– and then ordering the resulting

directed acyclic graph In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called ''arcs''), with each edge directed from one v ...

. 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 In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...

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 In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices ...

of the initial undirected graph.

References

Further reading