Hybrid Algorithm Based on Obstacle Graph for Moving Job Search to Solve Distributed Job Shop Scheduling Problems

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

CLC Number:

TP301

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.

References

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