Back

Session TB8 - Programmation par contraintes et planification d'horaires / Constraint Programming and Scheduling

Day Tuesday, May 05, 2009
Room Hélène-Desmarais
President Louis-Martin Rousseau

Presentations

01h30 PM-
01h55 PM
Grammar-Based Integer Programing Models for Multi-Activity Shift Scheduling
  Marie-Claude Côté, École Polytechnique de Montréal, Mathématiques et génie industriel, C.P. 6079, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3A7
Bernard Gendron, Université de Montréal, Informatique et de recherche opérationnelle/CIRRELT, Montréal, Québec, Canada
Louis-Martin Rousseau, École Polytechnique de Montréal, MAGI et CIRRELT, C.P. 6079, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3A7

We present an implicit formulation for shift scheduling problems, using context-free grammars to model restrictions in the planning of shifts. From a grammar, we generate an integer programming model allowing the same set of shifts as Dantzig's set covering model. Our efficient method can encode constraints such as work sretch restrictions as well as multi-activity cases.


01h55 PM-
02h20 PM
An Optimal Constraint Programming Approach to the Open-Shop Problem
  Arnaud Malapert, École Polytechnique de Montréal, MAGI, C.P. 6079 , Succ Centre-Ville, Montréal, QC, Canada, H3C 3A7
Christelle Guéret, École des Mines de Nantes, IRCCyN, UMR CNRS 6597, France
Narendra Jussien, École des Mines de Nantes, LINA , UMR CNRS 6241, France
André Langevin, École Polytechnique de Montréal, Mathématiques et de génie industriel, C.P. 6079, succursale Centre-ville, Montréal, Québec, Canada, H3C 3A7
Louis-Martin Rousseau, École Polytechnique de Montréal, MAGI et CIRRELT, C.P. 6079, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3A7

We present an optimal constraint programming approach for the Open-Shop problem, which integrates recent constraint propagation and branching techniques with new upper bound heuristics. Randomized restart policies combined with nogood recording allow to search diversification and learning from restarts. The proposed solving technique outperforms the other approaches published so far on a wide range of benchmarks.


02h20 PM-
02h45 PM
A Hybrid LS/CP Approach to Solve the Weekly Log-Truck Scheduling Problem.
  Nizar El Hachemi, École Polytechnique de Montréal, Mathématiques et génie industriel, C.P. 6079, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3A7
Michel Gendreau, Université de Montréal, Informatique et recherche opérationnelle, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3J7
Louis-Martin Rousseau, École Polytechnique de Montréal, MAGI et CIRRELT, C.P. 6079, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3A7

We present the log-truck scheduling problem, which combine routing and scheduling of trucks. This problem includes aspects such as pick-up and delivery, multiple products, inventory stock, multiple supply points and multiple demand points. We developped a decomposed approach to solve the weekly version, in two phases. A hybrid approach combining LS and CP has been used.


02h45 PM-
03h10 PM
Checking the Feasibility of the Dial-a-Ride Problem Using Constraint Programming
  Gerardo Berbeglia, HEC Montréal, CIRRELT, 3000 Côte-Sainte-Catherine, Montréal, QC, Canada, H3T 2A7
Gilles Pesant, École Polytechnique de Montréal, Département de génie informatique et génie logiciel, C.P. 6079 Succ Centre Ville, Montreal, Quebec, Canada, H3C 3A7
Louis-Martin Rousseau, École Polytechnique de Montréal, MAGI et CIRRELT, C.P. 6079, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3A7

We develop a constraint programming algorithm to check whether a given instance of the Dial-a-Ride Problem (DARP) is feasible. For this, we present some DARP relaxations and then develop filtering algorithms for each of them. Computational results show that the filtering algorithms are effective and that the resulting algorithm is advantageous on the more constrained instances.


Back