基于时间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]. 上海交通大学学报, 2025, 59(4): 476-488.
[2]	吴静, 刘轩宇, 李响, 齐笑言, 李成俊, 张忠. 碳市场价格不确定性对电网调度影响机理分析[J]. 上海交通大学学报, 2025, 59(3): 354-364.
[3]	赵莹莹, 仇越, 朱天晨, 李凡, 苏运, 邰振赢, 孙庆赟, 凡航. 基于分层强化学习的新型电力系统在线稳态调度[J]. 上海交通大学学报, 2025, 59(3): 400-412.
[4]	娄为, 胡蓉, 于谨铭, 张希鹏, 樊飞龙, 刘嵩源. 内嵌市场博弈模型的电网-抽水蓄能多主体协调调度[J]. 上海交通大学学报, 2025, 59(3): 365-375.
[5]	周思怡, 杨欢红, 黄文焘, 周泽, 焦伟, 杨镇瑜. 集装箱港口综合能源系统日前-日内两阶段滚动优化调度[J]. 上海交通大学学报, 2024, 58(9): 1357-1369.
[6]	王轩, 汪宝, 陈艳萍, 刘洪, 马晓慧. 低碳自动化码头AGV物流调度和有序充电的联合经济优化[J]. 上海交通大学学报, 2024, 58(9): 1370-1380.
[7]	段佳南, 谢俊, 邢单玺. 风电-光伏-抽蓄-电制氢多主体能源系统增益的合作博弈分配策略[J]. 上海交通大学学报, 2024, 58(6): 872-880.
[8]	张程, 匡宇, 陈文兴, 郑杨. 计及电动汽车充电方式与多能耦合的综合能源系统低碳经济优化运行[J]. 上海交通大学学报, 2024, 58(5): 669-681.
[9]	蒋祖华1, 周宏明2, 陶宁蓉3, 李柏鹤1. 基于知识的船舶曲面分段建造调度及应用[J]. J Shanghai Jiaotong Univ Sci, 2024, 29(5): 759-765.
[10]	陈旖旎，蒋祖华. 船舶舾装件立体仓储考虑车辆冲突的多AGV任务调度策略研究[J]. J Shanghai Jiaotong Univ Sci, 2024, 29(3): 492-508.
[11]	顾慧杰, 周华锋, 彭超逸, 胡亚平, 赵心怡, 谢俊, 施雄华. 含抽水蓄能电站的高比例新能源发电系统多时间尺度调度模型[J]. 上海交通大学学报, 2024, 58(12): 1957-1967.
[12]	陈熠, 王晗, 曾丹, 严正, 薛必克, 赵乐, 熊雪君, 冯煜尧. 基于低秩逼近代理模型的N-1安全约束经济调度快速计算方法[J]. 上海交通大学学报, 2024, 58(10): 1524-1533.
[13]	米阳, 吴继伟, 田书欣, 马思源, 王育飞. 考虑个体自私的热电联产系统完全分布式经济调度[J]. 上海交通大学学报, 2024, 58(1): 50-58.
[14]	陈熠, 王晗, 徐潇源, 胡友琳, 严正, 曾丹, 冯凯. 省间-省内两级市场协调下两阶段分布鲁棒经济调度模型[J]. 上海交通大学学报, 2023, 57(9): 1114-1125.
[15]	胡博, 程欣, 邵常政, 黄威, 孙悦, 谢开贵. 计及建筑热负荷弹性的综合能源系统调度方法[J]. 上海交通大学学报, 2023, 57(7): 803-813.