什么算法的调度程序

我有这个调度任务的问题。每个任务都有一个建议的开始时间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