基于束搜索和A^(*)两段混合Petri网的柔性作业车间调度  

Flexible job-shop scheduling based on A^(*)and beam search algorithms two-stage hybrid Petri net

作　　者：刘稳 李明富[1,3,4] 谢思晨[1] 刘忠喜 LIU Wen;LI Mingfu;XIE Sichen;LIU Zhongxi(School of Mechanical Engineering,Xiangtan University,Xiangtan 411105,China;Changsha Aeronautical Vocational and Technical College,Changsha 410124,China;Engineering Research Center of Complex Tracks Processing Technology and Equipment of Ministry of Education,Xiangtan University,Xiangtan 411105,China;Key Laboratory of Welding Robot and Application Technology of Hunan Province,Xiangtan University,Xiangtan 411105,China)

机构地区：[1]湘潭大学机械工程学院,湖北湘潭411105 [2]长沙航空职业技术学院,湖南长沙410124 [3]湘潭大学复杂轨迹加工工艺及装备教育部工程研究中心,湖北湘潭411105 [4]湘潭大学焊接机器人与应用技术湖南省重点实验室,湖北湘潭411105

出　　处：《武汉大学学报（工学版）》2023年第10期1255-1263,共9页Engineering Journal of Wuhan University

基　　金：国家自然科学基金面上项目(编号:52375519)。

摘　　要：采用启发式优化算法对柔性作业调度的Petri网模型进行搜索和寻优存在内存占用过大和最优性损失问题。为此,将A*算法和束搜索算法相结合,提出一种两阶段混合搜索算法,对柔性作业车间调度的Petri网模型进行寻优。在调度活动的早期阶段,采用束搜索算法对搜索空间智能剪枝,后期阶段采用深度优先算法选取一条可行的次优路径,从而保证以较小的代价找到较好的调度结果。最后,通过2个基准实例对算法的性能进行测试。与其他算法的对比结果显示,这种两阶段混合算法不仅可以获得高质量的调度方案,还在减少内存需求和加快收敛速度方面有一定的作用。It is popular to use the heuristic optimization algorithm to search and optimize the Petri net models of flexible job-shop scheduling.However,there are problems of excessive memory-occupancy and loss of optimality.Accordingly,a two-stage hybrid algorithm which combines A'and beam search algorithm,is proposed to optimize the Petri net model of flexible job-shop scheduling.In the first stage,the search space is intelligently pruned by using beam search algorithm.In the second stage,a feasible suboptimal path is selected by depth-first search algorithm,so as to ensure that better scheduling results can be found at less cost.Two benchmarks instances are used to test the performances of the proposed algorithm.The results show that the two-stage hybrid algorithm can get better quality schedules with lower memory requirements and higher convergence speed compared with other algorithms.

关 键 词：柔性作业车间 调度优化 PETRI网 A^(*)搜索算法 束搜索 

分 类 号：TH165[机械工程—机械制造及自动化] TP278[自动化与计算机技术—检测技术与自动化装置]