We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
An Improved Branch-and-Bound Algorithm for the One-Machine Scheduling Problem with Delayed Precedence Constraints.
- Authors
Zhang, Wenda; Sauppe, Jason J.; Jacobson, Sheldon H.
- 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.
- Subjects
PROBLEM solving; ALGORITHMS; SCHEDULING; PRODUCTION scheduling; COMBINATORIAL optimization
- Publication
INFORMS Journal on Computing, 2021, Vol 33, Issue 3, p1091
- ISSN
1091-9856
- Publication type
Article
- DOI
10.1287/ijoc.2020.0988