机械专业外文翻译----起重机调度与空间限制(编辑修改稿)

机械专业外文翻译----起重机调度与空间限制(编辑修改稿)内容摘要：

different cases: 1. If x = 1 and y = 1, P1， 1:= W1， 1 6 2. If x = 1 and y 1, P1,y:= max{W1， y’, P 1,y 1} 3. If x 1 and y = 1, Px， 1:= max{Wx,1, Px1,1 } 4. If x 1 and y 1, Px,y:= max{Px,y1,P x1,y’ ,P x1,y1 +Wx,y} (1) is the basic case: If we only 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, ., when there is only one node in each part of the bipartite graph. As these are symmetrical, we need consider 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 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 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 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, . . . , cx1 to jobs j1, j2, . . . , jy. By induction, the optimal value is then Px1,y。 • Assign crane cxto job jy(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, . . . , cx1 to jobs j1, j2, . . . , jy 1. Hence, the value is Px1,y1+Wx,y. Taking the maximum of these throughput values, the optimal solution is then the final partial optimal solution Pm,n obtained. A Proof of Optimal Substructure We provide an outline a proof that the problem defined 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’(*), which is easily verified since Px,y≥ Px,y 1 and Px,y≥ Px1,y. We can now verify the four cases given above by induction: 1. If x = 1 and y = 1, clearly P1,y = Wx,1 is the only solution and must be optimal 2. If (x, y)∈ R’x,y, thenPx,y’≤Pak1,bk1+Wx,y. By (*), we know Px1,y−1 ≥Pak1,b1 since x − 1 ≥ ak1, y1 ≥ bk1. So Px,y’≤ Px1,y 1+Wx,y. Because Px,y≥Px1,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, 7 The Time Complexity of the Algorithm The putation for every partial solution Px,y is in constant time, so the time plexity for this algorithm is O(mn). 4 Scheduling with the Neighborhood Constraint The Problem In this problem, both the Noncrossing constraint and the Neighborhood constraint 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 affected 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 find 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, different from the definition 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)。 if there is no job in the interval [1, y] that can be assigned to crane x, then Px,y= 0. Now, we define the value of the partial optimal solution Px,yfor the different cases: 1. If x = 1 and y = 1, P1,1＝ W1,1 2. If x = 1 and y 1, P1,y:= max{W1,y,P1,y1} 3. If x 1 and y = 1, Px,1=Wx,1 4. If x 1 and y 1, Px,y:= max{Px,y1,P i,c +Wx,y}, 1 ≤ i x, c = y− max{sx, si} − 1. 8 (1) is the basic case and (2) and (3) are the special cases. (2) has been explained in the previous section. (3) is different. Since we require for Px,ythat 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 plex. In the first case, we keep job jyunassigned, so we are reduced to assigning cranes c1, c2, . . . , cx to jobs j1, j2, . . . , jy。 hence, we obtain Px,y1. In the second case, since we assigned job jyto crane cx, the Neighborhood constraint for cxmust be considered. Also, we must consider the Neighborhood constraint for the cranes c1, c2, . . . , cx which are assigned to jobs. The Noncrossing constraint simplifies the putation leaving us only to check the neighborhood constraint for the ―largest label‖crane assigned and is the reason the c value is needed in the formula. The final optimal is the maximum value of all partial optim。