A hybrid single and dual population search procedure for the job shop scheduling problem |
| |
Authors: | Veronique SelsMario Vanhoucke |
| |
Institution: | a Faculty of Economics and Business Administration, Ghent University, Tweekerkenstraat 2, 9000 Gent, Belgium b Operations and Technology Management Centre, Vlerick Leuven Gent Management School, Reep 1, 9000 Gent, Belgium c Department of Management Science and Innovation, University College London, Gower Street, London WC1E 6BT, United Kingdom |
| |
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. |
| |
Keywords: | Job shop scheduling Genetic algorithms Scatter search |
本文献已被 ScienceDirect 等数据库收录! |
|