Geek Answers Handbook

Scheduling tasks using shared resources using logical programming

Time 5, 3, 8, 2, 7, 3, 9, 3, 3, 5, 7

You have to plan players (who use Time) for three different showers. Get the best solution. So far my solution is:

use_module(library(clpfd)).

shower(S, E, D, Done) :- 
    D = [5, 3, 8, 2, 7, 3, 9, 3, 3, 5, 7],
    R =  [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    length(D, N),
    length(S, N),
    length(E, N),
    domain(S, 0, 100),
    domain(E, 0, 100),
    Done in 0..100,
    ready(E, Done),
    tasks(S, D, E, R, Tasks),
    cumulative(Tasks, [limit(3)]),
    labeling([minimize(Done)], [Done|S]).

tasks([], [], [], [], []).
tasks([S|Ss], [D|Ds], [E|Es], [R|Rs], [T|Ts]) :-
    T = task(S, D, E, R, 0),
    tasks(Ss, Ds, Es, Rs, Ts).

ready([], _).
ready([E|Es], Done) :-
    Done #>= E,
    ready(Es, Done).

If I run the program:

?- shower(S,D).

he will print:

D = 19,
S = [0,0,0,3,5,5,8,8,11,14,12]

Done is the total time (maximum time), S is the start time for each of the tasks, E is the end time of each of the tasks, and D is the duration of the tasks.

So far so good.

But now I'm struggling with other things. Exactly:

1) How can I print which player uses a shower?

2) How can I limit one rainfall to be able to work no more than four players?

Prolog, , , . , ( , ). , , - .

, !

+4
4

cumulatives/[2,3] cumulative/1, "free".

cumulatives ​​ .

, cumulatives:

:- use_module(library(clpfd)).
:- use_module(library(lists)).

go( Ss, Es, Ms) :-

    Ss = [S1, S2, S3, S4,S5,S6,S7], %Starttimes
    Es = [E1, E2, E3, E4,E5,E6,E7], %Endtimeds
    Ms = [M1, M2, M3, M4,M5,M6,M7], %MachineIds

    domain(Ss, 0, 10),
    domain(Es, 0, 10),
    domain(Ms, 1, 4),

    Tasks = [
        task(  S1, 3,  E1,  1, M1 ), 
        task(  S2, 4,  E2,  1, M2 ), 
        task(  S3, 1,  E3,  1, M3 ), 
        task(  S4, 1,  E4,  1, M4 ), 
        task(  S5, 1,  E5,  1, M5 ), 
        task(  S6, 1,  E6,  1, M6 ), 
        task(  S7, 4,  E7,  1, M7 )
    ],

    %All machines has resource capacity = 1
    Machines = [
        machine(  1, 1 ),
        machine(  2, 1 ),
        machine(  3, 1 ), 
        machine(  4, 1 ) 
    ],

    cumulatives(Tasks, Machines, [bound(upper)] ),
    maximum( MaxEndTime, Es ),

    %The variables to lable:
    append([Ms, Ss ], Vars),

    labeling( [minimize(MaxEndTime)], Vars).

:

| ?- go( Ss, Es, Ms) .
Ss = [0,0,3,0,1,2,0],
Es = [3,4,4,1,2,3,4],
Ms = [1,2,1,3,3,3,4] ?

: 1 1 0 2 2 0 3 1 3 , .

+3

, +1!

: , , . , , .

:

distribution(Starts, Ends, Machines) :-
        pairs_keys_values(Pairs, Starts, Ends),
        length(Ms0, 4),
        maplist(=(0-[]), Ms0),
        foldl(task_machines0_machines, Pairs, Ms0, Ms1),
        pairs_values(Ms1, Machines0),
        maplist(reverse, Machines0, Machines1),
        msort(Machines1, Machines).

task_machines0_machines(Start-End, Ms0, [End-[Start|Starts]|Ms1]) :-
        Start #>= OccupiedUntil,
        select(OccupiedUntil-Starts, Ms0, Ms1),
        L #=< 2,
        length(Starts, L).

Machines , , .

.

:

?- shower(Starts, Ends, _, _), distribution(Starts, Ends, Machines).
Starts = [0, 0, 0, 1, 2, 3, 0],
Ends = [3, 3, 1, 2, 3, 4, 4],
Machines = [[0], [0], [0, 1, 2], [0, 3]] .

, 4, - :

?- setof(Ms, Starts^Ends^Ds^(shower(Starts, Ends, Ds, 4),
                             distribution(Starts, Ends, Ms)),
         Mss),
   length(Mss, L).
Mss = [[[0], [0, 1], [0, 3], [0, 3]], ...]
L = 14.

, , .

20 , , :

distributions([
    [[1],[2,3],[4,5,6],[7]], [[1],[2,4],[3,5,6],[7]], [[1],[2,5],[3,4,6],[7]],
    [[1],[2,6],[3,4,5],[7]], [[1,3],[2],[4,5,6],[7]], [[1,3],[2,4],[5,6],[7]],
    [[1,3],[2,5],[4,6],[7]], [[1,3],[2,6],[4,5],[7]], [[1,4],[2],[3,5,6],[7]],
    [[1,4],[2,3],[5,6],[7]], [[1,4],[2,5],[3,6],[7]], [[1,4],[2,6],[3,5],[7]],
    [[1,5],[2],[3,4,6],[7]], [[1,5],[2,3],[4,6],[7]], [[1,5],[2,4],[3,6],[7]],
    [[1,5],[2,6],[3,4],[7]], [[1,6],[2],[3,4,5],[7]], [[1,6],[2,3],[4,5],[7]],
    [[1,6],[2,4],[3,5],[7]], [[1,6],[2,5],[3,4],[7]]
  ]).
+3

, SWI-...

:- use_module(library(clpfd)).

shower(Durations, NumMachines, Starts, Done) :- 
    sum_list(Durations, Max),
    Done in 0..Max,
    maplist(task(Max, Done), Durations, Tasks, Starts),
    cumulative(Tasks, [limit(NumMachines)]),
    labeling([min(Done)], [Done|Starts]).

task(Max, Done, Duration, task(Start, Duration, End, 1, 0), Start) :-
    MaxStart is Max-Duration,
    Start in 0..MaxStart,
    End #= Start + Duration, %End in 0..Max,
    Done #>= End.

/4 , makepan ( ).

1 ?- shower([3, 3, 1, 1, 1, 1, 4], 4, S, D).
S = [0, 0, 0, 1, 2, 3, 0],
D = 4 ;
S = [0, 0, 0, 1, 3, 2, 0],
D = 4 
...

, ​​

?- aggregate(count,S^shower([1, 1, 1, 1, 3, 3, 4], 4, S, 4),N).
N = 348.

:

?- forall(shower([1, 1, 1, 1, 3, 3, 4], 4, S, 4), writeln(S)).

:

allocate_machines(Machines, Starts, Durations, Gantt) :-
    findall(M-[], member(M, Machines), Pool),
    distribute(Starts, Durations, Pool, Gantt).

distribute([], [], Allocated, Allocated).
distribute([S|Ss], [D|Ds], Pool, Allocated) :-
    select(M-Duties, Pool, Reduced),
    \+ busy(S, Duties),
    length(Duties, L), L < 3,
    append(Duties, [S/D], Updated),
    distribute(Ss, Ds, [M-Updated|Reduced], Allocated).

busy(S, [Sd/Dd|_]) :- S < Sd+Dd, !.
busy(S, [_|Ds]) :- busy(S, Ds).
+1

@MortenM

, ( , - , , - , 0, 1). :

go( Ss, Es, Ms) :-

Ss = [S1, S2, S3, S4,S5,S6,S7], %Starttimes
Es = [E1, E2, E3, E4,E5,E6,E7], %Endtimeds
Ms = [M1, M2, M3, M4,M5,M6,M7], %MachineIds


domain(Ss, 0, 20),
domain(Es, 0, 20),
domain(Ms, 1, 10),

%All task has duration = 1
Tasks = [
    task(  S1, 3,  E1,  1, M1 ), 
    task(  S2, 3,  E2,  1, M2 ), 
    task(  S3, 1,  E3,  1, M3 ), 
    task(  S4, 1,  E4,  1, M4 ), 
    task(  S5, 1,  E5,  1, M5 ), 
    task(  S6, 1,  E6,  1, M6 ), 
    task(  S7, 4,  E7,  1, M7 )
],

%All machines has resource capacity = 1
Machines = [
    machine(  1, 1 ),
    machine(  2, 1 ),
    machine(  3, 1 ),
    machine(  4, 1)
],

cumulatives(Tasks, Machines, [bound(upper)] ),
 maximum( MaxEndTime, Es ),

%The variables to lable:
append([Ms, Ss ], Vars),
labeling( [minimize(MaxEndTime)], Vars).

, , ( ):

?- go(Ss,Es,Ms).
Ss = [0,0,3,3,0,1,0],
Es = [3,3,4,4,1,2,4],
Ms = [1,2,1,2,3,3,4] ?

, . , , . , .

, .

NB: , :)

0

More articles:


All Articles