An Effective Solution Space Clipping-Based Algorithm for Large-Scale Permutation Flow Shop Scheduling Problem

作     者：Li, Yang Li, Xinyu Gao, Liang 

作者机构：Huazhong Univ Sci & Technol State Key Lab Digital Mfg Equipment & Technol Wuhan 430074 Peoples R China 

出 版 物：《IEEE TRANSACTIONS ON SYSTEMS MAN CYBERNETICS-SYSTEMS》 (IEEE Trans. Syst. Man Cybern. Syst.)

年 卷 期：2023年第53卷第1期

页      面：635-646页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National Natural Science Foundation of China [U21B2029, 51825502, 52188102] Key Research and Development Program of Huber Province [2021AAB001] 

主　　题：Job shop scheduling Heuristic algorithms Optimization Production Optimal scheduling Approximation algorithms Simulated annealing Improved simulated annealing (SA) algorithm large-scale permutation flow shop scheduling solution space clipping method 

摘      要：The permutation flow shop scheduling problem (PFSP) is one of the most important scheduling types in the mass customization production with many real-world applications. It is also a well-known NP-hard problem, when the number of jobs increases, the difficulty of solving the problem exponentially increases. However, most of the reported algorithms have not analyzed the solution space and may search many useless solution spaces, which impedes these algorithms from effectively optimizing the large-scale PFSPs in reasonable computation time. To address large-scale PFSPs with more than 100 jobs, this article proposes a solution space clipping-based improved simulated annealing (SA) algorithm. First, inspired by Johnson s rule, this article explores its essential principle and generalizes it to the general situation. Before the optimization algorithm is used to find the optimal solution, a preordering combination is performed on the processed jobs according to this extended rule to considerably clip the solution space. Second, a hybrid release strategy based on the Palmer algorithm is developed for the proposed algorithm. Then, some key operators of the SA algorithm are also improved. Finally, to verify the performance of the proposed algorithm, this work performs a set of comparative experiments with the-state-of-art methods on the part of the TA benchmark and VRF benchmark with more than 100 jobs. The experimental results show that the proposed method can achieve superior results compared to other algorithms. Furthermore, the performance of the algorithm is comprehensively analyzed, which confirms the effectiveness of the proposed method.