Solving shift scheduling problems

nextmv sdk install

The Nextmv Software Development Kit (SDK) lets you automate any operational decision in a way that looks and feels like writing other code. It provides the guardrails to turn your data into automated decisions, and test and deploy them into production environments.

This guide will walk you through our shift-scheduling template. To get the template, simply run the following command.

nextmv sdk init -t shift-scheduling

You can check that all files are available in the newly created shift-scheduling folder. Running the tree command, you should see the file structure.

tree shift-scheduling

• README.md gives a short introduction to the shift scheduling problem and shows you how to run the template.
• go.mod and go.sum define a Go module and are used to manage dependencies, including the Nextmv SDK.
• input.json describes the input data for a specific shift scheduling problem that is solved by the template.
• license contains the Apache License 2.0 under which we distribute this template.
• main.go contains the actual code of shift scheduling app.
• The shift-scheduling.code-workspace file should be used to open the template in Visual Studio Code. It is pre-configured for you so that you can run and debug the template without any further steps.

Now you can run the template with the Nextmv CLI, reading from the input.json file and writing to an output.json file. The following command shows you how to specify solver limits as well. You should obtain an output similar to the one shown.

nextmv sdk run main.go -- \
    -runner.input.path input.json \
    -runner.output.path output.json \
    -limits.duration 5s \
    -diagram.expansion.limit 1

Note that transient fields like timestamps, duration, versions, etc. are represented with dummy values due to their dynamic nature. I.e., every time the input is run or the version is bumped, these fields will have a different value.

Now we will show you, step by step, what the code inside the main.go achieves.

The first part of the main.go defines a package name, imports packages that are needed by the code below and a main function which is the starting point for the app. In the main function the Run function from the Nextmv run package is being called. This function executes a solver which is passed in the form of the solver function further down in the file.

package main

import (
	"fmt"
	"log"
	"time"

	"github.com/nextmv-io/sdk/model"
	"github.com/nextmv-io/sdk/run"
	"github.com/nextmv-io/sdk/store"
)

func main() {
	err := run.Run(solver)
	if err != nil {
		log.Fatal(err)
	}
}

But before we look into the solver function, we will examine the different structs that represent the needed data used by the app.

The struct schedulingProblem represents the data that is directly needed as input data for the app to work. It describes a Nurse scheduling problem where we want to assign a number of total nurses/workers (Workers) to shifts (fixed: morning, day, night) for a number of days (Days), such that each shift has a worker assigned. Doing this, we will also take the workers shift preferences (Preferences) and also vacation/unavailability (Unavailable) into account.

// Workers can also be unavailable for certain full days.
type schedulingProblem struct {
	Days        int           \`json:"days"\`
	Workers     int           \`json:"workers"\`
	Preferences preference    \`json:"preferences"\`
	Unavailable []unavailable \`json:"unavailable"\`
}

The preferences and unavailability are defined as their own types. The type preference contains a slice of the shiftTypePreference which is set up as a tuple of a worker by index and a shift type they prefer. The unavailability maps a worker by index to a slice of integer, representing the days they are unavailable by index. Both types and helper types can be seen here:

type preference struct {
	ShiftType []shiftTypePreference \`json:"shift_type"\`
}
type shiftTypePreference struct {
	Worker workerID  \`json:"worker"\`
	Type   shiftType \`json:"type"\`
}
type unavailable struct {
	Worker workerID \`json:"worker"\`
	Days   []int    \`json:"days"\`
}
type shiftType string

type workerID int

The solver function is where the model is defined. The function's signature adheres to the run.Run function we saw earlier already.

func solver(input schedulingProblem, opts store.Options) (store.Solver, error) {

When you first ran the template you passed in the parameter -runner.input.path followed by the path to an input file. This file is automatically parsed and converted to our schedulingProblem struct. Other optional arguments are also interpreted automatically and passed to the solver as an Options struct.

First we create a store called schedule which holds all the decision variables we need to track and some helper variables:

• nShifts represents the number of shifts available given the number of days we are creating the schedule for.
• workers represents a list of available workers as an integer domain, so a worker is represented by index.
• typeMap represents the available shifts per day as a map (morning, day, night) and allows for a quick access later on.
• prefShiftType maps the preferred shift type to a worker.

schedule := store.New()

// We define some helper variables that are useful later.
nShifts := input.Days * 3
workers := model.NewDomain(model.NewRange(1, input.Workers))
typeMap := [3]shiftType{"morning", "day", "night"}
prefShiftType := map[int]shiftType{}
for _, v := range input.Preferences.ShiftType {
	prefShiftType[int(v.Worker)] = v.Type
}

Now with the helper variables set up, we can now create the decision variables for our store schedule.

• shifts: represents all the shifts that we need to assign a worker to. At the beginning when no decision has been made yet each shift has all the available workers assigned.
• workerCount: represents the total number of workers active in our store schedule.
• happiness: represents the total number of happy workers, meaning workers that are assigned to their preferred shift. If a worker has no preferences then they will also be counted as happy.

shifts := store.Repeat(schedule, nShifts, workers)

// The number of workers active in a schedule.
workerCount := store.NewVar(schedule, 0)

// We also want to maximize worker happiness by fulfilling as many
// preferences as possible.
happiness := store.NewVar(schedule, 0)

Since we know up front that some workers are unavailable on certain days, we can reduce the problem size by removing them before we start optimizing. To do this we create a new variable changes as a slice of changes to which we add the changes we want to make. Thus, we loop over the slice of unavailable workers and then the days they are unavailable on. For each day, we remove the worker as an option from the respective shifts (morning, day, night) since they are unavailable the whole day. Finally we apply the changes to our store.

changes := []store.Change{}

for _, v := range input.Unavailable {
	for _, d := range v.Days {
		morning := (d - 1) * 3
		day := morning + 1
		night := day + 1
		changes = append(changes,
			shifts.Remove(morning, []int{int(v.Worker)}),
			shifts.Remove(day, []int{int(v.Worker)}),
			shifts.Remove(night, []int{int(v.Worker)}),
		)
	}
}
schedule = schedule.Apply(changes...)

We now have a schedule with reduced optionality. Next we will define an objective value for it. In this case, we would like to minimize the weighted number of active workers while maximizing the worker's happiness. We introduce a variable workerCountImportance that represents our weight first and define our Value function as follows:

workerCountImportance := 10
schedule = schedule.Value(func(s store.Store) int {
	return workerCountImportance*workerCount.Get(s) - happiness.Get(s)
})

Note that the happiness is subtracted since we want to maximize it while we want to minimize the number of active workers and thus, the overall Value function.

After that we set up a variable constraint by calling the newBreakConstraint function which we implemented like this:

func newBreakConstraint(shifts store.Domains, breakDuration int) constraint {
	return &breakConstraint{
		shifts:        shifts,
		breakDuration: breakDuration,
	}
}

You can see that all the function does is take two parameters, shifts and an integer breakDuration and returns a type that implements the constraint interface, in this case the specific type breakConstraint.

The constraint interface requires the implementation of two functions, propagate and isProvenInfeasible.

type constraint interface {
	propagate(store.Store) []store.Change
	isProvenInfeasible(s store.Store) bool
}

For now we will not worry about how they are implemented for our type breakConstraint.

Calling the newBreakConstraint function, as we just saw, requires two parameters to be passed in: shifts and a number 2 for the breakDuration. This number represents the number of shifts that a worker must have a break before and after a shift they are assigned to, to avoid an assignment of consecutive shifts for the same worker.

constraint := newBreakConstraint(shifts, 2)

Now that we have the constraint, we call the schedule's Propagate function passing in the constraint's propagate function.

schedule.Propagate(constraint.propagate)

This will execute the propagate function that is implemented for the type breakConstraint:

func (t *breakConstraint) propagate(s store.Store) []store.Change {
	changes := make([]store.Change, 0)

	for i := 0; i < t.shifts.Len(s); i++ {
		domain := t.shifts.Domain(s, i)

		if v, singleton := domain.Value(); singleton {
			for j := 1; j <= t.breakDuration; j++ {
				if i-j > 0 {
					changes = t.remove(s, i-j, v, changes)
				}
				if i+j < t.shifts.Len(s) {
					changes = t.remove(s, i+j, v, changes)
				}
			}
		}
	}

	return changes
}

This function is used to eliminate workers from shifts, if possible. That is the case when there is exactly one worker assigned to a shift because we can then remove this worker from the previous and next breakDuration shifts.

So, we first create a new slice for the changes we are going to make on our store. After that we loop over all shifts. We check if a shift is a singleton, meaning exactly one worker is assigned to the shift, and append to the list of changes every time a worker is within the shift break restriction.

Since this could lead to new singleton shifts, this function is called automatically after the changes have been returned. So it is again checked whether more workers can be removed.

To remove workers from shifts we added a small helper function to re-use code:

func (t *breakConstraint) remove(
	s store.Store,
	domain,
	value int,
	changes []store.Change,
) []store.Change {
	if t.shifts.Domain(s, domain).Contains(value) {
		return append(changes, t.shifts.Remove(domain, []int{value}))
	}
	return changes
}

This repeats until there are no new changes to be made. It is important to note that the base case to break out of this re-calling is returning an empty slice of changes.

Going back to where we called the propagate function, the next thing we do is check if the current store can be proven infeasible.

if constraint.isProvenInfeasible(schedule) {
	return nil, fmt.Errorf("input can not be solved")

If we can, then there is no solution to the input data. Let's look at what happens in the isProvenInfeasible:

func (t *breakConstraint) isProvenInfeasible(s store.Store) bool {
	for i := 0; i < t.shifts.Len(s); i++ {
		domain := t.shifts.Domain(s, i)
		// being empty can never result in a solution if we assume we can only
		// remove more values (which there aren't any)
		if domain.Empty() {
			return true
		}
		if w1, singleton := domain.Value(); singleton {
			for j := 1; j <= t.breakDuration; j++ {
				if i-j > 0 && t.checkFeasible(s, w1, i-j) {
					return true
				}
				if i+j < t.shifts.Len(s) && t.checkFeasible(s, w1, i+j) {
					return true
				}
			}
		}
	}
	return false
}

We are removing workers from shifts in order to have exactly one worker assigned to each shift. Thus, if we encounter an empty shift, there is no solution for the input data. Also, if a shift is a singleton, there must not be any other singleton neighbor shifts with the same worker within the breakDuration bound because workers must have their breaks after working a shift. If the worker is not given their break time then there is no solution to the input data.

We wrote a little helper function that handles the check to see if a worker is assigned consecutive shifts:

func (t *breakConstraint) checkFeasible(s store.Store, w1, domain int) bool {
	if w2, isSingleton := t.shifts.Domain(s, domain).Value(); isSingleton {
		if w1 == w2 {
			return true
		}
	}
	return false
}

Up until this part we have set up input and output structures, made a function to prove infeasibility, and propagated changes to the store to exclude solutions that we know to be impossible due to decisions we made in the past.

What now follows in this template are a couple of functions that operate on our store schedule. First, we will explain briefly what they are doing before we look at them in detail.

• Generate: The Generate function is used to find new solutions by creating new stores. Undoubtedly, this is a very important part of the app because it defines how the search space is traversed.
• Validate: The Validate function checks if a solution fulfills certain criteria and thus, can be brought into operation.
• Format: The Format function changes the solution's output format, e.g. to be human-readable or better suited for post-processing the solution.
• Bound: The Bound function sets a lower and upper bound to improve performance when searching for new solutions.

The Generate function is used to branch on the search tree and traverse the search space. In this template the Lazy function is used to achieve this. But before we call the Lazy function we define two helper variables:

• From the current store, we use the First function to get the first shift with a length greater 1. The function also returns a bool flag that indicates whether a shift of length greater than 1 exits.
• We then also get the workers that are currently still able to work this shift.

i, ok := shifts.First(s)
workers := shifts.Domain(s, i).Slice()

The Lazy function returns a new Generator of stores. It does this lazily, meaning on demand, and does this until there are no new stores to be created based on the current store. To achieve this, the Lazy function takes two functions as arguments. The first function controls if we want to generate new child stores given the current store.

func() bool {
	for j := 0; j < nShifts; j++ {
		if shifts.Domain(s, j).Empty() {
			return false
		}
	}
	return ok && len(workers) > 0
},

In this case, the condition is to continue branching when all of the following is true:

• none of the shifts are empty (there are still workers who can be assigned)
• there is a shift with a length greater 1 still
• the current shift has more than 1 worker to select from

The second function takes a store and generates new child stores. Upon this child store the Generate function will be called to create new stores.

Let's see how we create a child store. First we take the first worker out of the slice of workers.

worker := workers[0]
// Note that workers is a pointer to the variable defined above.
workers = workers[1:]

Then we assign this worker to the current shift i by creating a change for the store.

changes := []store.Change{
	shifts.AtLeast(i, worker),
	shifts.AtMost(i, worker),
}

We also need to update our decision variable for our happiness. We use our previously defined typeMap to quickly get the type of the current shift (morning, day, night). If the worker prefers to work in this shift or has no preference at all, we increase the value for happiness by 1. We do this by adding another change to the store. This is done in the following lines:

shiftType := typeMap[i%3]
if pref, ok := prefShiftType[worker]; ok {
	if pref == shiftType {
		changes = append(changes, happiness.Set(happiness.Get(s)+1))
	}
} else {
	// In case the worker has no preferences we assume they are
	// happy.
	changes = append(changes, happiness.Set(happiness.Get(s)+1))
}

Next, we then apply the changes to create a new store s - so we do not change the original store at this point - and use the Propagate function as before to remove workers from shifts that they cannot work anymore. The result will again be written into our store s.

s = s.Apply(changes...)
s = s.Propagate(constraint.propagate)

Last, before we return our store s, we count the number of active workers by using a map. Each time a shift is a singleton, meaning a final decision on who works this shift was made, we add the worker to the map. This way we make sure to not count any worker twice. We apply the new count to s.

workerMap := map[int]bool{}
for j := 0; j < nShifts; j++ {
	if value, ok := shifts.Domain(s, j).Value(); ok {
		workerMap[value] = true
	}
}

return s.Apply(workerCount.Set(len(workerMap)))

We have a valid solution if every shift has exactly one worker assigned and the solution is not proven infeasible. We can simply check both conditions with the following lines of code:

}).Validate(func(s store.Store) bool {
	// The store is operationally valid if exactly one worker is assigned
	// to a shift and no constraints are violated.
	if !shifts.Singleton(s) {
		return false
	}

	return !constraint.isProvenInfeasible(s)

Because our value function consists of two pieces, the number of active workers and the happiness, we are looking for estimates for them for the lower and upper bound.

We know that a final valid solution will have exactly one worker assigned to each shift. So we can estimate the upper bound by fixing every shift to a worker that has not yet been fixed to one worker exclusively. To do this, we take the current workerCount we have for the store as well as the current happiness and increase them for every unfixed shift by 1.

wcUpper := workerCount.Get(s)
happinessUpper := happiness.Get(s)
for i := 0; i < nShifts; i++ {
	d := shifts.Domain(s, i)
	if _, ok := d.Value(); !ok {
		wcUpper++
		happinessUpper++
	}
}

For the lower bound we know that we need at least three workers for one day because of the breakDuration that prohibits working consecutive shifts. This means we can use at least three as the upper bound or more, if we have already more active workers in the store.

wcLower := workerCount.Get(s)
if wcLower < 3 {
	wcLower = 3
}

To find the lower bound for the happiness, we start with the current store's value for happiness. Now we look at every shift that is not assigned yet. If a shift has a possible assignment for a worker, but the shift fails to meet that worker's preference, we leave the lower bound for happiness untouched. This shift did not increase the happiness score, because it is not the worker's preferred shift. If the shift is a preferred shift assignment for the worker, we increase the value for happiness as well as the lower bound (we can't do any worse!).

happinessLower := happiness.Get(s)
for i := 0; i < nShifts; i++ {
	d := shifts.Domain(s, i)
	increase := 1
	if d.Len() <= 1 {
		continue
	}
	for _, v := range d.Slice() {
		if _, ok := prefShiftType[v]; ok {
			// there is one worker who has a preference
			increase = 0
			break
		}
	}
	happinessLower += increase
}

Then, we return the bounds as a store.Bound. Returning the lower and upper bound, we replicate the Value function we looked at earlier already.

return store.Bounds{
	Lower: workerCountImportance*wcLower - happinessUpper,
	Upper: workerCountImportance*wcUpper - happinessLower,
}

To represent the solution in a better, readable way, we define a couple of structs. The struct output contains fields for the number of total workers (Workers), a field Happiness that indicates how often a worker was assigned to their preferred shift (in case they had no preferred shift, we assume they are happy with the assigned shift) and a field Shifts. Shifts is a slice of shift and represents the day and shift each worker was assigned.

type output struct {
	// Shifts describe the assigned workers to days and shift type.
	Shifts []shift \`json:"shifts"\`
	// Happiness is the number of times a preference of a worker has been met.
	// If a worker has no preferences, then it is assumed they are happy.
	Happiness int \`json:"happiness"\`
	// Workers shows the number of total workers assigned.
	Workers int \`json:"workers"\`
}

We create a slice of Shifts, loop over the store's shifts adding information to the slice:

outputShifts := make([]shift, 0, nShifts)
for i, v := range shifts.Slices(s) {
	day := i/3 + 1
	shiftType := typeMap[i%3]
	outputShifts = append(outputShifts, shift{
		Worker: workerID(v[0]),
		Day:    day,
		Type:   shiftType,
	})
}

Last we return an output as our solution, containing the store's shifts, happiness and workerCount:

return output{
	Shifts:    outputShifts,
	Happiness: happiness.Get(s),
	Workers:   workerCount.Get(s),
}

Finally, we return a solver for our store schedule by using the Minimizer function passing in options that were given at the very beginning by the calling function. This solver is then executed by the run.Run function from the beginning.

return schedule.Minimizer(opts), nil