Article ID: | iaor1998709 |
Country: | Netherlands |
Volume: | 78 |
Issue: | 2 |
Start Page Number: | 146 |
End Page Number: | 161 |
Publication Date: | Oct 1994 |
Journal: | European Journal of Operational Research |
Authors: | Pinson E., Carlier J. |
Keywords: | programming: branch and bound |
The efficiency of recent enumerative methods for the job-shop problem crucially depends on immediate selections of disjunctive constraints leading to adjustment of heads and tails. This paper presents new investigations concerning this powerful tool. More efficient algorithms are proposed, and global operations are introduced. We also describe a new lower bound and a new branching scheme which are used to design a branch and bound method. Computational results show that these techniques permit drastic reduction of the size of the search trees.