在员工列表中平均分配任务列表

Question

我想在活跃员工列表中平均分配 alerts/notifications 列表，以尝试确保每个人都有相似数量的职责。我目前收到一份要分配的警报列表和活跃用户以及每个人当前分配的活动数。截至目前，我只设法按照与 for 循环迭代相同的顺序实现分配，但我想不出一种方法来均匀地做到这一点。

例如：

e1 有 1 个警报
e2 有 1 个警报
e3 有 3 个警报

我想将任务分配给 e1 和 e2，直到它们达到 3，然后循环可以正常继续，直到用完警报。

Employee 是一个包含 {"id": "oid", "alerts": int} 的字典 unassignedAlerts 只是 ObjectIds

的列表

代码：

for alert in unassignedAlerts:
                for employee in activeEmployees:
                    if employee ["alerts"] > maxAlerts:
                        maxAlerts = employee["alerts"]
                    elif employee ["_id"] in activeUsers:
                        operations.append(
                            UpdateOne({"_id": alert}, {"$set": {"employeeResponsible": employee["_id"], "status": "assigned"}})
                        )
                        employee["alerts"] += 1

欢迎任何想法。

Answer 1

这是一个经典的负载均衡问题。暴力破解的方法就是反复查找当前告警次数最少的员工：

for alert in unassigned_alerts:
    assigned_employee = min(active_employees, key=lambda e: e["alerts"])
    assigned_employee["alerts"] += 1
    ...

这会在 O(m*n) 时间内运行，其中 m 是未分配警报的数量，n 是活跃员工的数量。

您可以将此改进为 O(m*log(n))，方法是使用最小堆数据结构来查找最佳员工。 Python 在 heapq module 中提供了一个内置的最小堆实现。要使用它，您可以将员工存储为成对列表（长度为 2 的元组），其中第一个元素是警报数，第二个元素是包含其他信息的字典：

import heapq


active_employees = [
    (3, {"name": "John", "id": 1}),
    (5, {"name": "Jane", "id": 2})
]
heapq.heapify(active_employees)

for alert in unassigned_alerts:
    num_alerts, assigned_employee = heapq.heappop(active_employees)
    heapq.heappush(active_employees, (num_alerts+1, assigned_employee))
    ...

最后，我要提一下，您不需要总是分配给负载最小的员工。您可以通过简单地随机挑选两名员工然后分配给工作较少的员工来实现非常好的平衡（概率很高）。有关更多详细信息，请参阅这个优秀的 blog post。

在员工列表中平均分配任务列表

Distribute list of tasks evenly among list of employees

python

arrays

mongodb

loops

load-balancing