Scheduling Shift-Work

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”.

MINION

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

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:

We can’t change the past.
No one can work more than one shift at a time.
No one is allowed to work two adjacent shifts.

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

./emit.py | ./minion -printsolsonly -quiet -- | ./parse.py

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

{
    "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 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:

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

{
    "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:

{
    "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.)

Scheduling Shift-Work

Contents

Introduction

Classical Scheduling

MINION