sql - 公平分配分配算法

Question

我正在尝试提出一个高效的 sql 来解决公平分配问题。

我的数据模型由一个可以有 1+ 个“案例”的“客户”组成。每个客户都需要一名“案件处理员”，负责照顾该客户。

我正在尝试将“客户”分配给所有“案件处理人员”，以使所有“案件处理人员”彼此之间的“案件”数量尽可能接近。

我有一个查询，它为我提供了“客户 ID”和“案例计数”

我有一个案例处理程序表，目前我总共有 4 个案例处理程序(可以添加或删除案例处理程序，然后必须重新运行此分发)。

我知道我需要对案例处理程序表和上面的查询进行连接，这样我就可以为每个客户执行更新，为他们分配一个案例处理程序。但我不知道如何做到这一点，以平衡最公平的庄园。

我有一个几乎可行的方法是，我根据案例处理程序的计数使用查询行号的模数加入，因此查询中按案例计数顺序排序的每一行都可以用于分配客户轮询到案件处理程序。但这并没有提供公平的分配。

(实际上，我的实时系统中的客户表超过 100,000，其中大多数只有一个案例，更少有 2 个，甚至更少有 3 个等等，最多有一个客户有 51 个案例)

感谢任何人可以给我的任何帮助/建议。

Answer 1

有正式的优化框架可以解决这类问题，但我认为您可以通过更简单的方法解决问题。根据您的描述，听起来每个客户只能有一个案件处理员，所以有些不幸的人需要处理您最大客户的所有 51 个案件。

尝试这样的事情(伪代码):

total_cases = SUM(Case_Count)
total_handlers = COUNT(Case_Handlers)

foreach SELECT Customer_Id, Case_Count ORDER BY Case_Count DESCENDING:

   # Calculate the target number of cases to assign to the next handler
   target_cases_per_handler = total_cases / total_handlers

   # If a customer has more than the target number of cases, then
   # it must be assigned to a case handler
   if Case_Count > target_cases_per_handler:
       assign_to_handler(Customer_Id)
       total_handlers = total_handlers - 1
       total_cases = total_cases - Case_Count

   # Otherwise, try to pair up the cases with a small number of cases
   # that is close to average (this part is inefficient)
   else:
       assign_to_handler(Customer_Id)
       residual = CEIL(target_cases_per_handler - Case_Count)
       while (residual > 0)
           best_customer_id, best_case_count = SELECT TOP 1 Customer_Id, Case_Count ORDER BY ABS(Case_Count - residual) ASCENDING

           assign_to_handler(best_customer)
           residual = residual - best_case_count
           total_cases = total_cases - best_case_count

       total_handlers = total_handlers - 1

这应该可以让您粗略地将客户分配给案例处理程序，同时仍然确保每个客户都有一个处理程序。