Improved NEH-based heuristic for the blocking flow-shop problem with bicriteria of the makespan and machine utilization

The blocking flow-shop scheduling problem, which is an NP-hard problem, has wide applications in industry. Many studies have focused primarily on single-objective optimization, such as minimizing the makespan or total flow time, which is insufficient for practical problems. In this study, a blocking flow-shop scheduling problem with bicriteria of the makespan and machine utilization is considered. A simple constructive heuristic, NEHCG, is proposed by developing new priority and tie-breaking rules based on the Nawaz-Enscore-Ham heuristic. In the new priority rule, the quartile deviation of job processing times is included for the first time, and the new tie-breaking rule is designed to break ties effectively in the insertion phase. Then, an improved constructive heuristic, PW_NEHCG, is presented by effectively combining NEHCG with an improved profile-fitting approach. Computational experiments show that the proposed constructive heuristics exhibit excellent performance compared to other well-known heuristics.