Petri Net Decomposition Approach to Optimization of Route Planning Problems for AGV Systems
Authors:
- 26 April 2010
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Automation Science and Engineering
- Vol. 7 (3) , 523-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
This publication has 38 references indexed in Scilit:
- A performance-based structural policy for conflict-free routing of bi-directional automated guided vehiclesComputers in Industry, 2005
- Elementary siphons of Petri nets and their application to deadlock prevention in flexible manufacturing systemsIEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans, 2004
- Deadlock avoidance in an automated guidance vehicle system using a coloured Petri net modelInternational Journal of Production Research, 2002
- A bi-directional path layout for conflict-free routing of AGVsInternational Journal of Production Research, 2001
- An AGV routing policy reflecting the current and future state of semiconductor and LCD production linesInternational Journal of Production Research, 2001
- A dynamic-zone strategy for vehicle-collision prevention and load balancing in an AGV system with a single-loop guide pathComputers in Industry, 2000
- Dynamic conflict-free routing of automated guided vehiclesInternational Journal of Production Research, 1999
- Deadlock prediction and avoidance for zone-control AGVSInternational Journal of Production Research, 1998
- Detection of deadlocks in flexible manufacturing cellsIEEE Transactions on Robotics and Automation, 1991
- Conflict-free shortest-time bidirectional AGV routeingInternational Journal of Production Research, 1991