ADJUSTMENT OF HEADS AND TAILS FOR THE JOB-SHOP PROBLEM

The efficiency of recent enumerative methods for the job-shop problem crucially depends on immediate selections of disjunctive constraints l eading to adjustment of heads and tails. This paper presents new inves tigations concerning this powerful tool. More efficient algorithms are proposed, and global operations are introduced. We also describe a ne w lower bound and a new branching scheme which are used to design a br anch and bound method. Computational results show that these technique s permit to drastically reduce the size of the search trees.