A branch and bound algorithm to minimize the total flow time for m-machine permutation flowshop problems

Chung C., Flynn J., Kirca O.

INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, cilt.79, sa.3, ss.185-196, 2002 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 79 Sayı: 3
  • Basım Tarihi: 2002
  • Doi Numarası: 10.1016/s0925-5273(02)00234-7
  • Dergi Adı: INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.185-196
  • Anahtar Kelimeler: scheduling theory, permutation flowshop, flow time, machine-based lower bounds, branch and bound, WEIGHTED COMPLETION-TIME, SINGLE-MACHINE, SHOP PROBLEM, SUM, JOB
  • Orta Doğu Teknik Üniversitesi Adresli: Hayır

Özet

The m-machine permutation flowshop problem with the total flow-time objective is a common scheduling problem, which is known to be NP-hard for m greater than or equal to 2. In this article, we develop a branch and bound algorithm to solve both the weighted and unweighted version of this problem. Our algorithm incorporates a new machine-based lower bound and a dominance test for pruning nodes. Computational experiments suggest that the algorithm can handle test problems with n less than or equal to 15. It also seems capable of dealing with larger problems for the unweighted objective, especially when the processing times are correlated. (C) 2002 Elsevier Science B.V. All rights reserved.