【正文】 if there is no job in the interval [1, y] that can be assigned to crane x, then Px,y= 0. Now, we de?ne the value of the partial optimal solution Px,yfor the di?erent 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 di?erent. 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 ?rst 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 ?nal optimal is the maximum value of all partial optimal solutions obtained, ., it is max{Px,y} over all (x, y), 1 ≤ x ≤ m, 1 ≤ y ≤ n. A Proof of Optimal Substructure 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’(**). This is easy to verify since a partial optimal solution is cumulative for each crane x. As before, we have the following cases: 1. If x = 1 and y = 1, clearly P1,1= W1,1 is the optimal solution 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 3. If x 1 and y = 1, since crane cxhas to be assigned a job, and there is only one job, clearly Px,1 = Wx,1 4. If x 1 and y 1, Px,y= max{Px,y1, Pi,c+ Wx,y}, 1 ≤ i x, c = y?max{sx, si} ? 1. We 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, ., a1≤ a2≤ . . . ≤ akand b1≤ b2≤ . . . ≤ bk, by virtue of the Noncrossing constraint. Noting ak= x from the de?nition above, there are now two possibilities for Px,y’ : (a) If (x, y) ∈ R’x,y, then Px,y’ ≤ Pak,bk, since 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. Hence, we get Px,y≥ Px,y’, which contradicts the assumption Px,y’ Px,y. So Px,y is the optimal solution in this case (b) If (x, y ) ∈ R’x,y, then Px,y’ ≤ Pak1,bk1+Wx,y, since Pak1,bk1 is the partial optimal 9 solution. Obviously 1 ≤ ak1x, so we let i = ak1 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 get Pi,c≥ Pi,bk1 because of c ≥ bk?1, ., Pak1,c + Wx,y≥ Pak1,bk1,+Wx,y, and so Pak1,c+Wx,y≥Px,y’. From the de?nition Px,y= max{Px,y1,Pi,c+Wx,y}, we know Px,y≥ Px,y’ , which contradicts the assumption Px,y’ Px,y. Hence, Px,y must be the optimal solution in this case We conclude that Px,y is the optimal solution for all (x, y), 1 ≤ x ≤ m, 1 ≤ y ≤ n. The Time Complexity of the Algorithm Since, for each partial solution Px,y, we take the maximum value of the partial solutions Pi,c, 1 ≤ i x, the time plexity is O. 5 Scheduling with the Job Separation Constraint The Problem We can now study the third and most general spatial constraint — the Jobseparation 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 simultaneously. 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: 1. For all (p1, q1), (p2, q2) ∈ R, p1 p2 if 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 = max{q + sp, n}, then (p’, q’) ∈ R (Neighborhood constraint) 3. For all (p, q) ∈ R, if 1≤ p’≤ m, and Dq,q’= 1, then (p’, q’)∈ R(Jobseparation constraint) The objective is to ?nd a set R which 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. Proof of NPpleteness To show that this problem is NPplete, we use the Independent Set problem which is de?ned as follows: Given a graph G= (V, E) and a positive integer k≤ |V |, is there a V’? V such that for all u, v ∈ V’, the edge (u, v) is not in E and |V’| ≥ k? In order to prove that this problem is NPhard, we transform an arbitrary instance of the Independent Set problem to the problem in polynomial time. Assuming there are n nodes in the 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 Jobseparation constraint matrix D is de?ned as follows: For all 10 (x, y) ∈ E, Dx,y= 1, otherwise Dx,y= 0, 1 ≤ x, y ≤ n. The transformation is illustrated in Figure 5 and can be achieved in polynomial time. Now we show that the Independent Set problem has a solution of size k if and only if the problem has a solution with total pro?t k. First, if there are k independent nodes in graph G, there must be k jobs that do not, pairwise, con?ict. Since we constructed n parallel edge