Minimizing total flow time in permutation flowshop environment

Shih Wei Lin, Chien Yi Huang, Chung-Cheng Lu, Kuo Ching Ying*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


The permutation flowshop scheduling problem with the objective of minimizing total flow time is known as a NP-hard problem, even for the two-machine cases. Because of the computational complexity of this problem, a multi-start simulated annealing (MSA) heuristic, which adopts a multi-start hill climbing strategy in the simulated annealing (SA) heuristic, is proposed to obtain close-to-optimal solutions. To examine the performance of the MSA algorithm, a set of computational experiments was conducted, on a well-known benchmark-problem set from the literature. The experiment results show that the performance of the traditional single-start SA can be significantly improved by incorporating the multi-start hill climbing strategy. In addition, the proposed MSA algorithm is highly effective and efficient as compared with the other state-of-the-art metaheuristics on the same benchmark-problem instances. In terms of both solution quality and computational expense, the proposed algorithm contributes significantly to this extremely challenging scheduling problem.

Original languageEnglish
Pages (from-to)6599-6612
Number of pages14
JournalInternational Journal of Innovative Computing, Information and Control
Issue number10 A
StatePublished - 1 Oct 2012


  • Permutation flowshop
  • Scheduling
  • Total flow time


Dive into the research topics of 'Minimizing total flow time in permutation flowshop environment'. Together they form a unique fingerprint.

Cite this