An effective constructive heuristic for permutation flow shop scheduling problem with total flow time criterion

作者：Rossi Fernando Luis; Nagano Marcelo Seido; Sagawa Juliana Keiko

来源：International Journal of Advanced Manufacturing Technology, 2017, 90(1-4): 93-107.

DOI：10.1007/s00170-016-9347-0

• Scheduling
• Flow shop
• Heuristics
• Total flow time

This article addresses the permutation flow-shop scheduling problem with total flow time minimization criterion. The problem is proved to be NP-hard; thus, the development of heuristic methods that provide high-quality solutions with computational efficiency are the motivating aspects for the development of this research. In this article, a new simple constructive heuristic method has been proposed to solve the problem. Initially, an extensive literature review with key methods was performed for analysis, comparison, and evaluation. Then, a new simple heuristic method has been proposed and evaluated by means of extensive computational experiments. The results showed that the proposed method provides high-quality solutions with computational efficiency, significantly outperforming the best simple heuristics found in the literature.

• 出版日期2017-4