Solving open benchmark instances for the job-shop problem by parallel head–tail adjustments

A fast and efficient head–tail adjustment algorithm is presented for the job-shop scheduling problem. The main feature of this algorithm is to do the adjustments on different machines in parallel and simultaneously to propagate the results between the machines. In connection with a branching scheme this algorithm is used to improve lower and upper bounds, and to prove the optimality of solutions for benchmark problems which have been open for some time.