A branch, bound, and remember algorithm for the 1|r i |σt i scheduling problem

Gio K. Kao, Edward C. Sewell, Sheldon H. Jacobson

Research output: Contribution to journalArticle

Abstract

This paper presents a modified Branch and Bound (B&B) algorithm called, the Branch, Bound, and Remember (BB&R) algorithm, which uses the Distributed Best First Search (DBFS) exploration strategy for solving the 1|r i |σt i scheduling problem, a single machine scheduling problem where the objective is to find a schedule with the minimum total tardiness. Memory-based dominance strategies are incorporated into the BB&R algorithm. In addition, a modified memory-based dynamic programming algorithm is also introduced to efficiently compute lower bounds for the 1|r i |σt i scheduling problem. Computational results are reported, which shows that the BB&R algorithm with the DBFS exploration strategy outperforms the best known algorithms reported in the literature.

Original languageEnglish (US)
Pages (from-to)163-175
Number of pages13
JournalJournal of Scheduling
Volume12
Issue number2
DOIs
StatePublished - Apr 1 2009

Keywords

  • Branch and bound algorithms
  • Dynamic programming
  • Scheduling theory and algorithms

ASJC Scopus subject areas

  • Software
  • Engineering(all)
  • Management Science and Operations Research
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'A branch, bound, and remember algorithm for the 1|r <sub>i</sub> |σt <sub>i</sub> scheduling problem'. Together they form a unique fingerprint.

  • Cite this