Faculty of Industrial Engineering, Iran University of Science and Technology, Tehran, Iran
Received date: March 20, 2014; Accepted date: May 26, 2014; Published date: June 08, 2014
Citation:Fazlollahtabar H and Saidi-Mehrabad M (2014) Delay Optimization in a Multiple AGV System. Int J Swarm Intel Evol Comput 3:109. doi:
Copyright: © 2014 Fazlollahtabar H, et al. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
Visit for more related articles at International Journal of Swarm Intelligence and Evolutionary Computation
The objective of this paper is to propose a scheduling problem for multiple automated guided vehicles (AGVs) in a manufacturing system. Considering the due date of AGVs requiring for material handling among shops in a job shop layout, their earliness and tardiness are significant in satisfying the expected cycle time and from an economic view point. Earliness results in AGVs waiting and tardiness causes temporary part storages in the shop floor. Therefore, we design an innovative stream to minimize the penalized earliness and tardiness.
Delay; Scheduling; Optimization; AGV
Flexible manufacturing systems (FMSs), container terminals, warehousing systems, and service industries including hospital transportations are employing automated guided vehicle systems (AGVs) for the material handling to maintain flexibility and efficiency of production and distribution. For the efficient operation, it is requested to realize the synchronized operations for the simultaneous scheduling of production systems and transportation systems. The main issue treated in this paper is the simultaneous optimization problems for penalized earliness and tardiness for the AGVs in the manufacturing system. The production scheduling problems asks an optimal production sequence and starting time of operations for jobs at machines for multi-stages with respect to a specified technical precedence relation. The vehicle management problems are classified into:
1. Dispatching, which is to assign tasks to vehicles?
2. Routing, which is to select specific paths taken by vehicles?
3. Scheduling, which is to determine the arrival and departure times?
Unlike the classical vehicle routing problem (VRP) formulation, conflict-free constraints should be considered for the routing of AGVs for semiconductor fabrication. The interaction between production and transportation control is discussed by Mantel and Landerweerd . In the flowshop production systems, the production and transportation schedules are usually controlled by a pull type of policy in case of fork lifts or conveyor systems. However, for FMSs environment with AGV systems, the optimal machine schedules highly depend on the selection of dispatching and routing because it is extremely difficult to predict the transportation time when the conflicts and interferences between vehicles cannot be neglected.
Automated guided vehicle (AGV) is a material handling equipment traveling on a network of guide paths. The FMS is a configuration of various shops, also called working stations, each with a specific function such as milling, washing, or assembly. Each shop is connected to the guide path network by a pick-up/delivery (P/D) station where pallets are transferred from/to the AGVs. Pallets of products are moved between the shops by the AGVs. The guide path is composed of aisle segments on which the vehicles are assumed to travel at a constant speed. The vehicles can travel forward or backward. As many vehicles travel on the guide path simultaneously, collisions must be avoided. AGV systems are implemented in various industrial contexts: container terminals, part transportation in heavy industry, flexible manufacturing systems [2-4]. For a recent review on AGVs scheduling and routing problems and issues, the reader is referred to the survey of Qiu et al. .
Therefore, the current study aims to introduce a delay optimization model for a manufacturing system so that the objectives of conflict-free and collision avoidance of multiple AGVs are regarded. Different routes exist in the shop floor and AGVs move through these paths to carry material and products. The part delivery and AGV’s waiting at the shops should be so that another AGV does not hit the previous one. Thus, an accurate scheduling plan should be elaborated for this purpose. An economic approach to handle this problem is penalized delay modeling. Delay is a combination of earliness and tardiness where both are considered as undesirable in scheduling. Therefore, a penalty is considered for each to prohibit their occurrences. This way an AGV should be at a shop in a suitable time period and move at once it does not hit another AGV in the next stage (at next shop). Early or tardy movements of AGV incur penalties to the model.
Scheduling problems arise in areas as diverse as production planning, personnel planning, product configuration, and transportation. An overview of the wide range of constraints in scheduling, together with the most powerful propagation algorithms for these constraints are given [6,7].
Production scheduling, dispatching, routing and scheduling decisions for AGVs can be made simultaneously or separately. Most of the literature treats one or two of the problems at the same time. An extensive review has been addressed by Vis  for operational control of AGVs. A widely used technique for dispatching is the simulation. The heuristic rules are used in on-line control systems. For routing and scheduling of AGVs, several techniques have been used to maximize the total system performance taking in to account for deadlock or conflicts for AGVs. Kim and Tanchoco  studied the problem of finding conflict-free routes in a bi-directional network. The algorithm is based on the shortest path methods through the concept of time-window graph. Petri net is used to analyze deadlock and conflict-free conditions [10,11]. Singh and Tiwari  presented an intelligent agent framework to find a conflict-free shortest-time path. Nishi et al.  provided a mathematical model for routing problem. Lagrangian decomposition technique was used solve the problem. Ghasemzadeh et al.  presented a conflict-free scheduling and routing in mesh topologies. It can generate the shortest path for scheduling predicting conflicts and select another path in the case of failure .
The literature discussed above on scheduling of AGVs hardly considers the capacity constraints of the machines where transportation jobs become available and sequencing of operations at the machines. The simultaneous production scheduling and transportation routing problem is one of the difficult joint problems. The problems for AGVs have been studied mostly in operations research and/or FMS literature. A common approach for FMS scheduling is based on the discrete event simulation with dispatching rules .
Lacomme et al.  introduced a branch and bound algorithm coupled with discrete event simulation. Blazewicz et al.  addressed the two steps algorithm for integrating machine scheduling and the conflict-free routing problems. In their approach, the production scheduling and routing problems are solved separately. Bilge and Ulusoy  developed a time-window approach to solve the simultaneous scheduling of machines and material handling in FMSs. They formulated the problem as a mixed integer programming problem. Ulusoy et al.  and Jerald et al.  dealt with the application of the genetic algorithm on the problem. Khayat et al.  studied an integrated method with mixed integer linear programming (MILP) and constrained programming. Never the less in their model, vehicles can always select a shortest path from a machine station to another machine station without the consideration of conflict and collision on the detailed routing for vehicles. Corre´a et al.  proposed an integrated scheduling of dispatching and vehicle routing with the consideration of conflict-free path selection, but it does not take into account the scheduling of machines and vehicles simultaneously .
In the above literature, it is extremely difficult to consider production scheduling and conflict-free routing because the number of decision variables is significantly increased. Therefore, the conventional decomposition algorithm is not sufficient to solve the problem efficiently. The integration of cut generation with various decomposition methods  is widely studied recently . The logic-based Benders decomposition method was introduced by Hooker . The advantage of the logic-based Benders is that it permits to combine MILP and the constraint programming approach. Similar idea was applied to solve the simultaneous planning and scheduling problems .
A number of authors have addressed the conflict free routing problem with a static transportation requests set, i.e., with all requests known a priori. Lee et al.  present a two-staged traffic control scheme to solve a conflict free routing problem. Their heuristic method consists of generating off-line k-shortest paths in the first stage before the on-line traffic controller picks a conflict free shortest path whenever a dispatch command for an AGV is issued (second stage). Rajotia et al.  propose a semi-dynamic time window constrained routing strategy. They use the notions of reserved and free time windows to manage the motion of vehicles. Krishnamurthy et al.  propose an optimization approach. Their objective is to minimize the makespan. They assume that the assignment of tasks to AGVs is given and they solve the routing problem by column generation. Their method generates very good solutions in spite of the fact that it is not optimal (column generation is performed at the root node of the search tree only) .
Oboth et al.  present a heuristic method to solve the dispatching and routing problems but not simultaneously. Scheduling is performed first and a sequential path generation heuristic (SPG) is used to generate conflict free routes. The SPG is inspired from Krishnamurthy et al. (1993) static version of the AGV routing problem and applied to a dynamic environment while relaxing some of the limiting assumptions like equal and constant speeds of AGVs. When conflict is encountered, no feedback is sent to the scheduling module. The AGV being routed has to be delayed if an alternate route cannot be generated. The authors use rules for positioning idle AGVs instead of letting the system manage those .
Langevin et al.  propose a dynamic programming based method to solve exactly instances with two vehicles. They solve the combined problem of dispatching and conflict free routing. Desaulniers et al.  propose an exact method that enables to solve instances with up to four vehicles. Their approach combines a greedy search heuristic (to find a feasible solution and set bound on delays), column generation and a branch and cut procedure. Their method presents however some limits since its efficiency depends highly on the performance of the starting heuristic. If no feasible solution is found by the search heuristic, then no optimal solution can be found. The search heuristic performs poorly when the level of congestion increases .
Consider a job shop manufacturing system with multiple AGVs performing material handling. There is a number of AGVs pre-specified for material handling. The AGVs guide paths may be occupied in the time that an AGV is sent to do the material handling. Therefore, finding the free path to fulfill the function is important. The manufacturing process plan of all jobs processing time is cleared. If an AGV arrives early, it should waits until the part processing is finished. The waiting time is related to the distance the AGV moves and the due date of jobs in shops. The overall problem is to determine the manufacturing schedule and routing for AGVs to minimize the total penalized earliness/tardiness and AGVs’ waiting times at the shops in job shop configuration. The following assumptions are considered for modeling the proposed problem.
The number of jobs, processing time for each job and the number of AGVs are given.
The started job cannot be interrupted once the processing of that is started at a shop.
Each AGV can transport a single load at a time. A transportation task is the set of a starting node and a destination node.
The overall decision variables for the problem consist of the allocation of AGVs to the shops for material handling and the conflict-free routing for vehicles. To estimate the time of traveling from one shop (node) to another in our proposed network, a mathematical relation is employed. While the velocity (v) of AGV is known, the time is computed by, d = v.t, where d is the movement distance, v is AGV velocity and t is the time of movement, due to a Cartesian coordinates structure as shown in Figure 1.
To compute the distance, we use rectilinear formulae, d=|x-x0|+|y-y0|, where x is the horizontal movement and y is the vertical movement. As a result, we have, t=d/v. Therefore, AGV movement time is computed.
Earliness/tardiness optimization in job scheduling for modern manufacturing systems is of rising trend in research and development. In future, due to competitive marked and mass demand the on time delivery toward just in time concept is vital. Due to complexities in modeling and solution heuristic algorithms should be developed for optimization purpose.
In this work, the automated guided vehicle scheduling problem was considered as a special case of the earliness/tardiness minimization. In the proposed problem the number of jobs, processing time for each job and the number of AGVs were assumed to be given. Also, the started job couldn't be interrupted once the processing of that was started at a shop, and each AGV could transport a single load at a time. Besides scheduling, the model was able to fulfill the conflict free routs for the AGVs. The solution should provide the optimal paths for each AGV and prohibit the conflict among AGVs minimizing the total earliness and tardiness.