起重機調度與空間限制-中英文翻譯

1、附錄英文原文Crane Scheduling with Spatial ConstraintsAndrew Lim, Brian Rodrigues, Fei Xiao, and Yi ZhuAbstractIn this work, we examine port crane scheduling with spatial and separation constraints. Although common to most port operations, these constraints have not been previously studied. We assume that

2、cranes cannot cross, there is a minimum distance between cranes and jobs cannot be done simultaneously. The objective is to find a crane-to-job matching which maximizes throughput under these constraints. We provide dynamic programming algorithms, a probabilistic tabu search and a squeaky wheel opti

3、mization heuristic for solution. Experiments show the heuristics perform well compared 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.IntroductionThe Port of Singapore Authority (P

4、SA) is a large port operator located in Singapore, one of the busiest ports in the world. PSA handles 17.04 million TEUs annually or nine percent of global container tra ffic in Singapore, the worlds largest transshipment hub.PSA is concerned with maximizing throughput at its port due to limited por

5、t 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 ffic lanes, intersections, and vehicle flo

6、w control systems. In this multi-channel interface we are likely to find bottlenecks where cranes and other cargo-handling equipment (forklifts, conveyors etc.) converge.Sabria and Daganzo studied port operations which focused on berthing and cargo-handling systems. In berthing, which is a widely-an

7、alyzed port activity, queuing theory has been used widely. Traffic and vehicle-flow 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 ti

8、me.The 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 efficiency. This constituted an “open shop” parallel and identical machines problem, where jobs consist o

9、f independent, single-stage and pre-emptable tasks. A branch- and-bound method was used to minimize delay costs for this problem. Crane scheduling has also been studied in the manufacturing environment context .Commonly-found constraints affecting crane operations are absent in studies available on

10、the subject. Such constraints a ffect 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 flexi

11、bility 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 decision-making at PSA was based largely on experience and simulation techniques. While the latter is of value, analytic models ar

12、e an advantage and are not limited by experience-generated rules-of-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 Daganzo study .Prob

13、lem DescriptionDuring the time ships are berthed, various cargo-handling equipment is used to unload cargo, mostly in the form of containers. Di fferent types of cargo require di fferent handling and many ports have bulk, container, dry and liquid-bulk terminals. Cargo that is containerized can be l

14、oaded 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 comprises containers of di fferent capacities, which,

15、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

16、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 specifi

17、c 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 stowag

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

19、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 simultaneo

20、usly, 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 centr

21、al 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 to

22、gether 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 o

23、n 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 an

24、d 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 di 任 e rent sizes, and cranes have di fferent handling capacities. Since we make the assumption that any crane assigned to a job completes i

25、t, 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

26、 crane-to-job throughput. This representation is shown in Figure 1.Figure 1This 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” cons

27、traints since they are related to the relative posi tions 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.,

28、there is no temporal component in the problem. Detailed definitions will be given in the relevant sections of this paper.Non-crossing constraint: Cranes cannot cross over each other. This is a structural constraint on cranes and crane tracks.Neighborhood constraint: There is a minimum distance betwe

29、en cranes. This arises, for example, since cranes require flexibility 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.Job-separation constraint: Certain jobs cannot be done simultaneo

30、usly. For example, jobs bound for the same yard may require separation in time to avoid trailer congestion in lanes.In the following sections, we first consider these constraints separately and then simultaneously. In section 3, an O(mn) dynamic programming (DP) algorithm is given to solve the probl

31、em with only the Non-crossing 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 Non-crossing and Neighborhood constraints. In section 5, assuming all three

32、spatial constraints, we show the problem to be NP-complete and give two heuristic approaches to solve the problem a probabilistic tabu search and a squeaky wheel optimization with local search method. In section 6, we provide experimental results and compare the di 任 erent approaches.Scheduling with

33、 the Non-Crossing ConstraintThe ProblemThroughout this work, C= cc2, . . . , c m is a set of cranes and J= j 1, j2, . . . , j n 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 j 1is j 2, the neighbor

34、s of j 2are j and j ,. . . , and the neighbor of j is j -1, The same holds for the cranes.1,377n ，n ,An m x n adjacency matrix, W , is used to represent the relationships between jobs and cranes. For each W xyW , the value W xyrepresents the throughput when job j yis assigned to crane cxwhere Wxy= 0

35、 if job jycannot be assigned to crane cx. The Wxy values arise from the di 任 erent job sizes and crane capacities.We seek a solution set,R=(p, q )|1 p m, iq 0, such thatthe following constraint is satisfied: For all (p1, q1), (p2, q2) e R, p1 p2if and only if q1 q2. Viewing ps and qs, as subscripts

36、in C and J respectively, we see that any crane-job assignment in R satisfies the Non-crossing Constraint.The objective is then to find a set R which maximizes Z (p,q)e 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.Algori

37、thm DescriptionWe now provide a dynamic programming (DP) approach 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 directly and are required

38、only in implementation.The Structure and Value of an Optimal SolutionWe consider the cranes one by one. For each crane c x, we assign every job jy(i y 1, P1y：= maxW1 y, P 1y1If x 1 and y = 1, Px 1：= maxWx 1, Px-11 If x 1 and y 1, Pxy:= maxPxy-1,P x-1y, ,P x-1y-1+Wxy(1) is the basic case: If we only

39、consider the first crane and the first job, 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 consider only (2). For crane c 1and job j

40、 y, we have two choices: either, assign jyto c1, or, assign a job from j 1, . . . , j y-1to c1. This is because at most one job can be assigned to this first crane. The throughput for the first choice is W1,y while the throughput for the second choice is P1,y-1 , which represents the maximum through

41、put if we assign a job among j , j , . , j to crane c . To achieveOJ17J277 Jy-11the cumulative optimal, we choose the larger of these. (4) is the general case in the DP algorithm. For cxand job jy(x 1, y 1), we have three choices:Leave job jy unassigned . We are reduced to assigning cranes c 1, c2,

42、. . . , c x to jobs j1, j2, . . . , jy-1. By induction, the optimal value is then Pxy-1;Leave crane cx unassigned . We are reduced to assigning cranes c1, c2, . . . , cx-1 to jobs j1, j2, . . . , jy. By induction, the optimal value is then Px-1y;Assign crane cxto job jy(or, leave both unassigned if

43、they are not assignable to each other). In this case, the total throughput is the throughput from this assignment plus the throughput from assigning cranes c 1, c2, . . . , c x-1 to jobs j 1, j2, . . . , j y-1. Hence, the value is Px-1y-1+Wxy.Taking the maximum of these throughput values, the optima

44、l solution is then the final partial optimal solution Pm n obtained.A Proof of Optimal SubstructureWe provide an outline a proof that the problem defined in this section possesses optimal substructures necessary in using DP. An important property for Pxyis: PxyPx，y,if x x，and y y(*), which is easily

45、 verified since P xy Pxy1 and Pxy Px1y. We can now verify the four cases given above by induction:If x = 1 and y = 1, clearly P1,y = Wx 1is the only solution and must beoptimalIf (x, y) e Rx,y, thenPxy，Pak 1b 1 since x -1 ak -1 y-i bk -1. So P ，P + W , we get P P ，, ,Jx,y x-1,y-1 x,yx,y x-1,y-1x,y x

46、,y x,y which contradicts our assumption Px y， Pxy. Hence, Pxy is the optimal solution.We can conclude that Pxy is the optimal solution for all (x, y), 1 x m, 1 y n,The Time Complexity of the AlgorithmThe computation for every partial solution Pxy is in constant time, so the time complexity for this

47、algorithm is O(mn).Scheduling with the Neighborhood ConstraintThe ProblemIn this problem, both the Non-crossing constraint and the Neighborhood constraint are considered. In addition to the Non-crossing constraint, we use the set S= s 1, s2,., sm to represent the Neighborhood constraint associated w

48、ith the cranes. Here s x= k if crane cxperforms job jyand job jz(a z b, z= y) cannot be worked on by any other crane, where a = maxi, y - kand b = miny + k, m. In other words, if crane c xperforms job jy, the job “interval” centered at y with length 2k + 1 is affe cted by crane cxwhen sx= k.We seek

49、a solution set R = (p, q)|i p m, 1 q 0 satisfying:For all (p1, q1), (p2, q2) e R, p1 p2if and only if q1 q2(Non-crossing constraint)For all (p, q) e R, if 1 p m and p= p, and a q b, where a = maxi, q - s p and b = minq + sp, n, then (p, q)e R (Neighborhood constraint)Our objective is to find R that

50、maximizes the total weight Zp,q) e rWp,q where each job is assigned to at most one crane and each crane is assigned to at most one job.Algorithm DescriptionWe follow the approach in section 3.2 here.The Structure and Value of an Optimal SolutionWe continue to consider the cranes one by one. For each

51、 crane c , we attempt to xassign every job j y(1 y n) to it and compute 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) e Rx y may not hold. However, di fferent from the definition used i

52、n the previous section, crane x must be assigned some job j (1 j y) for P xy, i.e., there must be an edge (x, j) e Rxy, where (1 j 1, P1,y:= maxW1y,P1y-1If x 1 and y = 1, Px 1=Wx 1If x 1 and y 1, Pxy:= maxPxy-1 P ic +Wx y, 1 i x, c = y- maxsx, si - 1.(1) is the basic case and (2) and (3) are the spe

53、cial cases. (2) has been explained in the previous section. (3) is di任erent. Since we require for Pxythat crane cxmust be assigned job jy, we have no choice but to assign this job to the current crane when there is only job available. The induction step in (4) is somewhat complex. In the first case,

54、 we keep job j yunassigned, so we are reduced to assigning cranes c 1, c2, . . . , c x to jobs j 1, j , . , j ; hence, we obtain P . In the second case, since we assigned job j to crane c , J 277 J y77x,yT7O J J yx，the Neighborhood constraint for cxmust be considered. Also, we must consider the Neig

55、hborhood constraint for the cranes c 1, c2, . . . , c x which are assigned to jobs. The Non-crossing constraint simplifies the computation leaving us only to check the neighborhood constraint for the “l(fā)argest labeTcrane assigned and is the reason the c value is needed in the formula.The final optima

56、l is the maximum value of all partial optimal solutions obtained,e., it is maxPxy over all (x, y), 1 x m, 1 y Pxy if y y (*). This is easy to verify since a partial optimal solution is cumulative for each crane x. As before, we have the following cases:If x = 1 and y = 1, clearly P11= W11is the opti

57、mal solutionIf x = 1 and y 1, only one crane is involved, so the Neighborhood constraint does not take the effe ct. The proof is then as given in the previous sectionIf x 1 and y = 1, since crane cxhas to be assigned a job, and there is only one job, clearly Px 1 = Wx 1If x 1 and y 1, P xy= maxPx y-

58、1, Pic+ Wx y, 1 i Px y and the solution set corresponding to Pxy is Rx,y=(ca1,j b1), (ca2,j b2), . . . , (c ak,j bk). Here, we can take this set to be ordered, i.e., a1 a2 . . . akand b1 b2 . . . bk, by virtue of the Non-crossing constraint. Noting ak= x from the definition above, there are now two

59、possibilities for Px y :If (x, y) ERxy, then Pxy Pakbk，since Pakbk is the partial optimal solution. Hence, Pxy Pxbk since y - 1 bk(job jyis unassigned). So Pxy-1 Pxy. By the recursive definition, Pxy Pxy-1. Hence, we get Pxy Pxy, which contradicts the assumption Pxy Pxy. So Pxy is the optimal soluti

60、on in this caseIf (x, y ) e Rx,y, then PJ Pak-1,bk-1+Wx, y, since Pak-1,bk-1 is the partial optimal solution. Obviously 1 ak-ix, so we let i = ak-1 and c = y-maxsx, si - 1. We know bk-i Pibk-1 because of c b k-1, i.e., Pak-1,c + Wxy Pak1bk1,+Wxy, and so Pak1c+WxyPxy,. From the definition Pxy= maxP ,