OR-Tools约束求解器中优化值班分配均匀性及节假日排班问题

我基于Google OR-Tools的员工调度脚本开发了一套值班调度器，目前运行正常，已实现以下功能：

• 确保每人的值班周期（两周一次）次数尽可能均等
• 支持班次请求
• 添加了禁止人员连续值班的约束

当前每人值班次数已尽可能均衡：

df['Name'].value_counts()
Out[42]: 
Jeff     7
Bubba    7
Sarah    6
Scott    6
Name: Name, dtype: int64

但排班存在人员集中安排的问题，例如会先集中安排某个人的班次，再切换到其他人，而非按轮值方式均匀分配。示例排班结果如下：

print(df)
     Name        Date    Shift
0   Sarah  01-09-2022  On Call
1   Scott  01-23-2022  On Call
2   Sarah  02-06-2022  On Call
3   Scott  02-20-2022  On Call
4   Sarah  03-06-2022  On Call
5    Jeff  03-20-2022  On Call
6   Sarah  04-03-2022  On Call
7    Jeff  04-17-2022  On Call
8   Sarah  05-01-2022  On Call
9    Jeff  05-15-2022  On Call
10  Sarah  05-29-2022  On Call
11   Jeff  06-12-2022  On Call
12  Bubba  06-26-2022  On Call
13   Jeff  07-10-2022  On Call
14  Bubba  07-24-2022  On Call
15   Jeff  08-07-2022  On Call
16  Scott  08-21-2022  On Call
17  Bubba  09-04-2022  On Call
18   Jeff  09-18-2022  On Call
19  Bubba  10-02-2022  On Call
20  Scott  10-16-2022  On Call
21  Bubba  10-30-2022  On Call
22  Scott  11-13-2022  On Call
23  Bubba  11-27-2022  On Call
24  Scott  12-11-2022  On Call
25  Bubba  12-25-2022  On Call

（初期集中安排Sarah值班是因为Scott有避班请求，此情况可接受，但希望其他人员排班更均匀）

现提出两个技术问题：

1. 如何调整约束求解器的设置，使人员的值班分配更均匀？
2. 如何添加新的约束，识别包含节假日的时段并实现这些时段的均等分配？

我的实现代码如下：

# %% imports
import pandas as pd
from ortools.sat.python import cp_model

# %% Data for the model
num_employees = 4
num_shifts = 1
num_oncall_shifts = 26
all_employees = range(num_employees)
all_shifts = range(num_shifts)
all_oncall_shifts = range(num_oncall_shifts)

dict_shift_name = {0: 'On Call'}

dict_emp_name = {0: 'Bubba', 1: 'Scott', 2: 'Jeff', 3: 'Sarah'}

dict_dates = {
    0: '01-09-2022',
    1: '01-23-2022',
    2: '02-06-2022',
    3: '02-20-2022',
    4: '03-06-2022',
    5: '03-20-2022',
    6: '04-03-2022',
    7: '04-17-2022',
    8: '05-01-2022',
    9: '05-15-2022',
    10: '05-29-2022',
    11: '06-12-2022',
    12: '06-26-2022',
    13: '07-10-2022',
    14: '07-24-2022',
    15: '08-07-2022',
    16: '08-21-2022',
    17: '09-04-2022',
    18: '09-18-2022',
    19: '10-02-2022',
    20: '10-16-2022',
    21: '10-30-2022',
    22: '11-13-2022',
    23: '11-27-2022',
    24: '12-11-2022',
    25: '12-25-2022'
    }

shift_requests = [
    [
     #Employee 0 Bubba
     #1/09  1/23  2/06  2/20  3/06  3/20  4/03  4/17  5/01  5/15  5/29  6/12
     [0],   [0],  [0],  [0],  [0],  [0],  [0],  [0],  [0],  [0],  [0],  [0],
     #6/26  7/10  7/24  8/07  8/21  9/04  9/18 10/02 10/16 10/30 11/13 11/27
     [0],   [0],  [0],  [0],  [-4],  [0],  [0], [0],  [0],  [0],  [0],  [0],
    #12/11 12/25
     [0],  [0]     
     ],
    
    [
     #Employee 1 Scott
     #1/09  1/23  2/06  2/20  3/06  3/20  4/03  4/17  5/01  5/15  5/29  6/12
     [0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[-1],[-1],
     #6/26  7/10  7/24  8/07  8/21  9/04  9/18 10/02 10/16 10/30 11/13 11/27
     [-1],[-1],[-1],[-1],[-1],[-1],[-1],[0],[0],[0],[0],[0],
    #12/11 12/25
     [0],[0]     
     ],
    
    [
     #Employee 2 Jeff
     #1/09  1/23  2/06  2/20  3/06  3/20  4/03  4/17  5/01  5/15  5/29  6/12
     [0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],
     #6/26  7/10  7/24  8/07  8/21  9/04  9/18 10/02 10/16 10/30 11/13 11/27
     [0],[0],[0],[0],[-2],[0],[0],[0],[0],[0],[0],[0],
    #12/11 12/25
     [0],[0]     
     ],
    
    [
     #Employee 3 Sarah
     #1/09  1/23  2/06  2/20  3/06  3/20  4/03  4/17  5/01  5/15  5/29  6/12
     [0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],
     #6/26  7/10  7/24  8/07  8/21  9/04  9/18 10/02 10/16 10/30 11/13 11/27
     [0],[0],[0],[0],[-3],[0],[0],[0],[0],[0],[0],[0],
    #12/11 12/25
     [0],[0]     
     ],
]

# dataframe
df = pd.DataFrame(columns=['Name', 'Date', 'Shift'])

# %% Create the Model
model = cp_model.CpModel()

# %% Create the variables

# Shift variables# Creates shift variables.
# shifts[(n, d, s)]: nurse 'n' works shift 's' on day 'd'.
shifts = {}
for n in all_employees:
    for d in all_oncall_shifts:
        for s in all_shifts:
            shifts[(n, d, s)] = model.NewBoolVar('shift_n%id%is%i' % (n, d, s))

# %% Add constraints
# Each shift is assigned to exactly one employee in .
for d in all_oncall_shifts :
    for s in all_shifts:
        model.AddExactlyOne(shifts[(n, d, s)] for n in all_employees)
        
# Each employee works at most one shift per oncall_shifts.
for n in all_employees:
    for d in all_oncall_shifts:
        model.AddAtMostOne(shifts[(n, d, s)] for s in all_shifts)

# Try to distribute the shifts evenly, so that each employee works
# min_shifts_per_employee shifts. If this is not possible, because the total
# number of shifts is not divisible by the number of employee, some employees will
# be assigned one more shift.
min_shifts_per_employee = (num_shifts * num_oncall_shifts) // num_employees
if num_shifts * num_oncall_shifts % num_employees == 0:
    max_shifts_per_employee = min_shifts_per_employee
else:
    max_shifts_per_employee = min_shifts_per_employee + 1
for n in all_employees:
    num_shifts_worked = 0
    for d in all_oncall_shifts:
        for s in all_shifts:
            num_shifts_worked += shifts[(n, d, s)]
    model.Add(min_shifts_per_employee <= num_shifts_worked)
    model.Add(num_shifts_worked <= max_shifts_per_employee)

# "penalize" working shift back to back
for d in all_employees:
    for b in all_oncall_shifts[:-1]:
        for r in all_shifts:
            for r1 in all_shifts:
                model.AddImplication(shifts[(d, b, r)], shifts[(d, b+1, r1)].Not())

# %% Objective
model.Maximize(
    sum(shift_requests[n][d][s] * shifts[(n, d, s)] for n in all_employees
        for d in all_oncall_shifts for s in all_shifts))

# %% Solve
# Creates the solver and solve.
solver = cp_model.CpSolver()
status = solver.Solve(model)
if status == cp_model.OPTIMAL:
    print('Solution:')
    for d in all_oncall_shifts:
        print('On Call Starts: ', dict_dates[d])
        for n in all_employees:
            for s in all_shifts:
                if solver.Value(shifts[(n, d, s)]) == 1:
                    if shift_requests[n][d][s] == 1:
                        print(dict_emp_name[n], ' is ', dict_shift_name[s], '(requested).')
                    else:
                        print(dict_emp_name[n], ' is ', dict_shift_name[s],
                              '(not requested).')
                        
                    list_append = [dict_emp_name[n], dict_dates[d], dict_shift_name[s]]
                    
                    df.loc[len(df)] = list_append
        print()
    print(f'Number of shift requests met = {solver.ObjectiveValue()}',
          f'(out of {num_employees * min_shifts_per_employee})')
else:
    print('No optimal solution found !')

# %% Stats
print('\nStatistics')
print('  - conflicts: %i' % solver.NumConflicts())
print('  - branches : %i' % solver.NumBranches())
print('  - wall time: %f s' % solver.WallTime())

问题解答 #

1. 调整约束使值班分配更均匀 #

当前约束仅保证总值班次数均衡，未控制时间维度的分布均匀，可通过以下两种方式优化：

方式一：添加滑动窗口约束

限制任意连续N个班次中，每个员工的值班次数不超过阈值，避免集中排班。以4人轮值为例，设置任意连续4个班次中每人最多值班1次：

# 添加滑动窗口均匀性约束
window_size = 4
max_shifts_in_window = 1

for d in range(num_oncall_shifts - window_size + 1):
    for n in all_employees:
        total = sum(shifts[(n, d+i, s)] for i in range(window_size) for s in all_shifts)
        model.Add(total <= max_shifts_in_window)

方式二：修改目标函数，最小化值班间隔方差

在目标函数中加入惩罚项，惩罚员工两次值班间隔偏离理想值的情况，引导求解器生成均匀排班：

# 原目标函数
original_objective = sum(shift_requests[n][d][s] * shifts[(n, d, s)] for n in all_employees
                        for d in all_oncall_shifts for s in all_shifts)

# 添加间隔惩罚项
penalty_weight = 100
interval_penalty = 0

for n in all_employees:
    # 遍历相邻值班班次，计算间隔偏差
    for d1 in range(num_oncall_shifts):
        for d2 in range(d1+1, num_oncall_shifts):
            # 当员工n在d1和d2都值班时，计算间隔与理想值（4）的偏差
            interval_diff = (d2 - d1) - 4
            interval_penalty += shifts[(n, d1, 0)] * shifts[(n, d2, 0)] * (interval_diff ** 2)

# 最大化原目标，同时最小化间隔惩罚
model.Maximize(original_objective - penalty_weight * interval_penalty)

2. 节假日时段均等分配约束 #

首先标记节假日对应的班次索引，再为这些班次单独设置均衡约束：

# 标记节假日班次索引（对应05-01-2022和12-25-2022）
holiday_shifts = [8, 25]

# 计算节假日班次的均衡范围
num_holiday_shifts = len(holiday_shifts)
min_holiday_shifts = num_holiday_shifts // num_employees
max_holiday_shifts = min_holiday_shifts + 1 if num_holiday_shifts % num_employees != 0 else min_holiday_shifts

# 添加节假日值班次数约束
for n in all_employees:
    holiday_worked = sum(shifts[(n, d, s)] for d in holiday_shifts for s in all_shifts)
    model.Add(min_holiday_shifts <= holiday_worked)
    model.Add(holiday_worked <= max_holiday_shifts)

若需更严格公平性，可在目标函数中添加节假日值班的惩罚项，避免同一员工多次被安排在节假日值班。

内容的提问来源于stack exchange，提问作者D.Wills