A hybrid single and dual population search procedure for the job shop scheduling problem
Sels, Veronique Craeymeersch, Kjeld Vanhoucke, Mario
Sels, Veronique
Craeymeersch, Kjeld
Vanhoucke, Mario
Citations
Altmetric:
Publication Type
Journal article with impact factor
Editor
Supervisor
Publication Year
2011
Journal
European Journal of Operational Research
Book
Publication Volume
215
Publication Issue
Publication Begin page
512
Publication End page
523
Publication Number of pages
Collections
Abstract
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.
Research Projects
Organizational Units
Journal Issue
Keywords
Operations & Supply Chain Management, Job Shop Scheduling, Genetic Algorithms, Scatter Search