A proposition for a distance measure in neighbourhood search for scheduling problems

Abstract

Meta-heuristics use iterations in which moves towards neighbourhood solutions are performed. Their power in escaping from local minima lies in accepting, according to some mechanism, solutions which worsen the current solution. It is generally accepted, that perturbations of solutions should be small. A solution for a scheduling problem is represented many times as a string of characters. The characters identify jobs to be scheduled. The use of a distance measure can enhance the search mechanism in a set of potential solutions. The notion of distance between two strings can be applied to patterns of production sequences. A distance measure is computed between permutations of the same string, which represent various single machine schedules. If cyclic permutations of the symbol sequence have distance zero, it is applicable to the Travelling Salesman Problem, where the symbol sequence represents the sequence of cities in the tour. Sometimes symbol sequences are divided into sub-strings called 'words' where the sequence of the words has no importance. This example can serve as a scheduling problem on parallel processors or as a multiple vehicle routing problem. The application of the distance measure to the single machine scheduling problem and the travelling salesman problem is shown. Also some implementation issues are discussed if the concept is applied within a genetic algorithm approach.