Or 工具的护士排班问题，在某些日子增加不同的轮班时间

Question

我正在修改 here 的代码，我希望能够为特定的一天添加不同长度的班次。（例如，我希望 Friday/Day 4 只有 2 个班次).我的代码总是以错误代码结尾。我认为这是由于我设置的约束存在一些内部问题。

我在 Whosebug 上看到了一些类似程序的 post，但找不到解决我的具体问题的程序。

from ortools.sat.python import cp_model

class employeePartialSolutionPrinter(cp_model.CpSolverSolutionCallback):
    """Print intermediate solutions."""
    def __init__(self, shifts, num_employee, num_days, num_shifts, sols):
        cp_model.CpSolverSolutionCallback.__init__(self)
        self._shifts = shifts
        self._num_employee = num_employee
        self._num_days = num_days
        self._num_shifts = num_shifts
        self._solutions = set(sols)
        self._solution_count = 0

    def on_solution_callback(self):
        self._solution_count += 1
        if self._solution_count in self._solutions:
            print('Solution %i' % self._solution_count)
            for d in range(self._num_days):
                print('Day %i' % d)
                for n in range(self._num_employee):
                    is_working = False
                    for s in range(self._num_shifts):
                        if self.Value(self._shifts[(n, d, s)]):
                            is_working = True
                            print('  Employee %i works shift %i' % (n, s))
                    if not is_working:
                        print('  Employee {} does not work'.format(n))

    def solution_count(self):
        return self._solution_count
model = cp_model.CpModel()
solver = cp_model.CpSolver()

num_employee = 5
num_shifts = 5
num_days = 5
all_employee = range(num_employee)
all_shifts = range(num_shifts)
all_days = range(num_days)

# Normal Hours
# Monday-Thursday Shift 0-4
# Friday Shift 0-1
friday_deduct = 3

shifts = {}
for n in all_employee:
    for d in all_days:
        if d == 4:
            for s in range(num_shifts-friday_deduct):
                shifts[(n, d, s)] = model.NewBoolVar('shift_n%id%is%i' % (n, d, s))
        else:
            for s in all_shifts:
                shifts[(n,d,s)] = model.NewBoolVar('shift_n%id%is%i' % (n,d,s))


"""
Constraints (Normal Time)
"""
# Each Shift is assigned to a single person per day
# Shift 2 need to be assigned to 3 person
# Shift 1 and 3 need to be assigned to 2 person
for d in all_days:
    if d == 4:
        for s in range(num_shifts-friday_deduct):
            if s == 1:
                model.Add(sum(shifts[(n, d, s)] for n in all_employee) == 2)
            else:
                model.Add(sum(shifts[(n, d, s)] for n in all_employee) == 1)
    else:
        for s in all_shifts:
            if s == 2 :
                model.Add(sum(shifts[(n,d,s)] for n in all_employee) == 3)
            elif s == 3 or s == 1:
                model.Add(sum(shifts[(n, d, s)] for n in all_employee) == 2)
            else:
                model.Add(sum(shifts[(n,d,s)] for n in all_employee) == 1)

#Each nurse works at most 10 shift per week, at least 4 shift per week
for n in range(num_employee):
    week = []
    for d in all_days:
        if d == 4:
            for s in range(num_shifts-friday_deduct):
                week.append(shifts[(n,d,s)])
            # week.append(sum(shifts[(n, d, s)] for s in range(num_shifts-friday_deduct)))
        else:
            for s in all_shifts:
                week.append(shifts[(n,d,s)])
            # week.append(sum(shifts[(n,d,s)] for s in all_shifts))
    model.Add(sum(week) >= 4)
    model.Add(sum(week) <=10)

solver.parameters.linearization_level = 0
a_few_solutions = range(5)
solution_printer = employeePartialSolutionPrinter(shifts, num_employee, 
num_days, num_shifts, a_few_solutions)
solver.SearchForAllSolutions(model, solution_printer)

这是 Pycharm IDE 的打印输出。当我从命令行运行时，window "Python has stopped working" 出现了。

Solution 1
Day 0
  Employee 0 does not work
  Employee 1 does not work
  Employee 2 works shift 2
  Employee 3 works shift 1
  Employee 3 works shift 2
  Employee 3 works shift 3
  Employee 3 works shift 4
  Employee 4 works shift 0
  Employee 4 works shift 1
  Employee 4 works shift 2
  Employee 4 works shift 3
Day 1
  Employee 0 works shift 2
  Employee 0 works shift 3
  Employee 0 works shift 4
  Employee 1 works shift 2
  Employee 2 works shift 1
  Employee 2 works shift 2
  Employee 2 works shift 3
  Employee 3 works shift 0
  Employee 3 works shift 1
  Employee 4 does not work
Day 2
  Employee 0 works shift 2
  Employee 0 works shift 3
  Employee 0 works shift 4
  Employee 1 works shift 0
  Employee 1 works shift 1
  Employee 1 works shift 2
  Employee 1 works shift 3
  Employee 2 works shift 1
  Employee 2 works shift 2
  Employee 3 does not work
  Employee 4 does not work
Day 3
  Employee 0 works shift 2
  Employee 0 works shift 3
  Employee 0 works shift 4
  Employee 1 works shift 1
  Employee 1 works shift 2
  Employee 1 works shift 3
  Employee 2 works shift 0
  Employee 2 works shift 1
  Employee 2 works shift 2
  Employee 3 does not work
  Employee 4 does not work
Day 4

Process finished with exit code -1073740791 (0xC0000409)

Answer 1

您的回调有一个关键错误（第 4 天只有 2 个班次）：

for s in range(self._num_shifts):
    if self.Value(self._shifts[(n, d, s)]):

一个简单的检查即可：

if (n, d, s) in self._shifts and self.Value(
    self._shifts[(n, d, s)]
):

但您绝对应该看看 Laurent 建议的另一个例子。 https://github.com/google/or-tools/blob/master/examples/python/shift_scheduling_sat.py

Or 工具的护士排班问题，在某些日子增加不同的轮班时间

Nurse Scheduling Problem with Or Tools, adding different length of shift on certain days

python

or-tools