Article ID: | iaor20117409 |
Volume: | 40 |
Issue: | 2 |
Start Page Number: | 218 |
End Page Number: | 229 |
Publication Date: | Apr 2012 |
Journal: | Omega |
Authors: | Wang Ling, Pan Quan-Ke |
Keywords: | combinatorial optimization, heuristics |
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