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

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的和。