PulP员工预约分配优化结果不符预期的问题排查

需求说明 #

开发Python程序实现员工-预约分配，核心规则：

• 尽可能减少参与任务的员工数量
• 仅当同一时段预约数量超过1个时，才增派后续员工处理该时段
• 优先让指定员工（如员工1）承接所有可分配的预约，剩余时段/超额预约再依次分配给员工2、3等

现有代码问题 #

当前基于PuLP的实现未达成预期，核心问题出在目标函数与约束设计：

原代码片段 #

prob = LpProblem("equally_employee_allocation",LpMinimize)

# 获取非休假员工信息
employee_dict = get_employees(date)
employee_count = len(employee_dict)

# 获取各时段需处理的预约数
slot_appo_dict = get_slot_appo_dict(date)

# 二进制变量：员工是否承接该时段的预约
empl_appo_bin = LpVariable.dicts("employ_appoi_bin", (slot_appo_dict, employee_dict),cat=LpBinary)

# 整数变量：员工承接的总预约数
empl_appo_count= LpVariable.dicts("employ_appoi_count", employee_dict, cat=LpInteger, lowBound= 0)

##### 目标函数 #####
prob+=lpSum(empl_appo_count[emp] for emp in employee_dict)

##### 约束条件 #####

# 每个时段分配的员工数等于该时段的预约数
for slot in slot_appo_dict:
    prob += lpSum(empl_appo_bin[slot][e] for e in employee_dict) == slot_appo_dict[slot]

for empl in employee_dict:
    # 员工总承接数等于各时段承接数之和
    prob += empl_appo_count[empl] == lpSum(empl_appo_bin[slot][empl] for slot in slot_appo_dict)

    # 弹性约束：试图惩罚偏离平均预约数的情况
    flex_constraint1 = LpConstraint(e=empl_appo_count[empl], name=f"equal_allocation{empl}", sense=LpConstraintEQ, rhs= 1)
    prob.extend(flex_constraint1.makeElasticSubProblem(penalty=1, proportionFreeBound=0))

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

核心错误分析 #

1. 目标函数无效：原目标是最小化所有员工的预约数总和，但该总和等于总预约数（固定值），求解器无法通过此目标进行有效优化，导致分配结果随机。
2. 约束方向完全偏离需求：弹性约束试图让员工的预约数接近固定值（如1），本质是追求平均分配，与“优先让少数员工多承接”的需求完全相反。
3. 未定义参与员工数量变量：无法直接约束或最小化实际参与任务的员工人数。

修正后的建模方案 #

核心调整思路 #

• 新增二进制变量标记员工是否参与任务，将最小化参与员工数作为第一优化目标
• 通过加权目标函数，在满足最小参与人数的前提下，优先让高优先级员工承接更多预约
• 新增优先级约束，确保同一时段的预约优先分配给高优先级员工

修正后代码 #

from pulp import LpProblem, LpMinimize, LpVariable, lpSum, LpBinary, LpInteger

prob = LpProblem("min_employee_allocation", LpMinimize)

# 获取员工与时段预约数据
employee_dict = get_employees(date)
# 按优先级排序员工（示例：员工ID越小优先级越高）
sorted_employees = sorted(employee_dict.keys())
slot_appo_dict = get_slot_appo_dict(date)
total_appointments = sum(slot_appo_dict.values())

# 二进制变量：员工是否参与任务（1=参与，0=未参与）
empl_used = LpVariable.dicts("empl_used", employee_dict, cat=LpBinary)

# 二进制变量：员工是否在该时段承接预约
empl_appo_bin = LpVariable.dicts("employ_appoi_bin", (slot_appo_dict, employee_dict), cat=LpBinary)

# 员工承接的总预约数
empl_appo_count = LpVariable.dicts("employ_appoi_count", employee_dict, cat=LpInteger, lowBound=0)

##### 目标函数 #####
# 加权双目标：优先最小化参与员工数（权重1000远大于总预约数，确保优先级），其次让高优先级员工多承接
priority_weights = {emp: idx+1 for idx, emp in enumerate(sorted_employees)}  # 优先级越高，权重越小
prob += 1000 * lpSum(empl_used[emp] for emp in employee_dict) + lpSum(priority_weights[emp] * empl_appo_count[emp] for emp in employee_dict)

##### 约束条件 #####
# 1. 每个时段的预约数 = 该时段分配的员工数
for slot in slot_appo_dict:
    prob += lpSum(empl_appo_bin[slot][e] for e in employee_dict) == slot_appo_dict[slot]

# 2. 员工总承接数 = 各时段承接数之和
for emp in employee_dict:
    prob += empl_appo_count[emp] == lpSum(empl_appo_bin[slot][emp] for slot in slot_appo_dict)

# 3. 未参与的员工不能承接任何预约
for emp in employee_dict:
    prob += empl_appo_count[emp] <= total_appointments * empl_used[emp]

# 4. 优先级约束：同一时段优先分配给高优先级员工
for slot in slot_appo_dict:
    for idx in range(1, len(sorted_employees)):
        prev_emp = sorted_employees[idx-1]
        curr_emp = sorted_employees[idx]
        # 当前员工仅能承接前序员工未覆盖的剩余预约
        prob += empl_appo_bin[slot][curr_emp] <= slot_appo_dict[slot] - lpSum(empl_appo_bin[slot][sorted_employees[j]] for j in range(idx))

# 求解并输出结果
prob.writeLP("data/min_employee_allocation.lp")
prob.solve()

for emp in employee_dict:
    print(f"员工{emp}承接预约数: {empl_appo_count[emp].value()}")
print(f"参与员工总数: {sum(empl_used[emp].value() for emp in employee_dict)}")

方案验证 #

针对4员工、12个分散时段预约（每个时段1个预约）的场景：

• 所有预约将全部分配给优先级最高的员工1
• 参与员工数为1，完全符合预期
• 若某时段有2个预约，则该时段分配给员工1和员工2，其余时段仍由员工1承接，参与员工数为2，满足规则

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