Cargo stacked in yards is moved by cranes onto movers and transported for loading onto ships. ”Cargo” here comprises containers of different capacities, which, whether in ships or in yards, are parcelled into fixed areas for access to cranes. For example, cargo placed in specific holds or deck sections on ships, or in sections within yards.

Containers are unloaded from ships by quay cranes onto movers or trailers which carry them to assigned yard locations where they are loaded onto stacks by yard cranes. Containers destined for import are set aside, and restacking, if required, is carried out. In the movement of containers, sequencing is crucial because containers are stored in stacks in the ship and on the yard and lanes may be designated to specific trailers at certain times. In addition, the movement of containers involves routing and crane operations where timings may be uncertain. In fact, crane scheduling is one activity among many that determine the movement of containers. Other such activities include berthing, yard storage, ship stowage and vehicle allocation and routing, all of which can be uncertain. Because of the uncertainty present over all activities, it is almost impossible to implement a plan over any length of time. This difficulty is present in scheduling cranes. For example, although a set of jobs may be assigned to a certain crane, it may not be possible for the crane to complete processing a job in this set onto movers once it was known that the route these movers are to take was congested. As another example, although we can specify that jobs bound for the same yard space are not unloaded from ships simultaneously, we cannot expect such containers to be unloaded at a time other than the allotted time interval, since a required resource to complete the job may become unavailable after this time, as for example, if the yard crane becomes unavailable. In view of the dynamically changing environment, a central control devises and maintains a job assignment plan that is periodically updated in order to coordinate operations, including crane scheduling. The system will allocate all jobs and resources periodically.

In the port we studied, a job parcel can include a number of ships and a number of cranes together with jobs. Typically, there can be up to five ships with four to seven cranes per ship and a number of jobs depending on the size and configuration of ships. Jobs have a profit value assigned to them and resources, e.g., cranes, movers, lanes etc., are assigned to each of the jobs depending on their value to the overall operations plan which aims to optimize total throughput. When an assignment plan is updated, the central system reassesses the current state of operations to regroup and reassign job parcels. Because of this, time is accommodated by constant adjustments of job parcels and assignments based on the current state of all operations. Hence, once jobs and resources are assigned for the time period no update is necessary.

Jobs come in different sizes, and cranes have different handling capacities. Since we make the assumption that any crane assigned to a job completes it, the throughput or profit, for a given crane-to-job assignment, is a fixed value independent of other crane-to-job assignments.

The problem is naturally represented by a bipartite graph matching problem when we take cranes and jobs to be the vertices and define the weights of connecting edges to be crane-to-job throughput. This representation is shown in Figure 1.

This matching problem is interesting because, in practice, a number of spatial constraintsarise for cranes and jobs. We first introduce qualitative notions of three particularly common constraints which we call “spatial” constraints since they are related to the relative positions of cranes and jobs. Our objective is to find a crane-to-job assignment scheme which maximizes throughput under these constraints. For reasons given above, we assume that crane-to-job assignments are performed in a given time interval, i.e., there is no temporal component in the problem. Detailed definitions will be given in the relevant sections of this paper.