IMPROVING LOCAL SEARCH HEURISTICS FOR SOME SCHEDULING PROBLEMS .1.

Local search techniques like simulated annealing and tabu search are b ased on a neighborhood structure defined on a set of feasible solution s of a discrete optimization problem. For the scheduling problems P2 / / C-max, 1/prec/ Sigma C-i and 1 // Sigma T-i we replace a simple neig hborhood by a neighborhood on the set of all locally optimal solutions . This allows local search on the set of solutions that are locally op timal.