Scheduling tasks with shared resources using logic programming

Question

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

You have to schedule players (which uses Time) to 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).

it 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 time of start for each of the tasks, E is the ending time for each of the tasks while D is the duration of the tasks.

So far, so good.

But now, I am struggling with the other things. Precisely:

1) How can I also print which player is using which shower?

2) How can I limit one shower to be able to run a maximum of four players?

I am a total newbie to Prolog, and it is quite likely that this might be the last program I am writing on it. I managed so far to do this, but I need to finish this (you guess it, it is an assignment). It is the very last thing I have to do on this course, and I haven't ever done any constraint logic programming before.

Thanks for reading and eventually replying on this!

Answer 1

If you use the cumulatives/[2,3] constraint instead of the cumulative/1 constraint, then you will get the assigned machine for 'free'.

By use of cumulatives each single machine can be given individual resource capacity.

This shows your problem solved by use of 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).

And when launched you get:

| ?- 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] ? 

As you can see: task 1 is assigned to machine 1 with start time 0 task 2 is assigned to machine 2 with start time 0 task 3 is assigned to machine 1 with start time 3 . .

Answer 2

Nice question, +1!

Here is one way to solve it: Suppose you have already found a schedule that satisfies the resource limit. Then you simply describe what must hold in addition so that the tasks can be allocated to the machines in the desired way.

For example:

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 contains one list for each machine, where each list in turn consists of the starting times of the tasks allocated to that machine.

I leave more precisely identifying the tasks as a simple exercise.

Example usage and its result:

?- 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]] .

Let us see how many unique solutions there are for a total duration of 4 time slots, which we already know to be the minimum due to the resource limit alone:

?- 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.

This is a lower bound on the number of actually unique solutions, which we can only compute if we take unique task identifiers into account instead of starting times.

I have done this and found 20 ways to distribute the tasks subject to all constraints, using the machines interchangeably:

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]]
  ]).