最小化任务分配问题中的集合大小

Question

我必须创建一个根据某些规则向用户分配任务的解决方案，并且我想尝试线性编程。

我有一个需要某种技能并属于特定团队的任务列表，并且我有一个可用用户列表、他们当天分配的团队以及他们的技能集：

# Creating dummies
task = pd.DataFrame({
    'id': [n for n in range(25)],
    'skill': [random.randint(0,3) for _ in range(25)]
})
task['team'] = task.apply(lambda row: 'A' for row.skill in (1, 2) else 'B', axis=1)

user_list = pd.DataFrame({
    'user': [''.join(random.sample(string.ascii_lowercase, 4)) for _ in range(10)],
    'team': [random.choice(['A', 'B']) for _ in range(10)]
})

user_skill = {user_list['user'][k]: random.sample(range(5), 3) for k in range(len(user_list))}

我必须实施的约束如下：

• 所有必须分配任务
• 任务只能分配给一个用户
• 用户不能执行他或她不熟练的任务 用户
• 不能为他或她以外的其他团队执行任务
• 每个用户应承担的任务量在团队中尽可能低调

我写这篇文章花了很大力气在 PuLP 中，但感谢 这篇文章 我设法得到了一些结果。

# Create the problem
task_assignment = pulp.LpProblem('task_assignment', pulp.LpMaximize)

# Create model vars
pair = pulp.LpVariable.dicts("Pair", (user_list.user, task.id), cat=pulp.LpBinary)
task_covered = pulp.LpVariable.dicts('Covered', task.id, cat=pulp.LpBinary)

# Set objective
task_assignment += pulp.lpSum(task_covered[t] for t in task.id) + \
        0.05 * pulp.lpSum(pair[u][t] for u in user_list.user for t in task.id)

# Constraint

# A task can only be done by one user
for t in task.id:
    task_assignment+= pulp.lpSum([pair[u][t] for u in user_list.user]) <= 1

# A user must be skilled for the task
for u in user_list.user:
    for t in task.id:
        if not task[task.id == t].skill.values[0] in user_skill[u]:
            task_assignment += pair[u][t] == 0

# A user can not do a task for another team
for u in user_list.user:
    for t in task.id:
        if not (task[task.id == t].team.values[0] == user_list[user_list.user == u].team.values[0]):
            task_assignment+= pair[u][t] == 0

task_assignment.solve()

我的问题是我完全不知道如何实现最后一个约束（即团队内每个用户的任务量应尽可能低）

有人知道如何做到这一点吗？

Answer 1

首先，您的虚拟数据集不是有效的Python代码，因为它错过了一些括号。

最大程度地减少团队内部用户任务数量的一种方法是最大程度地减少团队内部用户的最大任务数量。为此，我们只为每个团队提供一个非负变量eps，并添加以下约束：

teams = user_list.team.unique()

# Create the problem
task_assignment = pulp.LpProblem('task_assignment', pulp.LpMaximize)

# Create model vars
pair = pulp.LpVariable.dicts("Pair", (user_list.user, task.id), cat=pulp.LpBinary)
task_covered = pulp.LpVariable.dicts('Covered', task.id, cat=pulp.LpBinary)
eps = pulp.LpVariable.dicts("eps", teams, cat=pulp.LpContinuous, lowBound=0.0)

# Set objective
task_assignment += pulp.lpSum(task_covered[t] for t in task.id) + \
    0.05 * pulp.lpSum(pair[u][t] for u in user_list.user for t in task.id) - \
        0.01 * pulp.lpSum(eps[team] for team in teams)

# Constraint
# ... your other constraints here ...

# the amount of tasks per user should be as low as possible inside a time
for team in teams:
    # for all users in the current team
    for u in user_list[user_list["team"] == team].user:
        task_assignment += pulp.lpSum(pair[u][t] for t in task.id) <= eps[team]
    

task_assignment.solve()

由于您有最大化问题，我们需要减去eps 在目标中。