A hybrid backtracking search algorithm for permutation flow-shop scheduling problem. (July 2015)

• Record Type: Journal Article
• Authors: Lin, Qun; Gao, Liang; Li, Xinyu; Zhang, Chunjiang
• Is Part Of: Computers & industrial engineering. Volume 85(2015)
• Page Start: 437
• Page End: 446
• Publication Date: 2015-07
• Subjects: Hybrid backtracking search algorithm (HBSA) -- Permutation Flow-Shop Scheduling Problem (PFSP) -- Simulated annealing (SA) mechanism -- Random insertion local search; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2015.04.009
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: It is the first time that BSA is applied to solve discrete problems. The proposed HBSA combines methods in BSA and methods in SA algorithm. The random insertion local search method adopted by HBSA is effective. The effectiveness of proposed HBSA has been proven from statistical analysis. Abstract: The Permutation Flow-shop Scheduling Problem (PFSP) which is an NP-complete problem widely exists in many industrial manufacturing systems, such as motor industry, semiconductor industry, and appliance industry. Therefore, how to obtain the optimal schedule for PFSP is very important for these manufacturing systems. Many attentions from researchers and engineers have been paid to solve this problem, but the developments of more effective and efficient scheduling technologies and methods are never end. In this paper, based on a new evolutionary algorithm – Backtracking Search Algorithm (BSA), a hybrid BSA (HBSA) is proposed for PFSP with the objective to minimize the makespan. To make original BSA suitable for discrete problems, some improvements and relative techniques about original BSA, such as crossover and mutation strategies, simulated annealing (SA) mechanism used to avoid premature and random insertion local search, are presented. 29 famous benchmark problems have been used to evaluate the performance of the proposed HBSA. And several comparisons between HBSA and some other classical algorithms are conducted. The results show the effectiveness of proposed HBSA.