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

Despite being strongly NPNP-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.