Branch-and-bound algorithms for solving hard instances of the one-machine sequencing problem

摘要

Despite being strongly N P-hard, the one-machine sequencing problem that minimizes the makespan was thought to be computationally inexpensive to solve using Carlier's algorithm (CA). CA achieved excellent results on random instances with 50-10,000 jobs. However, a thorough computational study reveals that hard instances do exist for CA. In this paper, we present three improved branch-and-bound algorithms based on CA and other existing techniques. We also develop a new lower bound and a problem size reduction technique. The new algorithms are demonstrated to substantially outperform CA in terms of CPU time and robustness. (c) 2004 Elsevier B.V. All rights reserved.