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, ss.1-10, 2006 (SCI İndekslerine Giren Dergi) identifier identifier

  • Cilt numarası: 174 Konu: 1
  • Basım Tarihi: 2006
  • Doi Numarası: 10.1016/j.ejor.2004.12.023
  • Dergi Adı: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
  • Sayfa Sayıları: ss.1-10

Ö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.