Séance TB8 - Programmation par contraintes et planification d'horaires / Constraint Programming and Scheduling
Jour mardi, le 05 mai 2009 Salle Hélène-Desmarais Président Louis-Martin Rousseau
Présentations
|
13h30- 13h55 |
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. |
|
13h55- 14h20 |
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. |
|
14h20- 14h45 |
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. |
|
14h45- 15h10 |
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. |