什么算法的调度程序

Question

我有调度任务的这个问题.每个任务都有一个建议的开始时间T(需要从[T-10,T + 10]开始),需要L分钟才能完成并使用多个资源[R1,R2,...].使用资源时,没有其他任务可以使用它.鉴于只有开始时间是灵活的,我的目标是安排任务,以便他们可以访问他们需要的任何资源或指出需要解决的所有冲突.

我可以使用哪种算法来实现此目的？谢谢.

Answer 1

由于您已将其标记为，因此我建议在约束逻辑编程prolog(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(fd)，它适用于整数时间单位。CLP(R)对实值时间执行相同的操作，但稍微复杂一些。链接适用于 SWI-Prolog，但 SICStus 和ECLiPSe有类似的库。