週期性任務的最佳公平負載均衡/多處理器調度

Question

我一直在考慮調度和負載平衡算法，我想出了一個我認爲很有趣的問題。

有N個網箱和M動物園管理員。每個籠子的大小爲S，動物的數量爲A.籠子必須清理的頻率被計算爲A/S的一些函數（更多動物會變髒的更小的籠子）。清理籠子的難度按照A和S的其他功能計算，其細節不重要（籠子的尺寸貢獻大部分難度，而動物的數量貢獻一點）。每三天清潔一次（「清潔日」）清潔任何籠子。動物園管理員完全相同並且可以互換。動物園管理員每個清潔日都需要做類似的工作，而且不必比其他任何動物園管理員做更多的工作。籠子用來清理的時間不是問題的一部分（假定時間大致反映了困難，並且動物園管理員總有足夠的時間完成他們分配的任務）。

調度算法必須告訴

• 每個籠子在其理想的頻率清潔或儘可能靠近各動物園管理員來清潔每個清潔天，其籠，例如，
• 分配的最小和大致同等數量的每清潔日 飼養員清洗的，
• ，並保證在所有飼養員 （如等於工作量可能即在一段時間內，每個動物園管理員的工作量的總和困難是接近相等的可能，和卡格es以大概1/M的概率分佈在動物園管理員中）。

我想知道這樣的優化問題的近似算法是什麼樣子。它與NP-hard調度/資源利用問題的幾個不同的經典例子相似;也許它可以歸結爲一個這樣的問題，我只是想念它。如果我們擺脫任務元素的頻率/週期性，它與經典的multiprocessor scheduling或有限的bin packing問題類似。

Answer 1

鑑於目標是平衡動物園管理員的努力，處理這些任務的標準或多或少的方式是在線貪婪。

在這種情況下，這簡直是對的：

保持至今每個飼養員已花費了，最初爲零努力的理貨。在每個清潔日，清理所需的清潔工作，並採用首選，最適合或隨機的方式分配工作，以便平衡工作量。即爲了最好的配合，他把最大的工作分配給了迄今爲止工作中最遠的守門員。重複，直到所有任務被分配。