A general framework for scheduling equipment and manpower at container terminals

In this paper, we propose a general model for various scheduling problems that occur in container terminal logistics. The scheduling model consists of the assignment of jobs to resources and the temporal arrangement of the jobs subject to precedence constraints and sequence-dependent setup times. We demonstrate how the model can be applied to solve several different real-world problems from container terminals in the port of Hamburg (Germany). We consider scheduling problems for straddle carriers, automated guided vehicles (AGVs), stacking cranes, and workers who handle reefer containers. Subsequently, we discuss priority rule based heuristics as well as a genetic algorithm for the general model. Based on a tailored generator for experimental data, we examine the performance of the heuristics in a computational study. We obtain promising results that suggest that the genetic algorithm is well suited for application in practice.     

Deadlock handling for real-time control of AGVs at automated container terminals

In automated container terminals, situations occur where quay cranes, stacking cranes, and automated guided vehicles (AGVs), directly or indirectly request each other to start a specific process. Hence, all of the affected resources are blocked, possibly leading to the complete deadlock of individual cranes or AGVs. Particularly, AGVs are liable to deadlocks because they always need a secondary resource, either a quay crane or a stacking crane, to perform the pick-up and drop-off operations. Because usually no buffering of containers takes place at the interfaces between AGVs and cranes, the consequences of deadlocks are rather severe. Two different methods for the detection of deadlocks are presented. One is based on a matrix representation of the terminal system. The other directly traces the requests for the individual resources. To resolve deadlock situations arising in an automated container terminal, three different procedures are proposed. These procedures aim to modify the sequence of handling operations or to assign them to alternative resources so that conflicts between concurrent processes are resolved. The suitability of the concept is demonstrated in an extensive simulation study.     

Real-time scheduling for twin RMGs in an automated container yard

This paper proposes heuristic-based and local-search-based real-time scheduling methods for twin rail-mounted gantry (RMG) cranes working in a block at an automated container terminal. The methods reschedule the cranes in real time for a given fixed-length look-ahead horizon whenever an RMG finishes a job. One difficulty with this problem is that sometimes additional rehandling of containers needs to be carried out in order to complete a requested job, especially when other containers are stacked on top of the target container. These rehandlings are the main cause of the delay of the crane operations, leading to extended waiting of automated guided vehicles (AGVs) or external trucks that co-work with the cranes. By treating the rehandling operations as independent jobs in our solution methods, we can greatly facilitate the cooperation between the two RMGs. Through this cooperation, the workload of the two RMGs can be better balanced and interference can be more easily avoided, thereby maximizing crane utilization. Simulation experiments show that the waiting times of AGVs and external trucks are significantly reduced due to the increased utilization through cooperation.     

Comparison of vehicle types at an automated container terminal

At automated container terminals, containers are transshipped from one mode of transportation to another. Automated vehicles transport containers from the stack to the ship and vice versa. Two different types of automated vehicles are studied in this paper, namely automated lifting vehicles and automated guided vehicles. An automated lifting vehicle is capable of lifting a container from the ground by itself. An automated guided vehicles needs a crane to receive and deliver a container.In designing automated container terminals one have to consider the choice for a certain type of equipment. The choice for a certain type of equipment should be made by performing a feasibility and economic analysis on various types of equipment. In this paper, we examine effects of using automated guided vehicles and automated lifting vehicles on unloading times of a ship, with simulation studies. In choosing a certain type of equipment we have considered criteria such as unloading times of a ship, occupancy degrees and the number of vehicles required. 38% more AGVs need to be used than ALVs. From this specific study, we conclude that, by observing only purchasing costs of equipment, ALVs are a cheaper option than AGVs.To obtain an accurate analysis we have performed a sensitivity analysis. It can be concluded that the design of the terminal and technical aspects of quay cranes impact the number of vehicles required and as a result the choice for a certain type of equipment. Correspondence to: Iris F. A. Vis     

基于路段时间窗考虑备选路径的AGV路径规划

针对自动化集装箱码头基于卸箱任务的自动导引车（automated guided vehicle,AGV）路径规划问题,结合最优路径数学模型、路径搜索方法和时间窗,提出了一种基于路段时间窗的AGV路径规划方法。首先,在给AGV下派任务的基础上,用最优路径数学模型为AGV规划出最短路径;其次,用路径搜索方法搜索AGV的备选路径,在路径长度相同的情况下,按照路径中转折次数确定备选路径优先级,转折次数少的备选路径优先级高;最后,在各AGV最短路径下,设置各个路段的时间窗,时间窗无重叠则表明AGV无冲突,对于时间窗重叠的路段,采用在原路径上插入时间窗或者在备选路径上插入时间窗的方法,再进行时间窗重叠测试,若还存在重叠的,则继续调整至最终实现多AGV的无冲突路径规划。为了验证方法的有效性,以8台AGV分区同时工作为例,用实例证明所提出的路径规划方法的避碰效果。结果显示该方法能为多台同时工作的AGV规划出一条无冲突优化路径,并且用时较短;在试验中发现选择在备选路径上插入时间窗的方法效果更好。研究表明所提方法能有效实现AGV的避碰,提高AGV利用率和自动化集装箱码头的运作效率。     

Strategies for dispatching AGVs at automated seaport container terminals

Control of logistics operations at container terminals is an extremely complex task, especially if automated guided vehicles (AGVs) are employed. In AGV dispatching, the stochastic nature of the handling systems must be taken into account. For instance, handling times of quay and stacking cranes as well as release times of transportation orders are not exactly known in advance. We present a simulation study of AGV dispatching strategies in a seaport container terminal, where AGVs can be used in single or dual-carrier mode. The latter allows transporting two small-sized (20 ft) or one large-sized (40 ft) container at a time, while in single-mode only one container is loaded onto the AGV irrespective of the size of the container. In our investigation, a typical on-line dispatching strategy adopted from flexible manufacturing systems is compared with a more sophisticated, pattern-based off-line heuristic. The performance of the dispatching strategies is evaluated using a scalable simulation model. The design of the experimental study reflects conditions which are typical of a real automated terminal environment. Major experimental factors are the size of the terminal and the degree of stochastic variations. Results of the simulation study reveal that the pattern-based off-line heuristic proposed by the authors clearly outperforms its on-line counterpart. For the most realistic scenario investigated, a deviation from a lower bound of less than 5% is achieved when the dual-load capability of the AGVs is utilized.     

Determination of unit load sizes in an AGV-based material handling system for an FMS

Unit load size is a key factor in an automated guided vehicle based material handling system for a flexible manufacturing system. Highlighting this aspect and its importance at the design stage, this paper presents an integer programming formulation of the problem of finding the optimal unit load size. Using an existing analytical model to decide the number of AGVs required, an algorithm based on branching and implicit enumeration and a heuristic have been developed. Revised computations due to dynamic system conditions such as changes in part mix are also possible with the proposed algorithms. The methodologies have been demonstrated using numerical examples.     

Scheduling of machines and automated guided vehicles in FMS using differential evolution

This paper addresses the problem of simultaneous scheduling of machines and two identical automated guided vehicles (AGVs) in a flexible manufacturing system (FMS). For solving this problem, a new meta-heuristic differential evolution (DE) algorithm is proposed. The problem consists of two interrelated problems, scheduling of machines and scheduling of AGVs. A simultaneous scheduling of these, in order to minimise the makespan will result in a FMS being able to complete all the jobs assigned to it at the earliest time possible, thus saving resources. An increase in the performance of the FMS under consideration would be expected as a result of making the scheduling of AGVs as an integral part of the overall scheduling activity. The algorithm is tested by using problems generated by various researchers and the makespan obtained by the algorithm is compared with that obtained by other researchers and analysed.     

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.     

An effective heuristic for scheduling a yard crane to handle jobs with different ready times

In land-constrained port container terminals, yard cranes are commonly used for handling containers in a container yard to load containers onto or unload containers from trucks. However, yard cranes are bulky, slow and need to move frequently between their work locations. As it is common that the container flow in a terminal is bottlenecked by yard crane operations, effective work schedules of yard cranes are needed to increase the terminal’s throughput. This article studies the problem of scheduling a yard crane to perform a given set of container handling jobs with different ready times. The objective is to minimize the sum of job waiting times. It is noted that the scheduling problem is NP-complete. This research develops a heuristic to solve the scheduling problem and an algorithm to find lower bounds for benchmarking the schedules found by the heuristic. The performance of the heuristic is evaluated by a set of test problems generated on the basis of real-life terminal operations data. Indeed, the computational results show that the proposed heuristic can find effective solutions for the scheduling problem.     

Productivity improvement through a sequencing generalised assignment in an assembly line system

This paper considers the assignment of heterogeneous workers to workstations of an assembly line in order to minimise the total production time. As the structure of the system implies that each of the workstations needs at least one worker, thus the problem can be considered as a generalised assignment problem (GAP). The objective is to perform an efficient human resource planning for a specified horizon consisting of several periods. Hence, we present an extension of the generalised assignment problem, consisting of a set of GAPs (one for each planning period) in which each GAP depends on the previous ones. A mixed integer mathematical model is presented for this sequencing assignment problem. The model is solved by an exact algorithm using Gurobi solver. It is proved that the problem is NP-hard and solving the medium and large size instances is not possible by the exact algorithms. Hence, two matheuristic approaches based on the disaggregated formulation of GAP are proposed. The first approach solves the problem through two sub-problems as the transportation formulation and assignment formulation. The second approach solves the problem by decomposition of the problem into several classical GAPs. The approaches are examined by a total of 27 instances. The results illustrate the efficiency of the proposed algorithms in the computational time and accuracy of the solutions.     

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.     

Rescheduling with controllable processing times for number of disrupted jobs and manufacturing cost objectives

We consider a machine rescheduling problem that arises when a disruption such as machine breakdown occurs to a given schedule. Machine unavailability due to a breakdown requires repairing the schedule as the original schedule becomes infeasible. When repairing a disrupted schedule a desirable goal is to complete each disrupted job on time, i.e. not later than the planned completion time in the original schedule. We consider the case where processing times of jobs are controllable and compressing the processing time of a job requires extra processing cost. Usually, there exists a nonlinear relation between the processing time and manufacturing cost. We solve a bicriteria rescheduling problem that trades off the number of on-time jobs and manufacturing cost objectives. We give a mixed-integer second-order cone programming formulation for the problem. We develop a heuristic search algorithm to generate efficient solutions for the problem. Heuristic algorithm searches solution space by moving and swapping jobs among machines. We develop cost change estimates for job moves and swaps so that the heuristic implements only promising moves and hence generates a set of efficient solutions in reasonably short CPU times.     

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.     

Due date assignment in single machine with stochastic processing times

This paper considers two different due date assignment and sequencing problems in single machine where the processing times of jobs are random variables. The first problem is to minimise the maximum due date so that all jobs are stochastically on time. It is shown that sequencing the jobs in decreasing service level (DSL) order optimally solves the problem. The results are then extended for two special cases of flow shop problem. The other problem is to minimise a total cost function which is a linear combination of three penalties: penalty on job earliness, penalty on job tardiness, and penalty associated with long due date assignment. The assignment of a common due date and distinct due dates are investigated for this problem. It is shown that the optimal sequence for the case of common due date is V-shaped.     

Heuristic,storage space minimization methods for facility layouts served by looped AGV systems

An analytical method for predicting work-in-process storage requirements resulting from a fixed number of looping, automated guided vehicles (AGVs) serving a line layout is described. The method is based on a model of storage queue dynamics that predicts material flow rates and vehicle response times resulting from vehicle dispatching within a single loop system. The method is applied in the development of two heuristic, random number driven procedures designed to perform sequential search for WIP storage minimizing line layouts over alternative AGV fleet sizes. The first algorithm is a greedy, ‘CRAFT like’ procedure based on local improvement in storage requirements using random, pairwise exchanges of workcentre locations. The second algorithm is a modification to the greedy procedure using simulated annealing methods designed to avoid trapping at local minima. Limited computational studies using the methods are reported.     

Optimization Models for Scheduling of Jobs

This work is motivated by a particular scheduling problem that is faced by logistics centers that perform aircraft maintenance and modification. Here we concentrate on a single facility (hangar) which is equipped with several work stations (bays). Specifically, a number of jobs have already been scheduled for processing at the facility; the starting times, durations, and work station assignments for these jobs are assumed to be known. We are interested in how best to schedule a number of new jobs that the facility will be processing in the near future. We first develop a mixed integer quadratic programming model (MIQP) for this problem. Since the exact solution of this MIQP formulation is time consuming, we develop a heuristic procedure, based on existing bin packing techniques. This heuristic is further enhanced by application of certain local optimality conditions.     

Staffing a call center with uncertain non-stationary arrival rate and flexibility

We consider a multi-period staffing problem in a single-shift call center. The call center handles inbound calls, as well as some alternative back-office jobs. The call arrival process is assumed to follow a doubly non-stationary stochastic process with a random mean arrival rate. The inbound calls have to be handled as quickly as possible, while the back-office jobs, such as answering emails, may be delayed to some extent. The staffing problem is modeled as a generalized newsboy-type model under an expected cost criterion. Two different solution approaches are considered. First, by discretization of the underlying probability distribution, we explicitly formulate the expected cost newsboy-type formulation as a stochastic program. Second, we develop a robust programming formulation. The characteristics of the two methods and the associated optimal solutions are illustrated through a numerical study based on real-life data. In particular we focus on the numerical tractability of each formulation. We also show that the alternative workload of back-office jobs offers an interesting flexibility allowing to decrease the total operating cost of the call center.     

A tabu search algorithm for simultaneous machine/AGV scheduling problem

Machines and automated guided vehicles (AGVs) scheduling problems are two essential issues that need to be addressed for the efficiency of the overall production system. The purpose of this paper is to study the simultaneous scheduling problem of machines and AGVs in a flexible manufacturing system (FMS) since the global optimum cannot be reached by considering each of them individually. In this paper, a mixed integer linear programming (MILP) model is developed with the objective of makespan minimisation. The MILP model consists of the following two constraint sets: machines and AGVs scheduling sub-problems. As both sub-problems are known to be NP-hard, a heuristic algorithm based on tabu search (TS) is proposed to get optimal or near to optimal solution for large-size problems within reasonable computation time. The proposed algorithm includes a novel two-dimensional solution representation and the generation of two neighbour solutions, which are alternately and iteratively applied to improve solutions. Moreover, an improved lower bound calculation method is introduced for the large-size problems. Computational results show the superior performance of the TS algorithm for the simultaneous scheduling problem.     

Intelligent agent framework to determine the optimal conflict-free path for an automated guided vehicles system

Agent technology has been considered as an important approach for developing intelligent manufacturing systems. It offers a new way of thinking about many of the classical problems in manufacturing engineering. The conflict resolution of automated guided vehicles (AGVs) in a flexible manufacturing systems (FMS) environment is one such problem that comes under this category. This paper describe a multi-agent approach to the operational control of AGVs by integration of path generation, enumerating time-windows, searching interruptions, adjusting waiting time and taking decisions on the selection of routes. It presents an efficient algorithm and rules for finding a conflict-free shortest-time path for AGVs, which is applicable to a bi- and unidirectional flow path network. The concept of loop formation in a flow path network is introduced to deal with the parking of idle vehicles, without obstructing the path of moveable AGVs. The concept of loop formation at nodes reduces the timing-taking task of finding the dynamic positioning of idle AGVs in the network.