GUIDED LOCAL SEARCH WITH SHIFTING BOTTLENECK FOR JOB-SHOP SCHEDULING

Many recently developed local search procedures for job shop schedulin g use interchange of operations, embedded in a simulated annealing or tabu search framework. We develop a new variable depth search procedur e, GLS (Guided Local Search), based on an interchange scheme and using the new concept of neighborhood trees. Structural properties of the n eighborhood are used to guide the search in promising directions. Whil e this procedure competes successfully with others even as a stand-alo ne, a hybrid procedure that embeds GLS into a Shifting Bottleneck fram ework and takes advantage of the differences between the two neighborh ood structures proves to be particularly efficient. We report extensiv e computational testing on all the problems available from the literat ure.