Reconciling scheduled shifts with availabilities

Question

I'm writing a program to help schedule student employees at our university based on pre-defined shifts (time blocks) and student availabilities (also time blocks).

This strikes me as similar to the Air Crew problem, except for modelling the constraint that an employee is not simply generally available: it depends on their schedule.

What modelling strategies can a more seasoned constraint programmer recommend for solving this problem?

(I'm using Gecode.)

Answer 1

Doing this the best (or a good) way surely depends on your representation of the schedule.

One simple variant is to add an binary availability matrix, where x[i,j] = 1 marks that the i'th person is available at the j'th day (or transposed depending on your representation of the schedule).

A (simple) example of this is by taking MiniZinc's standard model for nurse rostering ("tutorial/nurse.mzn", a show case for the "regular" constraint) and then add an availability matrix. Here's my version of that: http://www.hakank.org/minizinc/nurse_rostering_with_availability.mzn

Assignments for specific slots for a person must ensure that a person is available for work a specific day, shown below ("available[i,j] = 1").

% availability matrix
array[1..num_nurses, 1..num_days] of int: available = 
     array2d(1..num_nurses, 1..num_days,
    [
    % days
     1,1,0,1,1,1,1, 1,1,1,0,1,1,1, % nurses
     0,1,1,1,0,1,1, 0,1,1,1,1,1,1, 
     1,0,1,1,0,1,1, 1,0,0,1,1,0,1, 
     1,1,1,1,1,0,1, 1,0,1,1,1,1,0, 
     1,1,1,0,1,1,1, 1,1,1,1,0,1,1, 
     1,1,0,1,1,0,1, 1,1,0,1,1,1,0, 
     1,1,1,0,1,1,1, 1,1,1,0,1,1,1, 
    ]);


% ...

% for each day the must be at least 3 nurses with day shift,
% and 2 nurses with night shifht
constraint
    forall(j in 1..num_days) (
        sum(i in 1..num_nurses) ( 
              bool2int(x[i,j] == day_shift /\ available[i,j] = 1) ) >= 3
        /\
        sum(i in 1..num_nurses) ( 
              bool2int(x[i,j] == night_shift /\ available[i,j] = 1) ) >= 2
    )
;

Also, to force that a person is off duty the day he/she is not available, we set it to "off_shift" in this model.

constraint
   forall(i in 1..num_nurses, j in 1..num_days) (
       if available[i,j] = 0 then
          x[i,j] = off_shift
       else
          true
       endif
   )
;