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]	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.
[2]	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.
[3]	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.
[4]	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.
[5]	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.
[6]	LU Qiuyu, YU Zhen, YANG Yinguo, LI Li. Two-Stage Optimal Schedule of Offshore Wind-Power-Integrated Multi-Microgrid Considering Uncertain Power of Sources and Loads [J]. Journal of Shanghai Jiao Tong University, 2022, 56(10): 1308-1316.
[7]	WANG Jinfeng, CHEN Lu, YANG Wenhui. A Single Machine Scheduling Problem Considering Machine Availability Constraints [J]. Journal of Shanghai Jiao Tong University, 2021, 55(1): 103-110.
[8]	JIANG Xiaokang, ZHANG Peng, LÜ Youlong, ZHAO Xinming, ZHANG Jie. Hybrid Ant Colony Algorithm for Batch Scheduling in Semiconductor Furnace Operation [J]. Journal of Shanghai Jiaotong University, 2020, 54(8): 792-804.
[9]	ZHU Hongwei, LU Zhiqiang. Modeling and Optimization of Resource Constrained Project Scheduling Problem Considering Employee-Timetabling [J]. Journal of Shanghai Jiaotong University, 2020, 54(6): 624-635.
[10]	MENG Lingtong, JIANG Zuhua, TAO Ningrong, LIU Jianfeng, ZHENG Hong. Multi-Stockyard Scheduling Considering Technological Process and Combined Assembly Block [J]. Journal of Shanghai Jiao Tong University, 2020, 54(4): 331-343.
[11]	MA Changpu，ZHOU Binghai. Scheduling of Multi-Load Rail Guided Vehicles in AS/RS with Collision Avoidance Constrains [J]. Journal of Shanghai Jiaotong University, 2020, 54(2): 126-134.
[12]	FANG Jia, LU Zhiqiang. Modeling and Optimization of Robust Scheduling Template Considering Equipment Failure [J]. Journal of Shanghai Jiao Tong University, 2020, 54(12): 1278-1290.
[13]	ZHAO Rui, GU Xingsheng. A Discrete Sine Optimization Algorithm for No-Idle Flow-Shop Scheduling Problem [J]. Journal of Shanghai Jiao Tong University, 2020, 54(12): 1291-1299.
[14]	CUI Weiwei (崔维伟). Approximate Approach to Deal with the Uncertainty in Integrated Production Scheduling and Maintenance Planning [J]. Journal of Shanghai Jiao Tong University (Science), 2020, 25(1): 106-117.
[15]	ZHOU Binghai,LIU Wenlong. Multi-Objective Hybrid Flow-Shop Scheduling Problem Considering Energy Consumption and On-Time Delivery [J]. Journal of Shanghai Jiaotong University, 2019, 53(7): 773-779.