调度程序的哪种算法

Question

我遇到了调度任务的问题。每个任务都有一个建议的开始时间T(它需要从T-10，T+10开始)，需要L分钟来完成，并使用多个资源R1，R2，...当资源正在被使用时，没有其他任务可以使用它。考虑到只有开始时间是灵活的，我的目标是安排任务，以便它们可以访问任何他们需要的资源，或者指出所有需要解决的冲突。

为此，我可以使用哪种算法？谢谢。

Answer 1

由于您已经将其标记为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(fd)，它适用于整数时间单位。CLP(R)对实值时间做了同样的事情，但它稍微复杂一些。链接是针对SWI-Prolog的，但SICStus和ECLiPSe有类似的库。

Answer 2

像这样的调度问题通常最好使用约束编程CP或混合整数编程(MIP)来解决。这两种方法都是声明性方法，因此您只需关注问题的属性，并让专门的引擎处理底层算法。更多信息可以在wikipedia上找到：

http://en.wikipedia.org/wiki/Constraint_programming

http://en.wikipedia.org/wiki/Linear_programming

Answer 3

如果你受到约束或者你的问题域将向外扩展，你也应该看看不完美的算法，例如：

• Metaheuristics，如禁忌搜索和模拟退火。有几种开源实现，比如Drools Planner.
• Genetic算法，比如JGap。