Analyzing the behavior of local search methods has received considerable attention over the last two decades. One interesting question is how the simplest form of local search, i.e., iterative improvement, behaves w.r.t. a certain neighborhood both in quality of the solution as well as number of iterations needed to obtain a local optimal solution.
In this talk, we consider the basic scheduling problem in which n jobs need to be scheduled on m identical machines so as to minimize the makespan, i.e., the completion time of the last job. Finn and Horowitz (1979) showed that the folklore jump neighborhood, that moves one job from its machine to another machine, yields a (2-2/(m+1))-approximation and this was shown to be tight by Schuurman and Vredeveld (2001/2007). Brucker, Hurink and Werner (1996/1997) showed that the iterative improvement procedure needs O(n^2) iterations to obtain a jump optimal solution, which was shown to be tight by Hurkens and Vredeveld (2003).
Schuurman and Vredeveld (2007) left as an open question to bound the number of iterations to obtain a swap-optimal solution.
In this talk, we consider the k-swap neighborhood, which is a generalization of the jump and the swap neighborhood. In the k-swap neighborhood, a neighboring solution is obtained by selecting at most k jobs scheduled on at most two machines and then interchanging the machine allocation of these jobs. For k=1 this is equivalent to the jump neighborhood and for k=2 it is equivalent to the swap neighborhood.
We analyze the number of iterations needed to obtain a k-swap optimal solution by iterative improvement; thereby answering the question posed in Schuurman and Vredeveld.
This is joint work with Lars Rohwedder and Ashkan Safari.
