หน้านี้ได้รับการแปลโดย Cloud Translation API

การตั้งเวลาของพนักงาน

องค์กรที่มีพนักงานทำงานหลายกะจะต้องจัดตารางเวลาให้เพียงพอ ของพนักงานในแต่ละกะในแต่ละวัน ปกติแล้วกำหนดการจะมี ข้อจำกัด เช่น "พนักงานไม่ควรทำงาน 2 กะติดกัน" หากำหนดการที่ ตอบสนองข้อจำกัดทั้งหมดอาจคำนวณได้ยาก

ส่วนต่อไปนี้จะแสดงตัวอย่าง 2 รายการของปัญหาการกำหนดเวลาของพนักงาน และ แสดงวิธีแก้โจทย์โดยใช้เครื่องมือแก้โจทย์ CP-SAT

สำหรับตัวอย่างที่ซับซ้อนมากขึ้น โปรดดู โปรแกรมจัดตารางเวลาสำหรับกะการทำงาน ใน GitHub

ปัญหาตารางเวลาของพยาบาล

ในตัวอย่างถัดไป หัวหน้างานของโรงพยาบาลต้องจัดตารางเวลาสำหรับ พยาบาลในช่วงเวลา 3 วัน ภายใต้เงื่อนไขต่อไปนี้

แต่ละวันแบ่งออกเป็น 3 กะ 8 ชั่วโมง
ทุกๆ วัน แต่ละกะจะมอบหมายให้พยาบาลเพียงคนเดียว และพยาบาลคนไหนก็ทำงานให้คุณน้อยลง มากกว่า 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 หากกำหนดกะการทำงานให้พยาบาลในวันที่ 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();
    }
}

บรรทัดสุดท้ายบอกว่าสำหรับกะแต่ละกะ ผลรวมพยาบาลที่ได้รับมอบหมาย Shift เท่ากับ 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 กะให้พยาบาลแต่ละคน ซึ่งระบุโดย ข้อจำกัด (ใน Python)

model.add(min_shifts_per_nurse <= sum(shifts_worked))

เนื่องจากมีการปรับทั้งหมด 9 ครั้งในระยะเวลา 3 วัน กะที่เหลือหลังจากทำกะ 2 กะให้พยาบาลแต่ละคน การเปลี่ยนแปลงเพิ่มเติมสามารถ มอบหมายให้กับพยาบาลคนใดก็ได้

บรรทัดสุดท้าย (ที่นี่ใน Python)

model.add(sum(shifts_worked) <= max_shifts_per_nurse)

ทำให้แน่ใจว่าพยาบาลไม่ได้ถูกจัดกะการทำงานเกิน 1 กะ

คุณไม่จำเป็นต้องใช้ข้อจำกัดในกรณีนี้ เนื่องจากมีเพียง 1 ส่วนเพิ่มเติม Shift แต่สำหรับค่าพารามิเตอร์ที่แตกต่างกัน อาจมีการปรับเพิ่มหลายครั้ง ในกรณีที่จำเป็นต้องใช้ข้อจำกัด

อัปเดตพารามิเตอร์ตัวแก้โจทย์

ในรูปแบบที่ไม่ใช่การเพิ่มประสิทธิภาพ คุณสามารถเปิดใช้งานการค้นหาโซลูชันทั้งหมดได้

Python

solver = cp_model.CpSolver()
solver.parameters.linearization_level = 0
# Enumerate all solutions.
solver.parameters.enumerate_all_solutions = True

C++

Model model;
SatParameters parameters;
parameters.set_linearization_level(0);
// Enumerate all solutions.
parameters.set_enumerate_all_solutions(true);
model.Add(NewSatParameters(parameters));

Java

CpSolver solver = new CpSolver();
solver.getParameters().setLinearizationLevel(0);
// Tell the solver to enumerate all solutions.
solver.getParameters().setEnumerateAllSolutions(true);

C#

CpSolver solver = new CpSolver();
// Tell the solver to enumerate all solutions.
solver.StringParameters += "linearization_level:0 " + "enumerate_all_solutions:true ";

ลงทะเบียน Callback ของโซลูชัน

คุณต้องลงทะเบียน Callback ในเครื่องมือแก้โจทย์ที่ระบบจะเรียก โซลูชัน

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 วัน ดังนั้นจำนวนวิธีที่เป็นไปได้ในการมอบหมายงานสำหรับพยาบาล Shift เพิ่มเติมเท่ากับ 4 · 3³ = 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

แต่ละแถวในแผนภาพด้านบน มีวิธีที่เป็นไปได้ 2³ = 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 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();

สร้างตัวแปร

โค้ดต่อไปนี้คืออาร์เรย์ของตัวแปรสำหรับปัญหา

นอกจากตัวแปรจากตัวอย่างก่อนหน้านี้แล้ว ข้อมูลยังมี เป็น 3 ส่วนเท่ากับ 3 กะต่อวัน องค์ประกอบแต่ละรายการของ สามเท่าเท่ากับ 0 หรือ 1 ซึ่งหมายความว่ามีการขอกะ ตัวอย่างเช่น พารามิเตอร์ สาม [0, 0, 1] ในตำแหน่งที่ 5 ของแถว 1 หมายความว่าพยาบาล 1 ร้องขอ Shift 3 ในวันที่ 5

Python

shifts = {}
for n in all_nurses:
    for d in all_days:
        for s in all_shifts:
            shifts[(n, d, s)] = model.new_bool_var(f"shift_n{n}_d{d}_s{s}")

C++

std::map<std::tuple<int, int, int>, BoolVar> shifts;
for (int n : all_nurses) {
  for (int d : all_days) {
    for (int s : all_shifts) {
      auto key = std::make_tuple(n, d, s);
      shifts[key] = cp_model.NewBoolVar().WithName(
          absl::StrFormat("shift_n%dd%ds%d", n, d, s));
    }
  }
}

Java

Literal[][][] shifts = new Literal[numNurses][numDays][numShifts];
for (int n : allNurses) {
  for (int d : allDays) {
    for (int s : allShifts) {
      shifts[n][d][s] = model.newBoolVar("shifts_n" + n + "d" + d + "s" + s);
    }
  }
}

C#

Dictionary<Tuple<int, int, int>, IntVar> shifts = new Dictionary<Tuple<int, int, int>, IntVar>();
foreach (int n in allNurses)
{
    foreach (int d in allDays)
    {
        foreach (int s in allShifts)
        {
            shifts.Add(Tuple.Create(n, d, s), model.NewBoolVar($"shifts_n{n}d{d}s{s}"));
        }
    }
}

สร้างข้อจำกัด

โค้ดต่อไปนี้สร้างข้อจำกัดสำหรับปัญหา

Python

for d in all_days:
    for s in all_shifts:
        model.add_exactly_one(shifts[(n, d, s)] for n in all_nurses)

C++

for (int d : all_days) {
  for (int s : all_shifts) {
    std::vector<BoolVar> nurses;
    for (int n : all_nurses) {
      auto key = std::make_tuple(n, d, s);
      nurses.push_back(shifts[key]);
    }
    cp_model.AddExactlyOne(nurses);
  }
}

Java

for (int d : allDays) {
  for (int s : allShifts) {
    List<Literal> nurses = new ArrayList<>();
    for (int n : allNurses) {
      nurses.add(shifts[n][d][s]);
    }
    model.addExactlyOne(nurses);
  }
}

C#

foreach (int d in allDays)
{
    foreach (int s in allShifts)
    {
        IntVar[] x = new IntVar[numNurses];
        foreach (int n in allNurses)
        {
            var key = Tuple.Create(n, d, s);
            x[n] = shifts[key];
        }
        model.Add(LinearExpr.Sum(x) == 1);
    }
}

Python

for n in all_nurses:
    for d in all_days:
        model.add_at_most_one(shifts[(n, d, s)] for s in all_shifts)

C++

for (int n : all_nurses) {
  for (int d : all_days) {
    std::vector<BoolVar> work;
    for (int s : all_shifts) {
      auto key = std::make_tuple(n, d, s);
      work.push_back(shifts[key]);
    }
    cp_model.AddAtMostOne(work);
  }
}

Java

for (int n : allNurses) {
  for (int d : allDays) {
    List<Literal> work = new ArrayList<>();
    for (int s : allShifts) {
      work.add(shifts[n][d][s]);
    }
    model.addAtMostOne(work);
  }
}

C#

foreach (int n in allNurses)
{
    foreach (int d in allDays)
    {
        IntVar[] x = new IntVar[numShifts];
        foreach (int s in allShifts)
        {
            var key = Tuple.Create(n, d, s);
            x[s] = shifts[key];
        }
        model.Add(LinearExpr.Sum(x) <= 1);
    }
}

Python

# Try to distribute the shifts evenly, so that each nurse works
# min_shifts_per_nurse shifts. If this is not possible, because the total
# number of shifts is not divisible by the number of nurses, some nurses will
# be assigned one more shift.
min_shifts_per_nurse = (num_shifts * num_days) // num_nurses
if num_shifts * num_days % num_nurses == 0:
    max_shifts_per_nurse = min_shifts_per_nurse
else:
    max_shifts_per_nurse = min_shifts_per_nurse + 1
for n in all_nurses:
    num_shifts_worked: Union[cp_model.LinearExpr, int] = 0
    for d in all_days:
        for s in all_shifts:
            num_shifts_worked += shifts[(n, d, s)]
    model.add(min_shifts_per_nurse <= num_shifts_worked)
    model.add(num_shifts_worked <= max_shifts_per_nurse)

C++

// Try to distribute the shifts evenly, so that each nurse works
// min_shifts_per_nurse shifts. If this is not possible, because the total
// number of shifts is not divisible by the number of nurses, some nurses will
// be assigned one more shift.
int min_shifts_per_nurse = (num_shifts * num_days) / num_nurses;
int max_shifts_per_nurse;
if ((num_shifts * num_days) % num_nurses == 0) {
  max_shifts_per_nurse = min_shifts_per_nurse;
} else {
  max_shifts_per_nurse = min_shifts_per_nurse + 1;
}
for (int n : all_nurses) {
  LinearExpr num_worked_shifts;
  for (int d : all_days) {
    for (int s : all_shifts) {
      auto key = std::make_tuple(n, d, s);
      num_worked_shifts += shifts[key];
    }
  }
  cp_model.AddLessOrEqual(min_shifts_per_nurse, num_worked_shifts);
  cp_model.AddLessOrEqual(num_worked_shifts, max_shifts_per_nurse);
}

Java

// Try to distribute the shifts evenly, so that each nurse works
// minShiftsPerNurse shifts. If this is not possible, because the total
// number of shifts is not divisible by the number of nurses, some nurses will
// be assigned one more shift.
int minShiftsPerNurse = (numShifts * numDays) / numNurses;
int maxShiftsPerNurse;
if ((numShifts * numDays) % numNurses == 0) {
  maxShiftsPerNurse = minShiftsPerNurse;
} else {
  maxShiftsPerNurse = minShiftsPerNurse + 1;
}
for (int n : allNurses) {
  LinearExprBuilder numShiftsWorked = LinearExpr.newBuilder();
  for (int d : allDays) {
    for (int s : allShifts) {
      numShiftsWorked.add(shifts[n][d][s]);
    }
  }
  model.addLinearConstraint(numShiftsWorked, minShiftsPerNurse, maxShiftsPerNurse);
}

C#

// Try to distribute the shifts evenly, so that each nurse works
// minShiftsPerNurse shifts. If this is not possible, because the total
// number of shifts is not divisible by the number of nurses, some nurses will
// be assigned one more shift.
int minShiftsPerNurse = (numShifts * numDays) / numNurses;
int maxShiftsPerNurse;
if ((numShifts * numDays) % numNurses == 0)
{
    maxShiftsPerNurse = minShiftsPerNurse;
}
else
{
    maxShiftsPerNurse = minShiftsPerNurse + 1;
}
foreach (int n in allNurses)
{
    IntVar[] numShiftsWorked = new IntVar[numDays * numShifts];
    foreach (int d in allDays)
    {
        foreach (int s in allShifts)
        {
            var key = Tuple.Create(n, d, s);
            numShiftsWorked[d * numShifts + s] = shifts[key];
        }
    }
    model.AddLinearConstraint(LinearExpr.Sum(numShiftsWorked), minShiftsPerNurse, maxShiftsPerNurse);
}

วัตถุประสงค์สำหรับตัวอย่าง

เราต้องการเพิ่มประสิทธิภาพฟังก์ชันวัตถุประสงค์ต่อไปนี้

Python

model.maximize(
    sum(
        shift_requests[n][d][s] * shifts[(n, d, s)]
        for n in all_nurses
        for d in all_days
        for s in all_shifts
    )
)

C++

LinearExpr objective_expr;
for (int n : all_nurses) {
  for (int d : all_days) {
    for (int s : all_shifts) {
      if (shift_requests[n][d][s] == 1) {
        auto key = std::make_tuple(n, d, s);
        objective_expr += shifts[key] * shift_requests[n][d][s];
      }
    }
  }
}
cp_model.Maximize(objective_expr);

Java

LinearExprBuilder obj = LinearExpr.newBuilder();
for (int n : allNurses) {
  for (int d : allDays) {
    for (int s : allShifts) {
      obj.addTerm(shifts[n][d][s], shiftRequests[n][d][s]);
    }
  }
}
model.maximize(obj);

C#

IntVar[] flatShifts = new IntVar[numNurses * numDays * numShifts];
int[] flatShiftRequests = new int[numNurses * numDays * numShifts];
foreach (int n in allNurses)
{
    foreach (int d in allDays)
    {
        foreach (int s in allShifts)
        {
            var key = Tuple.Create(n, d, s);
            flatShifts[n * numDays * numShifts + d * numShifts + s] = shifts[key];
            flatShiftRequests[n * numDays * numShifts + d * numShifts + s] = shiftRequests[n, d, s];
        }
    }
}
model.Maximize(LinearExpr.WeightedSum(flatShifts, flatShiftRequests));

เนื่องจาก shift_requests[n][d][s] * shifts[(n, d, s) เท่ากับ 1 หากมีการมอบหมายกะ s ถึงพยาบาล n ในวันที่ d และพยาบาลคนนั้นขอให้กะการทำงานของ (และอีก 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");
    }
}