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

Chung C., Flynn J., Kirca O.

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, cilt.174, sa.1, ss.1-10, 2006 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 174 Sayı: 1
  • Basım Tarihi: 2006
  • Doi Numarası: 10.1016/j.ejor.2004.12.023
  • Dergi Adı: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.1-10
  • Anahtar Kelimeler: scheduling, permutation flowshop, tardiness, branch and bound, EFFICIENT ALGORITHM, SCHEDULING PROBLEM, MEAN TARDINESS, HEURISTICS
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

The m-machine permutation flowshop problem with the total tardiness objective is a common scheduling problem, which is known to be NP-hard. Here, we develop a branch and bound algorithm to solve this problem. Our algorithm incorporates a machine-based lower bound and a dominance test for pruning nodes. We undertake a numerical study that evaluates our algorithm and compares it with the best alternative existing algorithm. Extensive computational experiments indicate that our algorithm performs better and can handle test problems with n <= 20. (c) 2005 Elsevier B.V. All rights reserved.