生成時間表 - 需要好的算法

昨天在試圖入睡時，我開始考慮如何解決下面的問題，並意識到我無法想出一個好的算法。即使它看起來像一個，這不是一個學校作業，我只想找到答案。 :)生成時間表 - 需要好的算法

基本上讓我們設想一個工作時間表，在一家商店的員工。該計劃應根據一系列要求生成計劃建議。

的要求是：

只有一個員工任何一週的工作。
員工無法連續工作兩週。
應該有防止僱員從得到安排某一週（假期）的工作方式。
分配應該儘可能平均，即如果我們有員工A，B和C，他們應該獲得大約相同的週數，並且這些周應該儘可能均勻地分配爲。

什麼是攻擊這個問題的最好方法是什麼？也許函數式編程更適合解決這個問題？

編輯：現在我知道這種類型的問題被稱爲「資源約束調度」。由於「調度」常常涉及計劃任務或線程等事情，所以對於這一點有點困難。對於誰仍然認爲我所要求的作業方案（儘管我明確地聲稱，否則以上）的人，你可以看看我以前的問題，我想他們清楚地表明我不是一個學生......

來源

2011-08-29 rickythefox

貪婪：使用一個PriorityQueue應該是一個很好的啓發式方法，但如果某個員工在最後一個預定的幾周內有一個長期「奉獻」，可能會失敗。 – amit

什麼是假期限制？ – naveen

嘗試將輸入參數和輸出值添加到問題中的算法，因爲這會使其更清晰 – Ankur

即使它好像這是家庭作業，我更願意相信你。

這裏是我想出來的：

let rec assignWork n upTo last workers = 
    if n <= upTo then 
     let checkNameIsEqualToLast = 
      match last with 
      | Some n -> ((=) n) 
      | _ -> fun _ -> false 
     let (name, _, _) as worker = 
      workers 
      |> List.filter (not << fun (name, _, v) -> checkNameIsEqualToLast name || List.exists ((=) n) v) 
      |> List.sortBy (fun (_, w, _) -> w) 
      |> List.head 
     workers 
     |> List.map (function 
      | n, w, v when n = name -> n, w + 1, v 
      | w -> w) 
     |> assignWork (n + 1) upTo (Some name) 
     |> fun t -> name::t 
    else []

例如：

let workers = 
    List.zip 
     [ 'A' .. 'E' ] 
     [ 
      [] 
      [ 2 .. 4 ] 
      [ 3 .. 5 ] 
      [ 1 .. 10000 ] 
      [ 3 ] 
     ] 
    |> List.map (fun (c, v) -> c, 0, v) 

assignWork 1 16 None workers

輸出（似乎是合理的我）：

val it : char list = 
    ['A'; 'C'; 'A'; 'E'; 'B'; 'C'; 'B'; 'E'; 'A'; 'B'; 'C'; 'E'; 'A'; 'B'; 'C'; 'E']

來源

2011-08-29 08:34:38

感謝您的代碼示例。至於這是作業，你可以檢查我的網站上的其他問題，看到我明顯失學了...... :) – rickythefox

你的結果會讓B連續工作兩次。根據這個問題，這是被禁止的，對嗎？ – primfaktor

我的不好，修好了。 –

第一兩點是對這個問題的限制。第三點指示排序候選解決方案的方法，如果將其正式化，則會出現優化問題。事實上，你正試圖最小化工作分配上的差異。

請注意，由於受到限制，問題可能沒有可接受的解決方案。

這是一個組合優化問題，您可以使用整數線性規劃方法或大致隨機隨機局部搜索方法（它們也稱爲元啓發式或許多其他名稱）來解決它，例如遺傳算法，模擬退火，禁忌搜索，迭代局部搜索，蟻羣優化等。

這個特定類的問題被稱爲作業調度和有很多關於它的文獻有許多變種。

如果這不是一項功課，我認爲這應該足以滿足你的好奇心，如果是這樣的話，我想我告訴過你可以看看。

來源

2011-08-29 08:17:06 Teudimundo

生成時間表 - 需要好的算法

回答

相關問題