A neural algorithm for finding the shortest flow path for an automated guided vehicle system

The automated guided vehicle (AGV)system is emerging as the dominant technology to maximize the flexibility of material handling, while increasing the overall productivity of manufacturing operations. This paper presents a new way of finding the shortest flow path for an AGV system on a specific routing structure. An optimal solution of the system is determined by using an approach based on the Hopfield neural network with the simulated annealing (SA) procedure. In other words, the proposed approach reduces the total cost of an AGV delivery path from one workstation to another on the shop floor. By changing the temperature of the two-stage SA, a solution can be found that avoids potential collisions between AGVs. Both the flow path and the potential collision, which are major problems in AGV systems, may be solved simultaneously by the proposed neural network approach. Other advantages offered by the proposed method are its simplicity compared with operations research (OR)methods and a decreased number of needed AGVs. The performance of the approach is also investigated.     

Scheduling and routing algorithms for AGVs: A survey

Automated guided vehicles (AGVs) are now becoming popular in automated materials handling systems, flexible manufacturing systems and even container handling applications. In the past few decades, much research has been devoted to the technology of AGV systems and rapid progress has been witnessed. As one of the enabling technologies, scheduling and routing of AGVs have attracted considerable attention. Many algorithms for the scheduling and routing of AGVs have been proposed. However, most of the existing results are applicable to systems with a small number of AGVs, offering a low degree of concurrency. With a drastically increased number of AGVs in recent applications (e.g. in the order of a hundred in a container handling system), efficient algorithms are needed to resolve the increased contention of resources (e.g. path, loading and unloading buffers) among AGVs. This survey paper first gives an account of the emergence of the problem of AGV scheduling and routing. It then differentiates it from several related problems and classifies major existing algorithms for the problem. Finally, the paper points out fertile areas for future study of AGV scheduling and routing.     

Route planning for automated guided vehicles in a manufacturing facility

Automated guided vehicles (AGVs) are widely used in manufacturing and transporting facilities for the movement of material from one location to another. Research in this area is directed toward the development of a path layout design and routing algorithms for movements of materials. The problem is to design a path layout and a routing algorithm that will route the AGVs along the bi-directional path so that the distance travelled will be minimized. This paper presents a bi-directional path flow layout and a routing algorithm that guarantee conflict-free, shortest-time routes for AGVs. Based on the path layout, a routing algorithm and sufficient, but necessary, conditions, mathematical relationships are developed among certain key parameters of vehicle and path. A high degree of concurrency is achieved in vehicle movement. Routing efficiency is analysed in terms of the distance travelled and the time required for AGVs to complete all pickup and drop-off jobs. Numerical results are presented to compare the performance of the proposed model. The research provides the foundation for a bi-directional path layout design and routing algorithms that will aid the designer to develop complicated path layouts.     

Optimal dwell point location of automated guided vehicles to minimize mean response time in a loop layout

An important control issue in operating an automated guided vehicle system is where to locate idle vehicles. Dwell points for idle vehicles affect the performance of manufacturing systems. A polynomial time algorithm has been developed to determine dwell points for idle automated guided vehicles that minimize the mean response time. Both uni- and bidirectional loop layouts are considered. The proposed algorithm, based on a dynamic programming model, partitions the set of pick-up stations into subsets so that a single vehicle serves all stations in a subset. The dynamic programming algorithm has been streamlined by applying certain optimality properties. Computational results show that the proposed algorithm can solve large-scale problems in a reasonable time. A simulation experiment has also been conducted to compare several idle vehicle positioning rules, and the results show that best performance is obtained by positioning idle vehicles in dwell points that minimize the mean response time.     

Book review of Global Strategic Management,by P. Lasserre,Palgrave Macmillan,Basingstoke, 2003, xx + 454 pp., £24.99, softcover (ISBN 0 333 79375 7)

This paper considers the simultaneous scheduling of material handling transporters (such as automatic guided vehicles or AGVs) and manufacturing equipment (such as machines and workcentres) in the production of complex asembled product. Given the shipping schedule for the end-items, the objective of the integrated problem is to minimize the cumulative lead time of the overall production schedule (i.e. total makespan) for on-time shipment, and to reduce material handling and inventory holding costs on the shop-floor. The problem of makespan minimization is formulated as a transportation integrated scheduling problem, which is NP-hard. For industrial size problems, an effective heuritsic is developed to simultaneouly schedule manufacturing and material handling operations by exploting the critical path of an integrated operation network. The performance of the proposed heuristic is evaluated via extensive numerical studies and compared with the traditional sequential scheduling approach. The superiority of the integrated heuristic is well documented.     

A multi-attribute dispatching rule for automated guided vehicle systems

This paper considers the dispatching problem associated with operations of automated guided vehicles (AGVs). A multi-attribute dispatching rule for dispatching of an AGV is developed and evaluated. The multi-attribute rule, using the additive weighting method, considers three system attributes concurrently: the remaining space in the outgoing buffer of a workstation, the distance between an idle AGV and a workstation with a job waiting for the vehicle to be serviced, and the remaining space in the input buffer of the destination workstation of a job. A neural network approach is used to obtain dynamically adjusting attribute weights based on the current status of the manufacturing system. Simulation analysis of a job shop is used to compare the multi-attribute dispatching rule with dynamically adjusting attribute weights to the same dispatching rule with fixed attribute weights and to several single attribute rules. Results show that the multi-attribute dispatching rule with the ability to adapt attribute weights to job shop operational conditions provides a better balance among the performance measures used in the study.     

Selection of circulatory loops for patrol vehicles operating in a network

Many applications exist in which a vehicle or set of vehicles have the responsibility of patrolling and providing coverage over a wide area or network for the purpose of responding quickly to service requests generated randomly at demand points in the network. One of the decisions in the operation of such patrol vehicles is that of determining the home location or circulatory loop for free or idle vehicles. A vehicle is said to be idle if it is not responding or attending to a service request. Such home location can be a point, a set of points in a network, a circulatory loop, or a set of circulatory loops in the network. The actual number of home locations is system, fleet size, and analyst dependent. Whether a point or loop strategy is implemented, the specification of the home locations or loops is usually done with the objective of improving the response time of idle vehicles to service requests originating from demand stations. In cases where circulatory loop strategy is adopted, the problem is one of determining the best overall circulatory loop or loops that would improve the overall system response time. In a typical conventional or generalized network, several loops may exist. Unless a systematic procedure is developed, non-optimal loops could be selected. In this paper, methodologies for determining the best circulatory loops for patrol vehicles for a given problem scenario in both unidirectional and bidirectional networks are presented. The problem is modelled as a mathematical programming problem. Example problems are given to illustrate the application of the approach. The criterion for optimization is the minimization of the maximum system response time.     

Deadlock prevention for automated guided vehicles in automated container terminals

Automated guided vehicles (AGVs) are an important component for automating container terminals. When utilizing AGVs to transport containers from one position to another in a container terminal, deadlocks are a serious problem that must be solved before real operations can take place. This study assumes that the traveling area for AGVs is divided into a large number of grid-blocks, and, as a method of traffic control, grid-blocks are reserved in advance when AGVs are running. The first purpose of the reservation is to make room between AGVs and to prevent deadlocks. The objective of this study is to develop an efficient deadlock prediction and prevention algorithm for AGV systems in automated container terminals. Because the size of an AGV is much larger than the size of a grid-block on a guide path, this study assumes that an AGV may occupy more than one grid-block at a time. This study proposes a method for reserving grid-blocks in advance to prevent deadlocks. A graphical representation method is suggested for a reservation schedule and a priority table is suggested to maintain priority consistency among grid-blocks. It is shown that the priority consistency guarantees deadlock-free reservation schedules for AGVs to cross the same area at the same time. The proposed method was tested in a simulation study.     

A bi-directional path layout for conflict-free routing of AGVs

Automated Guided Vehicles (or AGVs for short) are now widely used in automated material handling systems. Much research has been done on developing path layout and algorithms for the optimal routing and scheduling of AGVs. However, with the drastically increased number of AGVs in some recent applications (e.g. in the order of a hundred in container terminals), algorithms that can achieve a high degree of concurrency of AGV moves are urgently needed. This paper presents a bi-directional path layout and an algorithm for routing AGVs. To route the vehicles without conflicts and to minimize the space requirement of the layout, critical conditions for certain key parameters of the path and vehicle are derived. We further show theoretically that a high degree of concurrency of AGV moves can be achieved, although the routing decision takes only a constant amount of time for each vehicle. The routing efficiency is analysed in terms of the distance traversed and the time requirement for AGVs to complete all pickup and drop-off (or P/D for short) jobs. Results of this study could form a basis for more complicated path layouts and routing algorithms.     

Guide path design and location of load pick-up/drop-off points for an automated guided vehicle system

The guide path layout for an automated guided vehicle system (AGVS) is a critical component in the overall design of a flexible manufacturing system (FMS) that utilizes AGVs for materials handling. Not only does it affect the total distance travelled by the vehicles but it also affects vehicle requirements and space utilization. In this study, the problem of selecting the guide path as well as the location of pick-up and drop-off points for outward and inward bound parts to departments is addressed. The problem is modelled and solved as a linear integer program with the objective of minimizing the total distance travelled.     

Operational control of a bidirectional automated guided vehicle system

Bidirectional AGV systems are intuitively more attractive than unidirectional systems in terms of efficiency because of shorter travel distances. An efficient algorithm for finding conflict-free shortest-time routes for automated guided vehicles moving in a bidirectional flow path network has been proposed in a previous paper. This paper is a sequel and describes a conservative myopic strategy to coordinate the movements of vehicles in a bidirectional AGV system. Simulation results are presented to compare the performances of unidirectional and bidirectional systems.     

A machine-to-loop assignment and layout design methodology for tandem AGV systems with multiple-load vehicles

In this paper, we propose a design methodology for tandem Automated Guided Vehicle (AGV) systems with multiple-load vehicles. Our goal is to devise a design methodology that can achieve the following objectives in multiple-load tandem AGV designs. The first objective is to achieve the workload-balance between vehicles of different loops. The second objective is to minimize the inter-loop flow. The final objective is to minimize the flow distance. To achieve these objectives, the following problems are studied. First, we conduct simulations to study the relationship between a vehicle's load-carrying capacity and work capacity. This relationship is then considered in the second problem, i.e. the problem of determining the machine content of each loop. A two-stage machine-to-loop assignment method is proposed for solving this problem. At the first stage, an initial machine-to-loop assignment is generated. This initial assignment is then improved at the second stage using Simulated Annealing (SA). The third problem is the problem of determining the layout of machines in each loop. A flow-line design method and SA are adopted for solving this problem. The fourth problem is the layout problem of guide-path loops. To solve this problem, a famous layout method found in the literature is adopted. The last problem includes the problem of determining the best orientation of each loop and the problem of finding the best places to set up transfer stations between adjacent loops. A mathematical programming model that can solve them simultaneously is proposed. Simulations are then conducted to verify the design, and to show that the proposed design methodology is indeed capable of producing good and satisfactory tandem AGV designs with multiple-load AGVs. Finally, it is our hope that the knowledge learned from this study can help us have a better understanding of multiple-load AGV systems and allow us to have successful implementations of similar systems in practice.     

Load selection of automated guided vehicles in flexible manufacturing systems

This paper examines the operation of multiple-load AGVs in a flexible manufacturing system where AGVs in the system are capable of carrying two or more loads. The load selection problem arises when an AGV stops at a pick-up queue and has to decide which part(s) should be picked up. Five heuristic rules that may be used to select the load to be carried were suggested and evaluated under a hypothetical flexible manufacturing system with the aid of computer simulation. The results revealed that the variable-route-part-priority (VP) rule and fixed-route-part-priority (FP) rule generated significantly higher throughput than their counterparts, while the ’pick-all-send-nearest’ (PN) rule outperformed the other rules in part flowtime and work-in-process level. The results also suggest that when the carrying capacity of the AGV increases, the performance differences among the rules also increase. This finding sustains the need to explore an efficient operation strategy of multiple-load AGVs in flexible manufacturing systems.     

The value of the shortest loop covering all work centers in a manufacturing facility layout

In this study we develop mathematical models to design circular material flow systems. We first develop a tight formulation to find the shortest loop covering all work centers within a manufacturing facility layout. The shortest loop is an attractive solution for most types of conveyors and power-and-free systems, where the length of the flow path is the major driver of the total cost. We develop a primal as well as a dual graph formulation and discuss their one-to-one correspondence in node-edge as well as in connectivity constraints. Our solution times outperform other optimization models available for the facility layout shortest loop design problem. We then approach trip-based material handling, such as automated guided vehicle systems, where the total loaded and empty trip distance is the major driver of the total cost. The problem in these systems evolves into concurrent design of the loop, pickup and dropoff station, and the empty vehicle dispatching policies. On the foundation of the shortest loop model, we propose a decomposition heuristic for design of trip-based flow systems. Computational results indicate that the heuristic provides high quality and robust solutions.     

Dispatching multi-load AGVs in highly automated seaport container terminals

This paper is concerned with AGV dispatching in seaport container terminals. Special attention is given to multi-load vehicles which can carry more than one container at a time. The characteristics of this complex application environment and the impact on the AGV dispatching problem are analyzed and various solution techniques considered. For practical application within an online logistics control system, a flexible priority rule based approach is developed, making use of an extended concept of the availability of vehicles. For evaluation reasons, this approach is complemented by an alternative MILP formulation. Finally, the performance of the priority rule based approach and the MILP model are analysed for different scenarios with respect to total lateness of the AGVs. The main focus of the numerical investigation is on evaluating the priority rule based approach for single and dual-load vehicles as well as comparing its performance against the MILP modelling approach.     

Flow path design for automated guided vehicle systems

An important factor in the design of automated guided vehicle systems (AGVS) is the flow path design. This paper presents an approach to determining the optimal flow path. The objective is to find the flow path which will minimize total travel of loaded vehicles. The problem is formulated as a zero-one integer program. Examples are presented to demonstrate the approach.     

Solution methods for the mathematical models of single-loop AGV systems

Guide path simplification can potentially reduce the complexity inherent in conventional, multi-loop automated guided vehicle systems (AGVs). A single-loop configuration is one alternative. A procedure for designing single-loop AGV systems, the OSL method was presented in a previous paper. In this paper, we suggest faster and more efficient methods for solving the two mathematical models in the OSL procedure. The first model called the valid single-loop problem (VSLP) is used to determine an initial single loop for the procedure. The method suggested is a heuristic procedure that starts from a loop around one of the departments and keeps adding departments to the loop until a valid single loop is constructed. The second model called the single-loop station location problem (SLSLP) is used to determine the location of the pick-up and delivery stations along a given loop. The method suggested converts the mixed integer formulation into a linear formulation.     

The formation of subfamilies for machine loading of flow-line cells

Cellular manufacturing constitutes a key element of contemporary approaches to manufacturing such as just-in-time and flexible manufacturing systems. In some settings, it may not be possible to release all members of a family to a cell at the same time due to tooling, level of the in-process inventory and limited machine buffer capacity constraints. When such constraints exist, one approach is to partition each family into subfamilies.

In this research, we consider the effective partitioning of a family of parts into subfamilies in cyclically scheduled cells involving unidirectional material flow between machines laid out in a loop and where capacity constraints on tooling are present. The criterion for forming subfamilies is the minimization of the total machine idle time. This criterion maximizes the rate of output of the cell as well as maximizing machine utilization. A batching approach to part and tool change is utilized and all tool magazine set-ups are assumed lo occur off-line while the cell is in operation.

We present a model for the formation of subfamilies using the above criterion and develop four heuristic approaches based on it. We then examine their effectiveness by conducting computational experiments over a wide range of realistic situations generated by varying the characteristics of the operating environment, tooling requirements and tool magazine capacity.     

Optimally Locating Multiple Dwell Points in a Single Loop Guide Path System

Dwell points for idle vehicles affect the performance of automated guided vehicle systems. An exact polynomial-time algorithm to solve idle vehicle positioning problems in both unidirectional and bidirectional single loop systems is developed to minimize the maximum response time. The proposed algorithm considers several potential locations for the first dwell point and applies a dynamic programming procedure to obtain the remaining dwell points for each initial location. The algorithm is streamlined by applying certain optimality properties. Computational results show that the algorithm can solve large-scale problems in reasonable time.     

Reliability assessment for a stochastic manufacturing system with reworking actions

This article evaluates the system reliability of a manufacturing system with reworking actions, where the system reliability is an essential indicator to determine whether the manufacturing system is capable or not. Based on the path concept, we transformed the manufacturing system into a stochastic-flow network in which the capacity of each machine is stochastic (i.e., multistate) due to failure, partial failure, and maintenance. In such a manufacturing network, the input flow (raw materials/WIP; work-in-process) processed by each machine might be defective and thus the output flow (WIP/products) would be less than the input amount. To analyze the different sources processed by the manufacturing network, we decomposed the network into one general processing path and several reworking paths by a graphical technique. Subsequently, an algorithm for the manufacturing network was proposed to generate the lower boundary vector which allows sufficient products to satisfy the demand. In terms of such a vector, the system reliability can be derived easily.