An efficient critical path based method for permutation flow shop scheduling problem. (April 2022)

• Record Type: Journal Article
• Authors: Li, Yang; Li, Xinyu; Gao, Liang; Fu, Ling; Wang, Cuiyu
• Is Part Of: Journal of manufacturing systems. Volume 63(2022)
• Page Start: 344
• Page End: 353
• Publication Date: 2022-04
• Subjects: Permutation flow shop scheduling -- Neighborhood search method -- Critical path -- Theoretical derivation for key point -- Improved simulated annealing algorithm; Manufacturing processes -- Periodicals; Production engineering -- Data processing -- Periodicals; Robots, Industrial -- Periodicals; Production, Technique de la -- Informatique -- Périodiques; Robots industriels -- Périodiques; Electronic journals; 670.42
• DOI: 10.1016/j.jmsy.2022.04.005
• Languages: English
• ISSNs: 0278-6125

Abstract

Abstract: The permutation flow shop scheduling problem (PFSP) is one of the most important and typical scheduling types in the mass customization production and is also a well-known NP-hard problem. However, most of the reported algorithms lack the theoretical guidance to achieve the good accuracy and efficiency. To solve this problem, this paper proposes an efficient search method based on critical path with three theorems for the PFSP. Firstly, the concept of critical path and key points are defined according to the characteristics of the PFSP. On this basis, three theorems with the corresponding proofs are presented. Then, combined with above three theorems, a new neighborhood search method for the PFSP is developed. In each neighborhood search, only the first and last jobs in the processing sequence and the first job of each machine on the critical path need to be computed. No matter how large the scale of the problem is, this method only needs to search at most (2 m +2) times to find the optimal neighborhood solution ( m is the number of machines). Finally, the new neighborhood search method is combined with an improved simulated annealing algorithm to solve the PFSP. To verify the performance of the proposed algorithm, this paper implement a set of comparative experiments with the-state-of-art methods on the part of the TA benchmark. By the proposed method, some significant improvements are obtained according to the experimental results. Meanwhile, under the same algorithm framework, the proposed method can reduce the 35.2% average computation time. Especially, the best-known upper bound of TA116 is updated from 26477 to 26469 by the proposed algorithm. Highlights: This paper proposes a neighborhood search method of the PFSP based on critical path. The method only needs to search at most (2 m +2) times to find optimal neighborhood solution ( m is the number of machines). The concept of critical path and key points are defined. On this basis, three theorems with the proofs are presented. This method can be combined with other meta-heuristic algorithms and also be generalized to the variants of the PFSP. The best-known upper bound of TA116 is updated by the proposed algorithm.