基于Google OR-Tools CP-SAT的无硬约束班次均衡排班问题

核心思路 #

不依赖硬约束限制每周排班数，通过最大化员工参与的不同周数总和引导排班分散，同时兼顾班次分配均衡。核心是构建两层变量：基础排班变量（员工-班次-周），以及标记员工是否在某周工作的辅助变量，将辅助变量总和作为目标函数最大化。

具体实现步骤 #

1. 定义问题参数 #

from ortools.sat.python import cp_model

# 问题参数
NUM_WEEKS = 5
NUM_SHIFTS = 5
NUM_NURSES = 5

# 生成所有班次组合：(周数, 班次, 员工)
shifts = [(w, s, n) for w in range(NUM_WEEKS) for s in range(NUM_SHIFTS) for n in range(NUM_NURSES)]

2. 创建模型与变量 #

• 基础变量：x[w, s, n] 表示员工n在第w周第s班次是否工作（0/1）
• 辅助变量：y[w, n] 表示员工n在第w周是否有任何班次工作（0/1）

model = cp_model.CpModel()

# 基础排班变量
x = {}
for w, s, n in shifts:
    x[w, s, n] = model.NewBoolVar(f'x_w{w}_s{s}_n{n}')

# 辅助变量：标记员工n是否在第w周工作
y = {}
for w in range(NUM_WEEKS):
    for n in range(NUM_NURSES):
        y[w, n] = model.NewBoolVar(f'y_w{w}_n{n}')

3. 关联基础变量与辅助变量 #

通过逻辑约束，让辅助变量准确反映员工当周是否工作：

for w in range(NUM_WEEKS):
    for n in range(NUM_NURSES):
        # 员工n在第w周有至少一个班次工作 → y[w,n] = 1
        model.AddAtLeastOne(x[w, s, n] for s in range(NUM_SHIFTS)).OnlyEnforceIf(y[w, n])
        # y[w,n] = 0 → 员工n在第w周无任何班次
        model.Add(sum(x[w, s, n] for s in range(NUM_SHIFTS)) == 0).OnlyEnforceIf(y[w, n].Not())

4. 设置核心目标函数 #

最大化所有员工的工作周数总和：

model.Maximize(sum(y[w, n] for w in range(NUM_WEEKS) for n in range(NUM_NURSES)))

5. 可选：添加班次均衡的次要目标 #

如果需要进一步均衡员工总班次数量，可在核心目标外添加次要优化项，不使用硬约束：

# 计算每个员工的总班次
total_shifts_per_nurse = [sum(x[w, s, n] for w in range(NUM_WEEKS) for s in range(NUM_SHIFTS)) for n in range(NUM_NURSES)]

# 定义班次数量的最大/最小值
max_shifts = model.NewIntVar(0, NUM_WEEKS*NUM_SHIFTS, 'max_shifts')
min_shifts = model.NewIntVar(0, NUM_WEEKS*NUM_SHIFTS, 'min_shifts')

model.AddMaxEquality(max_shifts, total_shifts_per_nurse)
model.AddMinEquality(min_shifts, total_shifts_per_nurse)

# 优先最大化工作周数，其次最小化班次数量差（权重100保证核心目标优先级）
model.Maximize(sum(y[w, n] for w,n in y) * 100 - (max_shifts - min_shifts))

6. 求解并输出结果 #

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

if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    print('排班结果：')
    for w in range(NUM_WEEKS):
        print(f'第 {w+1} 周：')
        for s in range(NUM_SHIFTS):
            assigned_nurse = None
            for n in range(NUM_NURSES):
                if solver.Value(x[w, s, n]) == 1:
                    assigned_nurse = n
                    break
            print(f'  班次 {s+1}: 员工 {assigned_nurse+1}')
    
    # 输出每个员工的工作周数统计
    print('\n员工工作周数统计：')
    for n in range(NUM_NURSES):
        weeks_worked = sum(solver.Value(y[w, n]) for w in range(NUM_WEEKS))
        print(f'员工 {n+1}: {weeks_worked} 周')
else:
    print('未找到可行解')

关键说明 #

• 辅助变量y[w,n]的设计是核心，它准确捕捉员工当周工作状态，避免直接统计班次带来的逻辑误差。
• 最大化y的总和会自动引导算法让员工参与更多不同周次，从根源上减少集中排班的情况。
• 班次均衡通过次要目标实现，不依赖硬约束，保留了排班的灵活性。

内容的提问来源于stack exchange，提问作者Rolando Martino