A Job Shop Scheduling and Location of Battery Charging Storage for the Automated Guided Vehicles (AGVs)

Document Type : Original Manuscript


1 Department of Industrial Engineering, Yazd University, Yazd, Iran

2 Department of Management, Naragh Branch, Islamic Azad University, Naragh, Iran

3 Department of Industrial engineering, Iran University of Science and Technology, Tehran, Iran



When the Automated Guided Vehicles (AGVs) are transferring the parts from one machine to another in a job shop environment, it is possible that AGVsstopon their guidepaths since their batteries are discharged.Consequently, it is essential to establish at least one Battery Charging Storage (BCS) to replace full batteries with empty batteries for the stopped AGVs. Due to non-predictable routes for AGVs in the manufacturing systems, to find the best place toestablish the BCS can impact performance of the system. In this paper, anintegrated mathematical modelof job shop and AGV schedulingwith respect tothe location of a BCS is proposed. The proposed nonlinear model is transformed into a linear form to beefficiently solvedin GAMS software. Finally, several numerical examplesare presented to test the validity of the proposed mathematical model.The results show that the optimal cost and location of BCS can be obtained with respect to the number of AGVs, machines, parts, and other problem parameters. In addition, it is concluded that the increasing number of AGVs in a manufacturing systemcannot be always a suitable policy for reducing the cost because in such conditions.Further to that, the conflict of AGVs may increase leading tothe increase of the makespan. In other words, following the optimal point, increasing AGVs leads to the increase in costs.

Graphical Abstract

A Job Shop Scheduling and Location of Battery Charging Storage for the Automated Guided Vehicles (AGVs)


  • A Job Shop environment where AGVs are responsible to transfer the jobs between consideredmachines.
  • A nonlinear model to model the scheduling and location of BCS is developed.
  • The nonlinear model is transmitted to a linear model.
  • A computational experiment has been made to verify the model.


Main Subjects

Asef-Vaziri, A., Gilbert L., and Robert O. (2007). Exact and Heuristic Procedures for the Material Handling Circular Flow Path Design Problem. European Journal of Operational Research 176(2): 707–26.
Corréa, A.I., André L., and Louis M.R. (2007). Scheduling and Routing of Automated Guided Vehicles: A Hybrid Approach. Computers and Operations Research 34(6) 8.
Digani, V., Lorenzo S., Cristian S., and Cesare F.(2014). Hierarchical Traffic Control for Partially Decentralized Coordination of Multi Agv Systems in Industrial Environments. In Robotics and Automation (ICRA), 2014 IEEE International Conference on, IEEE, 6144–49.
Ebben, M.(2001). Logistic control in automated transportation networks. Beta Ph.D. thesis series D-40, Twente University Press, Enschede, The Netherlands.
ElMekkawy, T. Y., and S. Liu. (2009). A New Memetic Algorithm for Optimizing the Partitioning Problem of Tandem AGV Systems. International Journal of Production Economics 118(2): 508–20.
Glover, F., Woolsey, L. (1974). Converting the 0–1 polynomial programming problem to a 0–1 linear program. Oper Res,22:180–182
Ho, Ying-Chin, and Ping-Fong Hsieh. (2004). A Machine-to-Loop Assignment and Layout Design Methodology for Tandem AGV Systems with Multiple-Load Vehicles. International Journal of Production Research 42(4): 801–32.
Jun-jie, Z. (2007). Design of AGV battery monitoring system with smart battery monitoring chip. Hoisting and Conveying Machinery2, 4.
Kawakami, T., Takata, S. (2012). Battery Life Cycle Management for Automatic Guided Vehicle Systems. Design for Innovative Value Towards a Sustainable Society403-408.
Lee, J.H, Beom H.L, and Myoung H.C. (1998). A Real-Time Traffic Control Scheme of Multiple AGV Systems for Collision Free Minimum Time Motion: A Routing Table Approach. IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans 28(3): 347–58.
McHaney, R.(1995). Modeling battery constraints in discreteevent automated guided vehicle systems. International Journal of Production Research 33 (11), 3023–3040.
Pinlam, W., Mooghdaharn, C., Bupparit, Y. (2002). Automatic battery recharging station for AGVs. Advanced Micro Devices.
Qiu, L, Wen-Jing H., Shell-Ying H., and Han W. (2002). Scheduling and Routing Algorithms for AGVs: A Survey.” International Journal of Production Research 40(3)
Saidi-Mehrabad, M., Dehnavi-Arani., S., Evazabadian, F., and Mahmoodian, V. (2015). An Ant Colony Algorithm (ACA) for solving the new integrated model of job shop scheduling and conflict-free routing of AGVs. Computers and Industrial Engineering 86, 2-13.
Ventura, José A, and Brian Q.R. (2009). Optimal Location of Dwell Points in a Single Loop AGV System with Time Restrictions on Vehicle Availability. European Journal of Operational Research 192(1): 93–104.
Vis, I. (2006). Survey of research in the design and control of automated guided vehicle systems. European Journal of Operational Research, 170(3), 677–709.
Weyns, D., Nelis B., and Tom H. (2006). Gradient Field-Based Task Assignment in an Agv Transportation System. In Proceedings of the Fifth International Joint Conference on Autonomous Agents and Multiagent Systems, ACM, 842–49.