A BB&R algorithm for minimizing total tardiness on a single machine with sequence dependent setup times

Edward C. Sewell, Jason J. Sauppe, David R. Morrison, Sheldon H. Jacobson, Gio K. Kao

Research output: Contribution to journalArticlepeer-review


This paper presents a Branch, Bound, and Remember (BB&R) exact algorithm using the Cyclic Best First Search (CBFS) exploration strategy for solving the 1|STsd |∑Ti scheduling problem, a single machine scheduling problem with sequence dependent setup times where the objective is to find a schedule with minimum total tardiness. The BB&R algorithm incorporates memory-based dominance rules to reduce the solution search space. The algorithm creates schedules in the reverse direction for problems where fewer than half the jobs are expected to be tardy. In addition, a branch and bound algorithm is used to efficiently compute tighter lower bounds for the problem. This paper also presents a counterexample for a previously reported exact algorithm in Luo and Chu (Appl Math Comput 183(1):575-588, 2006) and Luo et al. (Int J Prod Res 44(17):3367-3378, 2006). Computational experiments demonstrate that the algorithm is two orders of magnitude faster than the fastest exact algorithm that has appeared in the literature. Computational experiments on two sets of benchmark problems demonstrate that the CBFS search exploration strategy can be used as an effective heuristic on problems that are too large to solve to optimality.

Original languageEnglish (US)
Pages (from-to)791-812
Number of pages22
JournalJournal of Global Optimization
Issue number4
StatePublished - Dec 2012


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

ASJC Scopus subject areas

  • Control and Optimization
  • Applied Mathematics
  • Business, Management and Accounting (miscellaneous)
  • Computer Science Applications
  • Management Science and Operations Research


Dive into the research topics of 'A BB&R algorithm for minimizing total tardiness on a single machine with sequence dependent setup times'. Together they form a unique fingerprint.

Cite this