起重机调度与空间限制英文文献和中文翻译(6)

菜单

(b) If (x, y ) ∈ R’x,y, then Px,y’ ≤ Pak-1,bk-1+Wx,y, since Pak-1,bk-1 is the partial 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 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 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.

4.3 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 complexity is O.

5 Scheduling with the Job Separation Constraint

5.1 The Problem

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 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(Non-crossing 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(Job-separation 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.

5.2 Proof of NP-completeness

To show that this problem is NP-complete, 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 NP-hard, 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 Job-separation constraint matrix D is deﬁned as follows: For all (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 edges with weight 1, the Non-crossing constraint 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 assume that there is a solution in this problem with proﬁt k, there must be k