Scheduling Flexible Manufacturing System Based on Timed Petri Net and Heuristic Search

Abstract

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

CLC Number:

TH 165

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.

References

［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]	ZHAO Yingying, QIU Yue, ZHU Tianchen, LI Fan, SU Yun, TAI Zhenying, SUN Qingyun, FAN Hang. Online Steady-State Scheduling of New Power Systems Based on Hierarchical Reinforcement Learning [J]. Journal of Shanghai Jiao Tong University, 2025, 59(3): 400-412.
[2]	ZHOU Siyi, YANG Huanhong, HUANG Wentao, ZHOU Ze, JIAO Wei, YANG Zhenyu. Two-Stage Day-Ahead and Intra-Day Rolling Optimization Scheduling of Container Integrated Port Energy System [J]. Journal of Shanghai Jiao Tong University, 2024, 58(9): 1357-1369.
[3]	WANG Xuan, WANG Bao, CHEN Yanping, LIU Hong, MA Xiaohui. Joint Economic Optimization of AGV Logistics Scheduling and Orderly Charging in a Low-Carbon Automated Terminal [J]. Journal of Shanghai Jiao Tong University, 2024, 58(9): 1370-1380.
[4]	JIANG Zuhua^1∗(蒋祖华), ZHOU Hongming²(周宏明), TAO Ningrong³(陶宁蓉), LI Baihe¹(李柏鹤). Knowledge-Based Curved Block Construction Scheduling and Application in Shipbuilding [J]. J Shanghai Jiaotong Univ Sci, 2024, 29(5): 759-765.
[5]	CHEN Yini(陈旖旎), JIANG Zuhua^* (蒋祖华). Multi-AGVs Scheduling with Vehicle Conflict Consideration in Ship Outfitting Items Warehouse [J]. J Shanghai Jiaotong Univ Sci, 2024, 29(3): 492-508.
[6]	GU Huijie, ZHOU Huafeng, PENG Chaoyi, HU Yaping, ZHAO Xinyi, XIE Jun, SHI Xionghua. A Multi-Time Scale Scheduling Model for Power Generation Systems with a High Proportion of New Energy Including Pumped Storage Power Stations [J]. Journal of Shanghai Jiao Tong University, 2024, 58(12): 1957-1967.
[7]	YE Zhiliang, LI Canbing, ZHANG Yongjun, LI Licheng, XIAO Yinjing, WU Yuhang, TAI Nengling. Optimization of Day-Ahead Dispatch Time Resolution in Power System with a High Proportion of Climate-Sensitive Renewable Energy Sources [J]. Journal of Shanghai Jiao Tong University, 2023, 57(7): 781-790.
[8]	LI Junshuang, HU Yan, TAI Nengling. Collaborative Optimization Scheduling of 5G Base Station Energy Storage and Distribution Network Considering Communication Load and Power Supply Reliability [J]. Journal of Shanghai Jiao Tong University, 2023, 57(7): 791-802.
[9]	FAN Houming, MA Xiaobin, PENG Wenhao, YUE Lijun, MA Mengzhi. Container Allocation in Multi-Blocks and Optimization of Yard Crane Dispatching in Non-Engagement of Container Delivery Truck [J]. Journal of Shanghai Jiao Tong University, 2023, 57(10): 1261-1272.
[10]	ZHANG Sujun, YANG Wenqiang, GU Xingsheng. An Improved Multi-Swarm Migrating Birds Optimization Algorithm for Hybrid Flow Shop Scheduling [J]. Journal of Shanghai Jiao Tong University, 2023, 57(10): 1378-1388.
[11]	LIU Yahui, SHEN Xingwang, GU Xinghai, PENG Tao, BAO Jinsong, ZHANG Dan. A Dual-System Reinforcement Learning Method for Flexible Job Shop Dynamic Scheduling [J]. Journal of Shanghai Jiao Tong University, 2022, 56(9): 1262-1275.
[12]	LI Dechang, YANG Hualong, DUAN Jingru. A Joint Optimization of Vessel Scheduling and Refueling Strategy for Container Liner Shipping with Cooperative Agreements [J]. Journal of Shanghai Jiao Tong University, 2022, 56(7): 953-964.
[13]	LI Linyan, HAN Shuang, QIAO Yanhui, LI Li, LIU Yongqian, YAN Jie, LIU Haidong. A Wind-Solar-Electric Vehicles Coordination Scheduling Method for High Proportion New Energy Grid-Connected Scenarios [J]. Journal of Shanghai Jiao Tong University, 2022, 56(5): 554-563.
[14]	WANG Zixiang, WU Zerui, LIU Ran. Weekly Physician Scheduling for Emergency Departments with Time-Varying Demands of Patients with Revisits [J]. Journal of Shanghai Jiao Tong University, 2022, 56(2): 242-252.
[15]	TANG Hongtao, WANG Dannan, SHAO Yiping, ZHAO Wenbin, JIANG Weiguang, CHEN Qingfeng. A Modified Migrating Birds Optimization for Multi-Objective Lot Streaming Hybrid Flowshop Scheduling [J]. Journal of Shanghai Jiao Tong University, 2022, 56(2): 201-213.