An Experimental Analysis of Local Minima to Improve Neighbourhood Search

The paper reports the results from a number of experiments on local search algorithms applied to job shop scheduling problems. The main aim was to get insights into the structure of the underlying configuration space. We consider the disjunctive graph representation where the objective function of job shop scheduling is equal to the length of longest paths. In particular, we analyse the number of longest paths, and our computational experiments on benchmark problems provide evidence that in most cases optimal and near optimal solutions do have a small number of longest paths. For example, our best solutions have one to five longest paths only while the maximum number is about sixty longest paths. Based on this observation, we investigate a non-uniform neighbourhood for simulated annealing procedures that gives preference to transitions where a decrease of the number of longest paths is most likely. The results indicate that the non-uniform strategy performs better than uniform methods, i.e. the non-uniform approach has a potential to find better solutions within the same number of transition steps. For example, we obtain the new upper bound 886 on the 20×20 benchmark problem YN1.