作业车间调度中非改进邻域解的识别理论与方法

doi:10.3901/JME.2025.10.427

摘要/Abstract

摘要： 在局部搜索算法求解作业车间调度问题(Job-shop scheduling problem，JSP)时，准确识别邻域中的改进和非改进邻域解，可提高计算效率。为此，提出一种改进和非改进邻域解的判定定理，该判定定理在传统判定理论的基础上进行拓展，能够更为精准地对改进和非改进邻域解进行识别。考虑到所提出的判定定理需要高代价的精确算法，针对JSP常用的N1、N4、N5、N6和N7邻域结构，进一步提出一种低代价的非改进邻域解判定方法，在不需要实际执行移动的前提下，可实现非改进邻域解的快速识别。试验结果表明：尽管不能完全识别邻域中的所有非改进邻域解，但仍然能够筛查掉邻域中36.12%～94.92%的非改进邻域解；与此同时，在不降低求解质量的前提下，显著提升了局部搜索算法的计算效率。

关键词: 非改进邻域解, 邻域结构, 局部搜索, 作业车间调度

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

中图分类号:

TP301

黄学文, 王强, 陈桢. 作业车间调度中非改进邻域解的识别理论与方法[J]. 机械工程学报, 2025, 61(10): 427-438.

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.

参考文献

[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.