基于障碍图的移动工件搜索混合算法求解分布式作业车间调度问题

doi:10.3901/JME.2025.10.479

摘要/Abstract

摘要： 针对分布式作业车间调度问题，以优化最大完工时间为目标，设计基于障碍图的移动工件搜索混合算法。基于障碍图的移动工件搜索可以实现工件级尺度搜索。当工件将要插入已有调度方案时，首先，采用快速路径规划算法求解路径。然后，根据路径解码规则科学的插入工件，保证工件插入之后新解的可行性和较优性。构建三种移动工件搜索方法：关键工厂自身移动工件搜索，移动关键工厂的工件到其他工厂进行搜索，关键工厂与其他工厂的工件交换进行搜索。三种移动工件搜索方法不仅适用于单个工厂的优化，而且可以在工厂之间进行移动或交换工件搜索，解决了工件的工厂选择问题。混合禁忌搜索算法，结合邻域结构对关键工厂进行集中搜索，进一步提升求解质量。通过对基准算例进行测试，验证了所提混合算法的有效性。特别是，所提算法刷新了多个基准算例的最优解。同时，移动工件搜索亦可作为共性技术用于求解其他作业车间调度扩展问题。

关键词: 分布式作业车间调度, 障碍图, 移动工件搜索, 混合算法, 最大完工时间

Abstract: Aiming at the distributed job shop scheduling problem, a hybrid algorithm for moving job search based on obstacle graph is designed with the goal of optimizing the maximum makespan. Moving job search based on obstacle graph can achieve job level scale search. When the job is to be inserted into an existing scheduling scheme, the fast path planning algorithm is first used to solve the path. Then, the job is scientifically inserted according to the path decoding rules, which ensures the feasibility and better performance of the new solution after the job is inserted. Three moving job search methods are constructed: moving job search in the critical factory itself, moving job search from the critical factory to others, and exchanging job search between the critical factory and others. The three moving job search methods are not only applicable to the optimization of a single factory, but also can be used to move or exchange job search among factories, which solves the problem of factory selection of a job. The hybrid tabu search algorithm, combined with the neighborhood structure, performs centralized search on critical factory to further improve the solution quality. The effectiveness of the proposed hybrid algorithm is verified by testing it on benchmark instances. In particular, the hybrid algorithm refreshes the optimal solutions of several benchmark instances. Meanwhile, the moving job search can also be used as a common technique to solve other job shop scheduling extension problems.

Key words: distributed job shop scheduling, obstacle graph, moving job search, hybrid algorithm, maximum completion time

中图分类号:

TP301

赵诗奎, 黄林, 刘子辉, 郑岩. 基于障碍图的移动工件搜索混合算法求解分布式作业车间调度问题[J]. 机械工程学报, 2025, 61(10): 479-494.

ZHAO Shikui, HUANG Lin, LIU Zihui, ZHENG Yan. Hybrid Algorithm Based on Obstacle Graph for Moving Job Search to Solve Distributed Job Shop Scheduling Problems[J]. Journal of Mechanical Engineering, 2025, 61(10): 479-494.

参考文献

[1] XIE Jin，LI Xinyu，GAO Liang，et al. A hybrid algorithm with a new neighborhood structure for job shop scheduling problems[J]. Computers and Industrial Engineering，2022，169：108205.
[2] XIE Jin，LI Xinyu，GAO Liang，et al. A new neighborhood structure for job shop scheduling problems[J]. International Journal of Production Research，2023，61(7)：2147-2161.
[3] 黄林，赵诗奎，黄森. 基于障碍图模型和禁忌搜索混合算法求解作业车间调度问题[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.
[4] TAMSSAOUET K，DAUZÈRE-PÉRÈS S. A general efficient neighborhood structure framework for the job-shop and flexible job-shop scheduling problems[J]. European Journal of Operational Research，2023，311(2)：455-471.
[5] JIA H Z，NEE A Y C，FUH J Y H，et al. A modified genetic algorithm for distributed scheduling problems[J]. Journal of Intelligent Manufacturing，2003，14(3-4)：351-362.
[6] JIA H Z，FUH J Y H，NEE A Y C，et al. Integration of genetic algorithm and Gantt chart for job shop scheduling in distributed manufacturing systems[J]. Computers & Industrial Engineering，2007，53(2)：313-320.
[7] NADERI B，AZAB A. Modeling and heuristics for scheduling of distributed job shops[J]. Expert Systems with Applications，2014，41(17)：7754-7763.
[8] NADERI B，AZAB A. An improved model and novel simulated annealing for distributed job shop problems[J]. International Journal of Advanced Manufacturing Technology，2015，81(1-4)：693-703.
[9] CHAOUCH I，DRISS O B，GHEDIRA K. A modified ant colony optimization algorithm for the distributed job shop scheduling problem[J]. Procedia Computer Science，2017，112：296-305.
[10] CHAOUCH I，DRISS O B，GHEDIRA K. A novel dynamic assignment rule for the distributed job shop scheduling problem using a hybrid ant-based algorithm[J]. Applied Intelligence，2019，49(5)：1903-1924.
[11] ŞAHMAN M A. A discrete spotted hyena optimizer for solving distributed job shop scheduling problems[J]. Applied Soft Computing，2021，106(1)：107349.
[12] XIE Jin，GAO Liang，PAN Quanke，et al. An effective multi-objective artificial bee colony algorithm for energy efficient distributed job shop scheduling[J]. Procedia Manufacturing，2019，39：1194-1203.
[13] JIANG Enda，WANG Ling，PENG Zhiping. Solving energy-efficient distributed job shop scheduling via multi-objective evolutionary algorithm with decomposition[J]. Swarm and Evolutionary Computation，2020，58(4)：100745.
[14] 王光辰. 基于Memetic算法的分布式车间调度方法研究[D]. 武汉：华中科技大学，2023.WANG Guangchen. Research on distributed shop scheduling methods based on Memetic algorithm[D]. Wuhan：Huazhong University of Science and Technology，2023.
[15] 王凌，邓瑾，王圣尧. 分布式车间调度优化算法研究综述[J]. 控制与决策，2016，31(1)： 1-11.WANG Ling，DENG Jin，WANG Shengyao. Survey on optimization algorithms for distributed shop scheduling[J]. Control and Decision，2016，31(1)：1-11.
[16] 王思涵，李新宇，高亮，等. 分布式车间调度研究综述[J]. 华中科技大学学报，2022，50(6)：1-10.WANG Sihan，LI Xinyu，GAO Liang，et al. A review of distributed shop scheduling problems[J]. Journal of Huazhong University of Science and Technology，2022，50(6)：1-10.
[17] XIE Jin，LI Xinyu，GAO Liang，et al. A hybrid genetic tabu search algorithm for distributed flexible job shop scheduling problems[J]. Journal of Manufacturing Systems，2023，71(5)：82-94.
[18] CHAN F T S，CHUNG S H，CHAN P L Y. An adaptive genetic algorithm with dominated genes for distributed scheduling problems[J]. Expert Systems with Applications，2005，29(2)：364-371.
[19] WANG Sihan，LI Xinyu，GAO Liang，et al. A multi-disjunctive-graph model-based memetic algorithm for the distributed job shop scheduling problem[J]. Advanced Engineering Informatics，2024，60：102401.
[20] 李浩然，高亮，李新宇. 基于离散人工蜂群算法的多目标分布式异构零等待流水车间调度方法[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.
[21] 牟健慧，段培永，高亮，等. 基于混合遗传算法求解分布式流水车间逆调度问题[J]. 机械工程学报，2022，58(6)：295-308.MU Jianhui，DUAN Peiyong，GAO Liang，et al. Hybrid genetic algorithm for distributed flow shop inverse scheduling problem[J]. Journal of Mechanical Engineering，2022，58(6)：295-308.
[22] 孟磊磊，张彪，任亚平，等. 求解分布式柔性作业车间调度的混合蛙跳算法[J]. 机械工程学报，2021，57(17)：263-272.MENG Leilei，ZHANG Biao，REN Yaping，et al. Hybrid shuffled frog-leaping algorithm for distributed flexible job shop scheduling[J]. Journal of Mechanical Engineering，2021，57(17)：263-272.
[23] SHELDON B，AKERS J. A graphical approach to production scheduling problems[J]. Operations Research，1956，4(2)：244-245.
[24] GONÇALVES J F，RESENDE M G C. An extended Akers graphical method with a biased random-key genetic algorithm for job-shop scheduling[J]. International Transactions in Operational Research，2014，21(2)：215-246.
[25] HUANG Lin，ZHAO Shikui，HAN Qing. A fast layered path planning algorithm for job shop scheduling problem[J]. IET Collaborative Intelligent Manufacturing，2022，4(4)：299-315.
[26] ZHANG Chaoyong，LI Peigen，GUAN Zailin，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.
[27] BALAS E，VAZACOPOULOS A. Guided local search with shifting bottleneck for job shop scheduling[J]. Management Science，1998，44(2)：262-275.
[28] TANG Jianchao，ZHANG Guoji，LIN Binbin，et al. A hybrid PSO/GA algorithm for job shop scheduling problem[C]//International Conference in Swarm Intelligence，June 12-15，2010，Beijing，China. London：Springer，2010：566-573.