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, vol.174, no.1, pp.1-10, 2006 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 174 Issue: 1
  • Publication Date: 2006
  • Doi Number: 10.1016/j.ejor.2004.12.023
  • Journal Name: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.1-10
  • Keywords: scheduling, permutation flowshop, tardiness, branch and bound, EFFICIENT ALGORITHM, SCHEDULING PROBLEM, MEAN TARDINESS, HEURISTICS
  • Middle East Technical University Affiliated: Yes

Abstract

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.