【正文】 ) ∈ 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 edges with weight 1, the Noncrossing 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 Jobseparation 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 jobs selected without violating the Jobseparation constraint. There must be k nodes that are not connected by any edges and therefore a set of nodes of size k. We can verify solutions by checking cranejob assignments one by one for violation of the three constraints. Clearly, this can be done in polynomial time, so the problem is in the class NP. Since the problem has been shown to be NPhard, it is NPplete and, unless P = NP, there are no polynomial algorithms to solve it optimally. It would be useful therefore to develop heuristic solutions for the problem, which we do in the following sections. A Probabilistic Tabu Search Approach Tabu Search (TS) is a search procedure that iterates from one solution to another by moves in a neighborhood space with the help of an adaptive memory. Probabilistic Tabu Search (PTS) is a variant of TS, which places emphasis on randomization when pared with basic TS . The basic approach is to create move evaluations that include references to the tabu status and other relevant biases from TS strategies using penalties, modifying underlying decision criterion and selecting the next move among those neighborhood moves with di?erent probabilities which are based on di?erent evaluation values . In this section, we describe how it can be employed for the crane scheduling problem. Neighborhood Structure From an initial feasible solution obtained by a greedy method or a random cranejob assign－ ment, the graph representation bees almost edge ―saturated‖, . we can hardly add an edge without violating the Noncrossing, Neighborhood and Jobseparation constraints. We can however delete an edge from the current solution and try to add other edges until it is ―saturated‖ again. Deleting the edge which connects crane c and job j allows some cranes and jobs to bee assignable. Obviously, these 11 can only e from cranes and jobs which are neighbors to c and j, respectively, which do not violate the Noncrossing constraint . all current assignments (discounting the c to j assignment). Jobs selected must also satisfy the Neighborhood and Jobseparation constraints. After deleting the edge connecting c to j, we consider each neighbor of c from these feasible neighbors together with c, one by one. For each crane, we assign a probability p1for it to be selected for a job. For each selected crane, we have two types of assignments: one is a greedy assignment which selects a patible job with the largest weight。 ? 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 ?nal partial optimal solution Pm,n obtained. A Proof of Optimal Substructure We provide an outline a proof that the problem de?ned 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 veri?ed 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