排班调度：如何确保员工工作时段的连续性

问题明确 #

员工每日有8个可选工作时段，需选择连续4小时工作（总时长固定为4小时，且必须连续），用二元决策变量dv[i]表示是否在第i小时工作（1=工作，0=休息）。示例解：

hrs : 0 1 2 3 4 5 6 7  [8小时时段]
dv  : 0 1 1 1 1 0 0 0  [连续工作1-4小时]

开源求解器实现思路 #

1. 核心约束建模 #

用整数规划（IP）或混合整数规划（MIP）建模，核心约束分为两类：

• 总工作时长约束：sum(dv[i] for 所有i) = 4
• 连续性约束：避免间断工作，推荐两种实现方式：
  • 方式一：引入辅助变量start[i]（表示是否在第i小时开始工作），添加约束：
    • sum(start[i] for 所有i) = 1（仅一个起始点）
    • 对每个有效起始点i（i+3不超过最后一个时段），强制dv[i] = dv[i+1] = dv[i+2] = dv[i+3] = 1
    • 对无法作为起始点的时段（最后3个小时），强制start[i] = 0
  • 方式二：直接添加逻辑约束：若dv[i]=1且dv[k]=1（i<j<k），则dv[j]=1——但这种方式约束数量多，仅适合小时数少的场景

2. 开源求解器选型与代码示例 #

• PuLP（Python）：快速建模首选，示例代码：

  from pulp import LpProblem, LpVariable, lpSum, LpBinary
  
  # 定义8个时段
  hours = list(range(8))
  # 创建问题（目标仅需可行解，设为最小化任意值即可）
  prob = LpProblem("ShiftScheduling", LpMinimize)
  # 决策变量：每个时段是否工作
  dv = [LpVariable(f"dv_{h}", cat=LpBinary) for h in hours]
  # 总时长约束：必须工作4小时
  prob += lpSum(dv) == 4
  # 引入起始点变量
  start = [LpVariable(f"start_{h}", cat=LpBinary) for h in hours]
  prob += lpSum(start) == 1  # 仅一个起始点
  # 约束起始点覆盖连续4小时
  for h in hours:
      if h + 3 < len(hours):
          prob += dv[h] >= start[h]
          prob += dv[h+1] >= start[h]
          prob += dv[h+2] >= start[h]
          prob += dv[h+3] >= start[h]
      else:
          # 最后3个时段无法作为起始点，强制start为0
          prob += start[h] == 0
  # 求解
  prob.solve()
  # 输出结果
  print("hrs:", hours)
  print("dv :", [int(v.varValue) for v in dv])
  

• OR-Tools（Google）：性能更优，适合大规模排班场景，核心建模逻辑与PuLP一致，通过MIP模块添加约束求解
• Cbc（Coin-or Branch and Cut）：底层高效求解器，可通过PuLP、Pyomo等上层框架调用

3. 非规划类简化解法 #

若仅需生成可行解（无需优化目标），可直接枚举所有连续4小时组合：

hours = list(range(8))
# 筛选所有合法起始点
possible_starts = [h for h in hours if h + 3 < len(hours)]
# 随机选一个起始点生成解
import random
start_idx = random.choice(possible_starts)
dv = [0]*8
for h in range(start_idx, start_idx+4):
    dv[h] = 1
print("hrs:", hours)
print("dv :", dv)

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