The Shifting Bottleneck Heuristic solves job shop scheduling by representing problems as networks with precedence and machine-capacity arcs, then iteratively optimizing the bottleneck machine using single-machine sub-problems. The 1|rj|Lmax sub-problem (single machine, release times, maximum tardiness) solved with preemptive-EDD lower bounds guides arc selection in the main network, reducing makespan through implicit enumeration. Table of Contents: • Network representation: precedence arcs (fixed), machine-capacity arcs (disjunctive, one per machine-job pair) • Longest path on network equals makespan under current arc selection • Bottleneck identification: machine with highest cumulative processing time load • Preemptive-EDD rule: lower bound for 1|rj|Lmax using job preemption to minimize tardiness • Arc activation strategy: choosing arcs for bottleneck machine to minimize longest path • Iterative refinement: sequentially optimize each machine, updating longest path after each machine • Solution verification: feasible schedule when all disjunctive arcs are resolved
The Shifting Bottleneck Heuristic solves job shop scheduling by representing problems as networks with precedence and machine-capacity arcs, then iteratively optimizing the bottleneck machine using s…