4 Presentations

• 
  09:00 AM - 09:25 AM

  Une approche à deux phases pour la résolution du problème de confection d’horaires multi-départements.

  • Emelyne Munezero, presenter, Polytechnique Montréal
  • Guy Desaulniers, GERAD - Polytechnique Montréal
  • Claudio Contardo, GERAD - ESG UQÀM

  Nous proposons une approche à deux phases pour résoudre le problème de confection d’horaires avec transferts d'employés entre les départements. Un modèle séquentiel département par département est utilisé dans la première phase sans permettre les transferts. La solution obtenue est alors ré-optimisée dans la seconde phase en permettant les transferts entre les départements. Différentes approches de résolution sont proposées pour la seconde phase. Des résultats numériques seront présentées pour comparer chaque approche.

• 
  09:25 AM - 09:50 AM

  Shift Scheduling with Employees' Preferences

  • Lê Nguyên Hoang, presenter, Polytechnique Montréal

  We present a shift scheduling program over a 1-week horizon for 29 employees, which includes employees' preferences. We use the MACBETH software to help employees enter their preferences, hence defining linear multi-attribute utility functions. These are inputs of a integer linear program in two phases. The first phase computes the optimal costs without preferences. Then, the second phase maximizes employees' utilities while guaranteeing a small gap from optimal costs. Crucially though, for this maximization to make sense, employees' utilities must be normalized. We discuss how to do so in a meaningful way.

• 
  09:50 AM - 10:15 AM

  A Decomposition Scheme to Solve Multi-Department Shift Scheduling Problems

  • Sana Dahmen, presenter, Université Laval
  • Guy Desaulniers, GERAD - Polytechnique Montréal
  • Monia Rekik, Université Laval
  • Francois Soumis, GERAD et Polytechnique

  We present a decomposition scheme to construct multi-department personalized schedules given some prior transfer decisions. We identify specific acyclic transfer graphs to decompose the NP-hard problem into a set of tractable sub-problems. These sub-problems are solved sequentially and framed within a rolling horizon procedure.

• 
  10:15 AM - 10:40 AM

  Grammar and Network based Column Generation for Multi-activity Tour Scheduling problems

  • Maria-Isabel Restrepo-Ruiz, presenter, Polytechnique Montréal
  • Louis-Martin Rousseau, Polytechnique Montréal
  • Bernard Gendron, Université de Montréal, CIRRELT

  We present a grammar and network based column generation approach to solve tour scheduling problems in a multi-activity context. In order to reach integrality, the column generation procedure is embedded into a branch-and-price method. Computational results show that our approach is able find high-quality solutions for all the instances tested.