We model an employee scheduling problem arising in service industries with flexible employee availability and flexible demand.
We devise a mixed-integer programming formulation for the problem.
We investigate a reformulation strategy based on maximal cliques in a graph representing potential employee assignments.
A decision support system based on our formulation has been implemented in a large health-care organization in Belgium.