Originally posted by: AELIX_01

I have a particular VRP that I can't figure out if I can model with CP. I think it's not possible, let's discuss it.

Can I model this with CP?:

> 2 machines A & B must execute operation 1 or 2

> T(A,1)  = 10m, T(A,2) = 20m, T(B,1) = 15m, T(B,2) = 15m

> operation 1 produces 10 items of type X and 20 items of type Y

> operation 2 produces 15 items of type X and 5 items of type Y

> Total demand is 250 items type X and 450 items type Y

> Find the schedule that completes the demand in the minimum amount of time.

Expected solution in my mind: A(1,1,2,1,2,2,1,1,1,1)  and B(2,2,2,2,1,2,2,2,2,2,2,1,1,2,2)     [ |A|=10, |B| = 13 ]

I now it has multiple solutions (permutations of a specific solution).

Basically I have a VRP that must allocate (and possibly repeat) tasks until some demand is fulfilled. I couldn't think of a way of allowing repetition in tasks in CP when I don't have a limit in the planning horizon.

Originally posted by: Petr Vilím

Hello,

you have to come up with some horizon in terms of maximum number of operations 1 and 2. Without it there's of course no way to model it.

In your case, a simple limit is 250/10=25 operations 1 and 450/5 operations 2. Of course, it is better to come up with a better limit (and if you have to fit the limit exactly then it may be worth to precompute possible combinations of numbers of operations 1 and 2 without actually scheduling them).

Once you have a limit you can create for example 25 interval variables for operation 1. The trickery part is to make those intervals optional: so if only 10 operations 1 are needed in the solution then 10 intervals will be present (and scheduled) and the remaining 15 will be absent (without assigned date). To break symmetries it is good to order the intervals using startBeforeStart (preferably with non-zero delay) or even better by endBeforeStart (if possible). For example endBeforeStart is possible if we model separately operations 1 on machine A and separately on machine B (assuming the machines cannot handle more than 1 operation at a time). The chain x_1, x_2, ... x_n could be created by constraints:

endBeforeStart(x_i, x_i+1)

Now, if we need just 10 operations then we want to use x_1,.. x_10 (i.e. make them present), not just any random 10 intervals from the chain. This could be done by constraints:

presenceOf(x_i) >= presenceOf(x_i+1)

Finally, number of produced items X by this chain could be computed by:

nbItemsX == 10*sum(presenceOf(x_i))

However it will not propagate well: the sum is propagated independently from the constraints presenceOf(x_i) >= presenceOf(x_i+1). So it will probably help to add redundant constraints:

presenceOf(x_i) == (nbItemsX >= 10*i)

This way, if propagation finds that nbItemsX must be at last 50 (because all other ways to produce item X are not available any more) then propagation automatically sets x1,.. x5 to present. That would not be done without the redundant constraints (the system would not know which 5 out of n x_i should be set to present).

Best regards, Petr