03:30 PM - 03:55 PM
A cutting plane algorithm for resource constrained project scheduling problems without preemption
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.
03:55 PM - 04:20 PM
Optimization of employee shift schedules with inter-department transfers
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.
04:20 PM - 04:45 PM
Integrated bus driver rostering and days off scheduling
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.
04:45 PM - 05:10 PM
Employee scheduling with short demand perturbations and extensible shifts
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.