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

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 代码，因为它缺少一些括号。

最小化团队内每个用户的任务数的一种方法是最小化团队内每个用户的最大任务数。为此，我们只为每个团队包含一个 non-negative 变量 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()

因为你有一个最大化问题，我们需要在objective中减去eps的总和。

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

Minimise set size in task assignation problem

python

optimization

linear-programming

pulp