직원 예약

직원이 여러 교대 근무를 하는 조직은 각 일일 교대 근무자 수 일반적으로 일정에는 제약이 있으며 예: "어떤 직원도 연속으로 두 교대 근무를 해서는 안 됩니다." 나에게 맞는 모든 제약 조건을 충족하는지 확인하는 것은 계산이 어려울 수 있습니다.

다음 섹션에서는 직원 일정 관리 문제의 두 가지 예를 보여줍니다. CP-SAT 솔버를 사용하여 푸는 방법을 보여줍니다.

더 정교한 예는 다음을 참조하세요. 교대 근무 일정 관리 프로그램 를 참조하세요.

간호사 일정 예약 문제

다음 예에서 병원 관리자는 이 4번 환자가 되기 위해 다음 조건을 충족하는 경우 3일 동안 간호사에게 광고를 게재할 수 있습니다.

  • 매일은 8시간씩 3회의 교대 근무로 나뉩니다.
  • 매일 각 교대 근무자는 한 명의 간호사에게 배정되며, 더 이상 일하는 간호사는 없습니다. 한 번 더 사용합니다.
  • 각 간호사는 3일 동안 최소 2회의 교대로 배정됩니다.

다음 섹션에서는 간호사 일정 예약 문제에 대한 솔루션을 보여줍니다.

라이브러리 가져오기

다음 코드는 필요한 라이브러리를 가져옵니다.

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"

자바

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);

자바

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;

자바

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));
    }
  }
}

자바

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}"));
        }
    }
}

배열은 간호사 교대 근무의 배정을 다음과 같이 정의합니다. 교대 근무 s가 d일에 n 간호사에게 할당되면 shifts[(n, d, s)]은 1이고 0은 0입니다. 없습니다.

교대 근무 간호사 배정

다음으로, 다음과 같은 제약조건에 따라 교대 근무에 간호사를 배정하는 방법을 보여드리겠습니다.

  • 각 교대 근무는 하루에 간호사 한 명에게 배정됩니다.
  • 각 간호사는 하루에 최대 한 교대로 근무합니다.

다음은 첫 번째 조건을 만드는 코드입니다.

Python

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

C++

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

자바

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

C#

List<ILiteral> literals = new List<ILiteral>();
foreach (int d in allDays)
{
    foreach (int s in allShifts)
    {
        foreach (int n in allNurses)
        {
            literals.Add(shifts[(n, d, s)]);
        }
        model.AddExactlyOne(literals);
        literals.Clear();
    }
}

마지막 줄에는 각 교대 근무에 대해 배정된 간호사 수의 합계가 Shift는 1입니다.

다음으로 각 간호사가 근무당 최대 한 교대로 일해야 하는 코드입니다 있습니다.

Python

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

C++

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

자바

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회 왜냐하면 간호사는 쉬는 날이 있기 때문이죠.)

교대 근무를 균등하게 할당

다음으로 간호사에게 가능한 한 교대 근무를 균등하게 할당하는 방법을 알아봅니다. 3일 동안 교대 근무 횟수가 9회이므로 2회 근무를 배정할 수 있습니다. 네 명의 간호사에게 말이죠. 그 후 교대 1회가 남게 되며, 이는 어느 간호사에게나 배정할 수 있습니다.

다음 코드를 사용하면 각 간호사가 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);
}

자바

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

C#

// Try to distribute the shifts evenly, so that each nurse works
// minShiftsPerNurse shifts. If this is not possible, because the total
// number of shifts is not divisible by the number of nurses, some nurses will
// be assigned one more shift.
int minShiftsPerNurse = (numShifts * numDays) / numNurses;
int maxShiftsPerNurse;
if ((numShifts * numDays) % numNurses == 0)
{
    maxShiftsPerNurse = minShiftsPerNurse;
}
else
{
    maxShiftsPerNurse = minShiftsPerNurse + 1;
}

List<IntVar> shiftsWorked = new List<IntVar>();
foreach (int n in allNurses)
{
    foreach (int d in allDays)
    {
        foreach (int s in allShifts)
        {
            shiftsWorked.Add(shifts[(n, d, s)]);
        }
    }
    model.AddLinearConstraint(LinearExpr.Sum(shiftsWorked), minShiftsPerNurse, maxShiftsPerNurse);
    shiftsWorked.Clear();
}

일정 기간에 총 num_shifts * num_days회의 근무조가 발생했으므로 최소 (num_shifts * num_days) // num_nurses개를 할당할 수 있음

각 간호사에게 교대로 근무하지만 일부 교대 근무는 그대로 남아 있을 수 있습니다. 여기서 //는 Python입니다. 정수 나누기 연산자가 있습니다.)

지정된 num_nurses = 4, num_shifts = 3, num_days = 3 값의 경우 표현식 min_shifts_per_nurse의 값이 (3 * 3 // 4) = 2이므로 각 간호사에게 최소 두 개의 교대 근무를 할당할 수 있습니다. 이는 제약조건 (여기 Python) 

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

3일 동안 총 9회의 변동이 있었으므로 각 간호사에게 2개의 교대 근무가 배정되었습니다. 추가 근무 시간은 간호사에게 배정할 수 있습니다

마지막 줄 (여기 Python)

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

두 번 이상 교대 근무를 배정받지 않습니다.

이 경우에는 추가 속성이 하나뿐이므로 제약 조건이 필요하지 않습니다. 있습니다. 그러나 다른 매개변수 값의 경우 몇 가지 추가 이동이 있을 수 있습니다. 이 경우 제약조건이 필요합니다.

문제 해결사 매개변수 업데이트

최적화가 아닌 모델에서는 모든 솔루션에 대해 검색을 사용 설정할 수 있습니다.

Python

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

C++

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

자바

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.";
  }
}));

자바

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);

자바

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

총 솔루션 수는 5,184개입니다. 다음 집계 인수에 그 이유가 설명되어 있습니다.

첫째, 추가 교대 근무를 하는 간호사 한 명에게는 네 가지 선택지가 있습니다. 해당 간호사를 선택하면 3개의 교대 근무를 배정할 수 있습니다. 3일마다 한 번씩 반복해야 하므로 추가 시프트는 4 · 33 = 108입니다. 이 간호사를 배정한 후, 매일 두 번의 미할당 교대 근무가 남아 있습니다.

나머지 3명의 간호사 중 한 명은 0일 차와 1일 차, 한 명은 0일 차와 2일 차에 근무했고 첫 번째 날과 둘째 날은 효과가 있습니다. 세 가지입니다. = 다음 그림에 표시된 것처럼 요즘 간호사를 배정하는 6가지 방법 참조하세요. (세 명의 간호사는 A, B, C로 되어 있는데 배정할 수 있습니다.)

Day 0    Day 1    Day 2
 A B      A C      B C
 A B      B C      A C
 A C      A B      B C
 A C      B C      A B
 B C      A B      A C
 B C      A C      A B

위 다이어그램의 각 행에는 다음과 같은 23 = 8가지 방법이 있습니다. 간호사에게 나머지 교대 근무 시간을 배정합니다 (매일 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;
}

자바

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"

자바

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},
    },
};

자바

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;

자바

CpModel model = new CpModel();

C#

CpModel model = new CpModel();

변수 만들기

다음 코드는 문제에 대한 변수 배열입니다.

이전 예의 변수 외에도 데이터에는 이는 하루 3회의 교대에 해당하는 3줄입니다. 이 triple은 0 또는 1로, 이동이 요청되었는지 여부를 나타냅니다. 예를 들어 1행의 다섯 번째 위치에 있는 트리플 [0, 0, 1] 은 간호사 1이 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));
    }
  }
}

자바

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);
  }
}

자바

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);
  }
}

자바

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);
}

자바

// 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);

자바

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

C#

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

근무 시간 s이(가) 할당된 경우 shift_requests[n][d][s] * shifts[(n, d, s)은(는) 1입니다. d에 n 간호사를 했으며 해당 간호사는 교대 근무를 요청했습니다 (그렇지 않으면 0). 목표는 요청에 맞는 할당 수를 이동하는 것입니다.

솔버 호출

다음 코드는 솔버를 호출합니다.

Python

solver = cp_model.CpSolver()
status = solver.solve(model)

C++

const CpSolverResponse response = Solve(cp_model.Build());

자바

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 !";
}

자바

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;
}

자바

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");
    }
}