Les organisations dont les employés travaillent à plusieurs quarts doivent prévoir suffisamment de temps pour chaque équipe quotidienne. En général, les calendriers ont des contraintes, telles que « aucun employé ne doit travailler deux fois de suite ». Trouver un calendrier qui qui répond à toutes les contraintes peut être difficile en termes de calcul.
Les sections suivantes présentent deux exemples de problèmes de planification des employés et montrez comment les résoudre à l'aide de la solution CP-SAT.
Pour un exemple plus complexe, consultez cette programme de planification des quarts sur GitHub.
Un problème de planification infirmière
Dans l'exemple suivant, un superviseur d'hôpital doit créer un calendrier pour quatre infirmiers sur une période de trois jours, sous réserve des conditions suivantes:
- Chaque journée est divisée en trois quarts de huit heures.
- Chaque jour, chaque équipe est assignée à une seule infirmière, et aucune infirmière ne travaille plus plusieurs équipes.
- Chaque infirmier est affecté à au moins deux quarts pendant une période de trois jours.
Les sections suivantes présentent une solution au problème de planification du personnel infirmier.
Importer les bibliothèques
Le code suivant importe la bibliothèque requise.
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 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;
C#
using System; using System.Collections.Generic; using System.IO; using System.Linq; using Google.OrTools.Sat;
Données pour l'exemple
Le code suivant crée les données pour l'exemple.
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();
Créer le modèle
Le code suivant crée le modèle.
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;
Créer les variables
Le code suivant crée un tableau de variables.
Python
shifts = {}
for n in all_nurses:
for d in all_days:
for s in all_shifts:
shifts[(n, d, s)] = model.new_bool_var(f"shift_n{n}_d{d}_s{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}"));
}
}
}
Le tableau définit les affectations pour les quarts d'infirmier comme suit:
shifts[(n, d, s)] est égal à 1 si le quart de travail s est attribué à l'infirmière n le jour d, et à 0.
sinon.
Désigner des infirmières par équipes
Ensuite, nous montrons comment affecter le personnel infirmier à des horaires de travail en tenant compte des contraintes suivantes:
- Chaque équipe est affectée à un seul infirmier par jour.
- Chaque infirmier travaille au maximum à un quart de travail par jour.
Voici le code qui crée la première condition.
Python
for d in all_days:
for s in all_shifts:
model.add_exactly_one(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();
}
}
La dernière ligne indique que pour chaque équipe, la somme des infirmiers affectés à ce Maj est égal à 1.
Ensuite, voici le code qui exige que chaque infirmier travaille au maximum un quart de travail par jour.
Python
for n in all_nurses:
for d in all_days:
model.add_at_most_one(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();
}
}
Pour chaque infirmier, la somme des quarts attribués à cette infirmière est au maximum de 1 (« au plus » parce qu'une infirmière peut avoir un jour de congé).
Répartir les équipes uniformément
Ensuite, nous montrons comment répartir les quarts des infirmières aussi équitablement que possible. Puisqu'il y a neuf quarts sur la période de trois jours, nous pouvons attribuer deux quarts à chacune des quatre infirmières. Après cela, il vous reste un quart de travail, qui peut être attribué à n'importe quelle infirmière.
Le code suivant garantit que chaque infirmier travaille au moins deux quarts dans le d'une période de trois jours.
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:
shifts_worked = []
for d in all_days:
for s in all_shifts:
shifts_worked.append(shifts[(n, d, s)])
model.add(min_shifts_per_nurse <= sum(shifts_worked))
model.add(sum(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> shifts_worked;
for (int d : all_days) {
for (int s : all_shifts) {
auto key = std::make_tuple(n, d, s);
shifts_worked.push_back(shifts[key]);
}
}
cp_model.AddLessOrEqual(min_shifts_per_nurse,
LinearExpr::Sum(shifts_worked));
cp_model.AddLessOrEqual(LinearExpr::Sum(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 shiftsWorked = LinearExpr.newBuilder();
for (int d : allDays) {
for (int s : allShifts) {
shiftsWorked.add(shifts[n][d][s]);
}
}
model.addLinearConstraint(shiftsWorked, 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> shiftsWorked = new List<IntVar>();
foreach (int n in allNurses)
{
foreach (int d in allDays)
{
foreach (int s in allShifts)
{
shiftsWorked.Add(shifts[(n, d, s)]);
}
}
model.AddLinearConstraint(LinearExpr.Sum(shiftsWorked), minShiftsPerNurse, maxShiftsPerNurse);
shiftsWorked.Clear();
}
Étant donné qu'il y a num_shifts * num_days d'ajustements au total pendant la période de planification, vous
peut attribuer au moins (num_shifts * num_days) // num_nurses
d’équipes infirmières, mais
certains changements peuvent encore se produire. (Ici, // correspond au code
de division d'entiers, qui renvoie le plancher du quotient habituel.)
Pour les valeurs num_nurses = 4, num_shifts = 3 et num_days = 3 fournies,
l'expression min_shifts_per_nurse a la valeur (3 * 3 // 4) = 2.
peut affecter au moins deux
équipes à chaque infirmier. Ceci est spécifié par le paramètre
(ici dans Python)
model.add(min_shifts_per_nurse <= sum(shifts_worked))
Puisqu'il y a neuf changements au total sur la période de trois jours, il y en a une quart de travail restant après avoir affecté deux quarts à chaque infirmier. L’ajustement supplémentaire peut être assigné à n’importe quelle infirmière.
La dernière ligne (ici en Python)
model.add(sum(shifts_worked) <= max_shifts_per_nurse)
garantit qu’aucun infirmier ne reçoit plus d’un quart de travail supplémentaire.
La contrainte n'est pas nécessaire dans ce cas, car il n'y a qu'un seul élément supplémentaire Maj. Mais pour différentes valeurs de paramètres, il peut y avoir plusieurs décalages supplémentaires, auquel cas la contrainte est nécessaire.
Mettre à jour les paramètres du résolveur
Dans un modèle sans optimisation, vous pouvez activer la recherche pour toutes les 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 ";
Enregistrer un rappel de solutions
Vous devez enregistrer un rappel sur le résolveur qui sera appelé à chaque 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(f"Solution {self._solution_count}")
for d in range(self._num_days):
print(f"Day {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(f" Nurse {n} works shift {s}")
if not is_working:
print(f" Nurse {n} does not work")
if self._solution_count >= self._solution_limit:
print(f"Stop search after {self._solution_limit} solutions")
self.stop_search()
def solutionCount(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#
Commencez par définir la classe SolutionPrinter.
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_;
}
Instanciez-la ensuite à l'aide de la commande suivante:
const int solutionLimit = 5; SolutionPrinter cb = new SolutionPrinter(allNurses, allDays, allShifts, shifts, solutionLimit);
Appeler le résolveur
Le code suivant appelle le résolveur et affiche les cinq premières 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
Voici les cinq premières 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
Le nombre total de solutions est de 5 184. L'argument de comptage suivant explique pourquoi.
Tout d'abord, il y a quatre choix pour l'infirmière qui travaille un quart de travail supplémentaire. Une fois cette infirmière choisie, elle peut être affectée à 3 équipes chacun des 3 jours, donc le nombre de façons possibles d’affecter à l’infirmière le le quart supplémentaire est 4 · 33 = 108. Après l’affectation de cette infirmière, il reste deux quarts non assignés chaque jour.
Sur les trois infirmières restantes, l’une travaille les jours 0 et 1, l’autre travaille les jours 0 et 2, et l'autre travaille les jours 1 et 2. Il y en a trois ! = 6 manières d'affecter le personnel soignant à ces jours, comme indiqué dans le du schéma ci-dessous. (Les trois infirmières portent les étiquettes A, B et C, et nous n'avons pas encore et les assigner à des équipes.)
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
Pour chaque ligne du diagramme ci-dessus, il y a 23 = 8 façons possibles de attribuer les quarts restants aux infirmières (deux choix par jour). Le nombre total d'attributions possibles est donc de 108·6·8 = 5 184.
Intégralité du programme
Voici l'ensemble du programme pour le problème de planification infirmière.
Python
"""Example of a simple nurse scheduling problem."""
from ortools.sat.python import cp_model
def main() -> None:
# 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.new_bool_var(f"shift_n{n}_d{d}_s{s}")
# Each shift is assigned to exactly one nurse in the schedule period.
for d in all_days:
for s in all_shifts:
model.add_exactly_one(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.add_at_most_one(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:
shifts_worked = []
for d in all_days:
for s in all_shifts:
shifts_worked.append(shifts[(n, d, s)])
model.add(min_shifts_per_nurse <= sum(shifts_worked))
model.add(sum(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(f"Solution {self._solution_count}")
for d in range(self._num_days):
print(f"Day {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(f" Nurse {n} works shift {s}")
if not is_working:
print(f" Nurse {n} does not work")
if self._solution_count >= self._solution_limit:
print(f"Stop search after {self._solution_limit} solutions")
self.stop_search()
def solutionCount(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(f" - conflicts : {solver.num_conflicts}")
print(f" - branches : {solver.num_branches}")
print(f" - wall time : {solver.wall_time} s")
print(f" - solutions found: {solution_printer.solutionCount()}")
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> shifts_worked;
for (int d : all_days) {
for (int s : all_shifts) {
auto key = std::make_tuple(n, d, s);
shifts_worked.push_back(shifts[key]);
}
}
cp_model.AddLessOrEqual(min_shifts_per_nurse,
LinearExpr::Sum(shifts_worked));
cp_model.AddLessOrEqual(LinearExpr::Sum(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 shiftsWorked = LinearExpr.newBuilder();
for (int d : allDays) {
for (int s : allShifts) {
shiftsWorked.add(shifts[n][d][s]);
}
}
model.addLinearConstraint(shiftsWorked, 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> shiftsWorked = new List<IntVar>();
foreach (int n in allNurses)
{
foreach (int d in allDays)
{
foreach (int s in allShifts)
{
shiftsWorked.Add(shifts[(n, d, s)]);
}
}
model.AddLinearConstraint(LinearExpr.Sum(shiftsWorked), minShiftsPerNurse, maxShiftsPerNurse);
shiftsWorked.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()}");
Console.WriteLine($" wall time: {solver.WallTime()}s");
}
}
Planifier avec des demandes d'équipes
Dans cette section, nous reprenons l'exemple précédent et ajoutons les demandes d'infirmier pour des changements spécifiques. Nous recherchons ensuite un calendrier qui optimise le nombre de requêtes satisfaites. Pour la plupart des problèmes de planification, il est préférable d'optimiser une fonction objectif, car elle il n'est généralement pas pratique d'imprimer toutes les planifications possibles.
Cet exemple présente les mêmes contraintes que l'exemple précédent.
Importer les bibliothèques
Le code suivant importe la bibliothèque requise.
Python
from typing import Union from ortools.sat.python import cp_model
C++
#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"
Java
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;
C#
using System; using System.Collections.Generic; using System.Linq; using Google.OrTools.Sat;
Données pour l'exemple
Les données de cet exemple sont présentées après.
Python
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]],
]
C++
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},
},
};
Java
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},
},
};
C#
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 },
},
};
Créer le modèle
Le code suivant crée le modèle.
Python
model = cp_model.CpModel()
C++
CpModelBuilder cp_model;
Java
CpModel model = new CpModel();
C#
CpModel model = new CpModel();
Créer les variables
Le code suivant est un tableau de variables correspondant au problème.
Outre les variables de l'exemple précédent, les données contiennent également série de triples, correspondant aux trois quarts de travail par jour. Chaque élément du le triple est 0 ou 1, indiquant si un quart a été demandé. Par exemple, un triple [0, 0, 1] en cinquième position de la ligne 1 indique que l’infirmière 1 demande Maj 3 le jour 5.
Python
shifts = {}
for n in all_nurses:
for d in all_days:
for s in all_shifts:
shifts[(n, d, s)] = model.new_bool_var(f"shift_n{n}_d{d}_s{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<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}"));
}
}
}
Créer les contraintes
Le code suivant crée les contraintes pour le problème.
Python
for d in all_days:
for s in all_shifts:
model.add_exactly_one(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#
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];
}
model.Add(LinearExpr.Sum(x) == 1);
}
}
Python
for n in all_nurses:
for d in all_days:
model.add_at_most_one(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)
{
IntVar[] x = new IntVar[numShifts];
foreach (int s in allShifts)
{
var key = Tuple.Create(n, d, s);
x[s] = shifts[key];
}
model.Add(LinearExpr.Sum(x) <= 1);
}
}
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: Union[cp_model.LinearExpr, int] = 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)
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];
}
}
cp_model.AddLessOrEqual(min_shifts_per_nurse, num_worked_shifts);
cp_model.AddLessOrEqual(num_worked_shifts, 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;
}
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];
}
}
model.AddLinearConstraint(LinearExpr.Sum(numShiftsWorked), minShiftsPerNurse, maxShiftsPerNurse);
}
Objectif pour l'exemple
Nous souhaitons optimiser la fonction objectif suivante.
Python
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) {
obj.addTerm(shifts[n][d][s], shiftRequests[n][d][s]);
}
}
}
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));
shift_requests[n][d][s] * shifts[(n, d, s) étant égal à 1 si le décalage s est attribué
à l'infirmière n le d et que celle-ci a demandé ce quart de travail (et 0 dans le cas contraire),
l’objectif est le changement du nombre
d’attributions qui répondent à une demande.
Appeler le résolveur
Le code suivant appelle le résolveur.
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}");
Afficher les résultats
Le code ci-dessous affiche la sortie ci-dessous, qui contient un exemple (même si ce n'est peut-être pas le seul). La sortie indique quel changement les attributions ont été demandées et le nombre de demandes satisfaites.
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.objective_value}",
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.");
}
Lorsque vous exécutez le programme, le résultat suivant s'affiche:
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
Intégralité du programme
Voici l'ensemble du programme de planification avec les demandes d'équipe.
Python
"""Nurse scheduling problem with shift requests."""
from typing import Union
from ortools.sat.python import cp_model
def main() -> None:
# 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.new_bool_var(f"shift_n{n}_d{d}_s{s}")
# Each shift is assigned to exactly one nurse in .
for d in all_days:
for s in all_shifts:
model.add_exactly_one(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.add_at_most_one(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: Union[cp_model.LinearExpr, int] = 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)
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.objective_value}",
f"(out of {num_nurses * min_shifts_per_nurse})",
)
else:
print("No optimal solution found !")
# Statistics.
print("\nStatistics")
print(f" - conflicts: {solver.num_conflicts}")
print(f" - branches : {solver.num_branches}")
print(f" - wall time: {solver.wall_time}s")
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];
}
model.Add(LinearExpr.Sum(x) == 1);
}
}
// 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];
}
model.Add(LinearExpr.Sum(x) <= 1);
}
}
// 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];
}
}
model.AddLinearConstraint(LinearExpr.Sum(numShiftsWorked), minShiftsPerNurse, maxShiftsPerNurse);
}
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");
}
}