公平分配分配算法

我試圖想出一個高效的SQL來解決公平分配問題。公平分配分配算法

我的數據模型包含一個'客戶'，可以有1個'案例'。每個客戶都需要一個'事件處理程序'來分配該客戶。

我試圖以所有'case handlers'儘可能接近相等數量的'cases'的方式來分配所有'case handlers'中的'customers'。

我有一個查詢，給了我一個「客戶ID」和「案例計數」

Example http://i39.tinypic.com/2zswxdw.jpg

我有辦案人員，其中我已經目前有4個總表（辦案可以添加或刪除，然後這個分配將不得不重新運行）。

我知道我需要做對辦案人員表和查詢中使用聯接的上方，然後我就可以執行更新爲每個客戶分配他們辦案。但我不知道如何做到這一點，以平衡最公平的莊園案件。

我有一個幾乎可以工作的方法是，我在查詢的行號上使用了查詢的行數，並通過事件處理程序的計數進行連接，因此查詢中按順序排列的查詢中的每一行都可以用來指定客戶通過循環法進行案件處理。但這並不能公平分配。

（實際上在我的生命系統中的客戶表是超過10萬，大多數人都只有一個的情況下以較少的有2則甚至更少有3等長達一個客戶誰擁有51例）

謝謝任何人可以給我的任何幫助/建議。

來源

2013-05-20 Mark Kennedy

我想你想要的是NTILE。你可以谷歌它，或看看這裏http://stackoverflow.com/questions/14355324/want-to-learn-more-on-ntile – Randy

有可以解決這類問題的正式優化框架，但我想你也許可以用更簡單的東西度日。從您的描述來看，聽起來每個客戶只能有一個案例處理程序，所以有一些不幸的人需要處理您最大客戶的所有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

這應該給你的客戶的粗略分配給辦案人員同時還確保每個客戶都有一個處理程序。

來源

2013-05-20 13:32:32 Lucas

您的案件分佈並不算太差。我建議以下方法：

（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到@NumHandlers的數字。然後計算「StillNeeded」情況的數量以達到最大值。注意：這假定處理程序的數量是客戶數量的確切倍數。修正這個問題使查詢看起來更加複雜。

然後它會計算每個處理程序仍需填寫的數量。關鍵是將其作爲累積和（這使用SQL Server 2012語法，在早期版本中，您使用相關子查詢執行此操作）。這個信息然後被用來將單例分配給每個處理程序。

最後一步是union這兩組客戶在一起，倍數和單身。

來源

2013-05-20 13:45:44

公平分配分配算法

回答

相關問題