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 (Bit 19 (1979) 312). 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.