算法 - 最大限度地減少總的遲到

Question

我想實現一個精確的算法，儘量減少單機的總拖期。我在網上搜索瞭解如何使用動態編程實現它。我閱讀了Lawler的論文，他在77年提出了PSEUDOPOLYNOMIAL算法。但是，仍然無法將其映射到java或c＃代碼中。

請你幫我提供一些參考如何有效地實現這個確切的算法？

編輯1：@bcat：不是真的。我需要爲我們的軟件實施它。 :(還是我無法找到任何指導如何實現它。貪婪的一個很容易實現，但調度的結果並不令人印象深刻。

親切的問候，

Xiaon

Answer 1

也許石溪算法庫的Job Scheduling Section可以幫助你。

Answer 2

你可以有不同的變量的數值範圍和輸入的整體特性一起指定您的特定問題的確切特性。

如果沒有此設置，我假設您使用此定義：

您希望將具有n個獨立作業（每個作業都有其處理時間和到期日期）的單個機器調度問題的總時間最小化。

你想要做的是挑選一部分作業，使它們不重疊（單機可用），你也可以選擇你做的順序，保持截止日期。

我想要做的第一步是按截止日期進行排序，似乎沒有以某種不同的方式對它們進行排序的好處。

下一步剩下的是挑選子集。這是動態編程幫助的地方。我將嘗試描述狀態和遞歸關係。

國家：

[current time][current job] = maximum number of jobs done 

關係：

你要麼處理當前工作，並呼籲

f(current time + processing_time_of[current job],current job +1) 

，或者你跳過過程，並呼籲

f(current time,current job +1) 

最後你花最少的那些調用返回的2個的值，並將其存儲在狀態

[current time][current job] 

你在時間0和作業0開始遞歸。

順便說一句，貪婪似乎做得相當好，檢查了這一點：

http://www.springerlink.com/content/f780526553631475/

Answer 3

對於單機，處理時間最長的時間表（也稱爲減少時間的算法），如果你是最佳提前知道所有的工作，並且可以將他們從最長到最短（所以你需要做的就是排序）。

如前所述，您沒有指定有關您的日程安排問題的信息，因此除此之外很難提供幫助（因爲沒有普遍優化的和高效的調度程序存在）。