Re: [or-tools-discuss] Scheduling problem with constraint on running total

[Laurent Perron]

In the CP-SAT solver, you can have a look at the reservoir constraint:

https://github.com/google/or-tools/blob/master/ortools/sat/doc/reference.md#addreservoirconstraint

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

Le mar. 11 déc. 2018 à 22:00, Marianne Hoogeveen <marianne....@gmail.com> a écrit :

Deal all,

I have a task scheduling problem, in which there is some quantity associated with each task, let's call it "resource_utilization", which has to stay within a range. This quantity can take both positive and negative values. (kind of like a knapsack problem but with both positive and negative weights and therefore two bounds)

What I am trying to add is a constraint on the running total of this quantity, namely it has to stay within some range.

For example, I have the following tasks with their resource_utilization: {A: -1, B: 4, C: 0, D: 2, E: -1}

These tasks are to be divided over 5 time slots: t1, t2, t3, t4 and t5.

The quantity I am interested in is the running total of resource_utilization. For instance, if I simply schedule the tasks in alphabetical order, the running total at time t1 is -1, at t2 it is 3, at t3 it is 3, at t4 it is 5 and at t5 it is 4. What I want to implement are constraints on this running total, e.g. it should never be below 0 and never above 4

How can such a constraint be efficiently implemented in OR-tools?

Kind regards,

Marianne

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Marianne Hoogeveen]

Thank you! The reservoir constraint is precisely what I've been looking for!

[Steve Sass]

Are there any examples that use AddReservoirConstraint?  Google only comes up with 5 search results.  It seems to be a good fit for our model, but I'm not certain.  The problem is:

Multiple parts, with customer demand by day, like:

Part       DAY0    DAY1    DAY2    ...

Part123     56      75      64

Part456     77      23      87

Part876     65      87      45

Part555     22      76      35

...

The order can be in minimum quantities, but should cover the parts needed most for the day first, schedule all parts in need order, then move to the next day.  Orders/changeovers will be scheduled in one of 3 machines, like:

MACHINE 1:  |  PART: Part123  Qty: 25  Duration: 75 minutes          |(5 minute changeover)|     PART: Part456  Qty: 35  Duration: 105 minutes         | ....

MACHINE 2:  |  PART: Part875  Qty: 15  Duration: 60 minutes|  (15 minute changeover)          |     PART: Part555  Qty: 25  Duration: 75 minutes | ....

MACHINE 3:  |  PART: Part456  Qty: 35  Duration: 105 minutes                     |  (10 minute changeover)    |     PART: Part875  Qty: 45  Duration: 135 minutes           | ....

Where the changeovers are dependent on the part switching from/to.  The goal would be to maximize efficiency (the amount of time actually running versus the total time, running + change overs).  Oh, and machines 1 and 2 can only run certain parts, machine 3 can run any part.

Any advice would be appreciated.

Side note: I am new to OR-Tools, but I was able to successfully use it to do a fun Crystal Maze number problem, if anyone is interested:

        //Each node, with 0, 1, 2, 3 along the middle, 4 and 5 at the top, and 6, 7 at the bottom

        IntVar[] nodes = new IntVar[8];

        int[,] neighbors = new int[,] {

            {4, 1, 6, -1, -1, -1 },{0, 2, 4, 5, 6, 7 },{1, 3, 4, 5, 6, 7 },{2, 5, 7, -1, -1, -1 }, //middle

            {0, 1, 2, 5, -1, -1 },{1, 2, 3, 4, -1, -1 },  //top

            {0, 1, 2, 7, -1, -1 },{1, 2, 3, 6, -1, -1 }   //bottom

        };

        //make each node

        for (int i = 0; i < 8; i++) {

            IntVar node = model.NewIntVar(0, 7, "NODE_" + i);

            nodes[i] = node;

        }

        //add neighbor constraints

        for (int i = 0; i < 8; i++) {

            for (var j = 0; j < 6; j++) {

                if (neighbors[i, j] >= 0) {

                    IntVar y = model.NewBoolVar("NEIGHBOR_CONSECUTIVE_" + i + "_" + j);

                    model.Add(nodes[i] > nodes[neighbors[i, j]]).OnlyEnforceIf(y);

                    model.Add(nodes[i] - nodes[neighbors[i, j]] > 1).OnlyEnforceIf(y);

                    model.Add(nodes[neighbors[i, j]] - nodes[i] > 1).OnlyEnforceIf(y.Not());

                }

            }

        }

        model.AddAllDifferent(nodes);