A hybrid single and dual population search procedure for the job shop scheduling problem
This paper presents a genetic algorithm and a scatter search procedure to solve the well-known job shop scheduling problem. In contrast to the single population search performed by the genetic algorithm, the scatter search algorithm splits the population of solutions in a diverse and high-quality set to exchange information between individuals in a controlled way. The extension from a single to a dual population, by taking problem specific characteristics into account, can be seen as a stimulator to add diversity in the search process. This has a positive influence on the important balance between intensification and diversification. Computational experiments verify the benefit of this diversity on the effectiveness of the meta-heuristic search process. Various algorithmic parameters from literature are embedded in both procedures and a detailed comparison is made. A set of standard instances is used to compare the different approaches and the best obtained results are benchmarked against heuristic solutions found in literature.
Year of publication: |
2011
|
---|---|
Authors: | Sels, Veronique ; Craeymeersch, Kjeld ; Vanhoucke, Mario |
Published in: |
European Journal of Operational Research. - Elsevier, ISSN 0377-2217. - Vol. 215.2011, 3, p. 512-523
|
Publisher: |
Elsevier |
Keywords: | Job shop scheduling Genetic algorithms Scatter search |
Saved in:
Online Resource
Saved in favorites
Similar items by person
-
A hybrid single and dual population search procedure for the job shop scheduling problem
Sels, Veronique, (2011)
-
A hybrid single and dual population search procedure for the job shop scheduling problem
Sels, Veronique, (2011)
-
Truncated branch-and-bound guided meta-heuristics for the unrelated parallel machine
Sels, Veronique, (2011)
- More ...