|
|
pl:prolog:pllib:task_scheduling [2019/06/27 15:50] |
pl:prolog:pllib:task_scheduling [2019/06/27 15:50] (aktualna) |
| ====== Task scheduling ====== |
| {{tag>operators planning graphs}} |
| ===== Description ===== |
| Problem-specific relations for the task-scheduling problem. |
| |
| **Source**: PROLOG programming for artificial intelligence, 3rd Edition, Harlow, 2001, ISBN 0-201-40375-7. |
| ===== Download ===== |
| Program source code: {{task_scheduling.pl}} |
| ===== Listing ===== |
| <code prolog> |
| % Figure 12.9 Problem-specific relations for the task-scheduling problem. |
| % The particular scheduling problem of Figure 12.8 is also defined by its |
| % precedence graph and an initial (empty) schedule as a start node for search. |
| |
| :- op( 900, fy, not). |
| |
| % not Goal): negation as failure; |
| % Note: This is often available as a built-in predicate, |
| % often written as prefix operator "\+", e.g. \+ likes(mary,snakes) |
| |
| not Goal :- |
| Goal, !, fail |
| ; |
| true. |
| |
| /* Problem-specific relations for task scheduling |
| |
| Nodes in the state space are partial schedules specified by: |
| |
| [ WaitingTask1/D1, WaitingTask2/D2, ...] * |
| [ Task1/F1, Task2/F2, ...] * FinTime |
| |
| The first list specifies the waiting tasks and their durations; the |
| second list specifies the currently executed tasks and their finishing |
| times, ordered so that F1 =< F2, F2 =< F3 ... . Fintime is the |
| latest completion time of current engagements of the processors. |
| */ |
| |
| % s( Node, SuccessorNode, Cost) |
| |
| s( Tasks1 * [_/F | Active1] * Fin1, Tasks2 * Active2 * Fin2, Cost) :- |
| del( Task/D, Tasks1, Tasks2), % Pick a waiting task |
| not ( member( T/_, Tasks2), before( T, Task) ), % Check precedence |
| not ( member( T1/F1, Active1), F < F1, before( T1, Task) ), %Active tasks too |
| Time is F + D, % Finishing time of activated task |
| insert( Task/Time, Active1, Active2, Fin1, Fin2), |
| Cost is Fin2 - Fin1. |
| |
| s( Tasks * [_/F | Active1] * Fin, Tasks * Active2 * Fin, 0) :- |
| insertidle( F, Active1, Active2). % Leave processor idle |
| |
| before( T1, T2) :- % Task T1 before T2 according to precedence |
| prec( T1, T2). |
| |
| before( T1, T2) :- |
| prec( T, T2), |
| before( T1, T). |
| |
| insert( S/A, [T/B | L], [S/A, T/B | L], F, F) :- % Task lists are ordered |
| A =< B, !. |
| |
| insert( S/A, [T/B | L], [T/B | L1], F1, F2) :- |
| insert( S/A, L, L1, F1, F2). |
| |
| insert( S/A, [], [S/A], _, A). |
| |
| insertidle( A, [T/B | L], [idle/B, T/B | L] ) :- % Leave processor idle |
| A < B, !. % until first greater finishing time |
| |
| insertidle( A, [T/B | L], [T/B | L1] ) :- |
| insertidle( A, L, L1). |
| |
| del( A, [A | L], L). % Delete item from list |
| |
| del( A, [B | L], [B | L1] ) :- |
| del( A, L, L1). |
| |
| goal( [] * _ * _). % Goal state: no task waiting |
| |
| % Heuristic estimate of a partial schedule is based on an |
| % optimistic estimate of the final finishing time of this |
| % partial schedule extended by all the remaining waiting tasks. |
| |
| h( Tasks * Processors * Fin, H) :- |
| totaltime( Tasks, Tottime), % Total duration of waiting tasks |
| sumnum( Processors, Ftime, N), % Ftime is sum of finishing times |
| % of processors, N is their number |
| Finall is ( Tottime + Ftime)/N, |
| ( Finall > Fin, !, H is Finall - Fin |
| ; |
| H = 0 |
| ). |
| |
| totaltime( [], 0). |
| |
| totaltime( [_/D | Tasks], T) :- |
| totaltime( Tasks, T1), |
| T is T1 + D. |
| |
| sumnum( [], 0, 0). |
| |
| sumnum( [_/T | Procs], FT, N) :- |
| sumnum( Procs, FT1, N1), |
| N is N1 + 1, |
| FT is FT1 + T. |
| |
| % A task-precedence graph |
| |
| prec( t1, t4). prec( t1, t5). prec( t2, t4). prec( t2, t5). |
| prec( t3, t5). prec( t3, t6). prec( t3, t7). |
| |
| % A start node |
| |
| start( [t1/4, t2/2, t3/2, t4/20, t5/20, t6/11, t7/11] * [idle/0, idle/0, idle/0] * 0). |
| |
| % An example query: start( Problem), bestfirst( Problem, Sol). |
| |
| </code> |
| ===== Comments ===== |
| |