Я программирую планировщик / планировщик задач на Прологе, и для этого я планирую использовать Библиотека CLPFD (на SWIPL). Мне было интересно, насколько мощным является использование конечных доменов для решения задач планирования и какое влияние будет на загрузку процессора, если я буду его использовать.
Проблема планирования будет основана на утверждениях, изложенных на странице 10 этого документа: "Планирование на основе ограничений". Фактически, мои задачи / действия будут очень разнородными (некоторые из них будут вытеснены, а другие нет), а ресурсы действий будут иметь разные возможности. Прямо сейчас я работаю над простым случаем (невытесняемое дизъюнктивное планирование) и пришел к примерно следующему:
/* Non-preemptive, disjunctive scheduling. *******************************/
planner :-
/* 'S' stands for start point.
'E' stands for end point. */
set(a1,S1,E1),
set(a2,S2,E2),
set(a3,S3,E3),
interval(intersection,[S1,E1],[S2,E2],[]), % Tests whether activities
interval(intersection,[S2,E2],[S3,E3],[]), % intersect. If they do,
interval(intersection,[S3,E3],[S1,E1],[]), % backtracking occurs and
(...). % an alternative solution
% will be looked for.
/* A set of times in which activity A executes (non-preemptive) */
set(A,[S],[E]) :-
/* 'A' is the activity.
'R' is release point and 'D' deadline point.
'Lst' stands for Latest Start Point.
'Eet' stands for Earliest End Point. */
preemptable(A,no),
rd(A,R,D),
p(A,P),
Lst is D-P,
Eet is R+P,
S in R..D,
E in R..D,
S #=< Lst,
E #>= Eet,
S #< E,
P #= E-S,
indomain(S),
indomain(E).
set(A,[],[]). /* When the activity can't be scheduled. */
Это действительно работает, и это действительно быстро (фактически, мгновенно). Но это всего лишь простой случай с тремя действиями, когда в моей последней программе их будут сотни, и задача планирования будет намного сложнее, чем эта.
Спасибо за совет!