Prolog의 CLP over Finite Domains 라이브러리 성능

Question

프롤로그에서 작업 스케줄러/플래너를 프로그래밍 중이므로 해당 플랫폼에서 SWIPL에 CLPFD library을 사용할 계획입니다. 스케쥴링 문제를 해결하기 위해 유한 도메인을 사용하는 것이 얼마나 강력한 지 궁금 하여요. 사용한다면 CPU로드에 어떤 영향을 미칠지 궁금합니다.

스케줄링 문제는이 백서의 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보다 훨씬 나은 성능을 제공하지만 문제를 모델링하고 솔루션을 검색하는 방법은 일반적으로 특정 구현의 최적화보다 훨씬 성능에 영향을 미칩니다.