Open Access iconOpen Access

ARTICLE

crossmark

An Effective Neighborhood Solution Clipping Method for Large-Scale Job Shop Scheduling Problem

Sihan Wang, Xinyu Li, Qihao Liu*

School of Mechanical Science and Engineering, Huazhong University of Science and Technology, Wuhan, 430074, China

* Corresponding Author: Qihao Liu. Email: email

(This article belongs to the Special Issue: Computing Methods for Industrial Artificial Intelligence)

Computer Modeling in Engineering & Sciences 2023, 137(2), 1871-1890. https://doi.org/10.32604/cmes.2023.028339

Abstract

The job shop scheduling problem (JSSP) is a classical combinatorial optimization problem that exists widely in diverse scenarios of manufacturing systems. It is a well-known NP-hard problem, when the number of jobs increases, the difficulty of solving the problem exponentially increases. Therefore, a major challenge is to increase the solving efficiency of current algorithms. Modifying the neighborhood structure of the solutions can effectively improve the local search ability and efficiency. In this paper, a genetic Tabu search algorithm with neighborhood clipping (GTS_NC) is proposed for solving JSSP. A neighborhood solution clipping method is developed and embedded into Tabu search to improve the efficiency of the local search by clipping the search actions of unimproved neighborhood solutions. Moreover, a feasible neighborhood solution determination method is put forward, which can accurately distinguish feasible neighborhood solutions from infeasible ones. Both of the methods are based on the domain knowledge of JSSP. The proposed algorithm is compared with several competitive algorithms on benchmark instances. The experimental results show that the proposed algorithm can achieve superior results compared to other competitive algorithms. According to the numerical results of the experiments, it is verified that the neighborhood solution clipping method can accurately identify the unimproved solutions and reduces the computational time by at least 28%.

Keywords


Cite This Article

APA Style
Wang, S., Li, X., Liu, Q. (2023). An effective neighborhood solution clipping method for large-scale job shop scheduling problem. Computer Modeling in Engineering & Sciences, 137(2), 1871-1890. https://doi.org/10.32604/cmes.2023.028339
Vancouver Style
Wang S, Li X, Liu Q. An effective neighborhood solution clipping method for large-scale job shop scheduling problem. Comput Model Eng Sci. 2023;137(2):1871-1890 https://doi.org/10.32604/cmes.2023.028339
IEEE Style
S. Wang, X. Li, and Q. Liu "An Effective Neighborhood Solution Clipping Method for Large-Scale Job Shop Scheduling Problem," Comput. Model. Eng. Sci., vol. 137, no. 2, pp. 1871-1890. 2023. https://doi.org/10.32604/cmes.2023.028339



cc This work is licensed under a Creative Commons Attribution 4.0 International License , which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
  • 763

    View

  • 382

    Download

  • 0

    Like

Share Link