A practical use of Jackson’s preemptive schedule for solving the job shop problem. (English) Zbl 0709.90061

Summary: We present a polynomial algorithm for optimally adjusting heads and tails in the job shop problem. This algorithm is based on Jackson’s preemptive schedule for the one-machine problem. We next use this algorithm to construct a new branch and bound method. Computational results show the superiority of this method over the classical ones.


90B35 Deterministic scheduling theory in operations research
90C60 Abstract computational complexity for mathematical programming problems
90-08 Computational methods for problems pertaining to operations research and mathematical programming