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

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

0.00 Avg rating0 Votes
Article ID: iaor20063315
Country: Netherlands
Volume: 168
Issue: 3
Start Page Number: 1030
End Page Number: 1039
Publication Date: Feb 2006
Journal: European Journal of Operational Research
Authors: ,
Keywords: programming: branch and bound
Abstract:

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

Reviews

Required fields are marked *. Your email address will not be published.