DocumentCode :
1479824
Title :
Petri Net Decomposition Approach to Optimization of Route Planning Problems for AGV Systems
Author :
Nishi, Tatsushi ; Maeno, Ryota
Author_Institution :
Div. of Math. Sci. for Social Syst., Osaka Univ., Toyonaka, Japan
Volume :
7
Issue :
3
fYear :
2010
fDate :
7/1/2010 12:00:00 AM
Firstpage :
523
Lastpage :
537
Abstract :
In this paper, we propose a Petri Net (PN) decomposition approach to the optimization of route planning problems for automated guided vehicles (AGVs) in semiconductor fabrication bays. An augmented PN is developed to model the concurrent dynamics for multiple AGVs. The route planning problem to minimize the total transportation time is formulated as an optimal transition firing sequence problem for the PN. The PN is decomposed into several subnets such that the subnets are made independent by removing the original shared places and creating its own set of resource places for each subnet with the appropriate connections. The partial solution derived at each subnet is not usually making a feasible solution for the entire PN. The penalty function algorithm is used to integrate the solutions derived at the decomposed subnets. The optimal solution for each subnet is repeatedly generated by using the shortest-path algorithm in polynomial time with a penalty function embedded in the objective function. The effectiveness of the proposed method is demonstrated for a practical-sized route planning problem in semiconductor fabrication bay from computational experiments.
Keywords :
Petri nets; automatic guided vehicles; optimisation; path planning; semiconductor industry; AGV systems; Petri net decomposition approach; automated guided vehicles; optimization; route planning problems; semiconductor fabrication bays; shortest path algorithm; Automated guided vehicles; Petri nets (PNs); decomposition; discrete-event systems; route planning problem; shortest-path algorithm;
fLanguage :
English
Journal_Title :
Automation Science and Engineering, IEEE Transactions on
Publisher :
ieee
ISSN :
1545-5955
Type :
jour
DOI :
10.1109/TASE.2010.2043096
Filename :
5454421
Link To Document :
بازگشت