2026年 01期

摘要(Abstract)：

针对柔性作业车间调度问题，构建障碍图模型，设计一种针对剩余工件左移和右移的混合剩余调度策略，以提高后续操作的机器空闲时间利用效率；在障碍图模型的路径搜索过程中，引入2种局部路径主动延误方法，以充分利用工件级插入邻域移动，避免冗余移动操作循环；采用移动工件选择搜索算法引导障碍图模型的整体迭代过程，以深入搜索解空间并生成更具区分度的邻域解集；以最大完工时间为优化目标，在包含遗传算法、两级邻域搜索的柔性作业车间调度算法基础上，提出一种融合障碍图模型的柔性作业车间调度混合算法；利用MATLAB软件编程实现所提出的算法，对31个基准算例进行测试、评估，并与其他文献中的经典算法进行对比。结果表明：所提出算法中融合障碍图模型后，31个基准算例的运算速度均得到提升，其中5个基准算例最大完工时间的最优值得到改进，求解BRdata、 BCdata基准算例集的相对偏差平均值分别优化为14.98、 22.45;通过比较所提出算法与其他文献经典算法求解结果中的相对偏差平均值，验证了所提出算法的有效性。

关键词(KeyWords)：柔性作业车间调度问题;障碍图模型;两级邻域;最大完工时间

基金项目(Foundation):国家自然科学基金项目(52275490);; 山东省自然科学基金项目(ZR2025MS766)

作者(Author):熊英杰,赵诗奎

DOI:10.13349/j.cnki.jdxbn.20251124.002

参考文献(References)：

[1] BRUCKER P,SCHLIE R.Job-shop scheduling with multi-purpose machines[J].Computing,1990,45:369.

[2] MASTROLILLI M,GAMBARDELLA L M.Effective neighbourhood functions for the flexible job shop problem[J].Journal of Scheduling,2000,3(1):3.

[3] GAO J,SUN L Y,GEN M.A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems[J].Computers & Operations Research,2008,35(9):2892.

[4] AMIRI M,ZANDIEH M,YAZDANI M,et al.A variable neighbourhood search algorithm for the flexible job-shop scheduling problem[J].International Journal of Production Research,2010,48(19):5671.

[5] YUAN Y,XU H.Flexible job shop scheduling using hybrid differential evolution algorithms[J].Computers & Industrial Engineering,2013,65(2):246.

[6] LI J Q,PAN Q K.SUGANTHAN P N,et al.A hybrid tabu search algorithm with an efficient neighborhood structure for the flexible job shop scheduling problem[J].The International Journal of Advanced Manufacturing Technology,2011,52(5):683.

[7] HMIDA A B,HAOUARI M,HUGUET M J,et al.Discrepancy search for the flexible job shop scheduling problem[J].Computers & Operations Research,2010,37(12):2192.

[8] 赵诗奎.求解柔性作业车间调度问题的两级邻域搜索混合算法[J].机械工程学报，2015,51(14):175.

[9] 赵诗奎.柔性作业车间调度的改进邻域结构混合算法[J].计算机集成制造系统，2018,24(12):3060.

[10] 谢晋.基于混合遗传禁忌搜索算法的作业车间调度方法[D].武汉：华中科技大学，2022.

[11] AKERS S B,Jr.Letter to the editor:a graphical approach to production scheduling problems[J].Operations Research,1956,4(2):244.

[12] BRUCKER P.An efficient algorithm for the job-shop problem with two jobs[J].Computing,1988,40:353.

[13] AGNETIS A,ORIOLO G.The machine duplication problem in a job shop with two jobs[J].International Transactions in Operational Research,1995,2(1):45.

[14] 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 Oper-ational Research,2014,21(2):215.

[15] 黄林，赵诗奎，黄森.基于障碍图模型和禁忌搜索混合算法求解作业车间调度问题[J].机械工程学报，2023,59(16):435.

[16] HUANG L,ZHAO S K,HAN Q.A fast layered path planning algorithm for job shop scheduling problem[J].IET Collaborative Intelligent Manufacturing,2022,4(4):299.

[17] 孟磊磊.面向高效节能的柔性作业车间调度问题建模与优化[D].武汉：华中科技大学，2020.

[18] 张铭鑫，张玺，彭建刚，等.不确定环境下再制造加工车间多目标调度优化方法[J].合肥工业大学学报(自然科学版),2016,39(4):433.

[19] WANG L,WANG S Y,XU Y,et al.A bi-population based estimation of distribution algorithm for the flexible job-shop scheduling problem[J].Computers & Industrial Engineering,2012,62(4):917.

[20] ZHANG G H,GAO L,SHI Y.An effective genetic algorithm for the flexible job-shop scheduling problem[J].Expert Systems with Applications,2011,38(4):3563.

[21] 肖华军，柴子力，张超勇，等.基于混合化学反应算法的柔性作业车间调度[J].计算机集成制造系统，2018,24(9):2234.

[22] BOZEJKO W, UCHRONSKI M, WODECKI M.Parallel hybrid metaheuristics for the flexible job shop problem[J].Computers & Industrial Engineering,2010,59(2):323.