% Scheduling Shift-Work
% Michael Stone
% February 23, 2013

## Introduction

I first became interested in using constraint programming to schedule
shift-work about 18 months ago (June 4, 2011) following a conversation with a
friend who was, at the time, the chief resident of a local pediatrics unit.

More recently, the problem has taken on new urgency for me as a result of my
having become responsible both for participating in and for scheduling some
shift-work of my own.

Anyhow, here's what I've come up with so far...

## Classical Scheduling

The data for a simple classical scheduling problem include:

  * a partial order $\leq$ on tasks,
  * a function $c : T \rightarrow C$ from tasks to cost vectors, and
  * a distinguished cost vector, $R : C$ called the resource constraint.

A solution $f : T \rightarrow 2^E$ is an assignment of tasks to
sets of episodes such that the solution is:

  * faithful: $t_1 \leq t_2 \implies \forall e_1 \in f\,(t_1), \forall e_2 \in f\,(t_2), e_1 < e_2$

  * costful: $\forall e \sum\limits_{t \in f^{-1}(e)} c\,(t) \leq R$ elementwise, and

  * adequate: $\forall t \sum\limits_{e \in f(t)} e = c\,(t)$

A good solution also minimizes some loss function $L$, like "total duration".

[Aurora]: http://www.stottlerhenke.com/products/aurora/index.htm

## MINION

[MINION] is a free and libre constraint solver suitable for solving classical
scheduling problems, among many other kinds of constraint satisfaction
problems.

[MINION]: http://minion.sourceforge.net/

To make use of MINION in my environment, I'm going to read a simple JSON config
file describing the problem, translate it to a constraint program expressing
these constraints:

  1. We can't change the past.

  2. No one can work more than one shift at a time.

  3. No one is allowed to work two adjacent shifts.

solve it, and then translate it back to JSON via a pipeline like:

~~~~ { .bash }
./emit.py | ./minion -printsolsonly -quiet -- | ./parse.py
~~~~

Here's the config file I eventually came up with:

~~~~ { .json }
{
    "data": {
        "num_shift_kinds": 2,
        "num_slots": 4,
        "num_people": 4
    },

    "person_idx": {
        "me": 0,
        "you": 1,
        "jdoe": 2,
        "kroe": 3
    },

    "shift_kind_idx": {
        "primary": 0,
        "backup": 1
    },

    "history": {
        "me": {
            "primary": [0, 0, 1],
            "backup": [1, 0, 0]
        },
        "you": {
            "primary": [1, 0, 0],
            "backup": [0, 0, 1]
        },
        "jdoe": {
            "primary": [0, 1, 0],
            "backup": [0, 0, 0]
        },
        "kroe": {
            "primary": [0, 0, 0],
            "backup": [0, 1, 0]
        }
    }
}
~~~~

The key idea is that, given some people who need to be scheduled for a rotation
of "primary" and "backup" shifts and given a matrix of truth values indicating
whether or not person X took shift type Y at time Z (XYZ = 1) or not (XYZ = 0),
we can calculate a new matrix of future assignments up to some horizon via a
constraint program like this one:

~~~~ { .minion }
MINION 3

**VARIABLES**
# a[shift_kind,slot,person]
BOOL a[2,4,4]
BOUND safety_cap[2] {0..4}

**SEARCH**
# VARORDER ...
# VALORDER ...
# MAXIMIZING ...
PRINT [a]

**CONSTRAINTS**
# history constraints
# me
eq(a[1,0,0], 1)
eq(a[1,1,0], 0)
eq(a[1,2,0], 0)
eq(a[0,0,0], 0)
eq(a[0,1,0], 0)
eq(a[0,2,0], 1)
# you
eq(a[1,0,1], 0)
eq(a[1,1,1], 0)
eq(a[1,2,1], 1)
eq(a[0,0,1], 1)
eq(a[0,1,1], 0)
eq(a[0,2,1], 0)
# jdoe
eq(a[1,0,2], 0)
eq(a[1,1,2], 0)
eq(a[1,2,2], 0)
eq(a[0,0,2], 0)
eq(a[0,1,2], 1)
eq(a[0,2,2], 0)
# kroe
eq(a[1,0,3], 0)
eq(a[1,1,3], 1)
eq(a[1,2,3], 0)
eq(a[0,0,3], 0)
eq(a[0,1,3], 0)
eq(a[0,2,3], 0)

# safety constraints
eq(safety_cap[0], 3)
eq(safety_cap[1], 1)
gcc([a[0,0,_]], [0,1], safety_cap)
gcc([a[1,0,_]], [0,1], safety_cap)
gcc([a[0,1,_]], [0,1], safety_cap)
gcc([a[1,1,_]], [0,1], safety_cap)
gcc([a[0,2,_]], [0,1], safety_cap)
gcc([a[1,2,_]], [0,1], safety_cap)
gcc([a[0,3,_]], [0,1], safety_cap)
gcc([a[1,3,_]], [0,1], safety_cap)

# mutual exclusion constraints
sumleq(a[_,0,0], 1)
sumleq(a[_,1,0], 1)
sumleq(a[_,2,0], 1)
sumleq(a[_,3,0], 1)
sumleq(a[_,0,1], 1)
sumleq(a[_,1,1], 1)
sumleq(a[_,2,1], 1)
sumleq(a[_,3,1], 1)
sumleq(a[_,0,2], 1)
sumleq(a[_,1,2], 1)
sumleq(a[_,2,2], 1)
sumleq(a[_,3,2], 1)
sumleq(a[_,0,3], 1)
sumleq(a[_,1,3], 1)
sumleq(a[_,2,3], 1)
sumleq(a[_,3,3], 1)

# fatigue constraints
sumleq([a[_,0,0],a[_,1,0]], 1)
sumleq([a[_,1,0],a[_,2,0]], 1)
sumleq([a[_,2,0],a[_,3,0]], 1)
sumleq([a[_,0,1],a[_,1,1]], 1)
sumleq([a[_,1,1],a[_,2,1]], 1)
sumleq([a[_,2,1],a[_,3,1]], 1)
sumleq([a[_,0,2],a[_,1,2]], 1)
sumleq([a[_,1,2],a[_,2,2]], 1)
sumleq([a[_,2,2],a[_,3,2]], 1)
sumleq([a[_,0,3],a[_,1,3]], 1)
sumleq([a[_,1,3],a[_,2,3]], 1)
sumleq([a[_,2,3],a[_,3,3]], 1)

**EOF**
~~~~

Solving the constraint program produces output like this:

~~~~
0 1 0 0
0 0 1 0
1 0 0 0
0 0 0 1
1 0 0 0
0 0 0 1
0 1 0 0
0 0 1 0
~~~~

which we can immediately parse and then pretty-print to get a more readable
schedule:

~~~~ { .json }
{
    "me": {
        "primary": [0, 0, 1, 0],
        "backup":  [1, 0, 0, 0]
    },
    "you": {
        "primary": [1, 0, 0, 0],
        "backup":  [0, 0, 1, 0]
    },
    "jdoe": {
        "primary": [0, 1, 0, 0],
        "backup":  [0, 0, 0, 1]
    },
    "kroe": {
        "primary": [0, 0, 0, 1],
        "backup":  [0, 1, 0, 0]
    }
}
~~~~

suitable for re-inclusion in the `history` field of the config file.

(For comparison, here was the original history:

~~~~ { .json }
{
    "me": {
        "primary": [0, 0, 1],
        "backup": [1, 0, 0]
    },
    "you": {
        "primary": [1, 0, 0],
        "backup": [0, 0, 1]
    },
    "jdoe": {
        "primary": [0, 1, 0],
        "backup": [0, 0, 0]
    },
    "kroe": {
        "primary": [0, 0, 0],
        "backup": [0, 1, 0]
    }
}
~~~~

As you can see, the original history has been faithfully extended with new
information consistent with proposed "history", "mutual exclusion", and
"fatigue" constraints mentioned above.)