Local variable constraint values

I am currently working on a scheduling problem using a library: - use_module (library (clpq)). My problem is getting a complete solution to my problem.

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.

      

This solution seems to be correct, but I don't have a specific task value (t2, _G66 , 10, c1) (task number, start time, duration, cpu core).

As far as I know, this is a local variable whose values ​​should be between 25 and 60 or 60 <_G66 <75, but I cannot find a way to print these values ​​in Prolog itself. I thought minimizing (TotTime) would force all variables to be minimized, which seems to happen with the rest.

Edit:

Added some more code to show where the problem should lie. No other mishaps are produced elsewhere. bestsofar/2

used to store the current best graphics solution and runtime. When we find a better, faster graph, replace it with update_time/2

. This search will always fail, so all possible solutions will be tested. After that we will reach bestsofar(BestSchedule,BestTotTime)

and return these values.

If I look at the debugger before returning the result. B=35-A

which supports my manual test 35<B<50

or 60<B<75

. There is no way to draw the conclusion on my own because I don't know how to interpret the meaning _

in these constraints.

[ 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)

      

Without, no_data/2

my code really works for examples where channel latency is not used. So I guess any problem should be with this piece of code.

Launch code if interested: http://pastebin.com/3PmRu7Aq

+3


source to share


1 answer


After some searching, I found the problem. The code was able to generate the correct schedule from the start. The only problem was that the initial "start times" of the tasks were kept to a minimum if they were to be forminimize(TotTime)

Therefore, if a specific task was not critical to the critical path, the start time was not specified in the solution. This was resolved by iterating over the result and minimizing each StartTime



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

      

+3


source







All Articles