Python PulP时段分配优化模型：跨时段预约员工分配约束问题

核心问题拆解 #

• 硬约束：同一跨时段预约的所有时段必须分配给同一名员工
• 软约束：员工任务量尽量均匀分配（允许小范围偏差）
• 可选优化：避免连续的不同预约分配给同一名员工
• 技术障碍：Pulp弹性约束默认不支持右侧为变量，需手动构建偏差惩罚

关键调整步骤 #

1. 重构数据结构：明确预约与时段的关联 #

原slot_appo_dict仅记录时段任务数，无法区分同一预约的连续时段，需新增预约字典，直接绑定预约ID与覆盖时段：

# 示例：预约ID: 覆盖的时段列表
appointment_slots = {
    "A": [3,4],  # 预约A覆盖时段3、4（对应6:10-6:20）
    "B": [5,6],  # 预约B覆盖时段5、6（对应6:20-6:30）
    "C": [5,6]   # 预约C覆盖时段5、6（第二个并行预约）
}
# 从预约字典反向生成时段任务数（替代原slot_appo_dict）
slot_appo_dict = {slot:0 for slot in range(1,7)}
for appo in appointment_slots.values():
    for slot in appo:
        slot_appo_dict[slot] +=1

2. 修改变量定义：以预约为单位分配员工 #

原变量empl_appo_bin是（时段，员工）二元变量，改为**（预约，员工）二元变量**，确保同一预约的所有时段绑定同一员工：

# 二元变量：empl_appo_bin[appo][e] = 1 表示员工e分配到预约appo
empl_appo_bin = LpVariable.dicts("employ_appoi_bin", (appointment_slots.keys(), employee_dict), cat=LpBinary)

3. 添加硬约束：跨时段预约绑定同一员工 #

• 每个预约必须恰好分配给1名员工：

  for appo in appointment_slots.keys():
      prob += lpSum(empl_appo_bin[appo][e] for e in employee_dict) == 1
  

• 时段任务数约束：每个时段的分配员工数等于该时段的预约数（由预约映射而来）：

  for slot in slot_appo_dict:
      # 收集所有覆盖该时段的预约
      relevant_appos = [appo for appo, slots in appointment_slots.items() if slot in slots]
      prob += lpSum(empl_appo_bin[appo][e] for appo in relevant_appos for e in employee_dict) == slot_appo_dict[slot]
  

4. 修复弹性约束：手动构建偏差惩罚（支持变量右侧） #

PulP的makeElasticSubProblem仅支持右侧为常数，若需动态计算基准值，需手动引入偏差变量：

# 员工总任务数：分配的所有预约覆盖的时段总数
empl_appo_count = LpVariable.dicts("employ_appoi_count", employee_dict, cat=LpInteger, lowBound=0)
for e in employee_dict:
    prob += empl_appo_count[e] == lpSum(
        len(appointment_slots[appo]) * empl_appo_bin[appo][e] 
        for appo in appointment_slots.keys()
    )

# 手动构建均匀分配软约束
dev_pos = LpVariable.dicts("dev_pos", employee_dict, cat=LpInteger, lowBound=0)  # 超过平均值的偏差
dev_neg = LpVariable.dicts("dev_neg", employee_dict, cat=LpInteger, lowBound=0)  # 低于平均值的偏差
avg_appointments = appointment_sum / employee_count

for e in employee_dict:
    prob += empl_appo_count[e] - avg_appointments == dev_pos[e] - dev_neg[e]

# 更新目标函数：优先最小化总任务数，其次惩罚偏差
prob += lpSum(empl_appo_count[e] for e in employee_dict) + 0.1 * lpSum(dev_pos[e] + dev_neg[e] for e in employee_dict)

5. 可选优化：避免连续不同预约分配给同一名员工 #

添加软约束惩罚连续时段被同一名员工分配不同预约的情况：

# 定义连续时段对
consecutive_slots = [(slot, slot+1) for slot in range(1, max(slot_appo_dict.keys()))]

# 二元变量：标记员工在连续时段分配不同预约的冲突
conflict = LpVariable.dicts("conflict", (employee_dict, consecutive_slots), cat=LpBinary)

for e in employee_dict:
    for (s1, s2) in consecutive_slots:
        appos_s1 = [appo for appo, slots in appointment_slots.items() if s1 in slots]
        appos_s2 = [appo for appo, slots in appointment_slots.items() if s2 in slots]
        # 若员工在s1和s2分配了不同预约，触发冲突标记
        prob += lpSum(empl_appo_bin[appo1][e] for appo1 in appos_s1) + lpSum(empl_appo_bin[appo2][e] for appo2 in appos_s2) - 2 * lpSum(empl_appo_bin[appo][e] for appo in appos_s1 if appo in appos_s2) <= 1 + conflict[e][(s1,s2)]

# 目标函数添加冲突惩罚（权重可调整）
prob += lpSum(empl_appo_count[e] for e in employee_dict) + 0.1 * lpSum(dev_pos[e] + dev_neg[e] for e in employee_dict) + 0.5 * lpSum(conflict[e][pair] for e in employee_dict for pair in consecutive_slots)

完整修改代码 #

def problem_modulation(date):
    prob = LpProblem("equally_employee_allocation", LpMinimize)

    # 员工字典
    employee_dict = {1:"Steve", 2:"Marcus", 3:"Rodger", 4:"Sara"}
    employee_count = len(employee_dict)

    # 预约字典：键=预约ID，值=覆盖的时段列表
    appointment_slots = {
        "A": [3,4],  # 6:10-6:20的预约
        "B": [5,6],  # 6:20-6:30的预约1
        "C": [5,6]   # 6:20-6:30的预约2
    }

    # 生成时段任务数字典（从预约反向推导）
    slot_appo_dict = {slot:0 for slot in range(1,7)}
    for appo_slots in appointment_slots.values():
        for slot in appo_slots:
            slot_appo_dict[slot] += 1

    # 总任务数（所有时段任务数之和）
    appointment_sum = sum(slot_appo_dict.values())
    avg_appointments = appointment_sum / employee_count

    # 二元变量：empl_appo_bin[appo][e] = 1 表示员工e分配到预约appo
    empl_appo_bin = LpVariable.dicts("employ_appoi_bin", (appointment_slots.keys(), employee_dict), cat=LpBinary)

    # 员工总任务数变量
    empl_appo_count = LpVariable.dicts("employ_appoi_count", employee_dict, cat=LpInteger, lowBound=0)

    # 偏差变量：用于均匀分配软约束
    dev_pos = LpVariable.dicts("dev_pos", employee_dict, cat=LpInteger, lowBound=0)
    dev_neg = LpVariable.dicts("dev_neg", employee_dict, cat=LpInteger, lowBound=0)

    # 目标函数：总任务数 + 偏差惩罚 + 冲突惩罚
    prob += lpSum(empl_appo_count[e] for e in employee_dict) + \
            0.1 * lpSum(dev_pos[e] + dev_neg[e] for e in employee_dict) + \
            0.5 * lpSum(LpVariable.dicts("conflict", (employee_dict, [(s,s+1) for s in range(1,6)]), cat=LpBinary)[e][pair] for e in employee_dict for pair in [(s,s+1) for s in range(1,6)])

    # 硬约束1：每个预约必须分配给1名员工
    for appo in appointment_slots.keys():
        prob += lpSum(empl_appo_bin[appo][e] for e in employee_dict) == 1

    # 硬约束2：每个时段的分配员工数等于该时段的任务数
    for slot in slot_appo_dict:
        relevant_appos = [appo for appo, slots in appointment_slots.items() if slot in slots]
        prob += lpSum(empl_appo_bin[appo][e] for appo in relevant_appos for e in employee_dict) == slot_appo_dict[slot]

    # 硬约束3：计算员工总任务数
    for e in employee_dict:
        prob += empl_appo_count[e] == lpSum(
            len(appointment_slots[appo]) * empl_appo_bin[appo][e] 
            for appo in appointment_slots.keys()
        )

    # 软约束：均匀分配（手动构建偏差）
    for e in employee_dict:
        prob += empl_appo_count[e] - avg_appointments == dev_pos[e] - dev_neg[e]

    # 可选：添加连续不同预约的冲突惩罚约束
    consecutive_slots = [(s, s+1) for s in range(1, max(slot_appo_dict.keys()))]
    conflict = LpVariable.dicts("conflict", (employee_dict, consecutive_slots), cat=LpBinary)

    for e in employee_dict:
        for (s1, s2) in consecutive_slots:
            appos_s1 = [appo for appo, slots in appointment_slots.items() if s1 in slots]
            appos_s2 = [appo for appo, slots in appointment_slots.items() if s2 in slots]
            # 若员工在s1和s2分配了不同预约，标记冲突
            prob += lpSum(empl_appo_bin[appo1][e] for appo1 in appos_s1) + lpSum(empl_appo_bin[appo2][e] for appo2 in appos_s2) - 2 * lpSum(empl_appo_bin[appo][e] for appo in appos_s1 if appo in appos_s2) <= 1 + conflict[e][(s1,s2)]

    prob.writeLP("data/equally_allocation.lp")
    prob.solve()

    # 输出结果
    for e in employee_dict:
        print(f"员工{employee_dict[e]}的总任务数：{empl_appo_count[e].value()}")
        assigned_appos = [appo for appo in appointment_slots.keys() if empl_appo_bin[appo][e].value() == 1]
        print(f"分配的预约：{assigned_appos}")

关键说明 #

• 数据结构重构是解决跨时段预约绑定的核心，必须明确每个预约覆盖的时段
• 以预约为单位分配员工，避免了对每个时段重复约束，提升模型效率
• 手动构建偏差变量替代Pulp的弹性约束，支持动态基准值（若需）
• 连续不同预约的约束为软约束，可通过调整惩罚权重平衡排班效率与员工休息需求

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