A feedback learning-based selection hyper-heuristic for distributed heterogeneous hybrid blocking flow-shop scheduling problem with flexible assembly and setup time

• Published in: Engineering applications of artificial intelligence 2024-05, Vol.131, p.107818, Article 107818
• Main Authors: Shao, Zhongshi, Shao, Weishi, Chen, Jianrui, Pi, Dechang
• Format: Article
• Language: English
• Subjects: Distributed scheduling; Feedback learning; Flexible assembly; Hybrid flow-shop; Hyper-heuristic
• ISSN: 0952-1976; 1873-6769
• DOI: 10.1016/j.engappai.2023.107818

Distributed manufacturing is increasingly common due to economic globalization. It has important practical significance to optimize global supply chains by considering cooperative scheduling of distributed production and flexible assembly. This paper studies a distributed heterogeneous hybrid blocking flow-shop scheduling problem with flexible assembly and setup time (DHHBFSP-FAST). The objective is to minimize makespan of all products. To tackle such problem, a mixed-integer linear programming model (MILP) is presented to formulate it. Then, a feedback learning-based selection hyper-heuristic (FLS-HH) is proposed, which contains high-level control strategies and low-level heuristics. For the high-level control strategies, the transition information between each pair of low-level heuristics is collected, then a feedback learning-based selection method is presented based on such transition information, which can automatically select the appropriate low-level heuristics. For the low-level heuristics, to assign jobs/products to machines, a composite dispatch rule is proposed. To generate an initial domain solution with high quality, a constructive heuristic based on double evaluation indexes is developed. The critical jobs and products are analyzed to avoid invalid searching. Based on such analysis, several low-level heuristics are presented to search the domain solution space, which combine six problem-specific perturbation heuristics and two local searches to balances exploration and exploitation. Comprehensive numerical experiments are carried out. The effectiveness of the proposed MILP and the special designs of FLS-HH are verified. To verify the effectiveness of FLS-HH, we compare it with 10 existing high-performing approaches. The comparison results show that FLS-HH significantly outperforms its competitors in solving DHHBFSP-FAST. •A DHHBFSP-FAST is studied and modeled by using a MILP.•A new hyper-heuristic (FLS-HH) is proposed for solving DHHBFSP-FAST.•A feedback-learning selection strategy is presented.•Several composite search operators are designed.•Experimental results prove the effectiveness of MILP and FLS-HH.