سازمان‌هایی که کارکنان آنها چندین شیفت کار می‌کنند باید برای هر شیفت روزانه کارگران کافی را برنامه‌ریزی کنند. به طور معمول، برنامه ها دارای محدودیت هایی هستند، مانند "هیچ کارمندی نباید دو شیفت پشت سر هم کار کند". یافتن برنامه ای که تمام محدودیت ها را برآورده کند، می تواند از نظر محاسباتی دشوار باشد.
بخش‌های زیر دو نمونه از مشکلات زمانبندی کارمندان را ارائه می‌کنند و نحوه حل آنها را با استفاده از حل‌کننده CP-SAT نشان می‌دهند.
برای مثال پیچیده‌تر، این برنامه زمانبندی تغییر را در GitHub ببینید.
مشکل برنامه ریزی پرستار
در مثال بعدی، سوپروایزر بیمارستان باید یک برنامه زمانی برای چهار پرستار در یک دوره سه روزه با رعایت شرایط زیر ایجاد کند:
- هر روز به سه شیفت 8 ساعته تقسیم می شود.
- هر روز هر شیفت به یک پرستار اختصاص داده می شود و هیچ پرستاری بیش از یک شیفت کار نمی کند.
- هر پرستار در طول دوره سه روزه حداقل در دو شیفت منصوب می شود.
بخش های زیر راه حلی برای مشکل برنامه ریزی پرستار ارائه می دهد.
کتابخانه ها را وارد کنید
کد زیر کتابخانه مورد نیاز را وارد می کند.
پایتون
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"
جاوا
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;
سی شارپ
using System; using System.Collections.Generic; using System.IO; using System.Linq; using Google.OrTools.Sat;
داده ها برای مثال
کد زیر داده های مثال را ایجاد می کند.
پایتون
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);
جاوا
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();
سی شارپ
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();
مدل را ایجاد کنید
کد زیر مدل را ایجاد می کند.
پایتون
model = cp_model.CpModel()
C++
CpModelBuilder cp_model;
جاوا
CpModel model = new CpModel();
سی شارپ
CpModel model = new CpModel(); model.Model.Variables.Capacity = numNurses * numDays * numShifts;
متغیرها را ایجاد کنید
کد زیر آرایه ای از متغیرها را ایجاد می کند.
پایتون
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));
}
}
}جاوا
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);
}
}
}سی شارپ
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 است اگر شیفت s در روز d به پرستار n اختصاص داده شود و در غیر این صورت 0 است.
پرستاران را به شیفت اختصاص دهید
در مرحله بعد، نحوه انتساب پرستاران به شیفت ها را با توجه به محدودیت های زیر نشان می دهیم:
- هر شیفت به یک پرستار در روز اختصاص داده می شود.
- هر پرستار حداکثر یک شیفت در روز کار می کند.
در اینجا کدی است که شرط اول را ایجاد می کند.
پایتون
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);
}
}جاوا
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);
}
}سی شارپ
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();
}
}خط آخر می گوید که برای هر شیفت، مجموع پرستارانی که به آن شیفت اختصاص داده شده اند 1 است.
بعد، در اینجا کدی وجود دارد که مستلزم آن است که هر پرستار حداکثر یک شیفت در روز کار کند.
پایتون
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);
}
}جاوا
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);
}
}سی شارپ
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 است ("حداکثر" زیرا ممکن است یک پرستار روز تعطیل باشد).
شیفت ها را به طور مساوی تعیین کنید
در مرحله بعد، نحوه تخصیص شیفت به پرستاران را تا حد امکان به طور مساوی نشان می دهیم. از آنجایی که در دوره سه روزه 9 شیفت وجود دارد، می توانیم به هر یک از چهار پرستار دو شیفت اختصاص دهیم. پس از آن یک شیفت باقی می ماند که می توان آن را به هر پرستاری اختصاص داد.
کد زیر تضمین می کند که هر پرستار حداقل دو شیفت در دوره سه روزه کار می کند.
پایتون
# 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);
}جاوا
// 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);
}سی شارپ
// 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 را اختصاص دهید
به هر پرستار تغییر می کند، اما ممکن است برخی از شیفت ها باقی بماند. (در اینجا // عملگر تقسیم عدد صحیح پایتون است که کف ضریب معمولی را برمی گرداند.)
برای مقادیر داده شده 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))
از آنجایی که در طول دوره سه روزه 9 شیفت کل وجود دارد، پس از اختصاص دو شیفت به هر پرستار، یک شیفت باقی مانده است. شیفت اضافی را می توان به هر پرستاری اختصاص داد.
خط آخر (اینجا در پایتون)
model.add(sum(shifts_worked) <= max_shifts_per_nurse)
تضمین می کند که به هیچ پرستاری بیش از یک شیفت اضافی اختصاص داده نشود.
محدودیت در این مورد ضروری نیست، زیرا تنها یک جابجایی اضافی وجود دارد. اما برای مقادیر پارامترهای مختلف، ممکن است چندین جابجایی اضافی وجود داشته باشد که در این صورت محدودیت ضروری است.
به روز رسانی پارامترهای حل کننده
در یک مدل غیر بهینه‌سازی، می‌توانید جستجوی همه راه‌حل‌ها را فعال کنید.
پایتون
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));
جاوا
CpSolver solver = new CpSolver(); solver.getParameters().setLinearizationLevel(0); // Tell the solver to enumerate all solutions. solver.getParameters().setEnumerateAllSolutions(true);
سی شارپ
CpSolver solver = new CpSolver(); // Tell the solver to enumerate all solutions. solver.StringParameters += "linearization_level:0 " + "enumerate_all_solutions:true ";
ثبت پاسخ به تماس Solutions
شما باید یک callback در حل کننده ثبت کنید که در هر راه حل فراخوانی می شود.
پایتون
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.";
}
}));جاوا
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);سی شارپ
ابتدا کلاس 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);
حل کننده را فراخوانی کنید
کد زیر حل کننده را فراخوانی می کند و پنج راه حل اول را نمایش می دهد.
پایتون
solver.solve(model, solution_printer)
C++
const CpSolverResponse response = SolveCpModel(cp_model.Build(), &model);
جاوا
CpSolverStatus status = solver.solve(model, cb);
System.out.println("Status: " + status);
System.out.println(cb.getSolutionCount() + " solutions found.");سی شارپ
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 شیفت پرستار در هر 3 روز وجود دارد، بنابراین تعداد راه های ممکن برای انتساب پرستار با شیفت اضافی 4 · 3 3 = 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
برای هر ردیف در نمودار بالا، 2 3 = 8 راه ممکن برای اختصاص دادن شیفت های باقی مانده به پرستاران وجود دارد (دو انتخاب در هر روز). بنابراین تعداد کل تخصیص های ممکن 108·6·8 = 5184 است.
کل برنامه
در اینجا کل برنامه برای مشکل زمانبندی پرستار آمده است.
پایتون
"""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;
}جاوا
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() {}
}سی شارپ
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");
}
}برنامه ریزی با درخواست شیفت
در این بخش، مثال قبلی را می‌گیریم و درخواست‌های پرستار برای شیفت‌های خاص را اضافه می‌کنیم. سپس به دنبال برنامه‌ای می‌گردیم که تعداد درخواست‌هایی را که برآورده می‌شوند به حداکثر برساند. برای اکثر مشکلات زمانبندی، بهتر است یک تابع هدف را بهینه کنید، زیرا معمولاً چاپ همه زمان‌بندی‌های ممکن عملی نیست.
این مثال همان محدودیت های مثال قبلی را دارد.
کتابخانه ها را وارد کنید
کد زیر کتابخانه مورد نیاز را وارد می کند.
پایتون
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"
جاوا
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;
سی شارپ
using System; using System.Collections.Generic; using System.Linq; using Google.OrTools.Sat;
داده ها برای مثال
داده های این مثال در ادامه نشان داده شده است.
پایتون
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},
},
};جاوا
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},
},
};سی شارپ
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 },
},
};مدل را ایجاد کنید
کد زیر مدل را ایجاد می کند.
پایتون
model = cp_model.CpModel()
C++
CpModelBuilder cp_model;
جاوا
CpModel model = new CpModel();
سی شارپ
CpModel model = new CpModel();
متغیرها را ایجاد کنید
کد زیر آرایه ای از متغیرها برای مشکل است.
علاوه بر متغیرهای مثال قبلی، داده ها شامل مجموعه ای از سه گانه نیز هستند که مربوط به سه نوبت در روز است. هر عنصر از سه گانه 0 یا 1 است، که نشان می دهد آیا تغییر درخواست شده است یا خیر. به عنوان مثال، سه گانه [0، 0، 1] در موقعیت پنجم ردیف 1 نشان می دهد که پرستار 1 در روز 5 شیفت 3 را درخواست می کند.
پایتون
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));
}
}
}جاوا
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);
}
}
}سی شارپ
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}"));
}
}
}محدودیت ها را ایجاد کنید
کد زیر محدودیت هایی را برای مشکل ایجاد می کند.
پایتون
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);
}
}جاوا
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);
}
}سی شارپ
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);
}
}پایتون
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);
}
}جاوا
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);
}
}سی شارپ
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
# 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);
}جاوا
// 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);
}سی شارپ
// 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);
}هدف برای مثال
ما می خواهیم تابع هدف زیر را بهینه کنیم.
پایتون
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);جاوا
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);سی شارپ
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 اختصاص داده شود و آن پرستار آن شیفت را درخواست کرده باشد (و 0 در غیر این صورت)، هدف این است که تغییر تعداد تکالیفی که یک درخواست را برآورده می کنند.
حل کننده را فراخوانی کنید
کد زیر حل کننده را فراخوانی می کند.
پایتون
solver = cp_model.CpSolver() status = solver.solve(model)
C++
const CpSolverResponse response = Solve(cp_model.Build());
جاوا
CpSolver solver = new CpSolver(); CpSolverStatus status = solver.solve(model);
سی شارپ
CpSolver solver = new CpSolver();
CpSolverStatus status = solver.Solve(model);
Console.WriteLine($"Solve status: {status}");نمایش نتایج
کد زیر خروجی زیر را نمایش می دهد که حاوی یک زمان بندی بهینه است (اگرچه شاید تنها برنامه نباشد). خروجی نشان می دهد که کدام تکالیف شیفت درخواست شده و تعداد درخواست هایی که برآورده شده است.
پایتون
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 !";
}جاوا
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 !");
}سی شارپ
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
کل برنامه
در اینجا کل برنامه برای زمان بندی با درخواست های شیفت است.
پایتون
"""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;
}جاوا
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() {}
}سی شارپ
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");
}
}