Effective heuristics for the blocking flowshop scheduling problem with makespan minimization

Effective heuristics for the blocking flowshop scheduling problem with makespan minimization

0.00 Avg rating0 Votes
Article ID: iaor20117409
Volume: 40
Issue: 2
Start Page Number: 218
End Page Number: 229
Publication Date: Apr 2012
Journal: Omega
Authors: ,
Keywords: combinatorial optimization, heuristics
Abstract:

The blocking flowshop scheduling problem with makespan criterion has important applications in a variety of industrial systems. Heuristics that explore specific characteristics of the problem are essential for many practical systems to find good solutions with limited computational effort. This paper first presents two simple constructive heuristics, namely weighted profile fitting (wPF) and PW, based on the profile fitting (PF) approach of McCormick et al. [Sequencing in an assembly line with blocking to minimize cycle time. Operations Research 1989;37:925–36] and the characteristics of the problem. Then, three improved constructive heuristics, called PF‐NEH, wPF‐NEH, and PW‐NEH, are proposed by combining the PF, wPF, and PW with the enumeration procedure of the Nawaz–Enscore–Ham (NEH) heuristic [A heuristic algorithm for the m‐machine, n‐job flow shop sequencing problem. OMEGA‐International Journal of Management Science 1983;11:91–5] in an effective way. Thirdly, three composite heuristics i.e., PF‐NEHLS, wPF‐NEHLS, and PW‐NEHLS, are developed by using the insertion‐based local search method to improve the solutions generated by the constructive heuristics. Computational simulations and comparisons are carried out based on the well‐known flowshop benchmarks of Taillard [Benchmarks for basic scheduling problems. European Journal of Operation Research 1993;64:278–85] that are considered as blocking flowshop instances. The results show that the presented constructive heuristics perform significantly better than the existing ones, and the proposed composite heuristics further improve the presented constructive heuristics by a considerable margin. In addition, 17 new best‐known solutions for Taillard benchmarks with large scale are found by the presented heuristics.

Reviews

Required fields are marked *. Your email address will not be published.