Dynamic programming algorithms for scheduling parallel machines with family setup times

Scott Webster, Meral Azizoglu

Research output: Contribution to journalArticlepeer-review

48 Scopus citations


We address the problem of scheduling jobs with family setup times on identical parallel machines to minimize total weighted flowtime. We present two dynamic programming algorithms - a backward algorithm and a forward algorithm - and we identify characteristics of problems where each algorithm is best suited. We also derive two properties that improve the computational efficiency of the algorithms. Scope and purpose While most production schedulers must balance conflicting goals of high system efficiency and timely completion of individual jobs, consideration of this conflict is underdeveloped in the scheduling literature. This paper examines a model that incorporates a fundamental cause of the efficiency/timeliness conflict in practice. We propose solution methodologies and properties of an optimal solution for the purpose of exposing insights that may ultimately be useful in research on more complex models. (C) 2000 Elsevier Science Ltd. All rights reserved.

Original languageEnglish (US)
Pages (from-to)127-137
Number of pages11
JournalComputers and Operations Research
Issue number2
StatePublished - Feb 2001
Externally publishedYes


  • Dynamic programming
  • Family setup times
  • Production scheduling

ASJC Scopus subject areas

  • General Computer Science
  • Modeling and Simulation
  • Management Science and Operations Research


Dive into the research topics of 'Dynamic programming algorithms for scheduling parallel machines with family setup times'. Together they form a unique fingerprint.

Cite this