HEC Montréal, Canada, May 2 - 4, 2011

2011 Optimization Days

HEC Montréal, Canada, 2 — 4 May 2011

Schedule Authors My Schedule

TA11 Ordonnancement II / Scheduling II

May 3, 2011 10:30 AM – 12:10 PM

Location: Rona

Chaired by Gerd Finke

3 Presentations

  • 10:30 AM - 10:55 AM

    An Adaptive Large Neighborhood Search for the National Hockey League Scheduling Problem

    • Elivelton Bueno, presenter, École Polytechnique de Montréal
    • Jacques Ferland, Université de Montreal
    • Michel Gendreau, Polytechnique Montréal

    Sports scheduling has provided numerous challenging applications for Combinatorial Optimization techniques. In this talk, we present an Adaptive Large Neighborhood Search algorithm to deal with the scheduling of games for the regular-season of the National Hockey League. In addition to typical scheduling constraints, this application features many specific requirements and raise appealing computational issues. In particular, we address some methodological challenges and present results on computational experiments.

  • 10:55 AM - 11:20 AM

    Solving the University Examination Timetabling Using a Parallel Hybrid Meta-Heuristics Approach

    • Malek Mouhoub, University of Regina
    • Ali Hmer, presenter, Univ. of Regina

    We propose a multi-phase parallel Hybrid meta-heuristics approach, integrating Local Search, Simulated Annealing and Great Deluge algorithms; for solving the University Examination Timetabling. When evaluated on problem instances taken from the ITC 2007 competition, this proposed approach was capable of producing comparable results to those returned by the best solvers.

  • 11:20 AM - 11:45 AM

    The Identical Coupled-Task Scheduling Problem

    • Gerd Finke, presenter, Laboratoire G-SCOP
    • Nadia Brauner, Laboratoire G-SCOP
    • Vassilissa Lehoux-Lebacque, Laboratoire G-SCOP

    General coupled-task problems originate in radar systems. Their complexity status is known with exception of the identical coupled-task case: multiple copies of a two-operation task, where the two operations are separated by a fixed distance, are to be processed with minimal makespan on a single machine. We shall present a polynomial complexity proof for the cyclic case.