《2016 A hybrid single and dual population search procedure for the job shop scheduling problem》.pdf

European Journal of Operational Research 215 (2011) 512–523 Contents lists available at ScienceDirect European Journal of Operational Research journal homepage: www.else /locate/ejor Discrete Optimization A hybrid single and dual population search procedure for the job shop scheduling problem Veronique Sels a, Kjeld Craeymeersch a, Mario Vanhoucke a,b,c,⇑ 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 a r t i c l e i n f o a b s t r a c t Article history: This paper presents a genetic algorithm and a scatter search procedure to solve the well-known job shop Received 7 July 2010 scheduling problem. In contrast to the single population search performed by the genetic algorithm, the Accepted 26 June 2011 scatter search algorithm splits the population of solutions in a diverse and high-quality set to exchange Available online 3 July 2011 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 Keywords: search process. This has a positive influence on the important balance between intensific