On the minimization of total weighted flow time with identical and uniform parallel machines

Azizoglu, MERAL; Kirca, O

doi:10.1016/s0377-2217(97)00427-x

On the minimization of total weighted flow time with identical and uniform parallel machines

Azizoglu M., Kirca O.

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, cilt.113, sa.1, ss.91-100, 1999 (SCI-Expanded, Scopus)

Yayın Türü: Makale / Tam Makale
Cilt numarası: 113 Sayı: 1
Basım Tarihi: 1999
Doi Numarası: 10.1016/s0377-2217(97)00427-x
Dergi Adı: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
Sayfa Sayıları: ss.91-100
Anahtar Kelimeler: scheduling, parallel machines, branch and bound
Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

We consider the NP-hard problem of scheduling jobs on identical parallel machines to minimize total weighted flow time. We discuss the properties that characterize the structure of an optimal solution, present a lower bound and propose a branch and bound algorithm. The algorithm is superior to prior methods presented in the literature. We also extend the algorithm to uniform parallel machines and solve medium-sized problem instances. (C) 1999 Elsevier Science B.V. All rights reserved.