Constraint Programming based Column Generation for Employee Timetabling

Employee timetabling problems form a large class of widely-encountered issues in service organizations. Often, the issue lies in the design of work shifts, which often have to satisfy many complex regulatory constraints coming from legislation and contractual agreements. The client, Omega Optimisation, was looking for a unified and flexible solution for these shift scheduling problems which address legal issues, activity requirements and labour costs. The approach developed by the research team at École Polytechnique de Montréal involved an algorithm consisting of a hybridization of constraint programming techniques and linear programming, which added flexibility to Omega’s current scheduling modules. The research team had the opportunity to evaluate their approach on a scheduling problem submitted by a client of the partner company and found that their approach was able to be quickly adapted to the regulation constraints of the problem.

Faculty Supervisor:

Dr. Gilles Pesant

Student:

Sophie Demassey

Partner:

Omega Optimisation

Discipline:

Engineering

Sector:

University:

Polytechnique Montréal

Program: