CODEWITHSUNDEEP
prologschedulingclp
PB101
PB101

Reputation: 142

Contraint Logic Programming Scheduling

I'm trying to solve a problem using clp in prolog. The problem is as follows:

Basically a ship is carrying a number of containers and we want to unload them. The containers is described as predicates container(I,N,D), where I is the containers identifier, N is number of persons required to unload and D is the duration. An example may look like:

container(a,1,1).
container(b,2,2).
container(c,2,2).
container(d,3,3).

The containers can also be put on top of another, like:

on(a,c).
on(b,c).
on(c,d).

Container a is on top of c and so on...

The problem is to minimize the cost of unloading the containers. The cost is defined as the number of persons hired times the required time. All persons are hired for the whole duration of the unloading.

I'm having problem starting with the problem, as I'm not familiar with the clp part of prolog. Does anyone have any suggestions on how to solve the problem or where you can find examples on how clp prolog works?

Upvotes: 3

Views: 348

Answers (2)

PB101
PB101

Reputation: 142

Okey, so I added

EA #=< SC,
EB #=< SC,
EC #=< SD,

And the solutions seems to be correct, so thats nice. But I feel this should be more general. Is there a way to generate:

EA #=< SC,
EB #=< SC, 
EC #=< SD,

By calling something like generate_constrains() that uses:

on(A,C).
on(B,C).
on(C,D).

And construct the constrains.

Upvotes: 2

CapelliC
CapelliC

Reputation: 60024

If you declare time variables for Start and End of each job, then cumulative/2 can model the whole process, and serialized/2 can model the on/2 constraint: 

...
Tasks =
    [task(SA,1,EA,1,_)
    ,task(SB,2,EB,2,_)
    ,task(SC,2,EC,2,_)
    ,task(SD,3,ED,3,_)],
cumulative(Tasks, [limit(MAX)]),

serialized([SA,SC,SD],[1,2,3]),
serialized([SB,SC,SD],[2,2,3]),
...

this would already yield a reasonable solution, with the easy to express minimization of the total time.

...
labeling([min(max(EA,max(EB,max(EC,ED))))], [SA,SB,SC,SD]).

[SA,SB,SC,SD] = [0,0,2,4]

But you must compute the cost of the schedule, multiplying the number of workers required and the total duration. Actually, this is a complex computation, since it depends on the overlapping of tasks. We cannot simply add workers on overlapping tasks, since tasks of different durations possibly use the same set of workers.

I think there is 'a trick' applicable : iterative deepening on limit(MAX), starting from the absolute minimum required (3, for container d, in this case).

edit

sorry I was wrong about serialized/2. Should be replaced by explicit comparisons, like

EA #=< SC,
...

Upvotes: 3

Related Questions