An improved branch-and-bound algorithm for the one-machine scheduling problem with delayed precedence constraints

Wenda Zhang, Jason J. Sauppe, Sheldon H. Jacobson

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish (US)
Pages (from-to)1091-1102
Number of pages12
JournalINFORMS Journal on Computing
Volume33
Issue number3
DOIs
StatePublished - Jun 2021

Keywords

  • Bound
  • Branch
  • Combinatorial optimization
  • One-machine scheduling

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Computer Science Applications
  • Management Science and Operations Research

Fingerprint

Dive into the research topics of 'An improved branch-and-bound algorithm for the one-machine scheduling problem with delayed precedence constraints'. Together they form a unique fingerprint.

Cite this