The quantity of good transported has been increased rapidly with increasing trade among nations. As a result, the advent of large-scale vessels is accelerated. A container terminal is trying to secure the competitiveness of marine transportation by using new types of equipment and state-of-the-art technologies.

Figure 1 illustrates a layout of a container terminal. The storage yard in a container terminal is a temporary storage space for containers before they are loaded on to the target vessel or delivered to consignees. There are two types of container flow in container terminals: one is the inbound flow in which import containers are unloaded from vessels, which called a discharging operation, and are delivered to consignees and customers, which we call a delivery operation. The other is the outbound flow in which export containers are delivered to a container terminal by road trucks and rail trains, which is called the receiving operation, and are loaded onto vessels, which is called the loading operation (Zhang 2010).

A typical performance measure in container terminals is the turnaround time of vessels which is the average time during which a vessel stays at a terminal. There are many factors which effect the turnaround time of vessels in a container terminal. The efficiency of ship operation schedules is one of the most important factors among them.

A typical type of QC schedules specifies the service sequence of ship-bays in a ship by each QC and the time schedule for the services. During the detail discharge and load sequencing process, the discharge and load sequence of individual containers and the pickup position of each outbound container are determined. Therefore the allocation of the yard space to inbound and outbound containers affects the efficiency of loading and discharging operations in the quayside, as well as receiving and delivery operations in the gate side (Won, 2009).

There are many studies for QC scheduling and yard planning. The QC scheduling problem was first suggested by Daganzo (1989), who proposed an algorithm to determine the number of cranes to be assigned to ship bays of multiple vessels. Peterkofsky and Daganzo (1990) also provided an algorithm to determine the number of cranes to assign to each holds of vessels at a specific time segment and the departure times of multiple vessels. These studies used a ship bay as a unit of the schedule and they did not considered the interference among QCs and precedence relationships among tasks. Kim and Park (2004) presented a QC scheduling method in which they defined the unit of scheduling as discharging and loading tasks on deck and those in hold. They also considered various precedence relationships among loading and discharging tasks and practical constraints. Because of the complexity of problem, they used a branch and bound technique and GRASP (Greedy Randomized Adaptive Search Procedures) for this problem. Jung et al. (2006) presented a scheduling method considering interference of yard cranes. Bierwirth and Meisel (2009) proposed a heuristic algorithm with modified interference constraints. An internal reshuffles problem was addressed by Meisel and Wichmann (2010). A quay crane scheduling algorithm considering the workload is developed by Wang and Kim (2011). About the space planning problem of yard, Kim and Kim (1999) proposed a segregation strategy to allocate storage space to import containers. Kim et al. (2000) studied a method to determine the positions of the arriving outbound containers in a bay considering their weights. Zhang et al. (2003) studied the allocation of storage space for outbound and inbound containers in a way of distributing the workload of handling equipment as uniformly as possible among blocks. Kim and Park (2003) studied the yard space allocation problem for inbound and outbound containers of various vessels with capacity constraints of storage spaces. Lee et al. (2006) proposed a method for allocating storage space to future arrivals of containers at each time shift by simultaneously considering both handling workload and traffic congestion. Won (2009) studied the yard planning problem considering various resources, such as space, yard cranes, travel lanes and internal trucks. The problem was represented as a multi-commodity minimum cost flow problem. Zhang (2010) extended the study of Won (2009) and developed a more efficient algorithm.

As stated above, a container terminal has complex operation procedures and all the operations require elaborate plans for the efficiency of the operations. Also it is more difficult to construct efficient plans for largescale vessels with the larger amount of containers because the planners should consider the workloads of resources which are used simultaneously for all types of operations in container terminals. Especially, the yard as a temporary storage space is one of the most important resources

This paper proposes a method for QC scheduling and yard planning considering workloads of various resources in container terminals. We consider that resources in the storage yard are shared by many QC operations for multiple vessels.

The main idea of the resource workload is similar to Won (2009) and Zhang (2010). The rest of the paper is organized as follows: section 2 proposes a QC scheduling procedure and a block assignment method. Section 3 deals with a heuristic rule for estimating workloads of various resources for the yard planning. Section 4 introduces a simulation study for evaluating the suggested two methods. Conclusions and future researches are given in section 5.

In this section, a QC scheduling method considering workload of resources is suggested including the block assignment rules for inbound and outbound containers.

A ship cluster is the basic unit of QC operation for scheduling, which indicates “a set of transfer operations for slots on the same deck or in the same hold of the same bay.” Thus, one ship cluster is identified by its ship bay number, on deck or hold, operation type (loading, unloading) and container size. A sub-cluster is defined to be the set of transfer operations for containers of the same group (the same type, the same destination port) included in the same ship-cluster. One ship cluster consists of multiple sub-clusters (Wang et al., 2011).

Table 1 illustrates a QC schedule. This schedule shows the number of containers in each ship cluster, the sequence of clusters to be operated, and the time schedule for each QC to handle the clusters.

Each row in a QC schedule corresponds to the schedule of each sub-cluster. Block assignment is related to the shaded part in Table 1. This part shows that how many containers should be moved from (or to) each block. A QC schedule in this paper is based on a result of Jung et al. (2006).

Only the block assignment part is modified as follows by considering the concept of the workload. There are two cases: loading and unloading operation. The block assignment method for unloading operation is described as follows:

(1) Calculate the number of containers and estimate workload requirement in each period. Because a unit of time period is 1 hour, it is necessary to calculate the number of containers to be handled during each period For example, 80 loading operations are scheduled from 9 : 30 am to 11 : 30 am. The required workload can be calculated as in Table 2. The handling time per operation was set to be 1.1 min.

(2) Find a block list using a priority rule and select a block. Each QC has a list of blocks ordered by using a priority rule. The list will be used for selecting a block for each container. The blocks in the list is ordered by using the travel distance between QC and

each block. After selecting a block from the list of blocks, it is necessary to check the workload of the selected block. In this process, it is necessary to check not only the YC workload but also the space availability.

(3) Calculate the number of containers and estimate workload requirement in each period. Because a unit of time period is 1 hour, it is necessary to calculate the number of containers to be handled during each period For example, 80 loading operations are scheduled from 9 : 30 am to 11 : 30 am. The required workload can be calculated as in Table 2. The handling time per operation was set to be 1.1 min.

(4) Find a block list using a priority rule and select a block. Each QC has a list of blocks ordered by using a priority rule. The list will be used for selecting a block for each container. The blocks in the list is ordered by using the travel distance between QC and each block. After selecting a block from the list of blocks, it is necessary to check the workload of the selected block. In this process, it is necessary to check not only the YC workload but also the space availability.

(5) Confirm the workload of the selected block and update workload information. If a selected block has enough amounts of available resources, the block can be assigned to the cluster. Then, specified amounts of resources are reserved for the operation of the cluster and workload information is updated considering the reservation.

(6) Repeat until all containers are assigned. After all the containers for a cluster are assigned to one or multiple blocks, we can get an assignment results like those in Table 3, which shows 60 inbound containers are assigned to block 1 and 20 inbound containers are assigned to block 2 for the unloading operation. This data will be put into the block assignment part in the QC schedule.

In case of loading operation, the procedure is different from the one for discharging containers because in this case we have to consider storage locations of outbound containers which already arrived at the yard. The blocks with containers which have the same attributes as the corresponding cluster will be candidate blocks for the cluster to be assigned to.

When selecting a block, it has to be checked if the block has some containers having the same attributes as the corresponding cluster. However, for the scheduling of loading operation, it is not necessary to consider the space availability, because the loading operation doesn’t need additional space for the operation. The assignment procedure will be repeated until all the clusters are assigned to blocks.

This section discusses a space planning method considering workload of resources such as the storage space and yard cranes and heuristic rules for efficient space planning in detail.

Space planning is to determine groups and quantities of arriving containers to be stored at each block and reserve the determined amount of space for each group of containers before they arrive at the yard. The process of determining the storage locations of containers can be divided into two stages (Bazzazi et al., 2009): at the first stage, the number of containers for each vessel to be placed in each storage block at each time period of the planning horizon is determined. In the second stage, Specific locations for each group of containers are reserved. This paper focuses on the first stage of the space planning procedure. An example of the result of the space planning is illustrated in Table 4.

There are two most popular strategies for the space planning which determines the storage blocks and the amounts of space reservation for inbound and outbound containers of each vessel: the first strategy is to minimize the travel distance of internal trucks between storage blocks and berthing positions of vessels; the second strategy is to balance workload among blocks. When the second strategy is adopted, for the space allocation of arriving containers at the next period, it is necessary to consider not only the present situation in the yard or the workload of equipment at the next period but also the workload at the moment when the containers are loaded into a vessel or delivered to road trucks in future. This study attempts to evaluate the space allocation strategy which simultaneously considers the current and the future workloads of handling equipment at storage blocks.

The storage space and the handling equipment are the main resources for space planning decisions. For example, a yard crane which is one of the most important equipment for handling containers is a time-related resource. An excessive workload on a yard crane will cause the delay of loading and discharging operation, which results in longer turnaround times of vessels. For reducing the turnaround times of vessels, it is important that the handling workload at each time period is distributed over all the blocks. This section introduces a heuristic rule for the space planning, which determines the number of containers to be stored at each block. The main objective of this heuristic rule is to allocate space requirements to blocks so as to balance the handling workload among all the blocks and simultaneously consider the travel distance of internal trucks between blocks and the corresponding berth for each vessel. Figure 3 shows the procedure of the space allocation. The following describes the main procedure:

(1) Selection of blocks for the space allocation. When there is no information on amount of containers for a vessel, firstly, the expected number of containers to arrive at the yard will be calculated based on historical data. And then, the requirements of resources for the containers will be estimated. The availability of resources must be checked from the current period to the berthing time of the corresponding vessel. Finally, candidate blocks are selected by considering the availability of resources and the block priority of each block which is assigned to each block by using the travel distance between the corresponding berth and the block.

(2) Allocation of the expected number of containers to the selected blocks. The expected number of containers of each vessel is allocated to blocks proportionally to the resource availability. The procedure is described in Figure 4. For example, suppose that candidate blocks are block 2, 4, and 6 and the expected number of arriving containers during the planning period is 40. Suppose that the minimum available resource between the planning period and the berthing period is 30, 20, and 50 at block 2, 4, and 5, respectively. Then, the number of resource to be allocated to each block can be calculated as in Table 4.

The performances of the methods in sections 2 and 3 are evaluated by simulation experiments. This section discusses the process of simulations in detail and analyzes the results.

In this study, the simulation models are composed the berth area for ship operations, a storage yard for storage and retrieve operations, and a gate for in/out road trucks. The process of simulation experiments for QC scheduling and yard planning is described at Figure 5.

The yard planning system makes allocation of arriving containers every 8 hours, and QC scheduling system makes schedules 10 hours before a vessel arriving under the stopped simulation status. Then the workload information is updated at the database and simulation would be preceded. At the beginning of simulation, the outbound containers arrive at the terminal 7 days before the start of ship operations for the corresponding vessel. The allocations of storage locations for those containers are decided by the heuristic method which is introduced in section 3 with regarding that the workload of resources decided by ship operations are 0 at first.

The simulation environment is described as follows.

1. The container terminal assumed in this simulation study has 3 berths. 20 vessels are served in these berths. Each vessel has around 1000 containers to load into or unload from.

2. The yard consists of 21(3 ^× 7) horizontal blocks with 34 bays and 9 rows in each block.

3. 2 yard cranes are installed in each block and 9 QCs are installed along the quayside.

4. The simulation horizon is 27 days.

5. The arrival ratios for outbound containers for each of 7 days and at each time period in a day are shown in Table 5 and Table 6.

The simulation is stopped and transfer yard information to database at the moment of 10 hours before the corresponding vessel arrives at the terminal. Then, the planning system schedules QC operations using these input data. QC schedule is saved in the database. A simulation start with this QC schedule. Each QC has a list of blocks with different priorities for assigning clusters. 45 vehicles are deployed to these QCs.

Two different rules are applied to allocate spaces to clusters. Method 1, which is called ‘DISTANCE,’ considers only distance between the berth and the corresponding block. Method 2 considers the distance and the workload of each block simultaneously, which will be called ‘DIST ANS WORKLOAD.’

Usually, the unloading containers have more flexibility than the loading containers, because the loading containers are already in the yard and the storage locations of loading containers will restrict the candidate blocks for clusters to be assigned to. However, the discharging containers have no limitations for the storage. Thus, in DIST AND WORKLOAD, we impose tighter constraints for allocating unloading containers in order to secure resources for loading containers which will be assigned storage locations later. We set the maximum available capacity of each block to be 30, 50, and 70%, respectively, of their full capacity for three simulation experiments, which means 70, 50, 30% of their capacity will be reserved for the loading containers which will be planned later.

In Table 7, we can see that turnaround times of DIST AND WORKLOAD are shorter than those of DISTANCE. When a smaller capacity is used for unloading, a shorter turnaround time results.

The results in Table 8 and Table 9 are explained in the following. Closest blocks have highest priorities for each QC. Thus many containers are assigned to these blocks when using DISTANCE. Because of this tendency of assignments, many vehicles visit these blocks and take longer time to wait for the service by yard cranes. With DIST AND WORKLOAD, we can distribute this workload. When workloads exceed a capacity of high priority blocks, containers are assigned to other blocks. Thus, we can avoid congestion. And this effect is more efficient when we use smaller capacity for loading operations.

We used 120 as the capacity in the previous experiments. It can be calculated 60×2 (available time× number of yard crane at each block). Because the capacity of 120 is fully tight to the maximum capacity of yard cranes, the congestion at a block was found during the simulation. Thus, we solved the problem (vessels 4~6) with smaller capacity and got better results in Table 12. The workload could be distributed more uniformly when

a lower percentage of the capacity is assumed to be available during the allocation of resources and thus the results became better as shown in Table 10~Table 11. When the maximum available capacity of handling

workload of each block was assumed to be 80% of its full capacity, in some cases, no feasible solution could

be found.

Figure 6 shows the event flow diagram for the event that a truck with an outbound container arrives at the gate. When an outbound truck arrives at the gate, the location of the outbound container is assigned by using a block allocation rule, which assigns a block for the outbound container by using the space plan. Next, the assigned empty slot in the yard is reserved for the outbound container. Finally, the outbound truck will move to the assigned block in the yard. For internal transportation, total 32 vehicles are deployed.

Three space planning methods to allocate spaces to containers are tested in the simulation experiment. The first method considers only the travel distance between the berth and the corresponding block (Distance). The second method considers only the workload of each block (Workload). The third method simultaneously considers the workload of each block and the travel distance of each block (Distance and Workload). Distance and Workload method allocates containers to blocks with lower priorities when workloads exceed capacities of blocks with higher priorities.

Figure 7 shows the average turnaround time of vessels by three space planning methods. It was found that Distance and Workload outperformed Distance and Workload by 7.5% and 2.5%, respectively.

Figure 8 and Figure 9 show the average and the variance of the system time of road trucks at blocks, which is the sum of the waiting time and the service time by yard cranes. Figure 8 shows that Distance rule results in the concentration of road trucks to several blocks nearest to the berth, while the other two workload- related rules do not show so much delays and congestion of road trucks because of spreading and balancing the workload over all the blocks in the yard. Figure 8 and 9 did not show any significant difference in the average or the variance of the system time of trucks between Workload and Distance and Workload rules

The last performance measure is the total travel time of internal trucks during the unloading and loading operations. In Figure 10, Distance and Distance and Workload methods showed a similar total travel time per container delivery by an internal truck. However, Workload rule showed a longer average travel time than Distance and Distance and Workload during the loading and unloading operations. The longer travel time means a more energy consumption by internal trucks during the ship operation. Figure 10 implies that both the travel distance and the workload need to be considered from the viewpoint of the turnaround time of vessels and the energy consumption by internal trucks.

Although there have been many studies which suggest QC scheduling methods and space planning methods considering workloads, they did not prove their idea in a dynamic situation similar to the real practice. This paper evaluated QC scheduling methods and space planning methods considering workloads on various resources in container terminals for the first time and showed that workload based planning methods are effective for reducing the turnaround time of vessels and road trucks. And the handling workload on each block in the yard was considered during a QC scheduling. It was tried to avoid congestion in the yard by using workload information and a block assignment method was provided. As the result of simulation experiments, it is proved the suggested method considering workload outperforms traditional methods. In addition, in this study, methods were provided for estimating the workloads of various resources for a yard plan or QC scheduling and availabilities of resources.

The rules tested in this study were simple and thus it is necessary to test more complicated algorithms in terms of their performance and the applicability to practices. This paper considered only two types of resources in container terminals. However, there are many resources such as berth, travelling lane, and human resource, etc. These resources may be additionally considered for more efficient allocation of storage space, which may be another interesting issue for a future study.