- A finite set of n jobs
- Each job consists of a chain of operations
- A finite set of m machines
- Each machine can handle at most one operation at a time
- Each operation needs to be processed during an uninterrupted period of a given length on a given machine
- Purpose is to find a schedule, that is, an allocation of the operations to time intervals to machines, that has minimal length
(Xu, 2001)
A disjunctive graph can be used to represent the JSSP. An example of such a graph for a JSSP with 2 jobs and 3 machines is shown below.
1. Conjunctive arcs (solid) represent the precedence relationships between operations in the same job. For instance, O11 has to be performed before O12, and O22 has to be performed before O23.
2. Disjunctive arcs (dashed) join two operations from different jobs which share the same machine.
3. The weight of each conjunctive arc represents the processing time of the operation at the start of the arc. For example, the processing time of operation O11 is 1, while the processing time of operation O21 is 6.
Initially, the disjunctive arcs are un-directed. In order to find a feasible solution, the direction of every disjunctive arc has to be set in such a way that it does not result in a cycle. The figure below shows an infeasible solution due to the presence of a cycle {O11, O12, O21, O22, O23, O11}.
