An acyclic days-off scheduling problem

This paper studies the days off scheduling problem when the demand for staffing fluctuates from day to another and when the number of total workdays is fixed in advance for each employee. The scheduling problem is then to allocate rests to employees with different days off policies: (1) two or three consecutive days off for each employee per week and (2) at least three consecutive days off for each employee per month. For each one, we propose a polynomial time algorithm to construct a solution if it exists. Received: April 2005 / Revised version: October 2005 AMS classification: 60K25, 60K30