4 présentations

• 
  15h30 - 15h55

  A cutting plane algorithm for resource constrained project scheduling problems without preemption

  • Janniele Aparecida Soares Araujo, CIRRELT and Federal University of Ouro Preto (UFOP)
  • Sanjay Dominik Jena, prés., Université du Québec à Montréal
  • Bernard Gendron, Université de Montréal, CIRRELT
  • Haroldo Gambini Santos, Federal University of Ouro Preto

  Resource Constrained Project Scheduling Problems without preemption are NP-hard combinatorial optimization problems. A solution consists in a schedule of jobs with specific execution modes respecting precedence constraints and resource usage limits. In this work we propose a cutting plane algorithm to generate strong bounds and improve the linear programming relaxations.

• 
  15h55 - 16h20

  Optimization of employee shift schedules with inter-department transfers

  • Dalia Attia, prés., PhD student
  • Francois Soumis, GERAD et Polytechnique
  • Guy Desaulniers, GERAD - Polytechnique Montréal

  Employee scheduling integer program is intractable for large real-life instances. We propose a three-phase heuristic, solving small integer sub-programs. The first phase identifies probable transfers needs.
  The second creates for each department, employee schedules using previously gathered information. The third globally fulfills remaining demand. Results and comparison with other similar work are presented. The results show that the heuristic scale very well for very large instances.

• 
  16h20 - 16h45

  Integrated bus driver rostering and days off scheduling

  • Safae Er-Rbib, prés., GERAD, Polytechnique Montréal
  • Guy Desaulniers, GERAD - Polytechnique Montréal
  • Issmail El Hallaoui, GERAD, Polytechnique Montréal

  We consider the problem of assigning duties and days off simultaneously to bus driver rosters in order to balance as much as possible the weekly working time among the rosters while satisfying various working rules concerning mostly the rest periods between two working days, and the number of days off per week. We model this problem as an integer program and we report computational results obtained on real-world instances.

• 
  16h45 - 17h10

  Employee scheduling with short demand perturbations and extensible shifts

  • Reinhard Bürgy, prés., GERAD, Polytechnique Montréal
  • Hélène Michon-Lacaze, GERAD & Ubisoft
  • Guy Desaulniers, GERAD - Polytechnique Montréal

  We consider a practice-inspired employee scheduling problem under demand uncertainty arising in retail stores. In particular, the scheduling problem includes short demand perturbations, potentially leading to an increase of the demand in some given time intervals, and the possibility of assigning overtime work by extending shifts to cope with a lack of employees in real-time. The goal is to find a schedule minimizing the sum of demand fulfillment and employee preference-related costs, where each cost term is expressed as a convex function of an appropriate variable. The cost of a schedule is evaluated using a simulation-based approach that reproduces the materialization of demand perturbations and shift extensions. In order to find high-quality robust employee schedules, we propose two integer programming models taking into account the demand uncertainty and shift extension possibilities in different ways. Extensive computational results on retail store instances reveal that the two proposed models improve the schedule quality significantly when compared with a basic non-robust model.