# Employee Scheduling

Organizations whose employees work multiple shifts need to schedule sufficient workers for each daily shift. Typically, the schedules will have constraints, such as "no employee should work two shifts in a row". Finding a schedule that satisfies all constraints can be computationally difficult.

The following sections present two examples of employee scheduling problems, and show how to solve them using the CP-SAT solver.

For a more sophisticated example, see this shift scheduling program on GitHub.

## A nurse scheduling problem

In the next example, a hospital supervisor needs to create a schedule for four nurses over a three-day period, subject to the following conditions:

• Each day is divided into three 8-hour shifts.
• Every day, each shift is assigned to a single nurse, and no nurse works more than one shift.
• Each nurse is assigned to at least two shifts during the three-day period.

The following sections present a solution to the nurse scheduling problem.

### Import the libraries

The following code imports the required library.

### Python

from ortools.sat.python import cp_model

### C++

#include <stdlib.h>

#include <atomic>
#include <map>
#include <numeric>
#include <string>
#include <tuple>
#include <vector>

#include "absl/strings/str_format.h"
#include "ortools/base/logging.h"
#include "ortools/sat/cp_model.h"
#include "ortools/sat/cp_model.pb.h"
#include "ortools/sat/cp_model_solver.h"
#include "ortools/sat/model.h"
#include "ortools/sat/sat_parameters.pb.h"
#include "ortools/util/time_limit.h"

### Java

import com.google.ortools.Loader;
import java.util.ArrayList;
import java.util.List;
import java.util.stream.IntStream;

### C#

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using Google.OrTools.Sat;

### Data for the example

The following code creates the data for the example.

### Python

num_nurses = 4
num_shifts = 3
num_days = 3
all_nurses = range(num_nurses)
all_shifts = range(num_shifts)
all_days = range(num_days)

### C++

const int num_nurses = 4;
const int num_shifts = 3;
const int num_days = 3;

std::vector<int> all_nurses(num_nurses);
std::iota(all_nurses.begin(), all_nurses.end(), 0);

std::vector<int> all_shifts(num_shifts);
std::iota(all_shifts.begin(), all_shifts.end(), 0);

std::vector<int> all_days(num_days);
std::iota(all_days.begin(), all_days.end(), 0);

### Java

final int numNurses = 4;
final int numDays = 3;
final int numShifts = 3;

final int[] allNurses = IntStream.range(0, numNurses).toArray();
final int[] allDays = IntStream.range(0, numDays).toArray();
final int[] allShifts = IntStream.range(0, numShifts).toArray();

### C#

const int numNurses = 4;
const int numDays = 3;
const int numShifts = 3;

int[] allNurses = Enumerable.Range(0, numNurses).ToArray();
int[] allDays = Enumerable.Range(0, numDays).ToArray();
int[] allShifts = Enumerable.Range(0, numShifts).ToArray();

### Create the model

The following code creates the model.

### Python

model = cp_model.CpModel()

### C++

CpModelBuilder cp_model;

### Java

CpModel model = new CpModel();

### C#

CpModel model = new CpModel();
model.Model.Variables.Capacity = numNurses * numDays * numShifts;

### Create the variables

The following code an array of variables for the problem.

### Python

shifts = {}
for n in all_nurses:
for d in all_days:
for s in all_shifts:
shifts[(n, d,
s)] = model.NewBoolVar('shift_n%id%is%i' % (n, d, s))

### C++

std::map<std::tuple<int, int, int>, BoolVar> shifts;
for (int n : all_nurses) {
for (int d : all_days) {
for (int s : all_shifts) {
auto key = std::make_tuple(n, d, s);
shifts[key] = cp_model.NewBoolVar().WithName(
absl::StrFormat("shift_n%dd%ds%d", n, d, s));
}
}
}

### Java

Literal[][][] shifts = new Literal[numNurses][numDays][numShifts];
for (int n : allNurses) {
for (int d : allDays) {
for (int s : allShifts) {
shifts[n][d][s] = model.newBoolVar("shifts_n" + n + "d" + d + "s" + s);
}
}
}

### C#

Dictionary<(int, int, int), BoolVar> shifts =
new Dictionary<(int, int, int), BoolVar>(numNurses * numDays * numShifts);
foreach (int n in allNurses)
{
foreach (int d in allDays)
{
foreach (int s in allShifts)
{
shifts.Add((n, d, s), model.NewBoolVar($"shifts_n{n}d{d}s{s}")); } } } The array defines assignments for shifts to nurses as follows: shifts[(n, d, s)] equals 1 if shift s is assigned to nurse n on day d, and 0 otherwise. ### Assign nurses to shifts Next, we show how to assign nurses to shifts subject to the following constraints: • Each shift is assigned to a single nurse per day. • Each nurse works at most one shift per day. Here's the code that creates the first condition. ### Python for d in all_days: for s in all_shifts: model.AddExactlyOne(shifts[(n, d, s)] for n in all_nurses) ### C++ for (int d : all_days) { for (int s : all_shifts) { std::vector<BoolVar> nurses; for (int n : all_nurses) { auto key = std::make_tuple(n, d, s); nurses.push_back(shifts[key]); } cp_model.AddExactlyOne(nurses); } } ### Java for (int d : allDays) { for (int s : allShifts) { List<Literal> nurses = new ArrayList<>(); for (int n : allNurses) { nurses.add(shifts[n][d][s]); } model.addExactlyOne(nurses); } } ### C# List<ILiteral> literals = new List<ILiteral>(); foreach (int d in allDays) { foreach (int s in allShifts) { foreach (int n in allNurses) { literals.Add(shifts[(n, d, s)]); } model.AddExactlyOne(literals); literals.Clear(); } } The last line says that for each shift, the sum of the nurses assigned to that shift is 1. Next, here's the code that requires that each nurse works at most one shift per day. ### Python for n in all_nurses: for d in all_days: model.AddAtMostOne(shifts[(n, d, s)] for s in all_shifts) ### C++ for (int n : all_nurses) { for (int d : all_days) { std::vector<BoolVar> work; for (int s : all_shifts) { auto key = std::make_tuple(n, d, s); work.push_back(shifts[key]); } cp_model.AddAtMostOne(work); } } ### Java for (int n : allNurses) { for (int d : allDays) { List<Literal> work = new ArrayList<>(); for (int s : allShifts) { work.add(shifts[n][d][s]); } model.addAtMostOne(work); } } ### C# foreach (int n in allNurses) { foreach (int d in allDays) { foreach (int s in allShifts) { literals.Add(shifts[(n, d, s)]); } model.AddAtMostOne(literals); literals.Clear(); } } For each nurse, the sum of shifts assigned to that nurse is at most 1 ("at most" because a nurse might have the day off). ### Assign shifts evenly Next, we show how to assign shifts to nurses as evenly as possible. Since there are nine shifts over the three-day period, we can assign two shifts to each of the four nurses. After that there will be one shift left over, which can be assigned to any nurse. The following code ensures that each nurse works at least two shifts in the three-day period. ### Python # Try to distribute the shifts evenly, so that each nurse works # min_shifts_per_nurse shifts. If this is not possible, because the total # number of shifts is not divisible by the number of nurses, some nurses will # be assigned one more shift. min_shifts_per_nurse = (num_shifts * num_days) // num_nurses if num_shifts * num_days % num_nurses == 0: max_shifts_per_nurse = min_shifts_per_nurse else: max_shifts_per_nurse = min_shifts_per_nurse + 1 for n in all_nurses: num_shifts_worked = [] for d in all_days: for s in all_shifts: num_shifts_worked.append(shifts[(n, d, s)]) model.Add(min_shifts_per_nurse <= sum(num_shifts_worked)) model.Add(sum(num_shifts_worked) <= max_shifts_per_nurse) ### C++ // Try to distribute the shifts evenly, so that each nurse works // min_shifts_per_nurse shifts. If this is not possible, because the total // number of shifts is not divisible by the number of nurses, some nurses will // be assigned one more shift. int min_shifts_per_nurse = (num_shifts * num_days) / num_nurses; int max_shifts_per_nurse; if ((num_shifts * num_days) % num_nurses == 0) { max_shifts_per_nurse = min_shifts_per_nurse; } else { max_shifts_per_nurse = min_shifts_per_nurse + 1; } for (int n : all_nurses) { std::vector<BoolVar> num_shifts_worked; // int num_shifts_worked = 0; for (int d : all_days) { for (int s : all_shifts) { auto key = std::make_tuple(n, d, s); num_shifts_worked.push_back(shifts[key]); } } cp_model.AddLessOrEqual(min_shifts_per_nurse, LinearExpr::Sum(num_shifts_worked)); cp_model.AddLessOrEqual(LinearExpr::Sum(num_shifts_worked), max_shifts_per_nurse); } ### Java // Try to distribute the shifts evenly, so that each nurse works // minShiftsPerNurse shifts. If this is not possible, because the total // number of shifts is not divisible by the number of nurses, some nurses will // be assigned one more shift. int minShiftsPerNurse = (numShifts * numDays) / numNurses; int maxShiftsPerNurse; if ((numShifts * numDays) % numNurses == 0) { maxShiftsPerNurse = minShiftsPerNurse; } else { maxShiftsPerNurse = minShiftsPerNurse + 1; } for (int n : allNurses) { LinearExprBuilder numShiftsWorked = LinearExpr.newBuilder(); for (int d : allDays) { for (int s : allShifts) { numShiftsWorked.add(shifts[n][d][s]); } } model.addLinearConstraint(numShiftsWorked, minShiftsPerNurse, maxShiftsPerNurse); } ### C# // Try to distribute the shifts evenly, so that each nurse works // minShiftsPerNurse shifts. If this is not possible, because the total // number of shifts is not divisible by the number of nurses, some nurses will // be assigned one more shift. int minShiftsPerNurse = (numShifts * numDays) / numNurses; int maxShiftsPerNurse; if ((numShifts * numDays) % numNurses == 0) { maxShiftsPerNurse = minShiftsPerNurse; } else { maxShiftsPerNurse = minShiftsPerNurse + 1; } List<IntVar> numShiftsWorked = new List<IntVar>(); foreach (int n in allNurses) { foreach (int d in allDays) { foreach (int s in allShifts) { numShiftsWorked.Add(shifts[(n, d, s)]); } } model.AddLinearConstraint(LinearExpr.Sum(numShiftsWorked), minShiftsPerNurse, maxShiftsPerNurse); numShiftsWorked.Clear(); } Since there are num_shifts * num_days total shifts in the schedule period, you can assign at least (num_shifts * num_days) // num_nurses shifts to each nurse, but some shifts may be left over. (Here // is the Python integer division operator, which returns the floor of the usual quotient.) For the given values of num_nurses = 4, num_shifts = 3, and num_days = 3, the expression min_shifts_per_nurse has the value (3 * 3 // 4) = 2, so you can assign at least two shifts to each nurse. This is guaranteed by the constraint model.Add(min_shifts_per_nurse <= num_shifts_worked) Since there are nine total shifts over the three-day period, there is one remaining shift after assigning two shifts to each nurse. The extra shift can be assigned to any nurse. The final line model.Add(num_shifts_worked <= max_shifts_per_nurse) ensures that no nurse is assigned more than one extra shift. The constraint isn't necessary in this case, because there's only one extra shift. But for different parameter values, there could be several extra shifts, in which case the constraint is necessary. ### Update solver parameters In an non-optimization model, you can enable the search for all solutions. ### Python solver = cp_model.CpSolver() solver.parameters.linearization_level = 0 # Enumerate all solutions. solver.parameters.enumerate_all_solutions = True  ### C++ Model model; SatParameters parameters; parameters.set_linearization_level(0); // Enumerate all solutions. parameters.set_enumerate_all_solutions(true); model.Add(NewSatParameters(parameters)); ### Java CpSolver solver = new CpSolver(); solver.getParameters().setLinearizationLevel(0); // Tell the solver to enumerate all solutions. solver.getParameters().setEnumerateAllSolutions(true); ### C# CpSolver solver = new CpSolver(); // Tell the solver to enumerate all solutions. solver.StringParameters += "linearization_level:0 " + "enumerate_all_solutions:true "; ### Register a Solutions Callback You need to register a callback on the solver that will be called at each solution. ### Python class NursesPartialSolutionPrinter(cp_model.CpSolverSolutionCallback): """Print intermediate solutions.""" def __init__(self, shifts, num_nurses, num_days, num_shifts, limit): cp_model.CpSolverSolutionCallback.__init__(self) self._shifts = shifts self._num_nurses = num_nurses self._num_days = num_days self._num_shifts = num_shifts self._solution_count = 0 self._solution_limit = limit def on_solution_callback(self): self._solution_count += 1 print('Solution %i' % self._solution_count) for d in range(self._num_days): print('Day %i' % d) for n in range(self._num_nurses): is_working = False for s in range(self._num_shifts): if self.Value(self._shifts[(n, d, s)]): is_working = True print(' Nurse %i works shift %i' % (n, s)) if not is_working: print(' Nurse {} does not work'.format(n)) if self._solution_count >= self._solution_limit: print('Stop search after %i solutions' % self._solution_limit) self.StopSearch() def solution_count(self): return self._solution_count # Display the first five solutions. solution_limit = 5 solution_printer = NursesPartialSolutionPrinter(shifts, num_nurses, num_days, num_shifts, solution_limit) ### C++ // Create an atomic Boolean that will be periodically checked by the limit. std::atomic<bool> stopped(false); model.GetOrCreate<TimeLimit>()->RegisterExternalBooleanAsLimit(&stopped); const int kSolutionLimit = 5; int num_solutions = 0; model.Add(NewFeasibleSolutionObserver([&](const CpSolverResponse& r) { LOG(INFO) << "Solution " << num_solutions; for (int d : all_days) { LOG(INFO) << "Day " << std::to_string(d); for (int n : all_nurses) { bool is_working = false; for (int s : all_shifts) { auto key = std::make_tuple(n, d, s); if (SolutionIntegerValue(r, shifts[key])) { is_working = true; LOG(INFO) << " Nurse " << std::to_string(n) << " works shift " << std::to_string(s); } } if (!is_working) { LOG(INFO) << " Nurse " << std::to_string(n) << " does not work"; } } } num_solutions++; if (num_solutions >= kSolutionLimit) { stopped = true; LOG(INFO) << "Stop search after " << kSolutionLimit << " solutions."; } })); ### Java final int solutionLimit = 5; class VarArraySolutionPrinterWithLimit extends CpSolverSolutionCallback { public VarArraySolutionPrinterWithLimit( int[] allNurses, int[] allDays, int[] allShifts, Literal[][][] shifts, int limit) { solutionCount = 0; this.allNurses = allNurses; this.allDays = allDays; this.allShifts = allShifts; this.shifts = shifts; solutionLimit = limit; } @Override public void onSolutionCallback() { System.out.printf("Solution #%d:%n", solutionCount); for (int d : allDays) { System.out.printf("Day %d%n", d); for (int n : allNurses) { boolean isWorking = false; for (int s : allShifts) { if (booleanValue(shifts[n][d][s])) { isWorking = true; System.out.printf(" Nurse %d work shift %d%n", n, s); } } if (!isWorking) { System.out.printf(" Nurse %d does not work%n", n); } } } solutionCount++; if (solutionCount >= solutionLimit) { System.out.printf("Stop search after %d solutions%n", solutionLimit); stopSearch(); } } public int getSolutionCount() { return solutionCount; } private int solutionCount; private final int[] allNurses; private final int[] allDays; private final int[] allShifts; private final Literal[][][] shifts; private final int solutionLimit; } VarArraySolutionPrinterWithLimit cb = new VarArraySolutionPrinterWithLimit(allNurses, allDays, allShifts, shifts, solutionLimit); ### C# First define the SolutionPrinter class. public class SolutionPrinter : CpSolverSolutionCallback { public SolutionPrinter(int[] allNurses, int[] allDays, int[] allShifts, Dictionary<(int, int, int), BoolVar> shifts, int limit) { solutionCount_ = 0; allNurses_ = allNurses; allDays_ = allDays; allShifts_ = allShifts; shifts_ = shifts; solutionLimit_ = limit; } public override void OnSolutionCallback() { Console.WriteLine($"Solution #{solutionCount_}:");
foreach (int d in allDays_)
{
Console.WriteLine($"Day {d}"); foreach (int n in allNurses_) { bool isWorking = false; foreach (int s in allShifts_) { if (Value(shifts_[(n, d, s)]) == 1L) { isWorking = true; Console.WriteLine($"  Nurse {n} work shift {s}");
}
}
if (!isWorking)
{
Console.WriteLine($" Nurse {d} does not work"); } } } solutionCount_++; if (solutionCount_ >= solutionLimit_) { Console.WriteLine($"Stop search after {solutionLimit_} solutions");
StopSearch();
}
}

public int SolutionCount()
{
return solutionCount_;
}

private int solutionCount_;
private int[] allNurses_;
private int[] allDays_;
private int[] allShifts_;
private Dictionary<(int, int, int), BoolVar> shifts_;
private int solutionLimit_;
}

Then instantiate it using:

const int solutionLimit = 5;
SolutionPrinter cb = new SolutionPrinter(allNurses, allDays, allShifts, shifts, solutionLimit);

### Invoke the solver

The following code calls the solver and displays the first five solutions.

### Python

solver.Solve(model, solution_printer)

### C++

const CpSolverResponse response = SolveCpModel(cp_model.Build(), &model);

### Java

CpSolverStatus status = solver.solve(model, cb);
System.out.println("Status: " + status);
System.out.println(cb.getSolutionCount() + " solutions found.");

### C#

CpSolverStatus status = solver.Solve(model, cb);
Console.WriteLine($"Solve status: {status}"); ### Solutions Here are the first five solutions. Solution 0 Day 0 Nurse 0 does not work Nurse 1 works shift 0 Nurse 2 works shift 1 Nurse 3 works shift 2 Day 1 Nurse 0 works shift 2 Nurse 1 does not work Nurse 2 works shift 1 Nurse 3 works shift 0 Day 2 Nurse 0 works shift 2 Nurse 1 works shift 1 Nurse 2 works shift 0 Nurse 3 does not work Solution 1 Day 0 Nurse 0 works shift 0 Nurse 1 does not work Nurse 2 works shift 1 Nurse 3 works shift 2 Day 1 Nurse 0 does not work Nurse 1 works shift 2 Nurse 2 works shift 1 Nurse 3 works shift 0 Day 2 Nurse 0 works shift 2 Nurse 1 works shift 1 Nurse 2 works shift 0 Nurse 3 does not work Solution 2 Day 0 Nurse 0 works shift 0 Nurse 1 does not work Nurse 2 works shift 1 Nurse 3 works shift 2 Day 1 Nurse 0 works shift 1 Nurse 1 works shift 2 Nurse 2 does not work Nurse 3 works shift 0 Day 2 Nurse 0 works shift 2 Nurse 1 works shift 1 Nurse 2 works shift 0 Nurse 3 does not work Solution 3 Day 0 Nurse 0 does not work Nurse 1 works shift 0 Nurse 2 works shift 1 Nurse 3 works shift 2 Day 1 Nurse 0 works shift 1 Nurse 1 works shift 2 Nurse 2 does not work Nurse 3 works shift 0 Day 2 Nurse 0 works shift 2 Nurse 1 works shift 1 Nurse 2 works shift 0 Nurse 3 does not work Solution 4 Day 0 Nurse 0 does not work Nurse 1 works shift 0 Nurse 2 works shift 1 Nurse 3 works shift 2 Day 1 Nurse 0 works shift 2 Nurse 1 works shift 1 Nurse 2 does not work Nurse 3 works shift 0 Day 2 Nurse 0 works shift 2 Nurse 1 works shift 1 Nurse 2 works shift 0 Nurse 3 does not work Statistics - conflicts : 5 - branches : 142 - wall time : 0.002484 s - solutions found: 5  The total number of solutions is 5184. The following counting argument explains why. First, there are 4 choices for the one nurse who works an extra shift. Having chosen that nurse, there are 3 shifts the nurse can be assigned to on each of the 3 days, so the number of possible ways to assign the nurse with the extra shift is 4 · 33 = 108. After assigning this nurse, there are two remaining unassigned shifts on each day. Of the remaining three nurses, one works days 0 and 1, one works days 0 and 2, and one works days 1 and 2. There are 3! = 6 ways to assign the nurses to these days, as shown in the diagram below. (The three nurses are labeled A, B, and C, and we have not yet assigned them to shifts.)  Day 0 Day 1 Day 2 A B A C B C A B B C A C A C A B B C A C B C A B B C A B A C B C A C A B For each row in the above diagram, there are 23 = 8 possible ways to assign the remaining shifts to the nurses (two choices on each day). So the total number of possible assignments is 108·6·8 = 5184. ### Entire program Here is the entire program for the nurse scheduling problem. ### Python """Example of a simple nurse scheduling problem.""" from ortools.sat.python import cp_model def main(): # Data. num_nurses = 4 num_shifts = 3 num_days = 3 all_nurses = range(num_nurses) all_shifts = range(num_shifts) all_days = range(num_days) # Creates the model. model = cp_model.CpModel() # Creates shift variables. # shifts[(n, d, s)]: nurse 'n' works shift 's' on day 'd'. shifts = {} for n in all_nurses: for d in all_days: for s in all_shifts: shifts[(n, d, s)] = model.NewBoolVar('shift_n%id%is%i' % (n, d, s)) # Each shift is assigned to exactly one nurse in the schedule period. for d in all_days: for s in all_shifts: model.AddExactlyOne(shifts[(n, d, s)] for n in all_nurses) # Each nurse works at most one shift per day. for n in all_nurses: for d in all_days: model.AddAtMostOne(shifts[(n, d, s)] for s in all_shifts) # Try to distribute the shifts evenly, so that each nurse works # min_shifts_per_nurse shifts. If this is not possible, because the total # number of shifts is not divisible by the number of nurses, some nurses will # be assigned one more shift. min_shifts_per_nurse = (num_shifts * num_days) // num_nurses if num_shifts * num_days % num_nurses == 0: max_shifts_per_nurse = min_shifts_per_nurse else: max_shifts_per_nurse = min_shifts_per_nurse + 1 for n in all_nurses: num_shifts_worked = [] for d in all_days: for s in all_shifts: num_shifts_worked.append(shifts[(n, d, s)]) model.Add(min_shifts_per_nurse <= sum(num_shifts_worked)) model.Add(sum(num_shifts_worked) <= max_shifts_per_nurse) # Creates the solver and solve. solver = cp_model.CpSolver() solver.parameters.linearization_level = 0 # Enumerate all solutions. solver.parameters.enumerate_all_solutions = True class NursesPartialSolutionPrinter(cp_model.CpSolverSolutionCallback): """Print intermediate solutions.""" def __init__(self, shifts, num_nurses, num_days, num_shifts, limit): cp_model.CpSolverSolutionCallback.__init__(self) self._shifts = shifts self._num_nurses = num_nurses self._num_days = num_days self._num_shifts = num_shifts self._solution_count = 0 self._solution_limit = limit def on_solution_callback(self): self._solution_count += 1 print('Solution %i' % self._solution_count) for d in range(self._num_days): print('Day %i' % d) for n in range(self._num_nurses): is_working = False for s in range(self._num_shifts): if self.Value(self._shifts[(n, d, s)]): is_working = True print(' Nurse %i works shift %i' % (n, s)) if not is_working: print(' Nurse {} does not work'.format(n)) if self._solution_count >= self._solution_limit: print('Stop search after %i solutions' % self._solution_limit) self.StopSearch() def solution_count(self): return self._solution_count # Display the first five solutions. solution_limit = 5 solution_printer = NursesPartialSolutionPrinter(shifts, num_nurses, num_days, num_shifts, solution_limit) solver.Solve(model, solution_printer) # Statistics. print('\nStatistics') print(' - conflicts : %i' % solver.NumConflicts()) print(' - branches : %i' % solver.NumBranches()) print(' - wall time : %f s' % solver.WallTime()) print(' - solutions found: %i' % solution_printer.solution_count()) if __name__ == '__main__': main() ### C++ // Example of a simple nurse scheduling problem. #include <stdlib.h> #include <atomic> #include <map> #include <numeric> #include <string> #include <tuple> #include <vector> #include "absl/strings/str_format.h" #include "ortools/base/logging.h" #include "ortools/sat/cp_model.h" #include "ortools/sat/cp_model.pb.h" #include "ortools/sat/cp_model_solver.h" #include "ortools/sat/model.h" #include "ortools/sat/sat_parameters.pb.h" #include "ortools/util/time_limit.h" namespace operations_research { namespace sat { void NurseSat() { const int num_nurses = 4; const int num_shifts = 3; const int num_days = 3; std::vector<int> all_nurses(num_nurses); std::iota(all_nurses.begin(), all_nurses.end(), 0); std::vector<int> all_shifts(num_shifts); std::iota(all_shifts.begin(), all_shifts.end(), 0); std::vector<int> all_days(num_days); std::iota(all_days.begin(), all_days.end(), 0); // Creates the model. CpModelBuilder cp_model; // Creates shift variables. // shifts[(n, d, s)]: nurse 'n' works shift 's' on day 'd'. std::map<std::tuple<int, int, int>, BoolVar> shifts; for (int n : all_nurses) { for (int d : all_days) { for (int s : all_shifts) { auto key = std::make_tuple(n, d, s); shifts[key] = cp_model.NewBoolVar().WithName( absl::StrFormat("shift_n%dd%ds%d", n, d, s)); } } } // Each shift is assigned to exactly one nurse in the schedule period. for (int d : all_days) { for (int s : all_shifts) { std::vector<BoolVar> nurses; for (int n : all_nurses) { auto key = std::make_tuple(n, d, s); nurses.push_back(shifts[key]); } cp_model.AddExactlyOne(nurses); } } // Each nurse works at most one shift per day. for (int n : all_nurses) { for (int d : all_days) { std::vector<BoolVar> work; for (int s : all_shifts) { auto key = std::make_tuple(n, d, s); work.push_back(shifts[key]); } cp_model.AddAtMostOne(work); } } // Try to distribute the shifts evenly, so that each nurse works // min_shifts_per_nurse shifts. If this is not possible, because the total // number of shifts is not divisible by the number of nurses, some nurses will // be assigned one more shift. int min_shifts_per_nurse = (num_shifts * num_days) / num_nurses; int max_shifts_per_nurse; if ((num_shifts * num_days) % num_nurses == 0) { max_shifts_per_nurse = min_shifts_per_nurse; } else { max_shifts_per_nurse = min_shifts_per_nurse + 1; } for (int n : all_nurses) { std::vector<BoolVar> num_shifts_worked; // int num_shifts_worked = 0; for (int d : all_days) { for (int s : all_shifts) { auto key = std::make_tuple(n, d, s); num_shifts_worked.push_back(shifts[key]); } } cp_model.AddLessOrEqual(min_shifts_per_nurse, LinearExpr::Sum(num_shifts_worked)); cp_model.AddLessOrEqual(LinearExpr::Sum(num_shifts_worked), max_shifts_per_nurse); } Model model; SatParameters parameters; parameters.set_linearization_level(0); // Enumerate all solutions. parameters.set_enumerate_all_solutions(true); model.Add(NewSatParameters(parameters)); // Display the first five solutions. // Create an atomic Boolean that will be periodically checked by the limit. std::atomic<bool> stopped(false); model.GetOrCreate<TimeLimit>()->RegisterExternalBooleanAsLimit(&stopped); const int kSolutionLimit = 5; int num_solutions = 0; model.Add(NewFeasibleSolutionObserver([&](const CpSolverResponse& r) { LOG(INFO) << "Solution " << num_solutions; for (int d : all_days) { LOG(INFO) << "Day " << std::to_string(d); for (int n : all_nurses) { bool is_working = false; for (int s : all_shifts) { auto key = std::make_tuple(n, d, s); if (SolutionIntegerValue(r, shifts[key])) { is_working = true; LOG(INFO) << " Nurse " << std::to_string(n) << " works shift " << std::to_string(s); } } if (!is_working) { LOG(INFO) << " Nurse " << std::to_string(n) << " does not work"; } } } num_solutions++; if (num_solutions >= kSolutionLimit) { stopped = true; LOG(INFO) << "Stop search after " << kSolutionLimit << " solutions."; } })); const CpSolverResponse response = SolveCpModel(cp_model.Build(), &model); // Statistics. LOG(INFO) << "Statistics"; LOG(INFO) << CpSolverResponseStats(response); LOG(INFO) << "solutions found : " << std::to_string(num_solutions); } } // namespace sat } // namespace operations_research int main() { operations_research::sat::NurseSat(); return EXIT_SUCCESS; } ### Java package com.google.ortools.sat.samples; import com.google.ortools.Loader; import com.google.ortools.sat.CpModel; import com.google.ortools.sat.CpSolver; import com.google.ortools.sat.CpSolverSolutionCallback; import com.google.ortools.sat.CpSolverStatus; import com.google.ortools.sat.LinearExpr; import com.google.ortools.sat.LinearExprBuilder; import com.google.ortools.sat.Literal; import java.util.ArrayList; import java.util.List; import java.util.stream.IntStream; /** Nurses problem. */ public class NursesSat { public static void main(String[] args) { Loader.loadNativeLibraries(); final int numNurses = 4; final int numDays = 3; final int numShifts = 3; final int[] allNurses = IntStream.range(0, numNurses).toArray(); final int[] allDays = IntStream.range(0, numDays).toArray(); final int[] allShifts = IntStream.range(0, numShifts).toArray(); // Creates the model. CpModel model = new CpModel(); // Creates shift variables. // shifts[(n, d, s)]: nurse 'n' works shift 's' on day 'd'. Literal[][][] shifts = new Literal[numNurses][numDays][numShifts]; for (int n : allNurses) { for (int d : allDays) { for (int s : allShifts) { shifts[n][d][s] = model.newBoolVar("shifts_n" + n + "d" + d + "s" + s); } } } // Each shift is assigned to exactly one nurse in the schedule period. for (int d : allDays) { for (int s : allShifts) { List<Literal> nurses = new ArrayList<>(); for (int n : allNurses) { nurses.add(shifts[n][d][s]); } model.addExactlyOne(nurses); } } // Each nurse works at most one shift per day. for (int n : allNurses) { for (int d : allDays) { List<Literal> work = new ArrayList<>(); for (int s : allShifts) { work.add(shifts[n][d][s]); } model.addAtMostOne(work); } } // Try to distribute the shifts evenly, so that each nurse works // minShiftsPerNurse shifts. If this is not possible, because the total // number of shifts is not divisible by the number of nurses, some nurses will // be assigned one more shift. int minShiftsPerNurse = (numShifts * numDays) / numNurses; int maxShiftsPerNurse; if ((numShifts * numDays) % numNurses == 0) { maxShiftsPerNurse = minShiftsPerNurse; } else { maxShiftsPerNurse = minShiftsPerNurse + 1; } for (int n : allNurses) { LinearExprBuilder numShiftsWorked = LinearExpr.newBuilder(); for (int d : allDays) { for (int s : allShifts) { numShiftsWorked.add(shifts[n][d][s]); } } model.addLinearConstraint(numShiftsWorked, minShiftsPerNurse, maxShiftsPerNurse); } CpSolver solver = new CpSolver(); solver.getParameters().setLinearizationLevel(0); // Tell the solver to enumerate all solutions. solver.getParameters().setEnumerateAllSolutions(true); // Display the first five solutions. final int solutionLimit = 5; class VarArraySolutionPrinterWithLimit extends CpSolverSolutionCallback { public VarArraySolutionPrinterWithLimit( int[] allNurses, int[] allDays, int[] allShifts, Literal[][][] shifts, int limit) { solutionCount = 0; this.allNurses = allNurses; this.allDays = allDays; this.allShifts = allShifts; this.shifts = shifts; solutionLimit = limit; } @Override public void onSolutionCallback() { System.out.printf("Solution #%d:%n", solutionCount); for (int d : allDays) { System.out.printf("Day %d%n", d); for (int n : allNurses) { boolean isWorking = false; for (int s : allShifts) { if (booleanValue(shifts[n][d][s])) { isWorking = true; System.out.printf(" Nurse %d work shift %d%n", n, s); } } if (!isWorking) { System.out.printf(" Nurse %d does not work%n", n); } } } solutionCount++; if (solutionCount >= solutionLimit) { System.out.printf("Stop search after %d solutions%n", solutionLimit); stopSearch(); } } public int getSolutionCount() { return solutionCount; } private int solutionCount; private final int[] allNurses; private final int[] allDays; private final int[] allShifts; private final Literal[][][] shifts; private final int solutionLimit; } VarArraySolutionPrinterWithLimit cb = new VarArraySolutionPrinterWithLimit(allNurses, allDays, allShifts, shifts, solutionLimit); // Creates a solver and solves the model. CpSolverStatus status = solver.solve(model, cb); System.out.println("Status: " + status); System.out.println(cb.getSolutionCount() + " solutions found."); // Statistics. System.out.println("Statistics"); System.out.printf(" conflicts: %d%n", solver.numConflicts()); System.out.printf(" branches : %d%n", solver.numBranches()); System.out.printf(" wall time: %f s%n", solver.wallTime()); } private NursesSat() {} } ### C# using System; using System.Collections.Generic; using System.IO; using System.Linq; using Google.OrTools.Sat; public class NursesSat { public class SolutionPrinter : CpSolverSolutionCallback { public SolutionPrinter(int[] allNurses, int[] allDays, int[] allShifts, Dictionary<(int, int, int), BoolVar> shifts, int limit) { solutionCount_ = 0; allNurses_ = allNurses; allDays_ = allDays; allShifts_ = allShifts; shifts_ = shifts; solutionLimit_ = limit; } public override void OnSolutionCallback() { Console.WriteLine($"Solution #{solutionCount_}:");
foreach (int d in allDays_)
{
Console.WriteLine($"Day {d}"); foreach (int n in allNurses_) { bool isWorking = false; foreach (int s in allShifts_) { if (Value(shifts_[(n, d, s)]) == 1L) { isWorking = true; Console.WriteLine($"  Nurse {n} work shift {s}");
}
}
if (!isWorking)
{
Console.WriteLine($" Nurse {d} does not work"); } } } solutionCount_++; if (solutionCount_ >= solutionLimit_) { Console.WriteLine($"Stop search after {solutionLimit_} solutions");
StopSearch();
}
}

public int SolutionCount()
{
return solutionCount_;
}

private int solutionCount_;
private int[] allNurses_;
private int[] allDays_;
private int[] allShifts_;
private Dictionary<(int, int, int), BoolVar> shifts_;
private int solutionLimit_;
}

public static void Main(String[] args)
{
const int numNurses = 4;
const int numDays = 3;
const int numShifts = 3;

int[] allNurses = Enumerable.Range(0, numNurses).ToArray();
int[] allDays = Enumerable.Range(0, numDays).ToArray();
int[] allShifts = Enumerable.Range(0, numShifts).ToArray();

// Creates the model.
CpModel model = new CpModel();
model.Model.Variables.Capacity = numNurses * numDays * numShifts;

// Creates shift variables.
// shifts[(n, d, s)]: nurse 'n' works shift 's' on day 'd'.
Dictionary<(int, int, int), BoolVar> shifts =
new Dictionary<(int, int, int), BoolVar>(numNurses * numDays * numShifts);
foreach (int n in allNurses)
{
foreach (int d in allDays)
{
foreach (int s in allShifts)
{
shifts.Add((n, d, s), model.NewBoolVar($"shifts_n{n}d{d}s{s}")); } } } // Each shift is assigned to exactly one nurse in the schedule period. List<ILiteral> literals = new List<ILiteral>(); foreach (int d in allDays) { foreach (int s in allShifts) { foreach (int n in allNurses) { literals.Add(shifts[(n, d, s)]); } model.AddExactlyOne(literals); literals.Clear(); } } // Each nurse works at most one shift per day. foreach (int n in allNurses) { foreach (int d in allDays) { foreach (int s in allShifts) { literals.Add(shifts[(n, d, s)]); } model.AddAtMostOne(literals); literals.Clear(); } } // Try to distribute the shifts evenly, so that each nurse works // minShiftsPerNurse shifts. If this is not possible, because the total // number of shifts is not divisible by the number of nurses, some nurses will // be assigned one more shift. int minShiftsPerNurse = (numShifts * numDays) / numNurses; int maxShiftsPerNurse; if ((numShifts * numDays) % numNurses == 0) { maxShiftsPerNurse = minShiftsPerNurse; } else { maxShiftsPerNurse = minShiftsPerNurse + 1; } List<IntVar> numShiftsWorked = new List<IntVar>(); foreach (int n in allNurses) { foreach (int d in allDays) { foreach (int s in allShifts) { numShiftsWorked.Add(shifts[(n, d, s)]); } } model.AddLinearConstraint(LinearExpr.Sum(numShiftsWorked), minShiftsPerNurse, maxShiftsPerNurse); numShiftsWorked.Clear(); } CpSolver solver = new CpSolver(); // Tell the solver to enumerate all solutions. solver.StringParameters += "linearization_level:0 " + "enumerate_all_solutions:true "; // Display the first five solutions. const int solutionLimit = 5; SolutionPrinter cb = new SolutionPrinter(allNurses, allDays, allShifts, shifts, solutionLimit); // Solve CpSolverStatus status = solver.Solve(model, cb); Console.WriteLine($"Solve status: {status}");

Console.WriteLine("Statistics");
Console.WriteLine($" conflicts: {solver.NumConflicts()}"); Console.WriteLine($"  branches : {solver.NumBranches()}");
}
}
}

### Create the constraints

The following code create the constraints for the problem.

### Python

for d in all_days:
for s in all_shifts:
model.AddExactlyOne(shifts[(n, d, s)] for n in all_nurses)

### C++

for (int d : all_days) {
for (int s : all_shifts) {
std::vector<BoolVar> nurses;
for (int n : all_nurses) {
auto key = std::make_tuple(n, d, s);
nurses.push_back(shifts[key]);
}
}
}

### Java

for (int d : allDays) {
for (int s : allShifts) {
List<Literal> nurses = new ArrayList<>();
for (int n : allNurses) {
}
}
}

### C#

foreach (int d in allDays)
{
foreach (int s in allShifts)
{
IntVar[] x = new IntVar[numNurses];
foreach (int n in allNurses)
{
var key = Tuple.Create(n, d, s);
x[n] = shifts[key];
}
}
}

### Python

for n in all_nurses:
for d in all_days:
model.AddAtMostOne(shifts[(n, d, s)] for s in all_shifts)

### C++

for (int n : all_nurses) {
for (int d : all_days) {
std::vector<BoolVar> work;
for (int s : all_shifts) {
auto key = std::make_tuple(n, d, s);
work.push_back(shifts[key]);
}
}
}

### Java

for (int n : allNurses) {
for (int d : allDays) {
List<Literal> work = new ArrayList<>();
for (int s : allShifts) {
}
}
}

### C#

foreach (int n in allNurses)
{
foreach (int d in allDays)
{
IntVar[] x = new IntVar[numShifts];
foreach (int s in allShifts)
{
var key = Tuple.Create(n, d, s);
x[s] = shifts[key];
}
}
}

### Python

# Try to distribute the shifts evenly, so that each nurse works
# min_shifts_per_nurse shifts. If this is not possible, because the total
# number of shifts is not divisible by the number of nurses, some nurses will
# be assigned one more shift.
min_shifts_per_nurse = (num_shifts * num_days) // num_nurses
if num_shifts * num_days % num_nurses == 0:
max_shifts_per_nurse = min_shifts_per_nurse
else:
max_shifts_per_nurse = min_shifts_per_nurse + 1
for n in all_nurses:
num_shifts_worked = 0
for d in all_days:
for s in all_shifts:
num_shifts_worked += shifts[(n, d, s)]
model.Add(num_shifts_worked <= max_shifts_per_nurse)

### C++

// Try to distribute the shifts evenly, so that each nurse works
// min_shifts_per_nurse shifts. If this is not possible, because the total
// number of shifts is not divisible by the number of nurses, some nurses will
// be assigned one more shift.
int min_shifts_per_nurse = (num_shifts * num_days) / num_nurses;
int max_shifts_per_nurse;
if ((num_shifts * num_days) % num_nurses == 0) {
max_shifts_per_nurse = min_shifts_per_nurse;
} else {
max_shifts_per_nurse = min_shifts_per_nurse + 1;
}
for (int n : all_nurses) {
LinearExpr num_worked_shifts;
for (int d : all_days) {
for (int s : all_shifts) {
auto key = std::make_tuple(n, d, s);
num_worked_shifts += shifts[key];
}
}
}

### Java

// Try to distribute the shifts evenly, so that each nurse works
// minShiftsPerNurse shifts. If this is not possible, because the total
// number of shifts is not divisible by the number of nurses, some nurses will
// be assigned one more shift.
int minShiftsPerNurse = (numShifts * numDays) / numNurses;
int maxShiftsPerNurse;
if ((numShifts * numDays) % numNurses == 0) {
maxShiftsPerNurse = minShiftsPerNurse;
} else {
maxShiftsPerNurse = minShiftsPerNurse + 1;
}
for (int n : allNurses) {
LinearExprBuilder numShiftsWorked = LinearExpr.newBuilder();
for (int d : allDays) {
for (int s : allShifts) {
}
}
}

### C#

// Try to distribute the shifts evenly, so that each nurse works
// minShiftsPerNurse shifts. If this is not possible, because the total
// number of shifts is not divisible by the number of nurses, some nurses will
// be assigned one more shift.
int minShiftsPerNurse = (numShifts * numDays) / numNurses;
int maxShiftsPerNurse;
if ((numShifts * numDays) % numNurses == 0)
{
maxShiftsPerNurse = minShiftsPerNurse;
}
else
{
maxShiftsPerNurse = minShiftsPerNurse + 1;
}
foreach (int n in allNurses)
{
IntVar[] numShiftsWorked = new IntVar[numDays * numShifts];
foreach (int d in allDays)
{
foreach (int s in allShifts)
{
var key = Tuple.Create(n, d, s);
numShiftsWorked[d * numShifts + s] = shifts[key];
}
}
}

### Objective for the example

We want to optimize the following objective function.

### Python

# pylint: disable=g-complex-comprehension
model.Maximize(
sum(shift_requests[n][d][s] * shifts[(n, d, s)] for n in all_nurses
for d in all_days for s in all_shifts))

### C++

LinearExpr objective_expr;
for (int n : all_nurses) {
for (int d : all_days) {
for (int s : all_shifts) {
if (shift_requests[n][d][s] == 1) {
auto key = std::make_tuple(n, d, s);
objective_expr += shifts[key] * shift_requests[n][d][s];
}
}
}
}
cp_model.Maximize(objective_expr);

### Java

LinearExprBuilder obj = LinearExpr.newBuilder();
for (int n : allNurses) {
for (int d : allDays) {
for (int s : allShifts) {
}
}
}
model.maximize(obj);

### C#

IntVar[] flatShifts = new IntVar[numNurses * numDays * numShifts];
int[] flatShiftRequests = new int[numNurses * numDays * numShifts];
foreach (int n in allNurses)
{
foreach (int d in allDays)
{
foreach (int s in allShifts)
{
var key = Tuple.Create(n, d, s);
flatShifts[n * numDays * numShifts + d * numShifts + s] = shifts[key];
flatShiftRequests[n * numDays * numShifts + d * numShifts + s] = shiftRequests[n, d, s];
}
}
}
model.Maximize(LinearExpr.WeightedSum(flatShifts, flatShiftRequests));

Since shift_requests[n][d][s] * shifts[(n, d, s) is 1 if shift s is assigned to nurse n on day d and that nurse requested that shift (and 0 otherwise), the objective is the number shift of assignments that meet a request.

### Invoke the solver

The following code calls the solver.

### Python

solver = cp_model.CpSolver()
status = solver.Solve(model)

### C++

const CpSolverResponse response = Solve(cp_model.Build());

### Java

CpSolver solver = new CpSolver();
CpSolverStatus status = solver.solve(model);

### C#

CpSolver solver = new CpSolver();
CpSolverStatus status = solver.Solve(model);
Console.WriteLine($"Solve status: {status}"); ### Display the results The following code displays the following output, which contains an optimal schedule (although perhaps not the only one). The output shows which shift assignments were requested and the number of request that were met. ### Python if status == cp_model.OPTIMAL: print('Solution:') for d in all_days: print('Day', d) for n in all_nurses: for s in all_shifts: if solver.Value(shifts[(n, d, s)]) == 1: if shift_requests[n][d][s] == 1: print('Nurse', n, 'works shift', s, '(requested).') else: print('Nurse', n, 'works shift', s, '(not requested).') print() print(f'Number of shift requests met = {solver.ObjectiveValue()}', f'(out of {num_nurses * min_shifts_per_nurse})') else: print('No optimal solution found !') ### C++ if (response.status() == CpSolverStatus::OPTIMAL) { LOG(INFO) << "Solution:"; for (int d : all_days) { LOG(INFO) << "Day " << std::to_string(d); for (int n : all_nurses) { for (int s : all_shifts) { auto key = std::make_tuple(n, d, s); if (SolutionIntegerValue(response, shifts[key]) == 1) { if (shift_requests[n][d][s] == 1) { LOG(INFO) << " Nurse " << std::to_string(n) << " works shift " << std::to_string(s) << " (requested)."; } else { LOG(INFO) << " Nurse " << std::to_string(n) << " works shift " << std::to_string(s) << " (not requested)."; } } } } LOG(INFO) << ""; } LOG(INFO) << "Number of shift requests met = " << response.objective_value() << " (out of " << num_nurses * min_shifts_per_nurse << ")"; } else { LOG(INFO) << "No optimal solution found !"; } ### Java if (status == CpSolverStatus.OPTIMAL || status == CpSolverStatus.FEASIBLE) { System.out.printf("Solution:%n"); for (int d : allDays) { System.out.printf("Day %d%n", d); for (int n : allNurses) { for (int s : allShifts) { if (solver.booleanValue(shifts[n][d][s])) { if (shiftRequests[n][d][s] == 1) { System.out.printf(" Nurse %d works shift %d (requested).%n", n, s); } else { System.out.printf(" Nurse %d works shift %d (not requested).%n", n, s); } } } } } System.out.printf("Number of shift requests met = %f (out of %d)%n", solver.objectiveValue(), numNurses * minShiftsPerNurse); } else { System.out.printf("No optimal solution found !"); } ### C# if (status == CpSolverStatus.Optimal || status == CpSolverStatus.Feasible) { Console.WriteLine("Solution:"); foreach (int d in allDays) { Console.WriteLine($"Day {d}");
foreach (int n in allNurses)
{
bool isWorking = false;
foreach (int s in allShifts)
{
var key = Tuple.Create(n, d, s);
if (solver.Value(shifts[key]) == 1L)
{
if (shiftRequests[n, d, s] == 1)
{
Console.WriteLine($" Nurse {n} work shift {s} (requested)."); } else { Console.WriteLine($"  Nurse {n} work shift {s} (not requested).");
}
}
}
}
}
Console.WriteLine(
$"Number of shift requests met = {solver.ObjectiveValue} (out of {numNurses * minShiftsPerNurse})."); } else { Console.WriteLine("No solution found."); } When you run the program, it displays the following output: Day 0 Nurse 1 works shift 0 (not requested). Nurse 2 works shift 1 (requested). Nurse 3 works shift 2 (requested). Day 1 Nurse 0 works shift 0 (not requested). Nurse 2 works shift 1 (requested). Nurse 4 works shift 2 (requested). Day 2 Nurse 1 works shift 2 (not requested). Nurse 3 works shift 0 (requested). Nurse 4 works shift 1 (requested). Day 3 Nurse 2 works shift 0 (requested). Nurse 3 works shift 1 (requested). Nurse 4 works shift 2 (not requested). Day 4 Nurse 0 works shift 2 (requested). Nurse 1 works shift 0 (requested). Nurse 4 works shift 1 (not requested). Day 5 Nurse 0 works shift 2 (not requested). Nurse 2 works shift 1 (requested). Nurse 3 works shift 0 (requested). Day 6 Nurse 0 works shift 1 (not requested). Nurse 1 works shift 2 (requested). Nurse 4 works shift 0 (not requested). Statistics - Number of shift requests met = 13 (out of 20 ) - wall time : 0.003571 s ### Entire program Here is the entire program for scheduling with shift requests. ### Python """Nurse scheduling problem with shift requests.""" from ortools.sat.python import cp_model def main(): # This program tries to find an optimal assignment of nurses to shifts # (3 shifts per day, for 7 days), subject to some constraints (see below). # Each nurse can request to be assigned to specific shifts. # The optimal assignment maximizes the number of fulfilled shift requests. num_nurses = 5 num_shifts = 3 num_days = 7 all_nurses = range(num_nurses) all_shifts = range(num_shifts) all_days = range(num_days) shift_requests = [[[0, 0, 1], [0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 0, 1]], [[0, 0, 0], [0, 0, 0], [0, 1, 0], [0, 1, 0], [1, 0, 0], [0, 0, 0], [0, 0, 1]], [[0, 1, 0], [0, 1, 0], [0, 0, 0], [1, 0, 0], [0, 0, 0], [0, 1, 0], [0, 0, 0]], [[0, 0, 1], [0, 0, 0], [1, 0, 0], [0, 1, 0], [0, 0, 0], [1, 0, 0], [0, 0, 0]], [[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 0, 0], [1, 0, 0], [0, 1, 0], [0, 0, 0]]] # Creates the model. model = cp_model.CpModel() # Creates shift variables. # shifts[(n, d, s)]: nurse 'n' works shift 's' on day 'd'. shifts = {} for n in all_nurses: for d in all_days: for s in all_shifts: shifts[(n, d, s)] = model.NewBoolVar('shift_n%id%is%i' % (n, d, s)) # Each shift is assigned to exactly one nurse in . for d in all_days: for s in all_shifts: model.AddExactlyOne(shifts[(n, d, s)] for n in all_nurses) # Each nurse works at most one shift per day. for n in all_nurses: for d in all_days: model.AddAtMostOne(shifts[(n, d, s)] for s in all_shifts) # Try to distribute the shifts evenly, so that each nurse works # min_shifts_per_nurse shifts. If this is not possible, because the total # number of shifts is not divisible by the number of nurses, some nurses will # be assigned one more shift. min_shifts_per_nurse = (num_shifts * num_days) // num_nurses if num_shifts * num_days % num_nurses == 0: max_shifts_per_nurse = min_shifts_per_nurse else: max_shifts_per_nurse = min_shifts_per_nurse + 1 for n in all_nurses: num_shifts_worked = 0 for d in all_days: for s in all_shifts: num_shifts_worked += shifts[(n, d, s)] model.Add(min_shifts_per_nurse <= num_shifts_worked) model.Add(num_shifts_worked <= max_shifts_per_nurse) # pylint: disable=g-complex-comprehension model.Maximize( sum(shift_requests[n][d][s] * shifts[(n, d, s)] for n in all_nurses for d in all_days for s in all_shifts)) # Creates the solver and solve. solver = cp_model.CpSolver() status = solver.Solve(model) if status == cp_model.OPTIMAL: print('Solution:') for d in all_days: print('Day', d) for n in all_nurses: for s in all_shifts: if solver.Value(shifts[(n, d, s)]) == 1: if shift_requests[n][d][s] == 1: print('Nurse', n, 'works shift', s, '(requested).') else: print('Nurse', n, 'works shift', s, '(not requested).') print() print(f'Number of shift requests met = {solver.ObjectiveValue()}', f'(out of {num_nurses * min_shifts_per_nurse})') else: print('No optimal solution found !') # Statistics. print('\nStatistics') print(' - conflicts: %i' % solver.NumConflicts()) print(' - branches : %i' % solver.NumBranches()) print(' - wall time: %f s' % solver.WallTime()) if __name__ == '__main__': main() ### C++ // Nurse scheduling problem with shift requests. #include <stdlib.h> #include <cstdint> #include <map> #include <numeric> #include <string> #include <tuple> #include <vector> #include "absl/strings/str_format.h" #include "ortools/base/logging.h" #include "ortools/sat/cp_model.h" #include "ortools/sat/cp_model.pb.h" #include "ortools/sat/cp_model_solver.h" namespace operations_research { namespace sat { void ScheduleRequestsSat() { const int num_nurses = 5; const int num_days = 7; const int num_shifts = 3; std::vector<int> all_nurses(num_nurses); std::iota(all_nurses.begin(), all_nurses.end(), 0); std::vector<int> all_days(num_days); std::iota(all_days.begin(), all_days.end(), 0); std::vector<int> all_shifts(num_shifts); std::iota(all_shifts.begin(), all_shifts.end(), 0); std::vector<std::vector<std::vector<int64_t>>> shift_requests = { { {0, 0, 1}, {0, 0, 0}, {0, 0, 0}, {0, 0, 0}, {0, 0, 1}, {0, 1, 0}, {0, 0, 1}, }, { {0, 0, 0}, {0, 0, 0}, {0, 1, 0}, {0, 1, 0}, {1, 0, 0}, {0, 0, 0}, {0, 0, 1}, }, { {0, 1, 0}, {0, 1, 0}, {0, 0, 0}, {1, 0, 0}, {0, 0, 0}, {0, 1, 0}, {0, 0, 0}, }, { {0, 0, 1}, {0, 0, 0}, {1, 0, 0}, {0, 1, 0}, {0, 0, 0}, {1, 0, 0}, {0, 0, 0}, }, { {0, 0, 0}, {0, 0, 1}, {0, 1, 0}, {0, 0, 0}, {1, 0, 0}, {0, 1, 0}, {0, 0, 0}, }, }; // Creates the model. CpModelBuilder cp_model; // Creates shift variables. // shifts[(n, d, s)]: nurse 'n' works shift 's' on day 'd'. std::map<std::tuple<int, int, int>, BoolVar> shifts; for (int n : all_nurses) { for (int d : all_days) { for (int s : all_shifts) { auto key = std::make_tuple(n, d, s); shifts[key] = cp_model.NewBoolVar().WithName( absl::StrFormat("shift_n%dd%ds%d", n, d, s)); } } } // Each shift is assigned to exactly one nurse in the schedule period. for (int d : all_days) { for (int s : all_shifts) { std::vector<BoolVar> nurses; for (int n : all_nurses) { auto key = std::make_tuple(n, d, s); nurses.push_back(shifts[key]); } cp_model.AddExactlyOne(nurses); } } // Each nurse works at most one shift per day. for (int n : all_nurses) { for (int d : all_days) { std::vector<BoolVar> work; for (int s : all_shifts) { auto key = std::make_tuple(n, d, s); work.push_back(shifts[key]); } cp_model.AddAtMostOne(work); } } // Try to distribute the shifts evenly, so that each nurse works // min_shifts_per_nurse shifts. If this is not possible, because the total // number of shifts is not divisible by the number of nurses, some nurses will // be assigned one more shift. int min_shifts_per_nurse = (num_shifts * num_days) / num_nurses; int max_shifts_per_nurse; if ((num_shifts * num_days) % num_nurses == 0) { max_shifts_per_nurse = min_shifts_per_nurse; } else { max_shifts_per_nurse = min_shifts_per_nurse + 1; } for (int n : all_nurses) { LinearExpr num_worked_shifts; for (int d : all_days) { for (int s : all_shifts) { auto key = std::make_tuple(n, d, s); num_worked_shifts += shifts[key]; } } cp_model.AddLessOrEqual(min_shifts_per_nurse, num_worked_shifts); cp_model.AddLessOrEqual(num_worked_shifts, max_shifts_per_nurse); } LinearExpr objective_expr; for (int n : all_nurses) { for (int d : all_days) { for (int s : all_shifts) { if (shift_requests[n][d][s] == 1) { auto key = std::make_tuple(n, d, s); objective_expr += shifts[key] * shift_requests[n][d][s]; } } } } cp_model.Maximize(objective_expr); const CpSolverResponse response = Solve(cp_model.Build()); if (response.status() == CpSolverStatus::OPTIMAL) { LOG(INFO) << "Solution:"; for (int d : all_days) { LOG(INFO) << "Day " << std::to_string(d); for (int n : all_nurses) { for (int s : all_shifts) { auto key = std::make_tuple(n, d, s); if (SolutionIntegerValue(response, shifts[key]) == 1) { if (shift_requests[n][d][s] == 1) { LOG(INFO) << " Nurse " << std::to_string(n) << " works shift " << std::to_string(s) << " (requested)."; } else { LOG(INFO) << " Nurse " << std::to_string(n) << " works shift " << std::to_string(s) << " (not requested)."; } } } } LOG(INFO) << ""; } LOG(INFO) << "Number of shift requests met = " << response.objective_value() << " (out of " << num_nurses * min_shifts_per_nurse << ")"; } else { LOG(INFO) << "No optimal solution found !"; } // Statistics. LOG(INFO) << "Statistics"; LOG(INFO) << CpSolverResponseStats(response); } } // namespace sat } // namespace operations_research int main() { operations_research::sat::ScheduleRequestsSat(); return EXIT_SUCCESS; } ### Java package com.google.ortools.sat.samples; import com.google.ortools.Loader; import com.google.ortools.sat.CpModel; import com.google.ortools.sat.CpSolver; import com.google.ortools.sat.CpSolverStatus; import com.google.ortools.sat.LinearExpr; import com.google.ortools.sat.LinearExprBuilder; import com.google.ortools.sat.Literal; import java.util.ArrayList; import java.util.List; import java.util.stream.IntStream; /** Nurses problem with schedule requests. */ public class ScheduleRequestsSat { public static void main(String[] args) { Loader.loadNativeLibraries(); final int numNurses = 5; final int numDays = 7; final int numShifts = 3; final int[] allNurses = IntStream.range(0, numNurses).toArray(); final int[] allDays = IntStream.range(0, numDays).toArray(); final int[] allShifts = IntStream.range(0, numShifts).toArray(); final int[][][] shiftRequests = new int[][][] { { {0, 0, 1}, {0, 0, 0}, {0, 0, 0}, {0, 0, 0}, {0, 0, 1}, {0, 1, 0}, {0, 0, 1}, }, { {0, 0, 0}, {0, 0, 0}, {0, 1, 0}, {0, 1, 0}, {1, 0, 0}, {0, 0, 0}, {0, 0, 1}, }, { {0, 1, 0}, {0, 1, 0}, {0, 0, 0}, {1, 0, 0}, {0, 0, 0}, {0, 1, 0}, {0, 0, 0}, }, { {0, 0, 1}, {0, 0, 0}, {1, 0, 0}, {0, 1, 0}, {0, 0, 0}, {1, 0, 0}, {0, 0, 0}, }, { {0, 0, 0}, {0, 0, 1}, {0, 1, 0}, {0, 0, 0}, {1, 0, 0}, {0, 1, 0}, {0, 0, 0}, }, }; // Creates the model. CpModel model = new CpModel(); // Creates shift variables. // shifts[(n, d, s)]: nurse 'n' works shift 's' on day 'd'. Literal[][][] shifts = new Literal[numNurses][numDays][numShifts]; for (int n : allNurses) { for (int d : allDays) { for (int s : allShifts) { shifts[n][d][s] = model.newBoolVar("shifts_n" + n + "d" + d + "s" + s); } } } // Each shift is assigned to exactly one nurse in the schedule period. for (int d : allDays) { for (int s : allShifts) { List<Literal> nurses = new ArrayList<>(); for (int n : allNurses) { nurses.add(shifts[n][d][s]); } model.addExactlyOne(nurses); } } // Each nurse works at most one shift per day. for (int n : allNurses) { for (int d : allDays) { List<Literal> work = new ArrayList<>(); for (int s : allShifts) { work.add(shifts[n][d][s]); } model.addAtMostOne(work); } } // Try to distribute the shifts evenly, so that each nurse works // minShiftsPerNurse shifts. If this is not possible, because the total // number of shifts is not divisible by the number of nurses, some nurses will // be assigned one more shift. int minShiftsPerNurse = (numShifts * numDays) / numNurses; int maxShiftsPerNurse; if ((numShifts * numDays) % numNurses == 0) { maxShiftsPerNurse = minShiftsPerNurse; } else { maxShiftsPerNurse = minShiftsPerNurse + 1; } for (int n : allNurses) { LinearExprBuilder numShiftsWorked = LinearExpr.newBuilder(); for (int d : allDays) { for (int s : allShifts) { numShiftsWorked.add(shifts[n][d][s]); } } model.addLinearConstraint(numShiftsWorked, minShiftsPerNurse, maxShiftsPerNurse); } LinearExprBuilder obj = LinearExpr.newBuilder(); for (int n : allNurses) { for (int d : allDays) { for (int s : allShifts) { obj.addTerm(shifts[n][d][s], shiftRequests[n][d][s]); } } } model.maximize(obj); // Creates a solver and solves the model. CpSolver solver = new CpSolver(); CpSolverStatus status = solver.solve(model); if (status == CpSolverStatus.OPTIMAL || status == CpSolverStatus.FEASIBLE) { System.out.printf("Solution:%n"); for (int d : allDays) { System.out.printf("Day %d%n", d); for (int n : allNurses) { for (int s : allShifts) { if (solver.booleanValue(shifts[n][d][s])) { if (shiftRequests[n][d][s] == 1) { System.out.printf(" Nurse %d works shift %d (requested).%n", n, s); } else { System.out.printf(" Nurse %d works shift %d (not requested).%n", n, s); } } } } } System.out.printf("Number of shift requests met = %f (out of %d)%n", solver.objectiveValue(), numNurses * minShiftsPerNurse); } else { System.out.printf("No optimal solution found !"); } // Statistics. System.out.println("Statistics"); System.out.printf(" conflicts: %d%n", solver.numConflicts()); System.out.printf(" branches : %d%n", solver.numBranches()); System.out.printf(" wall time: %f s%n", solver.wallTime()); } private ScheduleRequestsSat() {} } ### C# using System; using System.Collections.Generic; using System.Linq; using Google.OrTools.Sat; public class ScheduleRequestsSat { public static void Main(String[] args) { const int numNurses = 5; const int numDays = 7; const int numShifts = 3; int[] allNurses = Enumerable.Range(0, numNurses).ToArray(); int[] allDays = Enumerable.Range(0, numDays).ToArray(); int[] allShifts = Enumerable.Range(0, numShifts).ToArray(); int[,,] shiftRequests = new int[,,] { { { 0, 0, 1 }, { 0, 0, 0 }, { 0, 0, 0 }, { 0, 0, 0 }, { 0, 0, 1 }, { 0, 1, 0 }, { 0, 0, 1 }, }, { { 0, 0, 0 }, { 0, 0, 0 }, { 0, 1, 0 }, { 0, 1, 0 }, { 1, 0, 0 }, { 0, 0, 0 }, { 0, 0, 1 }, }, { { 0, 1, 0 }, { 0, 1, 0 }, { 0, 0, 0 }, { 1, 0, 0 }, { 0, 0, 0 }, { 0, 1, 0 }, { 0, 0, 0 }, }, { { 0, 0, 1 }, { 0, 0, 0 }, { 1, 0, 0 }, { 0, 1, 0 }, { 0, 0, 0 }, { 1, 0, 0 }, { 0, 0, 0 }, }, { { 0, 0, 0 }, { 0, 0, 1 }, { 0, 1, 0 }, { 0, 0, 0 }, { 1, 0, 0 }, { 0, 1, 0 }, { 0, 0, 0 }, }, }; // Creates the model. CpModel model = new CpModel(); // Creates shift variables. // shifts[(n, d, s)]: nurse 'n' works shift 's' on day 'd'. Dictionary<Tuple<int, int, int>, IntVar> shifts = new Dictionary<Tuple<int, int, int>, IntVar>(); foreach (int n in allNurses) { foreach (int d in allDays) { foreach (int s in allShifts) { shifts.Add(Tuple.Create(n, d, s), model.NewBoolVar($"shifts_n{n}d{d}s{s}"));
}
}
}

// Each shift is assigned to exactly one nurse in the schedule period.
foreach (int d in allDays)
{
foreach (int s in allShifts)
{
IntVar[] x = new IntVar[numNurses];
foreach (int n in allNurses)
{
var key = Tuple.Create(n, d, s);
x[n] = shifts[key];
}
}
}

// Each nurse works at most one shift per day.
foreach (int n in allNurses)
{
foreach (int d in allDays)
{
IntVar[] x = new IntVar[numShifts];
foreach (int s in allShifts)
{
var key = Tuple.Create(n, d, s);
x[s] = shifts[key];
}
}
}

// Try to distribute the shifts evenly, so that each nurse works
// minShiftsPerNurse shifts. If this is not possible, because the total
// number of shifts is not divisible by the number of nurses, some nurses will
// be assigned one more shift.
int minShiftsPerNurse = (numShifts * numDays) / numNurses;
int maxShiftsPerNurse;
if ((numShifts * numDays) % numNurses == 0)
{
maxShiftsPerNurse = minShiftsPerNurse;
}
else
{
maxShiftsPerNurse = minShiftsPerNurse + 1;
}
foreach (int n in allNurses)
{
IntVar[] numShiftsWorked = new IntVar[numDays * numShifts];
foreach (int d in allDays)
{
foreach (int s in allShifts)
{
var key = Tuple.Create(n, d, s);
numShiftsWorked[d * numShifts + s] = shifts[key];
}
}
}

IntVar[] flatShifts = new IntVar[numNurses * numDays * numShifts];
int[] flatShiftRequests = new int[numNurses * numDays * numShifts];
foreach (int n in allNurses)
{
foreach (int d in allDays)
{
foreach (int s in allShifts)
{
var key = Tuple.Create(n, d, s);
flatShifts[n * numDays * numShifts + d * numShifts + s] = shifts[key];
flatShiftRequests[n * numDays * numShifts + d * numShifts + s] = shiftRequests[n, d, s];
}
}
}
model.Maximize(LinearExpr.WeightedSum(flatShifts, flatShiftRequests));

// Solve
CpSolver solver = new CpSolver();
CpSolverStatus status = solver.Solve(model);
Console.WriteLine($"Solve status: {status}"); if (status == CpSolverStatus.Optimal || status == CpSolverStatus.Feasible) { Console.WriteLine("Solution:"); foreach (int d in allDays) { Console.WriteLine($"Day {d}");
foreach (int n in allNurses)
{
bool isWorking = false;
foreach (int s in allShifts)
{
var key = Tuple.Create(n, d, s);
if (solver.Value(shifts[key]) == 1L)
{
if (shiftRequests[n, d, s] == 1)
{
Console.WriteLine($" Nurse {n} work shift {s} (requested)."); } else { Console.WriteLine($"  Nurse {n} work shift {s} (not requested).");
}
}
}
}
}
Console.WriteLine(
$"Number of shift requests met = {solver.ObjectiveValue} (out of {numNurses * minShiftsPerNurse})."); } else { Console.WriteLine("No solution found."); } Console.WriteLine("Statistics"); Console.WriteLine($"  conflicts: {solver.NumConflicts()}");
Console.WriteLine($" branches : {solver.NumBranches()}"); Console.WriteLine($"  wall time: {solver.WallTime()}s");
}
}
[{ "type": "thumb-down", "id": "missingTheInformationINeed", "label":"Missing the information I need" },{ "type": "thumb-down", "id": "tooComplicatedTooManySteps", "label":"Too complicated / too many steps" },{ "type": "thumb-down", "id": "outOfDate", "label":"Out of date" },{ "type": "thumb-down", "id": "samplesCodeIssue", "label":"Samples / code issue" },{ "type": "thumb-down", "id": "otherDown", "label":"Other" }]
[{ "type": "thumb-up", "id": "easyToUnderstand", "label":"Easy to understand" },{ "type": "thumb-up", "id": "solvedMyProblem", "label":"Solved my problem" },{ "type": "thumb-up", "id": "otherUp", "label":"Other" }]