องค์กรที่พนักงานทำงานหลายกะจำเป็นต้องจัดตารางเวลาให้คนทำงานเพียงพอสำหรับกะการทำงานในแต่ละวัน โดยทั่วไปแล้ว ตารางเวลาจะมีข้อจำกัด เช่น "พนักงานไม่ควรทำงาน 2 กะติดกัน" การหากำหนดการที่ตอบสนองต่อข้อจำกัดทั้งหมด อาจเป็นเรื่องยาก
ส่วนต่อไปนี้แสดงตัวอย่างปัญหาการกำหนดเวลาของพนักงาน 2 ตัวอย่าง และแสดงวิธีแก้ไขปัญหาโดยใช้เครื่องมือแก้โจทย์ CP-SAT
ดูตัวอย่างที่ซับซ้อนมากขึ้นได้จากโปรแกรมจัดตารางเวลาสำหรับ Shift นี้ใน GitHub
ปัญหาการกำหนดเวลาพยาบาล
ในตัวอย่างถัดไป ผู้ดูแลโรงพยาบาลต้องสร้างตารางเวลาสำหรับพยาบาล 4 คนในช่วงเวลา 3 วัน โดยอยู่ภายใต้เงื่อนไขต่อไปนี้
- แต่ละวันจะแบ่งออกเป็น 3 กะเป็นเวลา 8 ชั่วโมง
- ทุกๆ วันจะมีการแบ่งกะสำหรับพยาบาล 1 คน และไม่มีพยาบาลคนใดทำงานเกิน 1 กะ
- พยาบาลแต่ละคนได้รับมอบหมายให้ทำงานอย่างน้อย 2 กะในระยะเวลา 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}")); } } }
อาร์เรย์จะกำหนดงานสำหรับกะงานของพยาบาล ดังนี้
shifts[(n, d, s)]
เท่ากับ 1 หากมีการกำหนดกะการทำงานให้กับพยาบาล n ในวันที่ d และ 0
หากไม่มี
แบ่งกะพยาบาล
ถัดไป เราจะแสดงวิธีมอบหมายให้พยาบาลกะงานภายใต้ข้อจำกัดต่อไปนี้
- กะงานแต่ละกะมีกับพยาบาล 1 คนต่อวัน
- พยาบาลแต่ละคนทำงานไม่เกินวันละ 1 กะ
นี่คือโค้ดที่สร้างเงื่อนไขแรก
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(); } }
บรรทัดสุดท้ายบอกว่าสำหรับแต่ละกะ ผลรวมของพยาบาลที่กำหนดให้กะงานนั้นเท่ากับ 1
ต่อไปเป็นรหัสที่กำหนดให้พยาบาลแต่ละคนทำงานไม่เกิน 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 กะในช่วง 3 วัน เราจึงสามารถมอบหมายกะ 2 กะให้แก่พยาบาลทั้ง 4 คน หลังจากนั้นก็จะต้องทำงานเหลือ 1 กะซึ่งสามารถมอบหมายให้พยาบาลคนใดก็ได้
โค้ดต่อไปนี้ช่วยให้พยาบาลแต่ละคนทำงานอย่างน้อย 2 กะในระยะเวลา 3 วัน
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
คุณจึงกำหนดเองได้อย่างน้อย 2 Shift แก่พยาบาลแต่ละคน โดยระบุตามข้อจํากัด (ใน Python)
model.add(min_shifts_per_nurse <= sum(num_shifts_worked))
เนื่องจากมีการเปลี่ยนกะทั้งหมด 9 ครั้งในระยะเวลา 3 วัน จึงเหลืออีก 1 กะหลังจากมอบหมายกะ 2 กะให้พยาบาลแต่ละคน กะลาส่วนเกินนั้น สามารถมอบหมายให้พยาบาลคนไหนก็ได้
บรรทัดสุดท้าย (ใน Python)
model.add(sum(num_shifts_worked) <= max_shifts_per_nurse)
ทำให้ไม่มีแพทย์ประจำตัวที่ได้รับมอบหมายกะทันหันมากกว่า 1 กะ
คุณไม่จำเป็นต้องใช้ข้อจำกัดในกรณีนี้ เนื่องจากจะมีเพียง 1 การเปลี่ยนแปลงเพิ่มเติมเท่านั้น แต่สำหรับค่าพารามิเตอร์ที่แตกต่างกัน อาจมีการเปลี่ยนแปลงเพิ่มเติมหลายครั้ง ซึ่งในกรณีนี้จำเป็นต้องมีข้อจำกัด
อัปเดตพารามิเตอร์เครื่องมือแก้โจทย์คณ
ในรูปแบบที่ไม่ใช่การเพิ่มประสิทธิภาพ คุณสามารถเปิดใช้การค้นหาสำหรับโซลูชันทั้งหมดได้
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);
เรียกใช้เครื่องมือแก้โจทย์
โค้ดต่อไปนี้เรียกเครื่องมือแก้โจทย์และแสดงโซลูชัน 5 รายการแรก
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}");
โซลูชัน
โซลูชัน 5 รายการแรกมีดังนี้
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 ทางเลือกสำหรับพยาบาล 1 คนที่ทำงานเพิ่มกะทันหัน เมื่อเลือกพยาบาลแล้ว จะมีการปรับกะ 3 กะที่พยาบาลสามารถกำหนดให้ในแต่ละวัน 3 วัน ดังนั้นจำนวนวิธีที่เป็นไปได้ในการมอบหมายงานให้พยาบาลเปลี่ยนกะคือ 4 · 33 = 108 หลังจากมอบหมายงานให้พยาบาลรายนี้แล้ว ก็ยังมีกะอีก 2 กะที่ไม่ได้มอบหมายในแต่ละวัน
จากพยาบาล 3 คนที่เหลือ 1 วันทำงาน 0 วันและ 1 วันทำงาน 1 วัน 0 และ 2 และอีก 1 วันทำงานวันที่ 1 และ 2 มี 3 ข้อ = 6 วิธีในการนัดพยาบาลให้ในช่วงเวลานี้ ดังที่แสดงในแผนภาพด้านล่าง (พยาบาล 3 คนมีป้ายกำกับเป็น A, B และ C และเรายังไม่ได้มอบหมายให้กะเหล่านี้)
Day 0 Day 1 Day 2
A B A C B C
A B B C A C
A C A B B C
A C B C A B
B C A B A C
B C A C A B
สำหรับแต่ละแถวในแผนภาพด้านบน มี 23 วิธีที่เป็นไปได้ 8 วิธีในการมอบหมายกะงานที่เหลือให้แก่พยาบาล (2 ตัวเลือกในแต่ละวัน) ดังนั้น จำนวนงานที่เป็นไปได้ทั้งหมดคือ 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 ortools.sat.python import cp_model
C++
#include <stdlib.h> #include <cstdint> #include <map> #include <numeric> #include <string> #include <tuple> #include <vector> #include "absl/strings/str_format.h" #include "ortools/base/logging.h" #include "ortools/sat/cp_model.h" #include "ortools/sat/cp_model.pb.h" #include "ortools/sat/cp_model_solver.h"
Java
import com.google.ortools.Loader; import com.google.ortools.sat.CpModel; import com.google.ortools.sat.CpSolver; import com.google.ortools.sat.CpSolverStatus; import com.google.ortools.sat.LinearExpr; import com.google.ortools.sat.LinearExprBuilder; import com.google.ortools.sat.Literal; import java.util.ArrayList; import java.util.List; import java.util.stream.IntStream;
C#
using System; using System.Collections.Generic; using System.Linq; using Google.OrTools.Sat;
ข้อมูลสำหรับตัวอย่าง
ข้อมูลของตัวอย่างนี้จะแสดงหลังจาก
Python
num_nurses = 5 num_shifts = 3 num_days = 7 all_nurses = range(num_nurses) all_shifts = range(num_shifts) all_days = range(num_days) shift_requests = [ [[0, 0, 1], [0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 0, 1]], [[0, 0, 0], [0, 0, 0], [0, 1, 0], [0, 1, 0], [1, 0, 0], [0, 0, 0], [0, 0, 1]], [[0, 1, 0], [0, 1, 0], [0, 0, 0], [1, 0, 0], [0, 0, 0], [0, 1, 0], [0, 0, 0]], [[0, 0, 1], [0, 0, 0], [1, 0, 0], [0, 1, 0], [0, 0, 0], [1, 0, 0], [0, 0, 0]], [[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 0, 0], [1, 0, 0], [0, 1, 0], [0, 0, 0]], ]
C++
const int num_nurses = 5; const int num_days = 7; const int num_shifts = 3; std::vector<int> all_nurses(num_nurses); std::iota(all_nurses.begin(), all_nurses.end(), 0); std::vector<int> all_days(num_days); std::iota(all_days.begin(), all_days.end(), 0); std::vector<int> all_shifts(num_shifts); std::iota(all_shifts.begin(), all_shifts.end(), 0); std::vector<std::vector<std::vector<int64_t>>> shift_requests = { { {0, 0, 1}, {0, 0, 0}, {0, 0, 0}, {0, 0, 0}, {0, 0, 1}, {0, 1, 0}, {0, 0, 1}, }, { {0, 0, 0}, {0, 0, 0}, {0, 1, 0}, {0, 1, 0}, {1, 0, 0}, {0, 0, 0}, {0, 0, 1}, }, { {0, 1, 0}, {0, 1, 0}, {0, 0, 0}, {1, 0, 0}, {0, 0, 0}, {0, 1, 0}, {0, 0, 0}, }, { {0, 0, 1}, {0, 0, 0}, {1, 0, 0}, {0, 1, 0}, {0, 0, 0}, {1, 0, 0}, {0, 0, 0}, }, { {0, 0, 0}, {0, 0, 1}, {0, 1, 0}, {0, 0, 0}, {1, 0, 0}, {0, 1, 0}, {0, 0, 0}, }, };
Java
final int numNurses = 5; final int numDays = 7; final int numShifts = 3; final int[] allNurses = IntStream.range(0, numNurses).toArray(); final int[] allDays = IntStream.range(0, numDays).toArray(); final int[] allShifts = IntStream.range(0, numShifts).toArray(); final int[][][] shiftRequests = new int[][][] { { {0, 0, 1}, {0, 0, 0}, {0, 0, 0}, {0, 0, 0}, {0, 0, 1}, {0, 1, 0}, {0, 0, 1}, }, { {0, 0, 0}, {0, 0, 0}, {0, 1, 0}, {0, 1, 0}, {1, 0, 0}, {0, 0, 0}, {0, 0, 1}, }, { {0, 1, 0}, {0, 1, 0}, {0, 0, 0}, {1, 0, 0}, {0, 0, 0}, {0, 1, 0}, {0, 0, 0}, }, { {0, 0, 1}, {0, 0, 0}, {1, 0, 0}, {0, 1, 0}, {0, 0, 0}, {1, 0, 0}, {0, 0, 0}, }, { {0, 0, 0}, {0, 0, 1}, {0, 1, 0}, {0, 0, 0}, {1, 0, 0}, {0, 1, 0}, {0, 0, 0}, }, };
C#
const int numNurses = 5; const int numDays = 7; const int numShifts = 3; int[] allNurses = Enumerable.Range(0, numNurses).ToArray(); int[] allDays = Enumerable.Range(0, numDays).ToArray(); int[] allShifts = Enumerable.Range(0, numShifts).ToArray(); int[,,] shiftRequests = new int[,,] { { { 0, 0, 1 }, { 0, 0, 0 }, { 0, 0, 0 }, { 0, 0, 0 }, { 0, 0, 1 }, { 0, 1, 0 }, { 0, 0, 1 }, }, { { 0, 0, 0 }, { 0, 0, 0 }, { 0, 1, 0 }, { 0, 1, 0 }, { 1, 0, 0 }, { 0, 0, 0 }, { 0, 0, 1 }, }, { { 0, 1, 0 }, { 0, 1, 0 }, { 0, 0, 0 }, { 1, 0, 0 }, { 0, 0, 0 }, { 0, 1, 0 }, { 0, 0, 0 }, }, { { 0, 0, 1 }, { 0, 0, 0 }, { 1, 0, 0 }, { 0, 1, 0 }, { 0, 0, 0 }, { 1, 0, 0 }, { 0, 0, 0 }, }, { { 0, 0, 0 }, { 0, 0, 1 }, { 0, 1, 0 }, { 0, 0, 0 }, { 1, 0, 0 }, { 0, 1, 0 }, { 0, 0, 0 }, }, };
สร้างโมเดล
โค้ดต่อไปนี้จะสร้างโมเดล
Python
model = cp_model.CpModel()
C++
CpModelBuilder cp_model;
Java
CpModel model = new CpModel();
C#
CpModel model = new CpModel();
สร้างตัวแปร
โค้ดต่อไปนี้คืออาร์เรย์ของตัวแปรของโจทย์
นอกจากตัวแปรจากตัวอย่างก่อนหน้านี้แล้ว ข้อมูลยังมีชุดการเปลี่ยนแปลงสามครั้งซึ่งสอดคล้องกับการเปลี่ยนแปลงสามครั้งต่อวัน แต่ละองค์ประกอบของสามเท่าคือ 0 หรือ 1 ซึ่งบ่งบอกว่ามีการขอการเปลี่ยนแปลงหรือไม่ ตัวอย่างเช่น เลขสาม [0, 0, 1] ในตำแหน่งที่ 5 ของแถว 1 หมายความว่าพยาบาล 1 ส่งคำขอเปลี่ยนรายการที่ 3 ในวันที่ 5
Python
shifts = {} for n in all_nurses: for d in all_days: for s in all_shifts: shifts[(n, d, s)] = model.new_bool_var(f"shift_n{n}_d{d}_s{s}")
C++
std::map<std::tuple<int, int, int>, BoolVar> shifts; for (int n : all_nurses) { for (int d : all_days) { for (int s : all_shifts) { auto key = std::make_tuple(n, d, s); shifts[key] = cp_model.NewBoolVar().WithName( absl::StrFormat("shift_n%dd%ds%d", n, d, s)); } } }
Java
Literal[][][] shifts = new Literal[numNurses][numDays][numShifts]; for (int n : allNurses) { for (int d : allDays) { for (int s : allShifts) { shifts[n][d][s] = model.newBoolVar("shifts_n" + n + "d" + d + "s" + s); } } }
C#
Dictionary<Tuple<int, int, int>, IntVar> shifts = new Dictionary<Tuple<int, int, int>, IntVar>(); foreach (int n in allNurses) { foreach (int d in allDays) { foreach (int s in allShifts) { shifts.Add(Tuple.Create(n, d, s), model.NewBoolVar($"shifts_n{n}d{d}s{s}")); } } }
สร้างข้อจำกัด
โค้ดต่อไปนี้จะสร้างข้อจำกัดสำหรับปัญหา
Python
for d in all_days: for s in all_shifts: model.add_exactly_one(shifts[(n, d, s)] for n in all_nurses)
C++
for (int d : all_days) { for (int s : all_shifts) { std::vector<BoolVar> nurses; for (int n : all_nurses) { auto key = std::make_tuple(n, d, s); nurses.push_back(shifts[key]); } cp_model.AddExactlyOne(nurses); } }
Java
for (int d : allDays) { for (int s : allShifts) { List<Literal> nurses = new ArrayList<>(); for (int n : allNurses) { nurses.add(shifts[n][d][s]); } model.addExactlyOne(nurses); } }
C#
foreach (int d in allDays) { foreach (int s in allShifts) { IntVar[] x = new IntVar[numNurses]; foreach (int n in allNurses) { var key = Tuple.Create(n, d, s); x[n] = shifts[key]; } model.Add(LinearExpr.Sum(x) == 1); } }
Python
for n in all_nurses: for d in all_days: model.add_at_most_one(shifts[(n, d, s)] for s in all_shifts)
C++
for (int n : all_nurses) { for (int d : all_days) { std::vector<BoolVar> work; for (int s : all_shifts) { auto key = std::make_tuple(n, d, s); work.push_back(shifts[key]); } cp_model.AddAtMostOne(work); } }
Java
for (int n : allNurses) { for (int d : allDays) { List<Literal> work = new ArrayList<>(); for (int s : allShifts) { work.add(shifts[n][d][s]); } model.addAtMostOne(work); } }
C#
foreach (int n in allNurses) { foreach (int d in allDays) { IntVar[] x = new IntVar[numShifts]; foreach (int s in allShifts) { var key = Tuple.Create(n, d, s); x[s] = shifts[key]; } model.Add(LinearExpr.Sum(x) <= 1); } }
Python
# Try to distribute the shifts evenly, so that each nurse works # min_shifts_per_nurse shifts. If this is not possible, because the total # number of shifts is not divisible by the number of nurses, some nurses will # be assigned one more shift. min_shifts_per_nurse = (num_shifts * num_days) // num_nurses if num_shifts * num_days % num_nurses == 0: max_shifts_per_nurse = min_shifts_per_nurse else: max_shifts_per_nurse = min_shifts_per_nurse + 1 for n in all_nurses: num_shifts_worked = 0 for d in all_days: for s in all_shifts: num_shifts_worked += shifts[(n, d, s)] model.add(min_shifts_per_nurse <= num_shifts_worked) model.add(num_shifts_worked <= max_shifts_per_nurse)
C++
// Try to distribute the shifts evenly, so that each nurse works // min_shifts_per_nurse shifts. If this is not possible, because the total // number of shifts is not divisible by the number of nurses, some nurses will // be assigned one more shift. int min_shifts_per_nurse = (num_shifts * num_days) / num_nurses; int max_shifts_per_nurse; if ((num_shifts * num_days) % num_nurses == 0) { max_shifts_per_nurse = min_shifts_per_nurse; } else { max_shifts_per_nurse = min_shifts_per_nurse + 1; } for (int n : all_nurses) { LinearExpr num_worked_shifts; for (int d : all_days) { for (int s : all_shifts) { auto key = std::make_tuple(n, d, s); num_worked_shifts += shifts[key]; } } cp_model.AddLessOrEqual(min_shifts_per_nurse, num_worked_shifts); cp_model.AddLessOrEqual(num_worked_shifts, max_shifts_per_nurse); }
Java
// Try to distribute the shifts evenly, so that each nurse works // minShiftsPerNurse shifts. If this is not possible, because the total // number of shifts is not divisible by the number of nurses, some nurses will // be assigned one more shift. int minShiftsPerNurse = (numShifts * numDays) / numNurses; int maxShiftsPerNurse; if ((numShifts * numDays) % numNurses == 0) { maxShiftsPerNurse = minShiftsPerNurse; } else { maxShiftsPerNurse = minShiftsPerNurse + 1; } for (int n : allNurses) { LinearExprBuilder numShiftsWorked = LinearExpr.newBuilder(); for (int d : allDays) { for (int s : allShifts) { numShiftsWorked.add(shifts[n][d][s]); } } model.addLinearConstraint(numShiftsWorked, minShiftsPerNurse, maxShiftsPerNurse); }
C#
// Try to distribute the shifts evenly, so that each nurse works // minShiftsPerNurse shifts. If this is not possible, because the total // number of shifts is not divisible by the number of nurses, some nurses will // be assigned one more shift. int minShiftsPerNurse = (numShifts * numDays) / numNurses; int maxShiftsPerNurse; if ((numShifts * numDays) % numNurses == 0) { maxShiftsPerNurse = minShiftsPerNurse; } else { maxShiftsPerNurse = minShiftsPerNurse + 1; } foreach (int n in allNurses) { IntVar[] numShiftsWorked = new IntVar[numDays * numShifts]; foreach (int d in allDays) { foreach (int s in allShifts) { var key = Tuple.Create(n, d, s); numShiftsWorked[d * numShifts + s] = shifts[key]; } } model.AddLinearConstraint(LinearExpr.Sum(numShiftsWorked), minShiftsPerNurse, maxShiftsPerNurse); }
วัตถุประสงค์ของตัวอย่าง
เราต้องการเพิ่มประสิทธิภาพให้ฟังก์ชันวัตถุประสงค์ต่อไปนี้
Python
model.maximize( sum( shift_requests[n][d][s] * shifts[(n, d, s)] for n in all_nurses for d in all_days for s in all_shifts ) )
C++
LinearExpr objective_expr; for (int n : all_nurses) { for (int d : all_days) { for (int s : all_shifts) { if (shift_requests[n][d][s] == 1) { auto key = std::make_tuple(n, d, s); objective_expr += shifts[key] * shift_requests[n][d][s]; } } } } cp_model.Maximize(objective_expr);
Java
LinearExprBuilder obj = LinearExpr.newBuilder(); for (int n : allNurses) { for (int d : allDays) { for (int s : allShifts) { obj.addTerm(shifts[n][d][s], shiftRequests[n][d][s]); } } } model.maximize(obj);
C#
IntVar[] flatShifts = new IntVar[numNurses * numDays * numShifts]; int[] flatShiftRequests = new int[numNurses * numDays * numShifts]; foreach (int n in allNurses) { foreach (int d in allDays) { foreach (int s in allShifts) { var key = Tuple.Create(n, d, s); flatShifts[n * numDays * numShifts + d * numShifts + s] = shifts[key]; flatShiftRequests[n * numDays * numShifts + d * numShifts + s] = shiftRequests[n, d, s]; } } } model.Maximize(LinearExpr.WeightedSum(flatShifts, flatShiftRequests));
เนื่องจาก shift_requests[n][d][s] * shifts[(n, d, s)
มีค่าเป็น 1 หากมีการมอบหมายกะที่ s
ให้กับพยาบาล n
ในวันที่ d
และพยาบาลคนนั้นขอปรับกะดังกล่าว (และอาจเป็น 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 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 = 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"); } }