Le contenu

GERAD Seminar

Learning variable neighborhood search for a job-scheduling problem

Friday June 21, 2019 from 10:30 to 11:30

Nicolas Zufferey – GSEM, Université de Genève, Switzerland

Variable neighborhood search is a local search metaheuristic that uses sequentially different neighborhood structures. This method has been successfully applied to various types of problems. In this work, variable neighborhood search is enhanced with a learning mechanism which helps to drive the search toward promising areas of the search space. The resulting method is applied to a single-machine scheduling problem with rejections, setups, and earliness and tardiness penalties. Experiments are conducted for instances from the literature. They show on the one hand the benefit of the learning mechanism (in terms of solution quality and robustness). On the other hand, the proposed method significantly outperforms state-of-the-art algorithms for the considered problem. Moreover, its flexibility allows its straightforward adaptation to other combinatorial optimization problems.

Presented jointly by the GERAD and the Chair in logistics and transportation.

Free entrance. Welcome to everyone!

Venue: Université de Montréal, André-Aisenstadt Building, Room 4488

hec.ca > Events