公平分配分配算法

Question

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

我的数据模型由一个'customer‘组成，它可以有1+ 'cases’。每个客户都需要一个被指派来照顾该客户的“案例处理员”。

我试图在所有的“案例处理程序”中分配“客户”，以使所有的“案例处理程序”彼此之间的“案例”数量尽可能接近。

我有一个查询，它给我一个‘客户Id’和‘案例计数’

​

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

我知道我需要在case handler表和上面的查询上做一个连接，这样我就可以为每个客户执行更新，为他们分配一个case处理程序。但我不知道如何在最公平的庄园中平衡这两种情况。

我有一个几乎有效的方法，那就是我通过案例处理程序的计数对查询的行数使用模数连接，这样查询中按案例计数顺序排序的每一行都可以用来在循环中将一个客户分配给一个案例处理程序。但这并没有给出一个公平的分配。

(实际上，我的实时系统中的客户表超过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

这应该会让您大致地将客户分配给案例处理程序，同时仍然确保每个客户端都有一个单独的处理程序。

Answer 2

你们的案例分布不算太差。我建议使用以下方法：

(1)将客户分为两组。。。多个案例和单个案例。

(2)将多个案例以循环方式分配给案例工作者。

(3)将单个案例分配给个案工作者，以平衡每个个案工作者。

这将适用于您的特定发行版(主要是单例)。它不一定是通用算法。

下面是SQL语句：

with multiples as (
      select CustomerId, COUNT(*) CaseCnt,
             ROW_NUMBER() over (partition by CustomerId order by CustomerId) % @NumHandlers as theHandler
      from customers c
      group by CustomerId
      having COUNT(*) > 1
     ),
    h as (
     select theHandler, SUM(CaseCnt) as CaseCnt,
            SUM(CaseCnt) - (NumCusts / @NumHandlers) as StillNeeded
     from multiples cross join
          (select COUNT(*) as NumCusts from customers c) const
     group by theHandler
    ),
    hsum as (
     select h.*, SUM(StillNeeded) over (order by StillNeeded) as endnum,
            SUM(StillNeeded) over (order by StillNeeded) - StillNeeded + 1 as startnum
     from h
    ),
    singles as (
     select CustomerId, ROW_NUMBER() over (partition by CustomerId order by CustomerId) as seqnum
     from Customers
     group by CustomerId
     having COUNT(*) = 1
    ),
    singlesh as (
     select singles.Customerid, h.theHandler
     from singles join
          hsum
          on singles.seqnum between h.startnum and h.endnum
   )
select *
from ((select CustomerId, theHandler
       from multiples
      ) union all
      (select CustomerId, theHandler
       from singlesh
      )
     ) t

SQL基本上遵循了上面的解释。它首先以循环方式将多个记录随机分配给处理程序。处理程序只是从0到@NumHandler的数字。然后，它计算"StillNeeded“案例的数量，以获得最大值。注意:这里假设处理程序的数量是客户数量的精确倍数。要修复的调整使查询看起来更复杂。

然后，它计算仍然需要为每个处理程序填充的数字。关键是获取累积和(这使用SQL Server 2012语法，在早期版本中使用相关子查询)。然后使用此信息将单例分配给每个处理程序。

最后一步是将两组客户( multiples和singletons ) union在一起。