www.uhasselt.be
DSpace

Document Server@UHasselt >
Research >
Research publications >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/6752

Title: A proposition for a distance measure in neighbourhood search for scheduling problems
Authors: JANSSENS, Gerrit
Issue Date: 2004
Citation: Journal of the Chinese Institute of Industrial Engineers, 21(3). p. 262-271
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.
URI: http://hdl.handle.net/1942/6752
Link to publication: http://www.jciie.ciie.org.tw:8080/archive/abstract/English/v21/21_3/21_3_6.pdf
Category: A1
Type: Journal Contribution
Validation: vabb, 2010
Appears in Collections: Research publications

Files in This Item:

There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.