Necessary and Sufficient Conditions for Feasible Neighbourhood Solutions in the Local Search of the Job-Shop Scheduling Problem
Abstract The meta-heuristic algorithm with local search is an excellent choice for the job-shop scheduling problem (JSP). However, due to the unique nature of the JSP, local search may generate infeasible neighbourhood solutions. In the existing literature, although some domain knowledge of the JSP...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
SpringerOpen
2023-08-01
|
| Series: | Chinese Journal of Mechanical Engineering |
| Subjects: | |
| Online Access: | https://doi.org/10.1186/s10033-023-00911-8 |
| _version_ | 1827635336763670528 |
|---|---|
| author | Lin Gui Xinyu Li Liang Gao Cuiyu Wang |
| author_facet | Lin Gui Xinyu Li Liang Gao Cuiyu Wang |
| author_sort | Lin Gui |
| collection | DOAJ |
| description | Abstract The meta-heuristic algorithm with local search is an excellent choice for the job-shop scheduling problem (JSP). However, due to the unique nature of the JSP, local search may generate infeasible neighbourhood solutions. In the existing literature, although some domain knowledge of the JSP can be used to avoid infeasible solutions, the constraint conditions in this domain knowledge are sufficient but not necessary. It may lose many feasible solutions and make the local search inadequate. By analysing the causes of infeasible neighbourhood solutions, this paper further explores the domain knowledge contained in the JSP and proposes the sufficient and necessary constraint conditions to find all feasible neighbourhood solutions, allowing the local search to be carried out thoroughly. With the proposed conditions, a new neighbourhood structure is designed in this paper. Then, a fast calculation method for all feasible neighbourhood solutions is provided, significantly reducing the calculation time compared with ordinary methods. A set of standard benchmark instances is used to evaluate the performance of the proposed neighbourhood structure and calculation method. The experimental results show that the calculation method is effective, and the new neighbourhood structure has more reliability and superiority than the other famous and influential neighbourhood structures, where 90% of the results are the best compared with three other well-known neighbourhood structures. Finally, the result from a tabu search algorithm with the new neighbourhood structure is compared with the current best results, demonstrating the superiority of the proposed neighbourhood structure. |
| first_indexed | 2024-03-09T15:25:22Z |
| format | Article |
| id | doaj.art-76a45dff15b947628f80d16ba5f47cd0 |
| institution | Directory Open Access Journal |
| issn | 2192-8258 |
| language | English |
| last_indexed | 2024-03-09T15:25:22Z |
| publishDate | 2023-08-01 |
| publisher | SpringerOpen |
| record_format | Article |
| series | Chinese Journal of Mechanical Engineering |
| spelling | doaj.art-76a45dff15b947628f80d16ba5f47cd02023-11-26T12:32:37ZengSpringerOpenChinese Journal of Mechanical Engineering2192-82582023-08-0136111610.1186/s10033-023-00911-8Necessary and Sufficient Conditions for Feasible Neighbourhood Solutions in the Local Search of the Job-Shop Scheduling ProblemLin Gui0Xinyu Li1Liang Gao2Cuiyu Wang3State Key Laboratory of Digital Manufacturing Equipment and Technology, Huazhong University of Science and TechnologyState Key Laboratory of Digital Manufacturing Equipment and Technology, Huazhong University of Science and TechnologyState Key Laboratory of Digital Manufacturing Equipment and Technology, Huazhong University of Science and TechnologyState Key Laboratory of Digital Manufacturing Equipment and Technology, Huazhong University of Science and TechnologyAbstract The meta-heuristic algorithm with local search is an excellent choice for the job-shop scheduling problem (JSP). However, due to the unique nature of the JSP, local search may generate infeasible neighbourhood solutions. In the existing literature, although some domain knowledge of the JSP can be used to avoid infeasible solutions, the constraint conditions in this domain knowledge are sufficient but not necessary. It may lose many feasible solutions and make the local search inadequate. By analysing the causes of infeasible neighbourhood solutions, this paper further explores the domain knowledge contained in the JSP and proposes the sufficient and necessary constraint conditions to find all feasible neighbourhood solutions, allowing the local search to be carried out thoroughly. With the proposed conditions, a new neighbourhood structure is designed in this paper. Then, a fast calculation method for all feasible neighbourhood solutions is provided, significantly reducing the calculation time compared with ordinary methods. A set of standard benchmark instances is used to evaluate the performance of the proposed neighbourhood structure and calculation method. The experimental results show that the calculation method is effective, and the new neighbourhood structure has more reliability and superiority than the other famous and influential neighbourhood structures, where 90% of the results are the best compared with three other well-known neighbourhood structures. Finally, the result from a tabu search algorithm with the new neighbourhood structure is compared with the current best results, demonstrating the superiority of the proposed neighbourhood structure.https://doi.org/10.1186/s10033-023-00911-8SchedulingJob-shop schedulingLocal searchNeighbourhood structureDomain knowledge |
| spellingShingle | Lin Gui Xinyu Li Liang Gao Cuiyu Wang Necessary and Sufficient Conditions for Feasible Neighbourhood Solutions in the Local Search of the Job-Shop Scheduling Problem Chinese Journal of Mechanical Engineering Scheduling Job-shop scheduling Local search Neighbourhood structure Domain knowledge |
| title | Necessary and Sufficient Conditions for Feasible Neighbourhood Solutions in the Local Search of the Job-Shop Scheduling Problem |
| title_full | Necessary and Sufficient Conditions for Feasible Neighbourhood Solutions in the Local Search of the Job-Shop Scheduling Problem |
| title_fullStr | Necessary and Sufficient Conditions for Feasible Neighbourhood Solutions in the Local Search of the Job-Shop Scheduling Problem |
| title_full_unstemmed | Necessary and Sufficient Conditions for Feasible Neighbourhood Solutions in the Local Search of the Job-Shop Scheduling Problem |
| title_short | Necessary and Sufficient Conditions for Feasible Neighbourhood Solutions in the Local Search of the Job-Shop Scheduling Problem |
| title_sort | necessary and sufficient conditions for feasible neighbourhood solutions in the local search of the job shop scheduling problem |
| topic | Scheduling Job-shop scheduling Local search Neighbourhood structure Domain knowledge |
| url | https://doi.org/10.1186/s10033-023-00911-8 |
| work_keys_str_mv | AT lingui necessaryandsufficientconditionsforfeasibleneighbourhoodsolutionsinthelocalsearchofthejobshopschedulingproblem AT xinyuli necessaryandsufficientconditionsforfeasibleneighbourhoodsolutionsinthelocalsearchofthejobshopschedulingproblem AT lianggao necessaryandsufficientconditionsforfeasibleneighbourhoodsolutionsinthelocalsearchofthejobshopschedulingproblem AT cuiyuwang necessaryandsufficientconditionsforfeasibleneighbourhoodsolutionsinthelocalsearchofthejobshopschedulingproblem |