Improved NEH-based heuristic for the blocking flow-shop problem with bicriteria of the makespan and machine utilization. Issue 3 (4th March 2023)

• Record Type: Journal Article
• Authors: Wu, Qinghua; Gao, Qingxuan; Liu, Weibo; Cheng, Shuai
• Is Part Of: Engineering optimization. Volume 55:Issue 3(2023)
• Page Start: 399
• Page End: 415
• Publication Date: 2023-03-04
• Subjects: Heuristic -- blocking flow shop -- makespan -- idle time -- blocking time; Engineering design -- Periodicals; Mathematical optimization -- Periodicals; 620.0042
• DOI: 10.1080/0305215X.2021.2010727
• Languages: English
• ISSNs: 0305-215X

Abstract

Abstract : 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.