Scheduling parallel tasks with weight constraint

[Torbjorn Backstrom]

  I feel fairly stupid at the moment. I've tried to wrap my mind around OR-Tools and CP-SAT, and even though I consider myself a fairly seasoned software developer, I don't "get it". I've read a lot of the examples but as I am lacking in theoretical background and I can't find a "OR-Tools for Dummies", I don't even know where to begin. Is there a basic API-tutorial (types, classes, intent, etc) available? ChatGPT4 hasn't been helpful either, as it led me astray in different directions and I've spent many hours trying to understand what I now think is its "hallucinations".

The problem I am trying to solve, which I think is a good fit for CP-SAT, similar to the "shop" examples, is this (in C# pseudo code):

class Task {

  int durationInMinutes;

  int weight;

}

Task[] tasks = [{10, 2},{5, 3},{10, 2},{2, 10}, ... , {25, 1}];

int[] weightLimitAtMinute = [10, 10, 10, 10, 50, 50, 50, 50, 50, 10, 10, 10, ... ,50, 50];

I want to schedule N number of tasks with as short makespan as possible. Tasks can run in parallel as long as the sum of task weights each minute is <= weightLimitAtMinute[i].

To this I have other constraints as well, like "latestCompletionMinute" and "earliestStartMinute" and so on, but the above is the basic.

Any pointer to how to "index" a constraint, what C# data types should be used, any docs etc would be very much appreciated. Thank you for reading this.

[Laurent Perron]

basic scheduling.

Intervals, cumulative with demands, and makespan objective.

Get inspiration from examples/python/line_balancing_sat.py

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

--
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.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/0c33cba3-5e53-49cc-b5de-9300cb896497n%40googlegroups.com.

[Torbjorn Backstrom]

Thank you for the input. I've successfully implemented the basics now, but one thing that I don't understand is how to use a "varying" cumulative constraint (sorry if I am using the wrong terminology).

I'm reading the source code but still feel quite lost. I am using C#, and my tasks look like this:

class CpTask {

    public int Weight { get; set; }
    public IntVar Start { get;set;}
    public IntVar End { get;  set;  }
    public IntervalVar Interval { get;  set;  }
}

after initializations etc I do this:

int[] demands = (from t in tasks select t.Weight).ToArray();
var intervals = (from t in tasks select t.Interval).ToArray();

and add the constraint:

model.AddCumulative(20).AddDemands(intervals, demands);

My issue is with the fixed value of "20". I would like to have a value that varies across time, ideally like

var maxWeights = [20, 20, 20, 10, 10, ... , 10, 20, 20];

model.AddCumulative(maxWeights).AddDemands(intervals, demands);

Is there a way to accomplish this?

Thanks again for reading and replying.

[Torbjorn Backstrom]

Maybe I am thinking about this in the wrong way. The tasks can be thought of as rectangles where width = duration and height = weight. The cumulative allowed heights vary over time (red line). The optimization result (max amount of tasks as soon as possible) could look something like this:

I've studied various examples (gate_scheduling_sat.py, line_balancing_sat.py, no_wait_baking_scheduling_sat.py and more) but I struggle with the concepts, how to combine logic. 

I have the intervals but somehow need to introduce a variable for each time step that is the Sum() of the weights and check that versus the allowed maxWeight at that same time step.

Any suggestions on how to think about this or pointers to similar examples would be much appreciated. And maybe this isn't suitable for CP-SAT/OR-Tools?

[Laurent Perron]

Just used fixed intervals to block the gap between the actual capacity and the max capacity.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/49762d7e-d5a1-4af1-b5b7-d32a8129bf58n%40googlegroups.com.

[Torbjorn Backstrom]

Thank you so much! Works perfectly.

Am I right in my understanding that an interval is [from, to) as opposed to [from, to] when values in arrays are referenced?
As in "from <= index < to" and not "from <= index <= to".

This is fun :)

[Torbjorn Backstrom]

Moving to real-world data, I've encountered something strange:

My "domain" is an x-axis that is 1440 minutes, and the y-axis is the "available capacity", which is used as a constraint in cumulative with demands. It's currently fixed at "670".

I have 30 intervals, and each interval is about 350 minutes, and the needed capacity is fixed at 60, which basically means for the tasks starting at "0", there can be 10 in parallell.

If I run the solver with 22 of those intervals, the running time is < 60 ms.

If I run the solver with 23 (or more) of those intervals, the running time is... well, I added a timeout for 60 seconds which is always hit.

Is this a characteristic of a CP-SAT solver (which means that if I had more experience, I shouldn't have been surprised), or does it imply I am doing something stupid in my code (which is very simple).

Feedback/opinion/experience much appreciated. I've fiddled with most values just to get a feeling for this, but it always cutoff at 22.

[Laurent Perron]

Are you using multiple workers ?

Have you enabled logging ?

Can you send me the model: model.ExportToFile('slow_cumulative_sat.pb.txt') ?

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/00283519-f678-44d9-b474-5bc7663aeb9cn%40googlegroups.com.

--

--Laurent

[Torbjorn Backstrom]

Yes, yes and yes :)

1) I think multiple workers are enabled, this is my code (and I can see 8 cores spike):
            var solver = new CpSolver
            {
                StringParameters = "max_time_in_seconds:60.0,num_search_workers:8" //relative_gap_limit:0.05"
            };

2/3) Please see the log below and attached file. And thank you for looking at this.

#Variables: 61 (#ints: 1 in objective)
  - 31 in [0,1440]
  - 2 in [311,1440]
  - 2 in [332,1440]
  - 1 in [341,1440]
  - 3 in [367,1440]
  - 1 in [408,1440]
  - 1 in [420,1440]
  - 2 in [426,1440]
  - 1 in [431,1440]
  - 2 in [437,1440]
  - 2 in [449,1440]
  - 4 in [454,1440]
  - 1 in [460,1440]
  - 1 in [466,1440]
  - 3 in [472,1440]
  - 2 in [483,1440]
  - 2 in [489,1440]
#kCumulative: 1 (#intervals: 30)
#kInterval: 30
#kLinMax: 1 (#expressions: 30)
#kLinear2: 30
Status: Feasible
scheduling_intervals_lns(d=0.46 s=37 t=0.10 p=0.50 stall=0)
CpSolverResponse summary:
status: FEASIBLE
objective: 1231
best_bound: 1156
integers: 31
booleans: 5390
conflicts: 1663889
branches: 1672276
propagations: 245547918
integer_propagations: 14267843
restarts: 56
lp_iterations: 0
walltime: 60.0595
usertime: 60.0595
deterministic_time: 480.676
gap_integral: 2075.4
solution_fingerprint: 0x9df45a9cfe1d792c

***
Feasible schedule length: 1231  (60076 ms)

[Laurent Perron]

This is called phase transition :-) And a very steep one.

I suppose up to 22, a trivial solution with cost equal to the energetic lower bound is found very fast.

Proof is hard for 23.

#12      0.27s best:1233  next:[1148,1232] probing (fixed_bools=13/466)                              

#13      0.29s best:1232  next:[1148,1231] probing (fixed_bools=15/477)                              

#14      0.30s best:1230  next:[1148,1229] probing (fixed_bools=16/497)                              

#15      0.43s best:1229  next:[1148,1228] probing (fixed_bools=23/664)

#16      0.45s best:1228  next:[1148,1227] probing_max_lp (fixed_bools=21/815)

#17      0.64s best:1227  next:[1148,1226] rnd_cst_lns (d=0.88 s=64 t=0.10 p=1.00 stall=0 h=auto_l0)

#18      0.68s best:1225  next:[1148,1224] max_lp (fixed_bools=4/3672)      

#19      0.68s best:1224  next:[1148,1223] max_lp (fixed_bools=9/3676)      

#Bound   0.13s best:1237  next:[1148,1236] reduced_costs [skipped_logs=260] 

and nothing happens afterwards

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

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/7ec52fc6-39ef-4f02-b5d0-fb6e298b8afcn%40googlegroups.com.

[Torbjorn Backstrom]

Thank you for checking, and for the support! I guess there is not much to do then. Do you have any suggestions on alternatives? I'll test to split the optimization (2 x 15 instead of 1 x 30) and merge the results, but I am not sure that will be better than my current solution (as it is not a "global" optimization). Also I don't like not knowing if I will fall off a phase transition cliff or not :-)

Long term I need to educate myself (not to become a specialist but to be able to make more informed decisions, this has been frustrating lol). Short term I have switched back to my homegrown scheduler (which I guess can be called a "brute-force version of rectangle packing"...).

I use this to schedule EVs for charging and the schedule (plan) is updated every time a vehicle connects/disconnects from a charger (there are other triggers as well). So the solver must complete within a few seconds of work, with a "good enough" solution, and it must be deterministic in the sense that the same inputs always give the same output. The schedule is used to control the chargers in real time. I think the max number of vehicles will never exceed 50-ish in each plan.

Also I did learn a cool expression, "phase transition". I'll drop that in the next conversation at the coffee machine ;-)

[Laurent Perron]

You should use the cp-sat version with a time limit. 

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/476ee424-4aca-422a-a49f-bed71d3bc52an%40googlegroups.com.

[Laurent Perron]

And take the best solution found during that time.

[Torbjorn Backstrom]

Ok, that's a good point, I will try that going forward (and I'll run the homegrown version in parallell and collect stats over time and see how it all compares in the end).

I assume the best solution is the one that is returned when the time limit expires?

[Torbjorn Backstrom]

Also thank you for making the software available, code, documentation and all.

[Laurent Perron]

Side node. If your heuristic is fast, you can always use its output to hint the first solution of CP-SAT.

This way, the solver will always return a solution no-worse than your heuristics.

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

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/51023476-d160-4718-972a-12697c82d4e8n%40googlegroups.com.

[Torbjorn Backstrom]

That's really interesting. I remember you using that in "line_balancing_sat.py" that you mentioned before. I will definitely try that. Thanks.
Just have to get some sleep first lol.