【正文】 he job may bee unavailable after this time, as for example, if the yard crane bees 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 ?ve ships with four to seven cranes per ship and a number of jobs depending on the size and con?guration of ships. Jobs have a pro?t value assigned to them and resources, ., 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 acmodated 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 e in di?erent sizes, and cranes have di?erent handling capacities. Since we make the assumption that any crane assigned to a job pletes it, the throughput or pro?t, for a given cranetojob assignment, is a ?xed value independent of other cranetojob assignments. The problem is naturally represented by a bipartite graph matching problem when we take cranes and jobs to be the vertices and de?ne the weights of connecting edges to be cranetojob throughput. This representation is shown in Figure 1. 4 Figure 1 This matching problem is interesting because, in practice, a number of spatial constraintsarise for cranes and jobs. We ?rst introduce qualitative notions of three particularly mon constraints which we call ―spatial‖ constraints since they are related to the relative positions of cranes and jobs. Our objective is to ?nd a cranetojob assignment scheme which maximizes throughput under these constraints. For reasons given above, we assume that cranetojob assignments are performed in a given time interval, ., there is no temporal ponent in the problem. Detailed de?nitions will be given in the relevant sections of this paper. 1. Noncrossing constraint: Cranes cannot cross over each other. This is a structural constraint on cranes and crane tracks. 2. Neighborhood constraint: There is a minimum distance between cranes. This arises, for example, since cranes require ?exibility in space to perform jobs and/or for safety reasons. The e?ect of this constraint is that neighboring jobs may be a?ected and may not be assignable to other cranes. 3. Jobseparation constraint: Certain jobs cannot be done simultaneously. For example, jobs bound for the same yard may require separation in time to avoid trailer congestion in lanes. In the following sections, we ?rst consider these constraints separately and then simultaneously. In section 3, an O(mn) dynamic programming (DP) algorithm is given to solve the problem with only the Noncrossing constraint where m is the number of cranes and n is the number of jobs. In section 4, we use an O(m2n) dynamic programming algorithm to achieve an optimal solution for the problem with both the Noncrossing and Neighborhood constraints. In section 5, assuming all three spatial constraints, we show the problem to be NPplete and give two heuristic approaches to solve the problem — a probabilistic tabu search and a squeaky wheel optimization 5 with local search method. In section 6, we provide experimental results and pare the di?erent approaches. 3 Scheduling with the NonCrossing Constraint The Problem Throughout this work, C= {c1, c2, . . . , cm} is a set of cranes and J= {j1, j2, . . . , jn} a set of jobs. The order of subscripts assigned to the cranes and jobs represents their spatial (assumed linear) distribution, ., the neighbor of j1is j2, the neighbors of j2are j1and j3,. . . , and the neighbor of jnis jn?1, The same holds for the cranes. An m n adjacency matrix, W , is used to represent the relationships between jobs and cranes. For each Wx,y∈ W , the value Wx,y represents the throughput when job jy is assigned to crane cxwhere Wx,y= 0 if job jycannot be assigned to crane cx. The Wx,y values arise from the di?erent job sizes and crane capacities. We seek a solution set,R={(p, q )|1 ≤ p≤ m, 1≤q≤n, Wp,q 0}, such that the following constraint is satis?ed: For all (p1, q1), (p2, q2)∈ R, p1 p2if and only if q1 q2. Viewing p’s and q’s, as subscripts in C and J respectively, we see that any cranejob assignment in R satis?es the Noncrossing Constraint. The objective is then to ?nd a set R which maximizes ∑(p,q)∈ rWp,q subject to the constraints that each job is assigned to at most one crane and each crane is assigned to at most one job. Algorithm Description We now provide a dynamic programming (DP) approach and describe how to characterize an optimal solution. DP procedures for puting values of solutions in a bottomup way and for constructing solutions from puted information are omitted since they follow directly and are required only in implementation. The Structure and Value of an Optimal Solution We consider the cranes one by one. For each crane cx, we assign every job jy(1 ≤ y ≤ n) to it and pute the total throughput to derive a partial optimal solution Px,ywhich denotes the optimal value up to the step we assign job jyto crane cx. Here, it is not necessary that job jyis actually assigned to crane cx, ., (x, y) ∈ Rx,y may not hold, where Rx,yis the partial solution set corresponding to the partial optimal solution Px,y. The following putes the partial optimal solution, Px,y, recursively, for the