機(jī)械專業(yè)外文翻譯 ----起重機(jī)調(diào)度與空間限制

1、<p><b>　　附錄</b></p><p><b>　　英文原文</b></p><p>　　Crane Scheduling with Spatial Constraints</p><p>　　Andrew Lim, Brian Rodrigues, Fei Xiao, and Yi Zhu</p

2、><p><b>　　Abstract</b></p><p>　　In this work, we examine port crane scheduling with spatial and separation constraints. Although common to most port operations, these constraints have n

3、ot 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 crane-to-job matching which maximizes throughpu

4、t under these constraints. We provide dynamic programming algorithms, a probabilistic tabu search and a squeaky wheel optimizat</p><p>　　1 Introduction</p><p>　　The Port of Singapore Authority

5、(PSA) is a large port operator located in Singapore, one of the busiest ports in the world. PSA handles 17.04 million TEU’s annually or nine percent of global container tra?c in Singapore, the world’s largest transshipme

6、nt 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

7、in port management since cra</p><p>　　Sabria and Daganzo studied port operations which focused on berthing and cargo-handling systems. In berthing, which is a widely-analyzed port activity, queuing theory ha

8、s 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 all

9、owed to work on one hold at any one time.The objective was to minimize the aggregate cost of delay. In [13], co</p><p>　　Commonly-found constraints a?ecting crane operations are absent in studies available o

10、n 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 separat

11、ing 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 arri</p><p>　　We

12、found that operational decision-making 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 experience-generated rules-of

13、-thumbs or simulation. The object of this work is to address the need for such models which take into account common spatial and separation requirements in the scheduling cranes. This work augments Peterkofsky and Daganz

14、o study .</p><p>　　2 Problem Description</p><p>　　During the time ships are berthed, various cargo-handling equipment is used to unload cargo, mostly in the form of containers. Di?erent types o

15、f cargo require di?erent handling and many ports have bulk, container, dry and liquid-bulk terminals. Cargo that is containerized can be loaded and unloaded in a fewer number of moves by cranes operating directly over sh

16、ip holds or by crane arms moving over holds or deck areas.</p><p>　　Cargo stacked in yards is moved by cranes onto movers and transported for loading onto ships. ”Cargo” here comprises containers of di?erent

17、 capacities, which, whether in ships or in yards, are parcelled into ?xed areas for access to cranes. For example, cargo placed in speci?c holds or deck sections on ships, or in sections within yards.</p><p>

18、;　　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

19、 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 speci?c trailers at certai

20、n times. In addition, the movement of containers involves routi</p><p>　　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

21、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, e.g., cranes, movers, lanes etc., are assig

22、ned to each of the jobs depending on their value to the overall operations plan which aims to optimize total throughput. When an assignment plan i</p><p>　　Jobs come in di?erent sizes, and cranes have di?ere

23、nt handling capacities. Since we make the assumption that any crane assigned to a job completes it, the throughput or pro?t, for a given crane-to-job assignment, is a ?xed value independent of other crane-to-job assignme

24、nts.</p><p>　　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 crane-to-job throughpu

25、t. This representation is shown in Figure 1.</p><p><b>　　Figure 1</b></p><p>　　This matching problem is interesting because, in practice, a number of spatial constraintsarise for cra

26、nes and jobs. We ?rst 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 ?n

27、d 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 </p><p>　　1. Non-crossing cons

28、traint: Cranes cannot cross over each other. This is a structural constraint on cranes and crane tracks.</p><p>　　2. Neighborhood constraint: There is a minimum distance between cranes. This arises, for exam

29、ple, 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.</p><p>

30、;　　3. Job-separation 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.</p><p>　　In the fol

31、lowing 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 Non-crossing constraint where

32、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 Non-crossing and Neighborhood constraints.

33、In section 5, assuming all three spatial constrain</p><p>　　3 Scheduling with the Non-Crossing Constraint</p><p>　　3.1 The Problem</p><p>　　Throughout this work, C= {c1, c2, . . .

34、 , 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, i.e., the neighbor of j1is j2, the neig

35、hbors of j2are j1and j3,. . . , and the neighbor of jnis jn?1, The same holds for the cranes.</p><p>　　An m × n adjacency matrix, W , is used to represent the relationships between jobs and cranes. For

36、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.<

37、/p><p>　　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

38、subscripts in C and J respectively, we see that any crane-job assignment in R satis?es the Non-crossing Constraint.</p><p>　　The objective is then to ?nd a set R which maximizes ∑(p,q)∈rWp,q subject to the c

39、onstraints that each job is assigned to at most one crane and each crane is assigned to at most one job.</p><p>　　3.2 Algorithm Description</p><p>　　We now provide a dynamic programming (DP) ap

40、proach and describe how to characterize an optimal solution. DP procedures for computing values of solutions in a bottom-up way and for constructing solutions from computed information are omitted since they follow direc

41、tly and are required only in implementation.</p><p>　　3.2.1 The Structure and Value of an Optimal Solution</p><p>　　We consider the cranes one by one. For each crane cx, we assign every job jy(

42、1 ≤ y ≤ n) to it and compute 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 assi

43、gned to crane cx, i.e., (x, y) ∈Rx,y may not hold, where Rx,yis the partial solution set corresponding to the partial optimal solution Px,y.</p><p>　　The following computes the partial optimal solution, Px,y

44、, recursively, for the di?erent cases:</p><p>　　1. If x = 1 and y = 1, P1，1:= W1，1</p><p>　　2. If x = 1 and y > 1, P1,y:= max{W1，y’, P 1,y-1}</p><p>　　3. If x > 1 and y = 1,

45、Px，1:= max{Wx,1, Px-1,1 }</p><p>　　4. If x > 1 and y > 1, Px,y:= max{Px,y-1,P x-1,y’ ,P x-1,y-1 +Wx,y}</p><p>　　(1) is the basic case: If we only consider the ?rst crane and the ?rst job,

46、we will assign this job to the crane if the job can be done by the crane. (2) and (3) are both special cases, i.e., when there is only one node in each part of the bipartite graph. As these are symmetrical, we need consi

47、der only (2). For crane c1and job jy, we have two choices: either, assign jyto c1, or, assign a job from {j1, . . . , jy?1}to c1. This is because at most one job can be assigned to this ?rst crane. The th</p><

48、p>　　?Leave job jy unassigned . We are reduced to assigning cranes c1, c2, . . . , cx to jobs j1, j2, . . . , jy-1. By induction, the optimal value is then Px,y-1;</p><p>　　?Leave crane cx unassigned .

49、We are reduced to assigning cranes c1, c2, . . . , cx-1 to jobs j1, j2, . . . , jy. By induction, the optimal value is then Px-1,y;</p><p>　　?Assign crane cxto job jy(or, leave both unassigned if they are

50、not assignable to each other). In this case, the total throughput is the throughput from this assignment plus the throughput from assigning cranes c1, c2, . . . , cx-1 to jobs j1, j2, . . . , jy-1. Hence, the value is Px

51、-1,y-1+Wx,y.</p><p>　　Taking the maximum of these throughput values, the optimal solution is then the ?nal partial optimal solution Pm,n obtained.</p><p>　　3.2.2 A Proof of Optimal Substructure

52、</p><p>　　We provide an outline a proof that the problem de?ned in this section possesses optimal substructures necessary in using DP. An important property for Px,yis: Px,y≥Px’,y’,if x ≥ x’and y ≥ y’(*), wh

53、ich is easily veri?ed since Px,y≥ Px,y-1 and Px,y≥ Px-1,y. We can now verify the four cases given above by induction:</p><p>　　1. If x = 1 and y = 1, clearly P1,y= Wx,1is the only solution and must be opti

54、mal</p><p>　　2. If (x, y)∈R’x,y, thenPx,y’≤Pak-1,bk-1+Wx,y. By (*), we know Px-1,y?1 ≥Pak-1,b-1 since x ? 1 ≥ ak-1, y-1 ≥ bk-1. So Px,y’≤ Px-1,y-1+Wx,y. Because Px,y≥Px-1,y-1+ Wx,y, we get Px,y≥ Px,y’ , whi

55、ch contradicts our assumption Px,y’> Px,y. Hence, Px,y is the optimal solution.</p><p>　　We can conclude that Px,y is the optimal solution for all (x, y), 1 ≤ x ≤ m, 1 ≤ y ≤ n,</p><p>　　3.3

56、 The Time Complexity of the Algorithm</p><p>　　The computation for every partial solution Px,y is in constant time, so the time complexity for this algorithm is O(mn).</p><p>　　4 Scheduling w

57、ith the Neighborhood Constraint</p><p>　　4.1 The Problem</p><p>　　In this problem, both the Non-crossing constraint and the Neighborhood constraint are considered. In addition to the Non-crossi

58、ng 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

59、 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 </p><p>　　We seek a solution set R = {(p, q)|1 ≤ p ≤ m

60、, 1 ≤ q ≤ n, Wp,q> 0} satisfying:</p><p>　　1. For all (p1, q1), (p2, q2) ∈ R, p1< p2if and only if q1< q2(Non-crossing constraint)</p><p>　　2. For all (p, q) ∈ R, if 1 ≤ p’≤ m and p’= p

61、, and a ≤ q’≤ b, where a = max{1, q ? sp} and b = min{q + sp, n}, then (p’, q’) ∈R (Neighborhood constraint)</p><p>　　Our objective is to ?nd R that maximizes the total weight ∑(p,q)∈rWp,q where each job is

62、assigned to at most one crane and each crane is assigned to at most one job.</p><p>　　4.2 Algorithm Description</p><p>　　We follow the approach in section 3.2 here.</p><p>　　4.2.1

63、 The Structure and Value of an Optimal Solution</p><p>　　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 compute the total throughput

64、up to this step to give a partial optimal solution Px,y.</p><p>　　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?nitio

65、n used in the previous section, crane x must be assigned some job j (1 ≤ j ≤ y) for Px,y, i.e., there must be an edge (x, j) ∈Rx,y, where (1 ≤ j≤ y); if there is no job in the interval [1, y] that can be assigned to cran

66、e x, then Px,y= 0. Now, we de?ne the value of the partial optimal solution Px,yfor the di?erent cases:</p><p>　　1. If x = 1 and y = 1, P1,1＝W1,1</p><p>　　2. If x = 1 and y > 1, P1,y:= max{W1,

67、y,P1,y-1}</p><p>　　3. If x > 1 and y = 1, Px,1=Wx,1</p><p>　　4. If x > 1 and y > 1, Px,y:= max{Px,y-1,P i,c +Wx,y}, 1 ≤ i < x, c = y? max{sx, si} ? 1.</p><p>　　(1) is th

68、e basic case and (2) and (3) are the special cases. (2) has been explained in the previous section. (3) is di?erent. Since we require for Px,ythat crane cxmust be assigned job jy, we have no choice but to assign this job

69、 to the current crane when there is only job available. The induction step in (4) is somewhat complex. In the ?rst case, we keep job jyunassigned, so we are reduced to assigning cranes c1, c2, . . . , cx to jobs j1, j2,

70、 . . . , jy; hence, we obtain Px,y-1. In the second</p><p>　　The ?nal optimal is the maximum value of all partial optimal solutions obtained, i.e., it is max{Px,y} over all (x, y), 1 ≤ x ≤ m, 1 ≤ y ≤ n.</

71、p><p>　　4.2.2 A Proof of Optimal Substructure</p><p>　　Similar to the earlier problem, we show that this problem has an optimal substructure. As before, we use the fact that Px,y≥ Px,y’ if y ≥ y’(

72、**). This is easy to verify since a partial optimal solution is cumulative for each crane x. As before, we have the following cases:</p><p>　　1. If x = 1 and y = 1, clearly P1,1= W1,1 is the optimal solutio

73、n</p><p>　　2. If x = 1 and y > 1, only one crane is involved, so the Neighborhood constraint does not take the e?ect. The proof is then as given in the previous section</p><p>　　3. If x >

74、1 and y = 1, since crane cxhas to be assigned a job, and there is only one job, clearly Px,1= Wx,1</p><p>　　4. If x > 1 and y > 1, Px,y= max{Px,y-1, Pi,c+ Wx,y}, 1 ≤ i < x, c = y?max{sx, si} ? 1. W

75、e assume there is an optimal solution Px,y0> Px,y and the solution set corresponding to Px,y’ is R’x,y={(ca1, j b1), (ca2,j b2), . . . , (cak, j bk)}. Here, we can take this set to be ordered, i.e., a1≤ a2≤ . . . ≤ ak

76、and b1≤ b2≤ . . . ≤ bk, by virtue of the Non-crossing constraint. Noting ak= x from the de?nition above, there are now two possibilities for Px,y’:</p><p>　　(a) If (x, y) ∈R’x,y, then Px,y’≤ Pak,bk, since

77、Pak,bk is the partial optimal solution. Hence, Px,y’≤ Px,bk, since ak= x. From property (**), we know Px,y-1 ≥ Px,bk since y ? 1 ≥ bk(job jyis unassigned). So Px,y?1 ≥ Px,y’. By the recursive de?nition,Px,y≥ Px,y-1. Hen

78、ce, we getPx,y≥ Px,y’, which contradicts the assumption Px,y’ > Px,y. So Px,y is the optimal solution in this case</p><p>　　(b) If (x, y ) ∈ R’x,y, then Px,y’≤ Pak-1,bk-1+Wx,y, since Pak-1,bk-1 is the p

79、artial optimal solution. Obviously 1 ≤ ak-1<x, so we let i = ak-1 and c = y?max{sx, si} ? 1. We know bk?1≤c since the cranes cxandciare both assigned jobs and their Neighborhood constraints are in e?ect. From (**), we

80、 get Pi,c≥ Pi,bk-1 because of c ≥ bk?1, i.e., Pak-1,c + Wx,y≥ Pak-1,bk-1,+Wx,y, and so Pak-1,c+Wx,y≥Px,y’. From the de?nition Px,y= max{Px,y-1,Pi,c+Wx,y}, we know Px,y≥ Px,y’ , which contradicts the assu</p><

81、p>　　We conclude that Px,y is the optimal solution for all (x, y), 1 ≤ x ≤ m, 1 ≤ y ≤ n.</p><p>　　4.3 The Time Complexity of the Algorithm</p><p>　　Since, for each partial solution Px,y, we t

82、ake the maximum value of the partial solutions Pi,c, 1 ≤ i < x, the time complexity is O.</p><p>　　5 Scheduling with the Job Separation Constraint</p><p>　　5.1 The Problem</p><p&

83、gt;　　We can now study the third and most general spatial constraint — the Job-separation constraint. An n × n matrix D represents this constraint: Dp,q= 1(1 ≤ i ≤ n, 1 ≤ j≤ n), when job jpand jq cannot be done simul

84、taneously. Otherwise, the elements of D are 0. Note that D is symmetric. We seek a solution set R = {(p, q)|1 ≤ p ≤ m, 1 ≤ q ≤ n, Wp,q> 0}, for which the following three conditions are satis?ed:</p><p>　　

85、1. For all (p1, q1), (p2, q2) ∈ R, p1< p2 if and only if q1< q2(Non-crossing constraint)</p><p>　　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 = max{q +

86、sp, n}, then (p’, q’) ∈R (Neighborhood constraint)</p><p>　　3. For all (p, q) ∈R, if 1≤p’≤ m, and Dq,q’= 1, then (p’, q’)∈R(Job-separation constraint)</p><p>　　The objective is to ?nd a set R w

87、hich maximizes 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.</p><p>　　5.2 Proof of NP-completeness</p><p>　　To show th

88、at this problem is NP-complete, we use the Independent Set problem which is de?ned as follows: Given a graphG= (V, E) and a positive integerk≤ |V |, is there a V’? V such that for all u, v ∈V’, the edge (u, v) is not i

89、n E and |V’| ≥ k?</p><p>　　In order to prove that this problem is NP-hard, we transform an arbitrary instance of the Independent Set problem to the problem in polynomial time. Assuming there are nnodes in t

90、he graph G = (V, E) of the Independent Set problem, we construct the model with n cranes and n jobs where the only edges are (1, 1), (2, 2),..., (n, n), all with weight equal to 1. The Job-separation constraint matrix D

91、is de?ned as follows: For all (x, y) ∈ E, Dx,y= 1, otherwise Dx,y= 0, 1 ≤ x, y ≤ n. The transformati</p><p>　　Now we show that the Independent Set problem has a solution of size k if and only if the problem

92、has a solution with total pro?t k. First, if there are kindependent nodes in graph G, there must be k jobs that do not, pairwise, con?ict. Since we constructed n parallel edges with weight 1, the Non-crossing constraint

93、 and Neighborhood constraint do not have any e?ect here. Hence, we can use k cranes to do the k jobs without violating the Job-separation constraint with total pro?t k. If we now assu</p><p>　　We can verify

94、solutions by checking crane-job assignments one by one for violation of the three constraints. Clearly, this can be done in polynomial time, so the problem is in the class NP. Since the problem has been shown to be NP-ha

95、rd, it is NP-complete and, unless P = NP, there are no polynomial algorithms to solve it optimally. It would be useful therefore to develop heuristic solutions for the problem, which we do in the following sections.</

96、p><p>　　5.3 A Probabilistic Tabu Search Approach</p><p>　　Tabu Search (TS) is a search procedure that iterates from one solution to another by moves in a neighborhood space with the help of an ada

97、ptive memory. Probabilistic Tabu Search (PTS) is a variant of TS, which places emphasis on randomization when compared with basic TS . The basic approach is to create move evaluations that include references to the tabu

98、status and other relevant biases from TS strategies using penalties, modifying underlying decision criterion and selecting the next move among</p><p>　　5.3.1 Neighborhood Structure</p><p>　　Fro

99、m an initial feasible solution obtained by a greedy method or a random crane-job assign－ment, the graph representation becomes almost edge “saturated”, i.e. we can hardly add an edge without violating the Non-crossing,

100、Neighborhood and Job-separation constraints. We can however delete an edge from the current solution and try to add other edges until it is “saturated” again. Deleting the edge which connects crane c and job j allows som