局部变量的约束值

Question

我目前正在使用:- use_module(库(Clpq))库解决一个调度问题。我的问题在于检索问题语句的完整解决方案。

schedule(BestSchedule, BestTotTime) :-          %BestSchedule of format [test(task,startTime,Duration Task, Core]
    (  findall(T,task(T),Tasks),
       findall(C,core(C),Cores),
       init_time,                               %Retract all facts of bestsofar(_,_)
       const_time(Tasks,Schedule,Cores,TotTime),%Here probably goes something wrong
       assign_processor(Schedule,Cores, TotTime),
       minimize(TotTime),
       update_time(Schedule, TotTime),  
       fail
    ;  bestsofar(BestSchedule,BestTotTime)
    ).

assign_processor([], _, _).  
assign_processor([task(T,S,D,C)|Rest], Cores, TotTime) :-
    assign_processor(Rest,Cores,TotTime),
    core(C),                            %Pick a core
    process_cost(T,C,D),                %Core/Task known, setting Duration (D)
    const_resource(task(T,S,D,C),Rest), %Setting extra constraints on chosen core 
    bestsofar(_,CurrentBestTime),       %Get current best time from fact bestsofar
    {TotTime < CurrentBestTime}.        %Set new constraint based on currentBestTime


const_resource(_,[]).
const_resource(Task,[Task2|Rest]) :- 
    no_data(Task,Task2),
    no_conflict(Task,Task2),            %No overlap on same processor
    const_resource(Task, Rest).         

no_conflict(task(_,S,D,C),task(_,S2,D2,C2)) :-
    C \== C2,!;                         %Tasks not on same processor
    { S+D =< S2;                        %Set no overlapping start/end times
     S2+D2 =< S }.  

no_data(task(T,S,D,C), task(T2,S2,D2,C2)) :-
         %depends_on(T,T2,_) = T2 needs to be finished before T can start
         %channel(C,C2,L,_) = Data transfer between cores generated latency L
         %Set no overlap including the latency if tasks are dependent
    depends_on(T,T2,_),channel(C,C2,L,_),!, { S2 + D2  =< S - L };
    depends_on(T2,T,_),!,channel(C2,C,L,_),!, { S + D   =< S2 - L};
    true.

init_time :-
    retract(bestsofar(_,_)), fail
    ;
    assert(bestsofar(foobar, 1000)).

update_time(Schedule,TotTime) :-
    retract(bestsofar(_,_)),!,
    assert(bestsofar(Schedule,TotTime)).

S = [task(t7, 100, 10, c1), task(t1, 0, 10, c1), task(t6, 75, 10, c1),
     task(t2, _G66, 10, c1), task(t4, 50, 10, c2), task(t3, 25, 10, c1),
     task(t5, 50, 10, c1)],
ET = 110.

这个解决方案似乎是正确的，但我没有任何特定的任务值(t2，_G66，10，c1) (任务号，启动时间，持续时间，处理器核心)。

据我所知，这是一个局部变量，它的值应该在25<_G66<35或60<_G66<75之间，但我似乎无法找到在Prolog本身中打印这些值的方法。我认为最小化(TotTime)会强制将所有变量最小化，这似乎发生在其他变量中。

编辑：

添加了更多的代码来说明问题的所在。其他地方不会产生任何其他故障。使用bestsofar/2存储当前最佳调度解决方案和执行时间。当我们找到一个更好、更快的时间表时，我们就用update_time/2代替它。这种搜索总是失败的，这样所有可能的解决方案都会被测试。一旦完成，我们就到达bestsofar(BestSchedule,BestTotTime)并返回这些值。

如果在返回结果.B=35-A之前查看调试器，它确实支持我对35<B<50或60<B<75的手动测试。因为我不知道如何在这些约束中解释_值，所以我自己无法真正地进行推断。

[ task(t7,100,10,c1),
  task(t1,0,10,c1),
  task(t6,75,10,c1),
  task(t2,B,10,c1),
  task(t4,50,10,c2),
  task(t3,25,10,c1),
  task(t5,50,10,c1)
], % with constraints
    {}(_ = -55 - A ',' _ = -40 - A ',' _ = -25 + A ',' _ = -10 + A ',' _ = -30 - A ',' _ = -5 - A ',' A >= -5 ',' A =< 0 ',' _ = -55 - A ',' _ = -25 + A ',' _ = 65 + A ',' B = 35 - A)

没有no_data/2，我的代码确实适用于没有使用信道延迟的例子。因此，我想任何问题都应该存在于这段代码中。

如果感兴趣，可以运行代码：http://pastebin.com/3PmRu7Aq

Answer 1

经过一番搜索，我发现了这个问题。代码能够从一开始就生成正确的时间表。问题是，如果任务需要minimize(TotTime)，则任务的开始“开始时间”被最小化。

因此，如果某个任务对关键路径不重要，则解决方案中没有定义启动时间。通过迭代结果并最小化每个StartTime，这是可以解决的。

minimize_schedule([]).
minimize_schedule([task(_,Start,_,_)|Rest]) :-
    minimize(Start), 
    minimize_schedule(Rest).