Staff Assignment Using Network Flow Techniques

Staff scheduling, also known as timetabling, is a task to be done in any organization with several employees. In this paper, we revisit its modeling as a minimum cost maximum flow problem in a network, which has the decisive advantage to be solvable with a polynomial time algorithm. Besides the usual availability and skills constraints, we consider additional constraints: targeted workload, satisfaction of employees seen as rotation constraints, tasks requiring several employees, pairs of employees which can not be assigned to a same task. We consider several cost specifications: types of employees, overtime, delayed tasks, profit associated with the execution of a task. We also analyze the limits of our model, showing types of constraints that transform the problem into an NP-hard problem