An Improved Branch-and-Bound Algorithm for the One-Machine Scheduling Problem with Delayed Precedence Constraints

Wenda Zhang (), Jason J. Sauppe () and Sheldon H. Jacobson ()
Additional contact information
Wenda Zhang: Department of Industrial and Systems Engineering, University of Illinois at Urbana-Champaign, Urbana, Illinois 61801
Jason J. Sauppe: Department of Computer Science, University of Wisconsin–La Crosse, La Crosse, Wisconsin 54601
Sheldon H. Jacobson: Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, Illinois 61801

INFORMS Journal on Computing, 2021, vol. 33, issue 3, 1091-1102

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 (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2020.0988 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:33:y:2021:i:3:p:1091-1102

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().