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 jo b-shop scheduling problem. The main feature of this algorithm is to do the adjustments on different machines in parallel and simultaneously to propaga te 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 som e time. Copyright (C) 2001 John Wiley & Sons, Ltd.