Local search for multiprocessor scheduling: How many moves does it take to a local optimum?

We analyze two local search algorithms for multiprocessor scheduling. The first algorithm is a job interchange algorithm for identical parallel machines due to Finn and Horowitz. We construct instances for which this algorithm takes a quadratic number of iterations. This contradicts the original analysis of Finn and Horowitz who claimed a linear number of iterations. The second algorithm adds an additional rule to the Finn and Horowitz algorithm. Even for n jobs on m uniformly related machines, this modified algorithm takes only O(nm) iterations.