@Article{cmes.2023.028339,
AUTHOR = {Sihan Wang, Xinyu Li, Qihao Liu},
TITLE = {An Effective Neighborhood Solution Clipping Method for Large-Scale Job Shop Scheduling Problem},
JOURNAL = {Computer Modeling in Engineering \& Sciences},
VOLUME = {137},
YEAR = {2023},
NUMBER = {2},
PAGES = {1871--1890},
URL = {http://www.techscience.com/CMES/v137n2/53351},
ISSN = {1526-1506},
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%.},
DOI = {10.32604/cmes.2023.028339}
}