|
|
pl:prolog:pllib:scheduling_clp [2019/06/27 15:50] |
pl:prolog:pllib:scheduling_clp [2019/06/27 15:50] (aktualna) |
| ====== Scheduling clp ====== |
| {{tag>planning CLP}} |
| ===== Description ===== |
| A CLP(R) scheduling program for problems with precedence and resource constraints. |
| |
| **Source**: PROLOG programming for artificial intelligence, 3rd Edition, Harlow, 2001, ISBN 0-201-40375-7. |
| ===== Download ===== |
| Program source code: {{scheduling_clp.pl}} |
| ===== Listing ===== |
| <code prolog> |
| % Figure 14.4 A CLP(R) scheduling program for problems with precedence and resource |
| % constraints. |
| |
| |
| % Scheduling with CLP with limited resources |
| |
| schedule( BestSchedule, BestTime) :- |
| tasks( TasksDurs), |
| precedence_constr( TasksDurs, Schedule, FinTime), % Set up precedence inequalities |
| initialise_bound, % Initialise bound on finishing time |
| assign_processors( Schedule, FinTime), % Assign processors to tasks |
| minimize( FinTime), |
| update_bound( Schedule, FinTime), |
| fail % Backtrack to find more schedules |
| ; |
| bestsofar( BestSchedule, BestTime). % Final best |
| |
| % precedence_constr( TasksDurs, Schedule, FinTime): |
| % For given tasks and their durations, construct a structure Schedule |
| % comprising start time variables. These variables and finishing time FinTime |
| % are constrained by inequalities due to precedences. |
| |
| precedence_constr( [], [], FinTime). |
| |
| precedence_constr( [T/D | TDs], [T/Proc/Start/D | Rest], FinTime) :- |
| Start >= 0, % Earliest start at 0 |
| Start + D =< FinTime , % Must finish by FinTime |
| precedence_constr( TDs, Rest, FinTime), |
| prec_constr( T/Proc/Start/D, Rest). |
| |
| prec_constr( _, []). |
| |
| prec_constr( T/P/S/D, [T1/P1/S1/D1 | Rest]) :- |
| ( prec( T, T1), !, { S+D =< S1} |
| ; |
| prec( T1, T), !, { S1+D1 =< S} |
| ; |
| true ), |
| prec_constr( T/P/S/D, Rest). |
| |
| % assign_processors( Schedule, FinTime): |
| % Assign processors to tasks in Schedule |
| |
| assign_processors( [], FinTime). |
| |
| assign_processors( [T/P/S/D | Rest], FinTime) :- |
| assign_processors( Rest, FinTime), |
| resource( T, Processors), % T can be executed by any of Processors |
| member( P, Processors), % Choose one of suitable processors |
| resource_constr( T/P/S/D, Rest), % Impose resource constraints |
| bestsofar( _, BestTimeSoFar), |
| { FinTime < BestTimeSoFar }. % New schedule better than best so far |
| |
| % resource_constr( ScheduledTask, TaskList): |
| % Construct constraints to ensure no resource conflict |
| % between ScheduledTask and TaskList |
| |
| resource_constr( _, []). |
| |
| resource_constr( Task, [Task1 | Rest]) :- |
| no_conflict( Task, Task1), |
| resource_constr( Task, Rest). |
| |
| no_conflict( T/P/S/D, T1/P1/S1/D1) :- |
| P \== P1, ! % Different processors |
| ; |
| prec( T, T1), ! % Already constrained |
| ; |
| prec( T1, T), ! % Already constrained |
| ; |
| { S+D =< S1 % Same processor, no time overlap |
| ; |
| S1+D1 =< S}. |
| |
| initialise_bound :- |
| retract(bestsofar(_,_)), fail |
| ; |
| assert( bestsofar( dummy_schedule, 9999)). % Assuming 9999 > any finishing time |
| |
| % update_bound( Schedule, FinTime): |
| % update best schedule and time |
| |
| update_bound( Schedule, FinTime) :- |
| retract( bestsofar( _, _)), !, |
| assert( bestsofar( Schedule, FinTime)). |
| |
| % List of tasks to be scheduled |
| |
| tasks( [t1/4,t2/2,t3/2, t4/20, t5/20, t6/11, t7/11]). |
| |
| % Precedence constraints |
| |
| prec( t1, t4). prec( t1, t5). prec( t2, t4). prec( t2, t5). |
| prec( t2, t6). prec( t3, t5). prec( t3, t6). prec( t3, t7). |
| |
| % resource( Task, Processors): |
| % Any processor in Processors suitable for Task |
| |
| resource( _, [1,2,3]). % Three processors, all suitable for any task |
| |
| </code> |
| ===== Comments ===== |
| |