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
fDate :
7/1/2010 12:00:00 AM
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;
Journal_Title :
Automation Science and Engineering, IEEE Transactions on
DOI :
10.1109/TASE.2010.2043096