Производительность библиотеки CLP над конечными доменами Prolog

Question

Я программирую планировщик задач/планировщик в Prolog, и для этого я планирую использовать CLPFD library (на SWIPL). Мне было интересно, насколько мощным является использование конечных доменов для решения задач планирования и того, какое влияние будет оказывать на загрузку процессора, если я его использую.

Проблема планирования будет основана на утверждениях, указанных на странице 10 настоящего документа: «Constraint-Based Scheduling». На самом деле мои задачи/действия будут очень неоднородными (некоторые из них будут превентивными, а другие - нет), а ресурсы деятельности будут иметь разные возможности. Прямо сейчас, я просто работаю на простом случае (не прерываться, дизъюнктивное планирование), и я пришел к чему-то вроде этого:

/* 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. */ 

Это делает работу, и это очень быстро (intstantaneous на самом деле) , Но это всего лишь простой случай с тремя действиями, когда в моей последней программе у меня будет сотни из них, и проблема планирования будет намного сложнее, чем эта.

Спасибо за ваш совет!

Answer 1

В общем, CLP (FD) является подходящим и устоявшимся способом решения таких проблем. Однако обратите внимание, что существует много разных способов моделирования вашей проблемы даже в пределах library(clpfd): вы можете, например, использовать глобальные ограничения serialized/2 или cumulative/1, чтобы выразить это. Другие системы Prolog часто дают вам гораздо лучшую производительность, чем SWI-Prolog, но способ моделирования вашей проблемы и поиска решений обычно влияет на производительность намного больше, чем оптимизация какой-либо конкретной реализации.