Optimal Scheduling of Automatic Guided Vehicle System via State Space Realization
Kenji Sawada*, Seiichi Shin*, Kenji Kumagai**,
and Hisato Yoneda**
*Department of Mechanical Engineering and Intelligent Systems, The University of Electro-Communications, 1-5-1 Choufugaoka, Chofu, Tokyo 182-8585, Japan
**Murata Machinery, Ltd., 9Fl., Yokohama Nishiguchi K Bldg., 2-8-19 Kitasaiwai, Nishi-ku, Yokohama-shi, Kanagawa, Japan
This paper considers dynamical system modeling of transportation systems in semiconductor manufacturing based on state space realization. Utilizing this method, we consider an optimal scheduling problem for an Automatic Guided Vehicle (AGV) transfer problem, which is to control AGV congestion at transport rail junctions. Our scheduling algorithm is based on model-predictive control in which the cycle of measurement, prediction and optimization is repeated. Its optimization is recast as an Integer Linear Programming (ILP) problem. Since little attention has been given to AGV scheduling based on model-predictive control, no method is, to our knowledge, known for determining appropriate cost functions. Here, we focus on throughput maximization and shortest transit time problems and show corresponding cost function settings. We also propose a visualization algorithm of AGV scheduling via state space realization, presenting numerical examples.
-  C. H. Kuo, “Modeling and Performance Evaluation of an Overhead Hoist Transport System in a 300 mm Fabrication Plant,” Int. J. Adv. Manuf. Technol., Vol.20, pp. 153-161, 2002.
-  K. Gartland, “Automated Material handling system (AMHS) framework user requirements document version 1.0,” Int. SEMATECH, Technol., Transfer # 99 073 793A-TR, 1999.
-  L. Qiu, W. J. Hsu, S. Y. Huang, and H. Wang, “Scheduling and routing algorithms for AGVs: A survey,” Int. J. Prod. Res., Vol.40, No.3, pp. 745-760, 2002.
-  G. K. Agrawal and S. Heragu, “A survey of automated material handling systems in 300-mm semiconductor fabs,” IEEE trans. Semiconductor Manufacturing, Vol.19, No.1, pp. 112-119, 2006.
-  I. F. A. Vis, “Survey of research in the design and control of auto-mated guided vehicle systems,” Eur. J. Oper. Res., Vol.170, No.3, pp. 677-709, 2006.
-  F. Kato and S. Shin, “Multistep optimal scheduling of automated guided vehicles in a semiconductor fabrication,” Proc. of SICE Annual Conf. in Taiwan, pp. 985-989, 2010.
-  T. Nishi and R. Maeno, “Petri Net Decomposition Approach to Optimization of Route Planning Problems for AGV Systems,” IEEE Trans. Aut. Sci. Eng., Vol.7, No.3, pp. 523-537, 2010.
-  Y. Tanaka, T. Nishi, and M. Inuiguchi, “Dynamic Optimization of Simultaneous Dispatching and Conflict-free Routing for Automated Guided Vehicles – Petri Net Decomposition Approach,” J. of Advanced Mechanical Design, Systems, and Manufacturing, Vol.4, No.3, pp. 701-715, 2010.
-  J. M. Maciejowski, “Predictive control with constraints,” Prentice Hall, 2002.
-  A. Bemporad and M. Morari, “Control of systems integrating logic, dynamics, and constraints, Automatica,” Vol.35, No.3, pp. 407-427, 1999.
-  R. Gondhalekar and J. Imura, “Least-restrictive move-blocking model predictive control,” Automatica, Vol.46, No.7, pp. 1234-1240, 2010.
-  M. N. Zeilinger, C. N. Jones, and M. Morari, “Real-Time Suboptimal Model Predictive Control Using a Combination of Explicit MPC and Online Optimization,” IEEE Trans. Automat. Contr., Vol.56, nN.7, pp. 1524-1534, 2011.
-  R. Nakamura, K. Sawada, S. Shin, K. Kumagai, and H. Yoneda, “On the MLD system modeling and its evaluation for AGV optimal path planning,” Proc. of SICE 13th Annual Conf. on Control Systems, SY0002/13/0000-0212, 2013. (in Japanese)
-  R. Nakamura, K. Sawada, S. Shin, K. Kumagai, and H. Yoneda, “Simultaneous Optimization of Dispatching and Routing for OHT Systems via Hybrid System Modeling,” the 39th Annual Conf. of the IEEE Industrial Electronics Society (IECON), 2013. (to appear)
-  T. M. Cavalier, P. M. Pardalos, and A. L. Soyster, “Modeling and integer programming techniques applied to propositional calculus,” Computer &Operations Research, Vol.17, No.2, pp. 561-570, 1990.
-  H. P. Williams, “Model building in mathematical programming,” 4th Ed., John Willey & Sons. Ltd, 1999.
-  http://www.mathworks.com/
-  http://www-01.ibm.com/software/integration/optimization/cplexoptimizer/