3

我目前正在使用 :- use_module(library(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.

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

据我所知，这是一个局部变量，其值应介于 25<_G66<35 或 60<_G66<75 之间，但我似乎找不到在 Prolog 本身中打印这些值的方法。我认为最小化（TotTime）会强制所有变量最小化，这似乎与其余变量一起发生。

编辑：

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

如果我在返回结果之前查看调试器。这确实支持我对orB=35-A的手动测试。自己无法真正进行演绎，因为我不知道如何解释这些约束中的值。35<B<5060<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

4

1 回答 1

3

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

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

minimize_schedule([]).
minimize_schedule([task(_,Start,_,_)|Rest]) :-
    minimize(Start), 
    minimize_schedule(Rest).
于 2014-12-31T15:30:35.130 回答