Dynamic programming algorithms for scheduling parallel machines with family setup times

Webster, S; Azizoglu, MERAL

doi:10.1016/s0305-0548(99)00094-5

Dynamic programming algorithms for scheduling parallel machines with family setup times

Webster S., Azizoglu M.

COMPUTERS & OPERATIONS RESEARCH, cilt.28, sa.2, ss.127-137, 2001 (SCI-Expanded, Scopus)

Yayın Türü: Makale / Tam Makale
Cilt numarası: 28 Sayı: 2
Basım Tarihi: 2001
Doi Numarası: 10.1016/s0305-0548(99)00094-5
Dergi Adı: COMPUTERS & OPERATIONS RESEARCH
Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
Sayfa Sayıları: ss.127-137
Anahtar Kelimeler: production scheduling, dynamic programming, family setup times, SINGLE-MACHINE, COMPLEXITY
Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

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.