【正文】 s 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 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 a?ected 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 ?nd 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, di?erent from the de?nition 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,