Scheduling trainees at a hospital department using a branch-and-price approach

Scheduling trainees (graduate students) is a complicated problem that has to be solved frequently in many hospital departments. We will describe a trainee-scheduling problem encountered in practice (at the ophthalmology department of the university hospital Gasthuisberg, Leuven). In this problem, a department has a number of trainees at its disposal, which assist specialists in their activities (surgery, consultation, etc.). For each trainee one has to schedule the activities in which (s)he will assist during a certain time horizon, usually one year. Typically, this kind of scheduling problem is characterized by four types of constraints: work covering constraints, formation requirements, non-availability constraints and setup restrictions. In this paper, we will describe an exact branch-and-price method to solve the problem to optimality.