Theories and Methods of Non-improved Neighbouring Solution Recognition in Job-shop Scheduling

doi:10.3901/JME.2025.10.427

Abstract

Abstract: In solving the job-shop scheduling problem(JSP) using local search algorithms, accurately identifying improved and non-improved neighboring solutions within the neighborhood can enhance computational efficiency. To this end, a decision theorem for identifying improved and non-improved neighboring solutions is proposed. This theorem extends traditional decision theories, enabling more precise identification of improved and non-improved neighboring solutions. Considering that the proposed decision theorem requires high-cost exact algorithms, a low-cost method for identifying non-improved neighboring solutions is further developed for commonly used neighborhood structures, such as N1, N4, N5, N6 and N7. It can realize the rapid identification of non-improved neighbouring solutions without really performing the move resulting in the neighbouring solution. The experimental results show that, although it may not be possible to fully identify all non-improved neighbouring solutions in the neighbourhood, the proposed method can screen out 36.12%-94.92% of non-improved neighboring solutions. Moreover, without compromising solution quality, it significantly improves the computational efficiency of local search algorithms.

Key words: non-improved neighbouring solution, neighborhood structure, local search, job-shop scheduling

CLC Number:

TP301

HUANG Xuewen, WANG Qiang, CHEN Zhen. Theories and Methods of Non-improved Neighbouring Solution Recognition in Job-shop Scheduling[J]. Journal of Mechanical Engineering, 2025, 61(10): 427-438.

References

[1] 李浩然，高亮，李新宇. 基于离散人工蜂群算法的多目标分布式异构零等待流水车间调度方法[J]. 机械工程学报，2023，59(2)：291-306.LI Haoran，GAO Liang，LI Xinyu. Discrete artificial bee colony algorithm for multi-objective distributed heterogeneous no-wait flowshop scheduling problem[J]. Journal of Mechanical Engineering，2023，59(2)：291-306.
[2] 黄学文，陈绍芬，周阗玉，等. 求解柔性作业车间调度的遗传算法综述[J]. 计算机集成制造系统，2022，28(2)：536-551.HUANG Xuewen，CHEN Shaofen，ZHOU Tianyu，et al. Survey on genetic algorithms for solving flexible job-shop scheduling problem[J]. Computer Integrated Manufacturing Systems，2022，28(2)：536-551.
[3] KUROWSKI K，PECYNA T，SLYSZ M，et al. Application of quantum approximate optimization algorithm to job shop scheduling problem[J]. European Journal of Operational Research，2023，310(2)：518-528.
[4] XIE J，LI X，GAO L，et al. A hybrid algorithm with a new neighborhood structure for job shop scheduling problems[J]. Computers & Industrial Engineering，2022，169：108205.
[5] 黄林，赵诗奎，黄森. 基于障碍图模型和禁忌搜索混合算法求解作业车间调度问题[J]. 机械工程学报，2023，59(16)：435-444，426.HUANG Lin，ZHAO Shikui，HUANG Sen. Hybrid algorithm based on obstacle graph model and tabu search for job shop scheduling problem[J]. Journal of Mechanical Engineering，2023，59(16)：435-444，426.
[6] FONTES D B M M，HOMAYOUNI S M，GONÇALVES J F. A hybrid particle swarm optimization and simulated annealing algorithm for the job shop scheduling problem with transport resources[J]. European Journal of Operational Research，2023，306(3)：1140-1157.
[7] ZIPFEL B，NEUFELD J，BUSCHER U. An iterated local search for customer order scheduling in additive manufacturing[J]. International Journal of Production Research，2024，62：605-625.
[8] 黄学文，陈绍芬，周阗玉，等. 求解柔性作业车间调度问题的一种新邻域结构[J]. 系统工程理论与实践，2021，41(9)：2367-2378.HUANG Xuewen，CHEN Shaofen，ZHOU Tianyu，et al. A new neighborhood structure for solving the flexible job-shop scheduling problem[J]. Systems Engineering：Theory & Practice，2021，41(9)：2367-2378.
[9] 赵诗奎，黄林，吕杰. Job shop强化多工序联动邻域结构与近似评价研究[J]. 机械工程学报，2023，59(4)：318-331.ZHAO Shikui，HUANG Lin，LÜ Jie. Research on strengthening multi-operation joint movement neighborhood structure and approximate evaluation of job shop scheduling problem[J]. Journal of Mechanical Engineering，2023，59(4)：318-331.
[10] BALAS E. Machine sequencing via disjunctive graphs：An implicit enumeration algorithm[J]. Operations Research，1969，17(6)：941-957.
[11] VAN LAARHOVEN P J M，AARTS E H L，LENSTRA J K. Job shop scheduling by simulated annealing[J]. Operations Research，1992，40(1)：113-125.
[12] MATSUO H，SUH C J，SULLIVAN R S. A controlled search simulated annealing method for the general job shop scheduling problem[R]. Texas：University of Texas at Austin，1988.
[13] NOWICKI E，SMUTNICKI C. A fast taboo search algorithm for the job shop problem[J]. Management Science，1996，42(6)：797-813.
[14] DELL’AMICO M，TRUBIAN M. Applying tabu search to the job-shop scheduling problem[J]. Annals of Operations Research，1993，41(3)：231-252.
[15] BALAS E，VAZACOPOULOS A. Guided local search with shifting bottleneck for job shop scheduling[J]. Management Science，1998，44(2)：262-275.
[16] ZHANG C Y，LI P G，GUAN Z L，et al. A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem[J]. Computers & Operations Research，2007，34(11)：3229-3242.
[17] XIE J，LI X，GAO L，et al. A new neighbourhood structure for job shop scheduling problems[J]. International Journal of Production Research，2023，61(7)：2147-2161.
[18] 巴智勇，袁逸萍，裴国庆，等. 作业车间调度的多工序精确联动邻域结构混合进化算法[J]. 计算机集成制造系统，2024，30(2)：537-552.BA Zhiyong，YUAN Yiping，PEI Guoqing，et al. Hybrid evolutionary algorithm with multi-operation precise joint movement neighborhood structure for job shop scheduling problem[J]. Computer Integrated Manufacturing System，2024，30(2)：537-552.
[19] BRAUNE R，ZAEPFEL G，AFFENZELLER M. Enhancing local search algorithms for job shops with min-sum objectives by approximate move evaluation[J]. Journal of Scheduling，2013，16(5)：495-518.
[20] MUROVEC B. Job-shop local-search move evaluation without direct consideration of the criterion’s value[J]. European Journal of Operational Research，2015，241(2)：320-329.
[21] BELLMAN R. On a routing problem[J]. Quarterly of Applied Mathematics，1958，16(1)：87-90.
[22] EIKELDER H M M，AARTS B J M，VERHOEVEN M G A，et al. Sequential and parallel local search algorithms for job shop scheduling[M]. Boston：Springer，1999.
[23] FISHER H. Probabilistic learning combinations of local job-shop scheduling rules[M]. London：Prentice-Hall 1963.
[24] LAWRENCE S. Supplement to resource constrained project scheduling：An experimental investigation of heuristic scheduling techniques[R]. Pittsburgh，PA：Carnegie Mellon University，1984.
[25] AARTS E H L ，LAARHOVEN P J M V ，LENSTRA J K，et al. A computational study of local search algorithms for job shop scheduling[J]. Journal on Computing，1994，6(2)：118-125.
[26] GLOVER F. Tabu search—Part I[J]. ORSA Journal on Computing，1989，1(3)：190-206.
[27] PENG B，LÜ Z，CHENG T C E. A tabu search/path relinking algorithm to solve the job shop scheduling problem[J]. Computers & Operations Research，2015，53：154-164.
[28] 赵诗奎. 基于新型邻域结构的混合算法求解作业车间调度[J]. 机械工程学报，2016，52(9)：141-151.ZHAO Shikui. A hybrid algorithm with a new neighborhood structure for the job shop scheduling problem[J]. Journal of Mechanical Engineering，2016，52(9)：141-151.