Dynamic programming algorithms for scheduling parallel machines with family setup times

Authors
Webster, S Azizoglu, M
Citation
S. Webster et M. Azizoglu, Dynamic programming algorithms for scheduling parallel machines with family setup times, COMPUT OPER, 28(2), 2001, pp. 127-137
Citations number
11
Categorie Soggetti
Engineering Management /General
Journal title
COMPUTERS & OPERATIONS RESEARCH
ISSN journal
03050548 → ACNP
Volume
28
Issue
2
Year of publication
2001
Pages
127 - 137
Database
ISI
SICI code
0305-0548(200102)28:2<127:DPAFSP>2.0.ZU;2-P
Abstract
We address the problem of scheduling jobs with family setup times on identi cal parallel machines to minimize total weighted flowtime. We present two d ynamic programming algorithms - a backward algorithm and a forward algorith m - and we identify characteristics of problems where each algorithm is bes t suited. We also derive two properties that improve the computational effi ciency of the algorithms.