We want to develop a program to schedule a project, decomposed in a set of tasks. Each task has successor tasks and a length. A high level view of the whole program has this layout:
sched(P):- project(P, Td), check_data(Td), build_constraints(Td, FinalTask, Dict), minimize(FinalTask, Dict), close_structure(Dict), write_results(Dict).
The definition of the project is (for this example) just a fact with relates a project name (the non-imaginative a) with a list of tasks, which define the initial and final tasks, and for each task, its name (an atom), its length, and the tasks which depend on it (atoms, again). This list will be used to built the constraint network and a dictionary where information about the tasks will be stored. The final task has, associated to it, an absolute limit for the project span.
project(a, [initial(a), task(a,0,[b,c,d]), task(b,1,[e]), task(c,2,[e,f]), task(d,3,[f]), task(e,4,[g]), task(f,1,[g]), final(g,10), task(g,0,[])]).
Checking the correctness of the data is one of the less elegant parts of the program. Each element in the list is checked to make sure that it defines the initial task, the final task, or an intermediate task. For each of them, we will also check that atoms appear where are expected, and that numbers appear where task lengths are expected.
check_data([]). check_data([T|Ts]):- check_datum(T), check_data(Ts). check_datum(Task):- Task = task(Name, Dur, Foll), check_atoms([Name], Task), check_number(Dur, Task), check_atoms(Foll, Task), !. check_datum(Initial):- Initial = initial(Name), check_atoms([Name], Initial), !. check_datum(Final):- Final = final(Name, Limit), check_atoms([Name], Final), check_number(Limit, Final), !. check_datum(What):- write_atoms(['Found ' ,What, ' (unknown).']). check_atoms([], _Where). check_atoms([A|As], Where):- check_atom(A, Where), check_atoms(As, Where). check_atom(A, _Where):- atom(A), !. check_atom(A, Where):- write_atoms(['Found ', A, ' in ', Where, ', expecting atom.']). check_number(N, _Where):- number(N), !. check_number(N, Where):- write_atoms(['Found ', N, ' in ', Where, ', expecting number.']). write_atoms([]):- nl. write_atoms([A|As]):- write(A), write_atoms(As).
The process of building the constraints actually makes two things: it sets up the constraints themselves, but it also constructs a dictionary which relates the task (the Key of each dictionary entry) with the task's< Start and Length (the Value associated to the Key). This is implemented using an open list (a list whose tail ends in a free variable), so that only one argument has to be used for the dictionary. In the case of a larger project, it might be advantageous replacing it by a binary sorted tree. The predicate lookup/4 is the only entry point for the dictionary: it retrieves and, in case of non-existence, adds new items.
lookup(Task, Start, Len, Dict):- insert(Task, data(Start, Len), Dict). insert(Key, Value, [pair(Key, ThisValue)|_Rest]):- !, Value = ThisValue. insert(Key, Value, [_OtherPair|Rest]):- insert(Key, Value, Rest).
As a utility predicate, and to make clearer the final printing of the list of tasks, close_structure/1 closes the dictionary, i.e., it will make the final variable of the list a [].
close_structure([]):- !. close_structure([_|R]):- close_structure(R).
The core of the program is the constraint generation. For each item in the project definition we add the corresponding constraint. Tasks are related one to each other through constraints which are actually put on the variables associated to the tasks names in the dictionary. The name of the final task is returned, so that the minimization predicate can use it to reduce the length of the project as much as possible. The actions taken for creating the constraints are:
build_constraints([], _FinalTask, Dict). build_constraints([Task|Tasks], FinalTask, Dict):- add_constraint(Task, FinalTask, Dict), build_constraints(Tasks, FinalTask, Dict). add_constraint(task(Name, Len, Succ), _Final, Dict):- lookup(Name, Start, Len, Dict), End = Start .+. Len, previous(Succ, End, Dict). add_constraint(initial(Name), _Final, Dict):- lookup(Name, 0, _Len, Dict). add_constraint(final(Name, Limit), Name, Dict):- le(End, Limit), End = Start .+. Len, lookup(Name, Start, Len, Dict). previous([], _End, Dict). previous([NextTask|Tasks], EndThisTask, Dict):- lookup(NextTask, StartNextTask, _Len, Dict), ge(StartNextTask, EndThisTask), previous(Tasks, EndThisTask, Dict).
Minimizing is made naïvely, which is enough for this application: the start of the last task (which has length zero) is forced to be at its minimum. In other cases special builtin predicates will have to be used.
minimize(FinalTask, Dict):- lookup(FinalTask, Start, _Len, Dict), glb(Start, Start).
Finally, writing the results takes advantage of the structure of the dictionary, and dumps it in a more readable form:
write_results([]).
write_results([pair(TaskName, TaskData)|Ps]):-
TaskData = data(TaskStart, TaskLen),
bounds(TaskStart, Lbound, Ubound),
write_bounds(TaskName, TaskLen, Lbound, Ubound),
write_results(Ps).
write_bounds(Task, Le, L, L):-
write_atoms(['Task ', Task, ' with length ', Le,
' starts at ', L, '.']).
write_bounds(Task, Le, L, U):-
lt(L, U),
write_atoms(['Task ', Task, ' with length ', Le,
' can start from ', L, ' to ', U, '.']).
And a query, with the results, is:
?- sched(a). Task a with length 0 starts at 0. Task b with length 1 can start from 0 to 1. Task c with length 2 starts at 0. Task d with length 3 can start from 0 to 2. Task e with length 4 starts at 2. Task f with length 1 can start from 3 to 5. Task g with length 0 starts at 6.
