Las organizaciones cuyos empleados trabajan en varios turnos necesitan programar una cantidad suficiente de trabajadores en cada turno diario. Por lo general, los cronogramas tienen restricciones, como "ningún empleado debe trabajar dos turnos seguidos". Encontrar un programa que satisface todas las restricciones puede ser difícil desde el punto de vista informático.
Las siguientes secciones presentan dos ejemplos de problemas de programación de los empleados y y aprenderás a resolverlos con el solucionador de problemas CP-SAT.
Para ver un ejemplo más sofisticado, consulte este programa de programación de turnos en GitHub.
Investigación de operaciones deUna enfermera con problemas de agenda
En el siguiente ejemplo, un supervisor de hospital debe crear un cronograma para cuatro enfermeros durante un período de tres días, bajo las siguientes condiciones:
- Cada día se divide en tres turnos de 8 horas.
- Cada día, cada turno se asigna a un solo enfermero, y ninguno trabaja más de un cambio.
- A cada enfermero se le asigna al menos dos turnos durante el período de tres días.
Las siguientes secciones presentan una solución al problema de programación del personal de enfermería.
Importa las bibliotecas
Con el siguiente código, se importa la biblioteca requerida.
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;
Datos para el ejemplo
Con el siguiente código, se crean los datos para el ejemplo.
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();
Crea el modelo
El siguiente código crea el modelo.
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;
Crea las variables
Con el siguiente código, se crea un array 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}"));
}
}
}
El array define las asignaciones de turnos a las enfermeras de la siguiente manera:
shifts[(n, d, s)] es igual a 1 si el turno s se asigna a la enfermera n en el día d, y a 0
de lo contrario.
Asignar enfermeras a turnos
A continuación, te mostramos cómo asignar a las enfermeras a turnos con las siguientes restricciones:
- Cada turno se asigna a un solo enfermero por día.
- Cada enfermera trabaja como máximo un turno por día.
Este es el código que crea la primera condición.
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 última línea dice que para cada turno, la suma de enfermeras asignadas a ese Mayúsculas es 1.
A continuación, este es el código que requiere que cada enfermero trabaje como máximo un turno por día.
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();
}
}
Para cada enfermero, la suma de los turnos asignados a ese enfermero es como máximo 1 (“como máximo” porque un enfermero podría tener el día libre).
Asignar cambios de manera uniforme
A continuación, mostramos cómo asignar turnos a las enfermeras de la manera más uniforme posible. Dado que hay nueve cambios durante el período de tres días, podemos asignar dos a cada una de las cuatro enfermeras. Luego, queda un turno, que puede asignarse a cualquier enfermero.
El siguiente código garantiza que cada enfermero trabaje al menos dos turnos en la de tres días.
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();
}
Dado que hay un total de num_shifts * num_days turnos en el período programado,
puede asignar, al menos, (num_shifts * num_days) // num_nurses
a cada enfermero, pero es posible que queden algunos. (Aquí, // es la API de Python
operador de división de enteros, que muestra el mínimo del cociente habitual)
Para los valores dados de num_nurses = 4, num_shifts = 3 y num_days = 3,
la expresión min_shifts_per_nurse tiene el valor (3 * 3 // 4) = 2, por lo que
puedes asignar al menos dos turnos a cada enfermero. Esto se especifica mediante el
(aquí en Python)
model.add(min_shifts_per_nurse <= sum(shifts_worked))
Dado que hay nueve cambios totales durante el período de tres días, hay uno turnos restante después de asignar dos turnos a cada enfermero. El cambio extra puede ser a ningún personal de enfermería.
La línea final (aquí en Python)
model.add(sum(shifts_worked) <= max_shifts_per_nurse)
asegura que a ningún enfermero se le asigne más de un turno extra.
La restricción no es necesaria en este caso, ya que solo hay una mayúscula. Pero para diferentes valores de los parámetros, podría haber varios cambios adicionales en cuyo caso la restricción es necesaria.
Actualiza los parámetros de la resolución
En un modelo que no sea de optimización, puedes habilitar la búsqueda de todas las soluciones.
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 ";
Registra una devolución de llamada de soluciones
Debes registrar una devolución de llamada en el solucionador que se llamará en cada de Google Cloud.
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#
Primero, define la clase 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_;
}
Luego, crea una instancia con lo siguiente:
const int solutionLimit = 5; SolutionPrinter cb = new SolutionPrinter(allNurses, allDays, allShifts, shifts, solutionLimit);
Invocar el solucionador
El siguiente código llama al solucionador y muestra las primeras cinco soluciones.
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}");
Soluciones
Estas son las primeras cinco soluciones.
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
La cantidad total de soluciones es 5,184. El siguiente argumento de recuento explica por qué.
En primer lugar, hay 4 opciones para la enfermera que trabaja un turno extra. Después de elegir al enfermero, hay 3 turnos a los que se le puede asignar cada uno de los 3 días, así que el número de formas posibles de asignar al enfermero con el el cambio extra es 4 · 33 = 108. Luego de asignar a este enfermero, quedan dos turnos sin asignar cada día.
De las tres enfermeras restantes, una trabaja los días 0 y 1, una trabaja los días 0 y 2, y uno de los días 1 y 2. Hay 3. = 6 formas de asignar a las enfermeras a estos días, como se muestra en el diagrama a continuación. (Las tres enfermeras están etiquetadas como A, B y C, y todavía no hemos se les asignaron a turnos).
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
Para cada fila del diagrama anterior, hay 23 = 8 formas posibles de asignar los turnos restantes a los enfermeros (dos opciones por día). Entonces, la cantidad total de asignaciones posibles es 108·6·8 = 5,184.
Todo el programa
Este es el programa completo para el problema de agenda de los enfermeros.
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");
}
}
Programa turnos con solicitudes de turnos
En esta sección, tomamos el ejemplo anterior y agregamos solicitudes de enfermeras para cambios específicos. Luego, buscamos un cronograma que maximice la cantidad de solicitudes que se cumplen. Para la mayoría de los problemas de programación, es mejor optimizar una función objetiva, ya que no suele ser práctico imprimir todos los horarios posibles.
Este ejemplo tiene las mismas restricciones que el ejemplo anterior.
Importa las bibliotecas
Con el siguiente código, se importa la biblioteca requerida.
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;
Datos para el ejemplo
Los datos para este ejemplo se muestran a continuación.
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 },
},
};
Crea el modelo
El siguiente código crea el modelo.
Python
model = cp_model.CpModel()
C++
CpModelBuilder cp_model;
Java
CpModel model = new CpModel();
C#
CpModel model = new CpModel();
Crea las variables
En el siguiente código, se codifica un array de variables para el problema.
Además de las variables del ejemplo anterior, los datos también contienen un conjunto de triples, que corresponde a los tres cambios por día. Cada elemento del triple es 0 o 1, lo que indica si se solicitó un cambio. Por ejemplo, el triple [0, 0, 1] en la quinta posición de la fila 1 indica que la enfermera 1 solicita la turno 3, el día 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}"));
}
}
}
Crea las restricciones
El siguiente código crea las restricciones para el problema.
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);
}
Objetivo del ejemplo
Queremos optimizar la siguiente función objetiva.
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));
Dado que shift_requests[n][d][s] * shifts[(n, d, s) es 1 si se asigna el cambio s
para enfermar a n el día d y ese personal solicitó ese turno (y 0 en caso contrario),
el objetivo es el número de cambios de asignaciones que cumplen con una solicitud.
Invocar el solucionador
El siguiente código llama al solucionador.
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}");
Cómo mostrar los resultados
El siguiente código muestra el siguiente resultado, que contiene un valor óptimo un cronograma de la organización (aunque quizás no sea el único). El resultado muestra qué cambio se solicitaron asignaciones y la cantidad de solicitudes que se cumplieron.
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.");
}
Cuando ejecutes el programa, se mostrará el siguiente resultado:
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
Todo el programa
Este es el programa completo para programar con solicitudes de turnos.
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");
}
}