Improving local search heuristics for some scheduling problems—I Original Research Article

Local search techniques like simulated annealing and tabu search are based on a neighborhood structure defined on a set of feasible solutions of a discrete optimization problem. For the scheduling problems P2 ∥ Cmax, 1 ¦ prec¦ ∑ Ci and 1 ∥ ∑ Ti we replace a simple neighborhood by a neighborhood on the set of all locally optimal solutions. This allows local search on the set of solutions that are locally optimal.