2018 Optimization Days

HEC Montréal, Québec, Canada, May 7 — 9, 2018

Schedule Authors My Schedule
Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402

WB5 Advances in scheduling

May 9, 2018 03:30 PM – 05:10 PM

Location: Manuvie (54)

Chaired by Reinhard Bürgy

4 Presentations

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    03:30 PM - 03:55 PM

    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, presenter, ESG UQAM
    • 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.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    03:55 PM - 04:20 PM

    Optimization of employee shift schedules with inter-department transfers

    • Dalia Attia, presenter, PhD student
    • François Soumis, Polytechnique Montréal
    • Guy Desaulniers, GERAD and Polytechnique Montreal

    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.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    04:20 PM - 04:45 PM

    Integrated bus driver rostering and days off scheduling

    • Safae Er-Rbib, presenter, GERAD, Polytechnique Montréal
    • Guy Desaulniers, GERAD and Polytechnique Montreal
    • 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.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    04:45 PM - 05:10 PM

    Employee scheduling with short demand perturbations and extensible shifts

    • Reinhard Bürgy, presenter, GERAD, Polytechnique Montréal
    • Hélène Michon-Lacaze, GERAD & Ubisoft
    • Guy Desaulniers, GERAD and Polytechnique Montreal

    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.