@@ Linia 1: / Linia 1: @@
+====== 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 =====

pl/prolog/pllib/scheduling_clp.txt · ostatnio zmienione: 2019/06/27 15:50 (edycja zewnętrzna)

Pokaż stronę Poprzednie wersje

Menadżer multimediów Do góry

AIwiki

Menu

Dla Studentów

Old specialized AI courses

SMaDA/SMaIDA/AIDA

Informatyka (EAIiIB)

Studia Dr

Inne materialy dydaktyczne

Archiwum

Dyplomanci

Geist Season of Code

HeKatE

Public

Różnice