تحتاج المؤسسات التي يعمل موظفوها نوبات متعددة إلى جدولة مهام العاملين في كل وردية يومية. عادةً، سيكون للجداول قيود، مثل "يجب ألا يعمل أي موظف على نوبتين متتاليتين". إن العثور على جدول زمني يلبي جميع القيود قد يكون صعبًا من الناحية الحسابية.
تقدم الأقسام التالية مثالين لمشكلات جدولة الموظف، عرض كيفية حلّ المشاكل باستخدام أداة حلّ CP-SAT
للاطلاع على مثال أكثر تعقيدًا، راجع هذا برنامج جدولة المهام على GitHub.
مشكلة في جدولة ممرّض
في المثال التالي، يحتاج مشرف المستشفى إلى إنشاء جدول زمني لأربعة الممرضات خلال فترة ثلاثة أيام، مع مراعاة الشروط التالية:
- يتم تقسيم كل يوم إلى ثلاث ورديات كل 8 ساعات.
- يتم تخصيص كل نوبة عمل إلى ممرّض واحد ولا تعمل أي ممرّض أكثر أكثر من وردية واحدة.
- يتم تخصيص نوبتين لكل ممرض على الأقل خلال فترة ثلاثة أيام.
تقدم الأقسام التالية حلاً لمشكلة جدولة الممرض.
استيراد المكتبات
يستورد الرمز التالي المكتبة المطلوبة.
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;
بيانات المثال
تُنشئ التعليمة البرمجية التالية البيانات للمثال.
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();
إنشاء النموذج
تُنشئ التعليمة البرمجية التالية النموذج.
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;
إنشاء المتغيّرات
تُنشئ التعليمة البرمجية التالية صفيفًا من المتغيرات.
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}"));
}
}
}
يحدد الصفيف المهام المطلوبة للورديات إلى الممرضات على النحو التالي:
shifts[(n, d, s)] تساوي 1 إذا تم تعيين shift s للممرض n في اليوم d، و0
وإلا.
تعيين الممرضين في نوبات العمل
بعد ذلك، نعرض كيفية تعيين الممرضات في نوبات العمل وفقًا للقيود التالية:
- يتم تخصيص كل نوبة عمل لممرّض واحد في اليوم.
- تعمل كل ممرضة وردية واحدة كحد أقصى في اليوم.
إليك الرمز الذي ينشئ الشرط الأول.
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();
}
}
يشير السطر الأخير إلى أنه لكل نوبة عمل، تم تعيين مجموع الممرضات المخصص لها Shift هو 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)
{
foreach (int s in allShifts)
{
literals.Add(shifts[(n, d, s)]);
}
model.AddAtMostOne(literals);
literals.Clear();
}
}
بالنسبة لكل ممرض، يكون مجموع الورديات المخصصة لتلك الممرضة 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:
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();
}
بما أنّ هناك num_shifts * num_days عمليات تبديل إجمالية في الفترة الزمنية للجدول الزمني، يمكنك
يمكن تعيين (num_shifts * num_days) // num_nurses على الأقل
لكل ممرض، ولكن قد يتم ترك بعض نوبات العمل. (هنا // هي لغة Python
عامل قسمة العدد الصحيح، الذي يكون ناتج قسمة القسمة المعتاد).
بالنسبة إلى القيم المحدّدة لـ num_nurses = 4 وnum_shifts = 3 وnum_days = 3،
التعبير min_shifts_per_nurse له القيمة (3 * 3 // 4) = 2، وبالتالي
يمكننا تعيين وردتين على الأقل لكل ممرض. يتم تحديده من خلال
القيد (هنا في بايثون)
model.add(min_shifts_per_nurse <= sum(shifts_worked))
نظرًا لوجود تسعة ورديات إجمالية خلال فترة الثلاثة أيام، فهناك واحد الوردية المتبقية بعد تعيين تبديلين لكل ممرض. يمكن أن يكون التحول الإضافي لأي ممرض.
السطر الأخير (هنا في بايثون)
model.add(sum(shifts_worked) <= max_shifts_per_nurse)
يضمن عدم تعيين أي ممرّض أكثر من وردية إضافية واحدة.
القيد ليس ضروريًا في هذه الحالة، لأنه يوجد واحد إضافي Shift. ولكن بالنسبة لقيم المعاملات المختلفة، قد يكون هناك العديد من التحولات الإضافية، وفي هذه الحالة يكون القيد ضروريًا.
تعديل مَعلمات أداة الحلّ
في نموذج عدم تحسين الأداء، يمكنك تفعيل البحث في جميع الحلول.
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 ";
تسجيل معاودة الاتصال بالحلول
تحتاج إلى تسجيل معاودة الاتصال في أداة الحل التي سيتم استدعاؤها على كل الحل.
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
حدِّد أولاً الفئة 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_;
}
ثم أنشئ مثيلاً لها باستخدام:
const int solutionLimit = 5; SolutionPrinter cb = new SolutionPrinter(allNurses, allDays, allShifts, shifts, solutionLimit);
استدعاء أداة الحلّ
تستدعي التعليمة البرمجية التالية أداة الحل وتعرض أول خمسة حلول.
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}");
الحلول
فيما يلي أول خمسة حلول.
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
إجمالي عدد الحلول هو 5184. تشرح وسيطة الاحتساب التالية السبب.
أولاً، هناك 4 خيارات للممرضة التي تعمل في وردية إضافية. بعد اختيار الممرضة، هناك 3 نوبات يمكن إسنادها إلى الممرض في كل يوم من الأيام الثلاثة، وبالتالي فإن عدد الطرق الممكنة لتعيين الممرض Shift الإضافي هو 4 · 33 = 108. بعد تعيين هذا الممرض، تتبقّى نوبات عمل غير معيّنة في كل يوم.
من بين الممرضات الثلاثة المتبقين، يوم عمل واحد 0 و1، ويوم عمل واحد 0 و2، ويعمل يوم 1 و2. هناك 3! = 6 طرق لتعيين الممرضات لهذه الأيام، كما هو موضح في الرسم التخطيطي أدناه. (يتم تصنيف الممرضات الثلاثة A وB وC، ولم نكن قد وتعيينهم إلى ورديات).
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
بالنسبة إلى كل صف في الرسم البياني أعلاه، هناك 23 = 8 طرق محتملة إسناد الورديات المتبقية إلى الممرضات (خياران في كل يوم). لذا فإن العدد الإجمالي للمهام الممكنة هو 108·6·8 = 5184.
البرنامج بالكامل
إليك البرنامج الكامل لمشكلة جدولة الممرضين.
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");
}
}
الجدولة باستخدام طلبات التبديل
في هذا القسم، نأخذ المثال السابق ونضيف طلبات الممرضات ورديات محددة. وبعد ذلك، نبحث عن جدول زمني يزيد عدد الطلبات التي تم تلبيتها إلى أقصى حد. بالنسبة لمعظم مشكلات الجدولة، من الأفضل تحسين دالة موضوعية، حيث عادةً لا يكون من العملي طباعة جميع الجداول الزمنية الممكنة.
هذا المثال له نفس القيود مثل المثال السابق.
استيراد المكتبات
يستورد الرمز التالي المكتبة المطلوبة.
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;
بيانات المثال
تظهر البيانات الخاصة بهذا المثال بعد ذلك.
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 },
},
};
إنشاء النموذج
تُنشئ التعليمة البرمجية التالية النموذج.
Python
model = cp_model.CpModel()
C++
CpModelBuilder cp_model;
Java
CpModel model = new CpModel();
#C
CpModel model = new CpModel();
إنشاء المتغيّرات
التعليمة البرمجية التالية صفيف من المتغيرات للمشكلة.
بالإضافة إلى المتغيرات من المثال السابق، تحتوي البيانات أيضًا على مجموعة من ثلاث مرات، بما يتوافق مع التحولات الثلاث في اليوم. يُعد كل عنصر من عناصر الثلاثي 0 أو 1، مما يشير إلى ما إذا كان قد تم طلب التبديل. على سبيل المثال، يشير ثلاثة [0, 0, 1] في الموضع الخامس من الصف 1 إلى أن الممرضة 1 تطلب التبديل 3 في اليوم 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}"));
}
}
}
وضع القيود
تضع التعليمة البرمجية التالية القيود للمشكلة.
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);
}
هدف المثال
نريد تحسين الدالة الموضوعية التالية.
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) تكون 1 في حال تخصيص المفتاح s
تمريض "n" في اليوم d وطلب هذا الممرض أن يتم تغييره (وصفر خلاف ذلك)،
والهدف هو تحويل عدد المهام التي تلبي الطلب.
استدعاء أداة الحلّ
تستدعي التعليمة البرمجية التالية أداة الحل.
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}");
عرض النتائج
يعرض التعليمة البرمجية التالية الإخراج التالي، والذي يحتوي على مثال (على الرغم من أنه ربما ليس الوحيد). ويوضح الناتج أي نوع المهام الدراسية وعدد الطلبات التي تم تلبيتها.
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.");
}
عند تشغيل البرنامج، يعرض الناتج التالي:
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
البرنامج بالكامل
إليك البرنامج الكامل للجدولة باستخدام طلبات نوبات العمل.
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");
}
}