3

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?

false
  • 10,264
  • 13
  • 101
  • 209
PB101
  • 142
  • 4
  • How many stacks are allowed? If there is just one stack then the number of people needed would be the same as for the container needing the most amount of people? If there are more than one stack are there 'gangs' of people who work on each stack separately? – user27815 Oct 26 '15 at 18:55
  • Since this is an automated scheduling problem, it could probably be solved using a [STRIPS planner in Prolog](https://www.google.com/search?q=prolog+%22STRIPS%22+planner). – Anderson Green Dec 09 '18 at 15:37

2 Answers2

3

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,
...
CapelliC
  • 59,646
  • 5
  • 47
  • 90
2

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.

PB101
  • 142
  • 4