Dynamic programming algorithms for scheduling parallel machines with family setup times

Webster S., Azizoglu M.

COMPUTERS & OPERATIONS RESEARCH, vol.28, no.2, pp.127-137, 2001 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 28 Issue: 2
  • Publication Date: 2001
  • Doi Number: 10.1016/s0305-0548(99)00094-5
  • Journal Name: COMPUTERS & OPERATIONS RESEARCH
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.127-137
  • Keywords: production scheduling, dynamic programming, family setup times, SINGLE-MACHINE, COMPLEXITY
  • Middle East Technical University Affiliated: Yes

Abstract

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.