什麼算法的調度程序

我有這個調度任務的問題。每個任務都有一個建議的開始時間T（它需要從[T-10，T + 10]開始），需要L分鐘才能完成並使用多個資源[R1，R2，...]。在使用資源時，其他任務都不能使用它。考慮到只有開始時間是靈活的，我的目標是安排任務，以便他們可以訪問任何他們需要的資源或指出需要解決的所有衝突。什麼算法的調度程序

我可以爲此使用哪種算法？謝謝。

來源

2010-11-01 Martin08

你看過哪些算法，你認爲他們不適用的原因？ – Welbog 2010-11-01 21:14:20

這是功課嗎？如果是這樣，它應該有「作業」標籤。 – 2010-11-01 21:15:34

這不是一項功課。我並沒有要求詳細的解決方案。我只需要一些算法的建議，以便我可以研究。 – Martin08 2010-11-01 21:43:55

既然你已經標記以此爲prolog，我建議在constraint logic programming（CLP）執行，並使用內置到您的CLP實現的算法。部分示例：

:- use_module(library(clpfd)). 

on_time([]). 
on_time([Task|Tasks]) :- 
    Task = task(TSuggested,TActual,L,Rs), 
    TActual #>= TSuggested - 10, 
    TActual #=< TSuggested + 10, 
    on_time(Tasks).

另一個謂詞會檢查任何兩個任務使用同一資源同時：

nonoverlap(R,Task1,Task2) :- 
    Task1 = task(_,T1,L1,Rs2), 
    Task2 = task(_,T2,L2,Rs2), 
    ((member(R,Rs1), member(R,Rs2)) -> 
     T2 #> T1+L1  % start Task2 after Task1 has finished 
     #\/    % OR 
     T1 #> T2+L2  % start Task1 after Task2 has finished 
    ; 
     true   % non-conflicting, do nothing 
    ).

最後，調用labeling上的所有約束變量給他們一致的值。這使用，它適用於整數時間單位。 CLP(R)對於實際值時間也是一樣，但稍微複雜一些。鏈接適用於SWI-Prolog，但SICStus和ECLiPSe具有類似的庫。

來源

2010-11-02 11:40:09