如何在安排活動工作

Question

這是一個非常困難的動態規劃的問題，我想與大家分享，我們可以討論一點點朝其解決方案中獲得最低的成本：

你會把你的新應用雲服務器;你必須安排你的工作，以獲得最低的成本。您無需關心在同一臺服務器上同時運行的作業數量。每個工作k由一個發佈時間sk，一個截止時間fk和一個持續時間dk給出，其中dk≤fk - sk。這項工作需要安排在時間sk和fk之間連續幾分鐘的時間間隔內。服務器公司將每臺服務器每分鐘收費。您只需要一個虛擬服務器，並且可以省錢將作業從sk移動到fk，從而最大限度地縮短時間，而無需運行任何作業，換句話說，可以最大限度地減少運行一個或多個作業的時間。採用動態規劃解決問題。你的算法應該是n中的多項式，即作業的數量。

Answer 1

這是最小化繁忙時間的問題。

見定理17 this paper的：

羅希特Khandekar，巴魯克希伯，哈達Shachnai和塔米塔米爾。最大限度地減少多臺計算機的實時調度中的繁忙時間 。在軟件技術的基礎和理論計算機科學 （FSTTCS）第30屆年會論文集，169頁 - 180，2010

對於一個多項式時間算法的描述。

的關鍵是：

1. 爲了實現還有一些需要考慮（如果你有一個時間表，考慮推遲每個忙碌的間隔，直到你打一個最後期限的工作之一，只有某些有趣的時光正在處理）

2. 要考慮何時完成最長的工期。這將問題分解成兩部分;之前和之後，這可以以正常的動態編程方式獨立解決。