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 (Journal Indexed in SCI) identifier identifier

  • Publication Type: Article / Article
  • Volume: 79 Issue: 3
  • Publication Date: 2002
  • Doi Number: 10.1016/s0925-5273(02)00234-7
  • Title of Journal : INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS
  • 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

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.