We can verify solutions by checking crane-job 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 NP-hard, it is NP-complete 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.

5.3  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 compared 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 different probabilities which are based on different evaluation values . In this section, we describe how it can be employed for the crane scheduling problem.

5.3.1  Neighborhood Structure

From an initial feasible solution obtained by a greedy method or a random crane-job assign－ment,  the graph representation becomes almost edge “saturated”, i.e. we can hardly add an edge without violating the Non-crossing, Neighborhood and Job-separation 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 become assignable. Obviously, these can only come from cranes and jobs which are neighbors to c and j, respectively, which do not violate the Non-crossing constraint w.r.t. all current assignments (discounting the c to j assignment). Jobs selected must also satisfy the Neighborhood and Job-separation 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 compatible job with the largest weight; the other is a random assignment which randomly picks one job from all the compatible jobs. Which scheme is chosen depends on yet another probability, p2.

5.3.2  Tabu Search Memory

TS memory structures guide the search process. There are two kinds of memory structures. One is “short-term memory”, which can prevent the search from being trapped in a local optimum and the other is “long-term memory”, which provides persification and inten－sification.

Short-term memory restricts the composition of new solutions generated. If an edge is deleted in a move, we forbid its addition in the next few moves; similarly, if an edge is added in a move, we forbid its deletion in the next few moves. Such a mechanism prevents the search from revisiting local optima in the short term and reduces the chance of cycling in the long term.

How long a restriction is in effect depends on a tabu tenure parameter, which identifies the number of iterations a particular restriction remains in force . We implemented short- term memory using a recency-based memory structure as follows. Let iter denote the current iteration number, tabu add(x, y) and tabu delete(x, y) denote future iteration values that forbid a reversal of the moves on adding edge (x, y) or deleting edge (x, y). Furthermore, let tabu add tenure and tabu delete tenure be the values of tabu tenure for these two moves. When the TS restriction is imposed, we update the recency memory by: