Graph Knowledge-Enhanced Iterated Greedy Algorithm for Hybrid Flowshop Scheduling Problem
This study presents a graph knowledge-enhanced iterated greedy algorithm that incorporates dual directional decoding strategies, disjunctive graphs, neighborhood structures, and a rapid evaluation method to demonstrate its superior performance for the hybrid flowshop scheduling problem (HFSP). The p...
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-07-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/13/15/2401 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849239770459275264 |
|---|---|
| author | Yingli Li Biao Zhang Kaipu Wang Liping Zhang Zikai Zhang Yong Wang |
| author_facet | Yingli Li Biao Zhang Kaipu Wang Liping Zhang Zikai Zhang Yong Wang |
| author_sort | Yingli Li |
| collection | DOAJ |
| description | This study presents a graph knowledge-enhanced iterated greedy algorithm that incorporates dual directional decoding strategies, disjunctive graphs, neighborhood structures, and a rapid evaluation method to demonstrate its superior performance for the hybrid flowshop scheduling problem (HFSP). The proposed algorithm addresses the trade-off between the finite solution space corresponding to solution representation and the search space for the optimal solution, as well as constructs a decision mechanism to determine which search operator should be used in different search stages to minimize the occurrence of futile searching and the low computational efficiency caused by individuals conducting unordered neighborhood searches. The algorithm employs dual decoding with a novel disturbance operation to generate initial solutions and expand the search space. The derivation of the critical path and the design of neighborhood structures based on it provide a clear direction for identifying and prioritizing operations that have a significant impact on the objective. The use of a disjunctive graph provides a clear depiction of the detailed changes in the job sequence both before and after the neighborhood searches, providing a comprehensive view of the operational sequence transformations. By integrating the rapid evaluation technique, it becomes feasible to identify promising regions within a constrained timeframe. The numerical evaluation with well-known benchmarks verifies that the performance of the graph knowledge-enhanced algorithm is superior to that of a prior algorithm, and seeks new best solutions for 183 hard instances. |
| format | Article |
| id | doaj-art-e37319c24e6c49c6af33be43a7c39461 |
| institution | Kabale University |
| issn | 2227-7390 |
| language | English |
| publishDate | 2025-07-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj-art-e37319c24e6c49c6af33be43a7c394612025-08-20T04:00:50ZengMDPI AGMathematics2227-73902025-07-011315240110.3390/math13152401Graph Knowledge-Enhanced Iterated Greedy Algorithm for Hybrid Flowshop Scheduling ProblemYingli Li0Biao Zhang1Kaipu Wang2Liping Zhang3Zikai Zhang4Yong Wang5School of Management, Wuhan University of Science and Technology, Wuhan 430081, ChinaSchool of Computer Science, Liaocheng University, Liaocheng 252000, ChinaHubei Digital Manufacturing Key Laboratory, School of Mechanical and Electronic Engineering, Wuhan University of Technology, Wuhan 430062, ChinaKey Laboratory of Metallurgical Equipment and Control Technology, Wuhan University of Science and Technology, Wuhan 430081, ChinaKey Laboratory of Metallurgical Equipment and Control Technology, Wuhan University of Science and Technology, Wuhan 430081, ChinaSchool of Management, Wuhan University of Science and Technology, Wuhan 430081, ChinaThis study presents a graph knowledge-enhanced iterated greedy algorithm that incorporates dual directional decoding strategies, disjunctive graphs, neighborhood structures, and a rapid evaluation method to demonstrate its superior performance for the hybrid flowshop scheduling problem (HFSP). The proposed algorithm addresses the trade-off between the finite solution space corresponding to solution representation and the search space for the optimal solution, as well as constructs a decision mechanism to determine which search operator should be used in different search stages to minimize the occurrence of futile searching and the low computational efficiency caused by individuals conducting unordered neighborhood searches. The algorithm employs dual decoding with a novel disturbance operation to generate initial solutions and expand the search space. The derivation of the critical path and the design of neighborhood structures based on it provide a clear direction for identifying and prioritizing operations that have a significant impact on the objective. The use of a disjunctive graph provides a clear depiction of the detailed changes in the job sequence both before and after the neighborhood searches, providing a comprehensive view of the operational sequence transformations. By integrating the rapid evaluation technique, it becomes feasible to identify promising regions within a constrained timeframe. The numerical evaluation with well-known benchmarks verifies that the performance of the graph knowledge-enhanced algorithm is superior to that of a prior algorithm, and seeks new best solutions for 183 hard instances.https://www.mdpi.com/2227-7390/13/15/2401hybrid flow-shop scheduling problemiterated greedy algorithmcritical pathsneighborhood structurerapid evaluation method |
| spellingShingle | Yingli Li Biao Zhang Kaipu Wang Liping Zhang Zikai Zhang Yong Wang Graph Knowledge-Enhanced Iterated Greedy Algorithm for Hybrid Flowshop Scheduling Problem Mathematics hybrid flow-shop scheduling problem iterated greedy algorithm critical paths neighborhood structure rapid evaluation method |
| title | Graph Knowledge-Enhanced Iterated Greedy Algorithm for Hybrid Flowshop Scheduling Problem |
| title_full | Graph Knowledge-Enhanced Iterated Greedy Algorithm for Hybrid Flowshop Scheduling Problem |
| title_fullStr | Graph Knowledge-Enhanced Iterated Greedy Algorithm for Hybrid Flowshop Scheduling Problem |
| title_full_unstemmed | Graph Knowledge-Enhanced Iterated Greedy Algorithm for Hybrid Flowshop Scheduling Problem |
| title_short | Graph Knowledge-Enhanced Iterated Greedy Algorithm for Hybrid Flowshop Scheduling Problem |
| title_sort | graph knowledge enhanced iterated greedy algorithm for hybrid flowshop scheduling problem |
| topic | hybrid flow-shop scheduling problem iterated greedy algorithm critical paths neighborhood structure rapid evaluation method |
| url | https://www.mdpi.com/2227-7390/13/15/2401 |
| work_keys_str_mv | AT yinglili graphknowledgeenhancediteratedgreedyalgorithmforhybridflowshopschedulingproblem AT biaozhang graphknowledgeenhancediteratedgreedyalgorithmforhybridflowshopschedulingproblem AT kaipuwang graphknowledgeenhancediteratedgreedyalgorithmforhybridflowshopschedulingproblem AT lipingzhang graphknowledgeenhancediteratedgreedyalgorithmforhybridflowshopschedulingproblem AT zikaizhang graphknowledgeenhancediteratedgreedyalgorithmforhybridflowshopschedulingproblem AT yongwang graphknowledgeenhancediteratedgreedyalgorithmforhybridflowshopschedulingproblem |