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 nd a crane-to-job matching which maximizes throughput under these constraints. We provide dynamic programming algorithms, a probabilistic tabu search and a squeaky wheel optim
3、ization 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.1 IntroductionThe Port of Singapore Authority (
4、PSA) 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 trac in Singapore, the worlds largest transshipment hub. PSA is concerned with maximizing throughput at its port due to limited port
5、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 trac lanes, intersections, and vehicle ow contro
6、l systems. In this multi-channel interface we are likely to nd 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-analyzed por
7、t activity, queuing theory has been used widely. Trac 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 time.The objectiv
8、e 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 eciency. This constituted an “open shop” parallel and identical machines problem, where jobs consist of independent, sin
9、gle-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 aecting crane operations are absent in studies available on the subject. Such co
10、nstraints aect 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
11、. 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 are an advantage and are no
12、t 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 .2 Problem DescriptionDuring t
13、he time ships are berthed, various cargo-handling equipment is used to unload cargo, mostly in the form of containers. Dierent types of cargo require dierent handling and many ports have bulk, container, dry and liquid-bulk terminals. Cargo that is containerized can be loaded and unloaded in a fewer
14、 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 dierent capacities, which, whether in ships or in yards, a
15、re parcelled into xed areas for access to cranes. For example, cargo placed in specic 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 b
16、y 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 specic trailers at certain times. In addit
17、ion, 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,
18、 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 diculty is present in scheduling cranes. For example, although a set of jobs may be assigned to a certain crane, it may not be possible fo
19、r 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 t
20、o 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 a
21、ssignment 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 b
22、e up to ve ships with four to seven cranes per ship and a number of jobs depending on the size and conguration of ships. Jobs have a prot 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 w
23、hich 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 al
24、l operations. Hence, once jobs and resources are assigned for the time period no update is necessary.Jobs come in dierent sizes, and cranes have dierent handling capacities. Since we make the assumption that any crane assigned to a job completes it, the throughput or prot, for a given crane-to-job a
25、ssignment, is a xed 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 dene the weights of connecting edges to be crane-to-job throughput. This representation is shown in F
26、igure 1.Figure 1This matching problem is interesting because, in practice, a number of spatial constraintsarise for cranes 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 c
27、ranes and jobs. Our objective is to nd 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 denitions
28、 will be given in the relevant sections of this paper.1. Non-crossing 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 exi
29、bility in space to perform jobs and/or for safety reasons. The eect of this constraint is that neighboring jobs may be aected and may not be assignable to other cranes.3. Job-separation constraint: Certain jobs cannot be done simultaneously. For example, jobs bound for the same yard may require sepa
30、ration 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 Non-crossing constraint where m is the number of
31、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 spatial constraints, we show the problem to be NP-complete and giv
32、e 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 dierent approaches.3 Scheduling with the Non-Crossing Constraint3.1 The ProblemThroughout this work, C=
33、 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, i.e., the neighbor of j1is j2, the neighbors of j2are j1and j3,. . . , and the neighbor of jnis jn1, The sam
34、e holds for the cranes.An m n adjacency matrix, W , is used to represent the relationships between jobs and cranes. For each Wx,yW , 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 diere
35、nt job sizes and crane capacities.We seek a solution set,R=(p, q )|1p m, 1qn, Wp,q 0, such that the following constraint is satised: For all (p1, q1), (p2, q2)R, p1 p2if and only if q1 1, P1,y:= maxW1，y, P 1,y-13. If x 1 and y = 1, Px，1:= maxWx,1, Px-1,1 4. If x 1 and y 1, Px,y:= maxPx,y-1,P x-1,y ,
36、P x-1,y-1 +Wx,y(1) is the basic case: If we only consider the rst crane and the rst 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 n
37、eed consider only (2). For crane c1and job jy, we have two choices: either, assign jyto c1, or, assign a job from j1, . . . , jy1to c1. This is because at most one job can be assigned to this rst crane. The throughput for the rst choice is W1,y while the throughput for the second choice is P1,y1 , w
38、hich represents the maximum throughput if we assign a job among j1, j2, . . . , jy-1 to crane c1. To achieve the 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
39、to assigning cranes c1, c2, . . . , cx to jobs j1, j2, . . . , jy-1. By induction, the optimal value is then Px,y-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-1,y;Assign crane cxto job jy(
40、or, leave both unassigned if 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 c1, c2, . . . , cx-1 to jobs j1, j2, . . . , jy-1. Hence, the value is Px-1,y-1+Wx,y.Taking the maximum of these th
41、roughput values, the optimal solution is then the nal partial optimal solution Pm,n obtained.3.2.2 A Proof of Optimal SubstructureWe provide an outline a proof that the problem dened in this section possesses optimal substructures necessary in using DP. An important property for Px,yis: Px,yPx,y,if
42、x xand y y(*), which is easily veried since Px,y Px,y-1 and Px,y Px-1,y. We can now verify the four cases given above by induction:1. If x = 1 and y = 1, clearly P1,y= Wx,1is the only solution and must be optimal2. If (x, y)Rx,y, thenPx,yPak-1,bk-1+Wx,y. By (*), we know Px-1,y1 Pak-1,b-1 since x 1 a
43、k-1, y-1 bk-1. So Px,y Px-1,y-1+Wx,y. Because Px,yPx-1,y-1+ Wx,y, we get Px,y Px,y , which contradicts our assumption Px,y Px,y. Hence, Px,y is the optimal solution.We can conclude that Px,y is the optimal solution for all (x, y), 1 x m, 1 y n,3.3 The Time Complexity of the AlgorithmThe computation
44、for every partial solution Px,y is in constant time, so the time complexity for this algorithm is O(mn).4 Scheduling with the Neighborhood Constraint4.1 The 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= 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
陕公网安备 61072602000132号 违法和不良信息举报：0916-4228922