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, vol.79, no.3, pp.185-196, 2002 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 79 Issue: 3
  • Publication Date: 2002
  • Doi Number: 10.1016/s0925-5273(02)00234-7
  • Journal Name: INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.185-196
  • Keywords: scheduling theory, permutation flowshop, flow time, machine-based lower bounds, branch and bound, WEIGHTED COMPLETION-TIME, SINGLE-MACHINE, SHOP PROBLEM, SUM, JOB
  • Middle East Technical University Affiliated: No

Abstract

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.