An Improved Branch-and-Bound Algorithm for the One-Machine Scheduling Problem with Delayed Precedence Constraints
Wenda Zhang, Jason J. Sauppe, Sheldon H. Jacobson
INFORMS Journal on Computing · 2021 · Volume 33 · Issue 3
Abstract
In this paper, we discuss the one-machine scheduling problem with release and delivery times with the minimum makespan objective. Both heuristics and branch-and-bound algorithms have been formulated for the problem. One such branch-and-bound algorithm solves the problem and a variation that requires a delay between the completion of one job and the start of another (delayed precedence constraints). This paper analyzes key components of this branch-and-bound algorithm and proposes an improved heuristic to be used in conjunction with a different search strategy. Computational experiments demonstrate that the modifications lead to substantial improvements in running time and number of iterations on the one-machine problem instances both with and without delayed precedence constraints.
Keywords
combinatorial optimization, one-machine scheduling, branch and bound
Enable JavaScript for citation tools and additional paper interactions.