what algorithm for a scheduling program

Question

I have this problem of scheduling tasks. Each task has a suggested start time T (it needs to start at [T-10, T+10]), takes L minutes to complete and uses a number of resources [R1, R2,...]. When a resource is being used, no other task can use it. Given that only the start time is flexible, my goal is to schedule the tasks so that they can access any resource they need or point out all the conflicts that needs resolving.

Which algorithm can I use for this purpose? Thank you.

Answer 1

Since you've tagged this as prolog, I recommend implementing it in constraint logic programming (CLP) and using the algorithms built into your CLP implementation. 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 would check that no two tasks use the same resource concurrently:

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 labeling on all the constrained variables to give them consistent values. This uses CLP(fd), which works for integer time units. CLP(R) does the same for real-valued time but it slightly more complicated. Links are for SWI-Prolog but SICStus and ECLiPSe have similar libraries.

Answer 2

Scheduling problems like this are often best addressed using either Constraint Programming CP or Mixed Integer Programming (MIP). Both are declarative approaches, so you only need to focus on the properties of your problem and let a specialized engine handle the underlying algorithm. More information can be found on wikipedia:

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

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

Answer 3

If you're constraints or your problem domain will scale out, you should also take a look at the imperfect algorithms, such as:

• Metaheuristics such as tabu search and simulated annealing. There are a couple of open source implementations out there, such as Drools Planner.

• Genetic algorithms, such as JGap.