In a job shop each job has its own route through the machines, so there is no single sequence to choose. What there is is one binary decision per pair of operations that share a machine. Fix all of them and the shop becomes an ordinary project network whose longest path is the makespan; fix them badly and the network has a cycle, which is a deadlock and a real answer rather than an error. On the lab's four operations there are four orientations, one of them deadlocks, and the best finishes at 6.
Core ideas
Three ideas, and the second is the one that makes this an integer programme rather than a sequencing problem.
Each job carries an ordered list of operations — this machine, then that one — and that list is part of the data. What is undecided is the order in which a machine serves the operations that need it. With two jobs going through two machines in opposite directions there is no single permutation to optimise: the two machines have two separate questions, and the answers interact.
Two operations needing the same machine must not overlap, which means one finishes before the other starts — a choice with exactly two answers. That is the either-or constraint of “Integer Programming”, and it is why this problem is an integer programme and the single-machine rules are not. With k shared pairs there are 2^k orientations, and the lab enumerates all of them at this size.
Orient the pairs and every precedence in the shop becomes an arc: the route arcs from the data, the disjunctive arcs from the choices. If the resulting network is acyclic it is an ordinary project network and its longest path is the makespan. If it has a cycle, the choices require each of a set of operations to wait for another, and no schedule exists at all. The lab counts those orientations rather than skipping them, because how many of the choices are infeasible is part of what the problem looks like.
The material
The model, one bit per shared pair, all four orientations of a two-job shop written out, and the one that cannot be run.
A set of jobs, each an ordered list of operations. Operation i of job j needs a named machine for a given duration and cannot start until operation i − 1 of the same job has finished. A machine runs one operation at a time. The route is fixed by the data; the order in which each machine serves the operations assigned to it is the decision.
A flow shop is the special case where every job has the same route. A job shop allows the routes to differ, and that is the whole of the difficulty.
Two operations needing the same machine form a disjunctive pair, and an orientation chooses, for every such pair, which of the two goes first. With k pairs there are 2^k orientations. An orientation together with the route arcs is a directed graph; when it is acyclic the earliest start times are a forward pass over it and the makespan is its longest path.
That last sentence is the whole method and it is borrowed rather than invented. Once every pair is oriented there is nothing left to decide, and what remains is the project network of “Networks: Flows, Paths and Assignments”, with the same forward pass and the same longest path. The scheduling content is entirely in the choice of orientation.
The best orientation is the one that lets the two jobs start at once on the machines they each need first. J1 takes M1 from 0 to 3; J2 takes M2 from 0 to 4; then J1 moves to M2 at 4 and finishes at 6, and J2 moves to M1 at 4 and finishes at 5. The makespan is 6, which equals the load on M2 — that machine never stopped, so nothing could have been faster.
Choose J2 before J1 on M1 and J1 before J2 on M2. Now follow the requirements round: J1's M1 operation waits for J2's M1 operation, which waits — by J2's own route — for J2's M2 operation, which waits for J1's M2 operation, which waits — by J1's own route — for J1's M1 operation.
Four requirements in a circle, and not one of the four is unreasonable on its own. Nothing can start. The lab reports this orientation as deadlocked rather than assigning it a makespan or quietly dropping it, and it counts how many of the orientations are in that state: one of the four here, seven of the sixteen on its three-job preset.
At this size the lab does the only completely honest thing: it builds all 2^k orientations, computes start times for each acyclic one, and reads the schedule back off the drawing to check that no machine runs two operations at once and no job starts a step before the one before it finished. Then it reports the best, the count and how many deadlocked.
2^k is the number to look at. Four pairs is sixteen orientations and is comfortable; ten pairs is a thousand and is still fine; thirty pairs is a billion and is not. The count of pairs grows roughly as the square of the operations on the busiest machine, so a shop with one machine everything passes through gets expensive fastest — which is what the lab's third preset is for, with three of its four pairs on a single machine.
There is no exchange argument here and there is not going to be. The single-machine rules worked because a schedule was an order, two jobs could be adjacent, and swapping them moved the objective by one subtraction. In a job shop a schedule is a set of binary choices whose feasibility is a property of the whole set — one flipped bit can turn a working schedule into a deadlock — and no local argument reaches that.
What remains is search, and the search is the one “Integer Programming” builds: branch on a disjunction, bound each node, and report a gap when the tree has not closed. The lower bound is free and worth taking — every machine's total load and every job's total length are both lower bounds on the makespan, since a machine cannot compress its own work and a job cannot overlap its own operations. On the two-job shop that gives 6, which the best orientation attains, so the enumeration was confirming something a bound had already proved.
Interactive
One bit per pair of operations on a machine; some settings of those bits deadlock
Method
Five steps, and the third is the one that decides whether there is a schedule at all.
job machine duration, listed in route order for each job. The route is data and is not up for discussion; writing it in the wrong order produces a perfectly consistent answer to a different shop.
A machine with r operations on it contributes r(r−1)/2 pairs, so the busiest machine dominates the count. Three operations on one machine is three pairs, and with a fourth pair elsewhere that is sixteen orientations to consider.
Draw the route arcs and the oriented arcs together and follow them. A cycle means no operation in it can start, and the orientation is a deadlock — not a slow schedule, not an error in the data, just a combination of choices that cannot be run.
Earliest start of an operation is the largest earliest finish among its predecessors, route arcs and disjunctive arcs alike. The makespan is the longest path, exactly as in a project network, and the critical path is the chain that holds it.
Every machine's total load and every job's total length bound the makespan from below. If the best orientation you have found attains the largest of them, you have a proof and can stop searching. On the two-job shop that bound is 6 and the best orientation attains it.
The lab's opening preset in full: two jobs passing through two machines in opposite directions, which is the smallest shop in which the sequencing questions interact.
The best schedule keeps M2 working from 0 to 6 without a break, and M2 carries six hours of work, so nothing could finish sooner. That is the bound and the schedule meeting each other, and it is why the free bounds are worth computing before any orientation is tried.
The deadlock is the part worth rereading. Each of the four requirements in the cycle is individually sensible — two of them are the jobs' own routes and two are sequencing choices — and together they describe nothing. That is what makes this an integer programme: the feasibility of a set of binary choices is not a property of any one of them.
For a rehearsal, switch to the three-job preset: five operations, four pairs, sixteen orientations. The supplied first move is that M1 carries three of the five operations, so three of the four pairs are on M1 alone. Predict how many of the sixteen deadlock before running it, and then compute the free bound from the machine loads and job lengths and compare it with the best makespan the enumeration finds.
You should be able to list the operations in route order, find every pair sharing a machine and count the orientations as 2^k, orient the pairs and draw the arcs, detect a cycle and report it as a deadlock rather than a number, run a forward pass on an acyclic orientation to get the makespan as a longest path, and compute the machine-load and job-length lower bounds before deciding whether any search is needed at all.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.