Tutorials

Solving shift scheduling problems

Learn to model a shift scheduling problem with the Nextmv SDK

This tutorial assumes you already completed the steps described in the 5-minute getting started experience. To test that the Nextmv CLI is correctly configured, you can optionally run the following command on your terminal. It will get some files that are necessary to work with the Nextmv Platform. You can see the expected output as well.

nextmv install
Copy

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.

Introduction

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

nextmv init -t shift-scheduling
Copy

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
Copy
  • 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 run local main.go -- \
    -hop.runner.input.path input.json \
    -hop.runner.output.path output.json \
    -hop.solver.limits.duration 5s \
    -hop.solver.diagram.expansion.limit 1
Copy

Note that transient fields are represented with "\u003c\u003cPRESENCE\u003e\u003e", which is the unicode representation of "<<PRESENCE>>", due to their dynamic nature: every time the input is run, these fields will have a different value. This representation is compliant with the jsonassert package.

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

Dissecting the app

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"

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

func main() {
	run.Run(solver)
}
Copy

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

The Input

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.

type SchedulingProblem struct {
	Days        int           `json:"days"`
	Workers     int           `json:"workers"`
	Preferences preference    `json:"preferences"`
	Unavailable []unavailable `json:"unavailable"`
}
Copy

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
Copy

The Solver

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) {
Copy

When you first ran the template you passed in the parameter -hop.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
}
Copy

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)
Copy

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...)
Copy

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)
})
Copy

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 BreakConstraint function which we implemented like this:

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

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.

	propagate(store.Store) []store.Change
	isProvenInfeasible(s store.Store) bool
}
Copy

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

Calling the BreakConstraint 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 := BreakConstraint(shifts, 2)
Copy

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

schedule.Propagate(constraint.propagate)
Copy

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
}
Copy

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
}
Copy

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")
}
Copy

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
}
Copy

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
}
Copy

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

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()
Copy

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
},
Copy

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:]
Copy

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),
}
Copy

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))
}
Copy

Next, we then apply the changes to create a new store s1 - 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 s1.

s1 := s.Apply(changes...)
s1 = s1.Propagate(constraint.propagate)
Copy

Last, before we return our store s1, 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 s1.

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

return s1.Apply(workerCount.Set(len(workerMap)))
Copy

The Validate function

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)
Copy

The Format function

To represent the solution in a better, readable way, we define a couple of structs. The struct Schedule 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.

	// 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"`
}

type shift struct {
	Day    int       `json:"day"`
	Worker workerID  `json:"worker"`
	Type   shiftType `json:"type"`
}
Copy

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,
	})
}
Copy

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

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

The Bound function

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++
	}
}
Copy

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
}
Copy

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
}
Copy

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,
}
Copy

Returning the solver

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
Copy

Page last updated

Go to on-page nav menu