基于时间Petri网和启发式搜索的柔性制造系统调度算法

摘要/Abstract

摘要：

摘要：利用库所延迟Petri网对柔性制造系统进行建模，在Petri网激发变迁生成的可达树中进行启发式搜索，求解最小完成时间调度策略，并改进了现有计算机器剩余时间的启发式函数，对剩余加工操作进行准确分类，以保证算法的最优性.为了提高算法的求解效率，改进后的启发式函数考虑了未产成操作的剩余时间，以使预测值更加准确并减少了计算量.同时，利用实验验证了所提出方法的正确性和有效性.
关键词：中图分类号：文献标志码： A

关键词: 柔性制造系统, 调度, Petri网, 启发式搜索

Abstract:

Abstract： The place-timed Petri net was used to model the flexible manufacturing system scheduling problems. Combined with the execution capacity and heuristic search, Petri net can achieve the minimum makespan strategy by expanding the partial reachability tree. The heuristic function for calculating the machine remaining operation time was improved. First, remaining operations for general FMS were classified into two categories to guarantee the optimality. Besides, the remaining time of onprocessing operations was also considered, which improved the lower bound for heuristic function. As a result, the optimal scheduling strategy could be achieved in less effort. Experiment results demonstrate the proposed heuristic function performs better as expected.

Key words: flexible manufacturing system (FMS), scheduling, Petri net, heuristic search

中图分类号:

TH 165

李诚，李爽，冯毅萍，荣冈. 基于时间Petri网和启发式搜索的柔性制造系统调度算法[J]. 上海交通大学学报（自然版）, 2015, 49(05): 708-713.

LI Cheng,LI Shuang,FENG Yiping,RONG Gang. Scheduling Flexible Manufacturing System Based on Timed Petri Net and Heuristic Search[J]. Journal of Shanghai Jiaotong University, 2015, 49(05): 708-713.

参考文献

［1］Lei H, Xing K Y, Han L B, et al. Deadlockfree scheduling for flexible manufacturing systems using Petri net and heuristic search ［J］. Computers and Industrial Engineering, 2014, 72: 297305.

［2］Caumond A, Lacomme P, Moukrim A, et al. An MILP for scheduling problems in an FMS with one vehicle ［J］. European Journal of Operational Research, 2009, 199(3): 706722.

［3］Prakash A, Felix T S, Deshmukh S G. FMS scheduling with knowledge based genetic algorithm［J］. Expert System with Applications, 2011, 38(4): 31613171.

［4］Adibi M A, Zandieh M, Amiri M. Multiobjective scheduling of dynamic job shop using varivable neighborhood search ［J］. Expert System with Applications, 2010, 37(1): 282287.

［5］Yan M M, Zhong C F. A deadlock prevention policy for a class of Petri net models of flexible manufacturing system［J］. International Journal of Production Research, 2011, 49(24): 73797396.

［6］Moslehi G, Mahnam M. A Pareto approach to multiobjective flexible jobshop scheduling problem using particle swarm optimization and local search ［J］. International Journal of Production Economics, 129(1): 1422.

［7］Li Z W, Liu G Y, Hanisch H M, et al. Deadlock prevention based on structure reuse of Petri net supervisors for flexible manufacturing system ［J］. IEEE Transactions on Systems, Man and Cybernetics, 2012, 42(1): 178191.

［8］Xiong H H, Zhou M C. Scheduling ofsemiconductor test facility via Petri Nets and hybrid heuristic search ［J］. Semiconductor Manufacturing, 1998, 11(3): 384393.

［9］Yu S, Reyes A, Cang S, et al. Combined petri netmodelling and AIbased heuristic hybrid search forflexiblemanufacturing systems—Part 2. Heuristic hybrid search［J］. Computers and Industrial Engineering, 2003, 44（4）: 545566.

［10］Lee J, Lee J S. Heuristic search for scheduling flexible manufacturing systems using lower bound reachability matrix ［J］. Computers and Industrial Engineering, 2010, 59(4): 799806.

［11］Huang B, Jiang R X, Zhang G X. Search strategy for scheduling flexible manufacturing systems simultaneously using admissible heuristic functions and nonadmissibleheuristic functions ［J］. Computers and Industrial Engineering, 2014, 71: 2126.

［12］Yu S, Reyes A, Cang S, et al. Combined Petri net modelling and AI based heuristic hybrid search for flexible manufacturing systems—Part 1. Petri net modelling and heuristic search ［J］. Computers and Industrial Engineering, 2003, 44(4): 527543.

［13］Huang B, Shi X X, Xu N. Scheduling FMS with alternative routing using Petri nets and near admissible heuristic search［J］. International Journal of Advanced Manufacturing Technology, 2012, 63(913):11311136.

[1]	刘亚辉, 申兴旺, 顾星海, 彭涛, 鲍劲松, 张丹. 面向柔性作业车间动态调度的双系统强化学习方法[J]. 上海交通大学学报, 2022, 56(9): 1262-1275.
[2]	李林晏, 韩爽, 乔延辉, 李莉, 刘永前, 阎洁, 刘海东. 面向高比例新能源并网场景的风光-电动车协同调度方法[J]. 上海交通大学学报, 2022, 56(5): 554-563.
[3]	汤洪涛, 王丹南, 邵益平, 赵文彬, 江伟光, 陈青丰. 基于改进候鸟迁徙优化的多目标批量流混合流水车间调度[J]. 上海交通大学学报, 2022, 56(2): 201-213.
[4]	陆秋瑜, 于珍, 杨银国, 李力. 考虑源荷功率不确定性的海上风力发电多微网两阶段优化调度[J]. 上海交通大学学报, 2022, 56(10): 1308-1316.
[5]	王兴志, 翟海保, 严亚勤, 吴庆曦. 基于数字孪生和深度学习的新一代调控系统预调度方法[J]. 上海交通大学学报, 2021, 55(S2): 37-41.
[6]	许凌, 王兴志, 肖林朋. 基于语义特征抓取电网调度事件的检测技术[J]. 上海交通大学学报, 2021, 55(S2): 86-91.
[7]	范厚明, 于佳琪, 马梦知, 蒋晓丹, 慈吉利, 翟志伟. 模糊时间窗下多船型不定期船调度与航速联合优化[J]. 上海交通大学学报, 2021, 55(3): 297-310.
[8]	吕祥梅, 刘天琪, 刘绚, 何川, 南璐, 曾红. 考虑高比例新能源消纳的多能源园区日前低碳经济调度[J]. 上海交通大学学报, 2021, 55(12): 1586-1597.
[9]	王金凤, 陈璐, 杨雯慧. 考虑设备可用性约束的单机调度问题[J]. 上海交通大学学报, 2021, 55(1): 103-110.
[10]	蒋小康, 张朋, 吕佑龙, 赵新明, 张洁. 基于混合蚁群算法的半导体生产线炉管区调度方法[J]. 上海交通大学学报, 2020, 54(8): 792-804.
[11]	李柏鹤, 蒋祖华, 陶宁蓉, 孟令通, 郑虹. 考虑平板车合作运输的船舶分段堆场间调度[J]. 上海交通大学学报, 2020, 54(7): 718-727.
[12]	朱宏伟, 陆志强. 考虑人力资源排班的资源受限项目调度问题建模与优化[J]. 上海交通大学学报, 2020, 54(6): 624-635.
[13]	孟令通, 蒋祖华, 陶宁蓉, 刘建峰, 郑虹. 考虑工艺顺序和组合分段的多堆场调度方法[J]. 上海交通大学学报, 2020, 54(4): 331-343.
[14]	许显杨，陈璐. 考虑设备可靠性与能耗的平行机调度[J]. 上海交通大学学报, 2020, 54(3): 247-255.
[15]	马昌谱，周炳海. 自动存取系统多载量轨道小车避碰调度方法[J]. 上海交通大学学报, 2020, 54(2): 126-134.