員工需要多班安排工作時間的機構 以便因應日常輪班的員工一般來說，排程會設有限制 例如「任何員工都不應該在同一處工作」正在尋找適合自己的時間表 在計算過程中要滿足所有限制，可能會相當困難。
以下各節提供兩個員工安排行程問題的例子。 說明如何使用 CP-SAT 解析工具解決問題。
如需更複雜的範例，請參閱 排班計畫 。
護理師安排時間問題
在下一個範例中，醫院主管必須 細胞組織，前提是符合以下條件：
- 每天會分成 3 小時的 3 小時。
- 每一天，輪班只會分配到一位護理師，整個護理師都能發揮更多功用 一次到位。
- 每個護理師至少會在三天期間內指派兩次輪班。
以下各節提供護理師排程問題的解決方法。
匯入程式庫
下列程式碼會匯入所需的程式庫。
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}"));
}
}
}
陣列定義了「護理人員」的班別指派作業，如下所示：
如果將位移值指派給第 d 天的護士，則 shifts[(n, d, s)] 等於 1，0 等於 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 (「最多」 因為護理師可能有休息時間)。
平均分配位移
接下來，我們會示範如何盡可能平均分配輪值給護理人員。 由於三天期間的變動幅度為 9 個，我們就能指派 2 個班表 幫助 4 位護理師的手 之後會再移動一個小時，可以指派給任何護理師。
下列程式碼可確保每個護理師至少在 三天的訂閱週期。
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，因此您
可至少為每位護理師指派兩個輪班。它是由
限制 (如 Python 所示)
model.add(min_shifts_per_nurse <= sum(shifts_worked))
由於這三天期間內共有九班，因此本來的 將下一個輪班給每個護士。額外移動週期可以是 任何護理師
最後一行 (這是 Python)
model.add(sum(shifts_worked) <= max_shifts_per_nurse)
確保護理人員不會分派超過一次
且不需要該限制，因為只有一個多餘的 。不過，不同參數值可能會有額外的位移 在這類情況下，必須設有限制條件
更新解題工具參數
在非最佳化模式中，您可以啟用所有解決方案的搜尋功能。
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
解決方案總數為 5,184 個。 下列計數引數說明原因。
首先，我們有 4 個選擇，任職的護理師可以做出額外職位。 選擇該護士後，可以給護理師有 3 種輪流指派的地方 因此，每隔 3 天就要分配時間 增加的偏移量為 4 · 33 = 108。 指派這個護士後，每天還有兩個未指派的輪班。
其餘三個護理師的職責為一個工作日 0 和 1，工作日 0 和 2 以及第 1 天和第 2 天的工作 有 3 個！= 將護理分派給這些日的 6 種方式，如 下圖。(我們現在還沒有 3 部、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，表示是否已要求轉移。舉例來說， 第 1 列第五位置的三倍 [0, 0, 1] 表示護理 1 次要求 第 5 天的調整 3。
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));
因為指派 s 值時，shift_requests[n][d][s] * shifts[(n, d, s) 為 1
在第 d 天為「n」護理，並要求護理人員提出轉移要求 (相反地，0 天)；
目標是符合要求的指派作業數
叫用解題工具
下列程式碼會呼叫解題工具。
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");
}
}