Geek Answers Handbook

What is the algorithm for the planning program

I have a problem with task scheduling. Each task has a suggested start time T (it should start with [T-10, T + 10]), takes L minutes and uses several resources [R1, R2, ...]. When a resource is used, no other task can use it. Given that only the start time is flexible, my goal is to schedule tasks so that they can access any resource they needed, or indicate all conflicts that need to be resolved.

What algorithm can I use for this purpose? Thank.

+5
source share
3 answers

Since you marked this as prolog, I recommend embedding it in logical constraint programming (CLP) and using the algorithms built into your CLP implementation. A partial example:

:- 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).

Another predicate will verify that two tasks do not use the same resource at the same time:

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
    ).

Finally, call labelingfor all restricted variables to give them consistent values. This uses CLP (fd) , which works for whole units of time. CLP (R) does the same for real time, but a little more complicated. Links for SWI-Prolog, but SICStus and ECLiPSe have similar libraries.

+4
source

, , Constraint Programming CP Mixed Integer Programming (MIP). , . :

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

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

+2

, , :

+1

More articles:


All Articles