【正文】 are considered. In addition to the Noncrossing constraint, we use the set S= {s1, s2, . . . , sm} to represent the Neighborhood constraint associated with the cranes. Here sx= k if crane cxperforms job jyand job jz(a ≤ z ≤ b, z= y) cannot be worked on by any other crane, where a = max{1, y ? k}and b = min{y + k, m}. In other words, if crane cxperforms job jy, the job ―interval‖ centered at y with length 2k + 1 is a?ected by crane cxwhen sx= k. We seek a solution set R = {(p, q)|1 ≤ p ≤ m, 1 ≤ q ≤ n, Wp,q 0} satisfying: 1. For all (p1, q1), (p2, q2) ∈ R, p1 p2if and only if q1 q2(Noncrossing constraint) 2. For all (p, q) ∈ R, if 1 ≤ p’≤ m and p’= p, and a ≤ q’≤ b, where a = max{1, q ? sp} and b = min{q + sp, n}, then (p’, q’) ∈ R (Neighborhood constraint) Our objective is to ?nd R that maximizes the total weight ∑(p,q)∈ rWp,q where each job is assigned to at most one crane and each crane is assigned to at most one job. Algorithm Description We follow the approach in section here. The Structure and Value of an Optimal Solution We continue to consider the cranes one by one. For each crane cx, we attempt to assign every job jy(1 ≤ y ≤ n) to it and pute the total throughput up to this step to give a partial optimal solution Px,y. Here, the partial optimal solution Px,y is cumulative and the edge inclusion (x, y) ∈ Rx,y may not hold. However, di?erent from the de?nition used in the previous section, crane x must be assigned some job j (1 ≤ j ≤ y) for Px,y, ., there must be an edge (x, j) ∈ Rx,y, where (1 ≤ j≤ y)。 1 附錄 英文原文 Crane Scheduling with Spatial Constraints Andrew Lim, Brian Rodrigues, Fei Xiao, and Yi Zhu Abstract In this work, we examine port crane scheduling with spatial and separation constraints. Although mon to most port operations, these constraints have not been previously studied. We assume that cranes cannot cross, there is a minimum distance between cranes and jobs cannot be done simultaneously. The objective is to ?nd a cranetojob matching which maximizes throughput under these constraints. We provide dynamic programming algorithms, a probabilistic tabu search and a squeaky wheel optimization heuristic for solution. Experiments show the heuristics perform well pared with optimal solutions obtained by CPLEX for small scale instances where a squeaky wheel optimization with local search approach gives good results within short times. 1 Introduction The Port of Singapore Authority (PSA) is a large port operator located in Singapore, one of the busiest ports in the world. PSA handles million TEU’s annually or nine percent of global container tra?c in Singapore, the world’s largest transshipment hub. PSA is concerned with maximizing throughput at its port due to limited port size, high cargo transshipment volumes and limited physical facilities and equipment . Crane scheduling and work schedules are critical in port management since cranes are at the interface between land and water sections of any port, each with its own tra?c lanes, intersections, and vehicle ?ow control systems. In this multichannel interface we are likely to ?nd bottlenecks where cranes and other cargohandling equipment (forklifts, conveyors etc.) converge. Sabria and Daganzo studied port operations which focused on berthing and cargohandling systems. In berthing, which is a widelyanalyzed port activity, queuing theory has been used widely. Tra?c and vehicle?ow scheduling on land in ports has also been well studied. Danganzo studied a static crane scheduling case where cranes could move freely from hold to hold and only one crane is allowed to work on one hold at any one objective was to minimize the aggregate cost of delay. In [13], container handling is modelled as ―work‖ which cranes perform at constant rates and cranes can interrupt work without loss of e?ciency. This constituted an ―open shop‖ parallel and identical machines problem, where jobs consist of independent, 2 singlestage and preemptable tasks. A branch andbound method was used to minimize delay costs for this problem. Crane scheduling has also been studied in the manufacturing environment context . Commonlyfound constraints a?ecting crane operations are absent in studies available on the subject. Such constraints a?ect crane work scheduling and need to be factored into operational models. These include the basic requirement that operating cranes do not cross over each other. Also, a minimum separating distance between cranes is necessary since cranes require some spatial ?exibility in performing jobs. Finally, there is a need for jobs arriving for stacking at yards to be separated in arrival time to avoid congestion. We found that operational decisionmaking at PSA was based largely on experience and simulation techniques. While the latter is of value, analytic models are an advantage and are not limited by experiencegenerated rulesofthumbs or simulation. The object of this work is to address the need for such models which take into account mon spatial and separation requirements in the scheduling cranes. This work augments Peterkofsky and Daganzo study . 2 Problem Description During the time ships are berthed, various cargohandling equipment is used to unload cargo, mostly in the form of containers. Di?erent types of cargo require di?erent handling and many ports have bulk, container, dry and liquidbulk terminals. Cargo that is containerized can be loaded and unloaded in a fewer number of moves by cranes operating directly over ship holds or by crane arms moving over holds or deck areas. Cargo stacked in yards is moved by cranes onto movers and transported for loading onto ships. ‖Cargo‖ here prises containers of di?erent capacities, which, whether in ships or in yards, are parcelled into ?xed areas for access to cranes. For examp