Network Flow Models for Days Off Scheduling

This paper studies the days off scheduling problem when the demand for staffing may differ from day to another and when the total load is fixed in advance for each employee. The scheduling problem is then to assign on-days and days-off to employees with different objectives: (1) exactly met the demand and the offer requirement (2) satisfy as best as possible the requirements. For each one, we propose a polynomial time algorithm based on network flow to construct a feasible scheduling.