Changing interval granularity from minutes to hours: Worth for performance?

[derkleinegauss5050]

Hello,

I am quite new in the field of Constraint Programming and CP-SAT (coming from MIP).

But I found out that for shift scheduling CP-SAT has nice modelling features (like non-overlap intervals for example..):

Right now I've got a model where (input) shifts and (input) employees can be allocated to each other.

Shifts are NOT "early", "late", "night" in buckets, but they all differ in length, start time and end time (in minutes from start of planning horizon).

For each employee, a shift is an optional interval with a presence variable.

Then each employee has some (optional) rest intervals. These are flexible in duration and start and end time. (But also in minutes again).

Then of course, the active rest intervals must not overlap with the active shifts for each employee..

This (minutes) is the "exact" modelling.

Now comes my question:

Is it worth to change from minutes to hours?
And what I mean is: Be on the safe side and round up and down such that each interval gets bigger (never smaller). Such that a solution for the hour model is always feasible for the minute model.

I would have thought, that this yields a (big?) performance boost. But my first tests do not confirm that. Perhaps I have still got some errors or some "minutes" left in the model, I will need to check.

But this leads me back to the "I am new in this field": Is this all really worth a try?
So: Its easier and more correct to model it with minutes. My hope was that restricting by using hours would lead to a significant perfomance boost by being a bit suboptimal.

Or are the decisions CP-SAT has to make still the same and the granularity does not hurt that much?

What would you say?

Thanks for your advice, I am happy to dig deeper into the CP-SAT world. ;)

[lperron]

I would go to 15 minutes granularity minimum. Performance will be improved but readability of the solution too, like you work until 11:03 on this, then 4 minutes break, then on something else for 7 minutes looks really bad.

[derkleinegauss5050]

Thanks for your answer.

For more clarity: The scheduling is for a whole month, so it is more like

• a shift on monday 10:23-18:51,
• then a rest time of around 12 hours and
• then the next shift on tuesday 7:10-17:11.
• and this for a whole month (with typically <= 1 shift per day and some larger rest times once per week)

Does this change what you feel about a good granularity? So changing the granularity is useful, right?
I know that this is my business to check the right value, but to get a feeling how CP-SAT works and what are directions worth to investigate i wanted to ask someone familar with CP-SAT... And I am happy that I have reached (a/the) right one. ;)

When you say 15 minutes minimum..
Do you mean 15 minutes or even 1 hour...
Or 15 minutes or even 1 minute granularity?

[CervEdin]

Shouldn't be too hard to benchmark different time granularities against each other.

That said, why would you want shifts like this?

a shift on monday 10:23-18:51

You know your use-case but I could see this level of shift scheduling not being appreciated and/or be appropriate in real-life.

[derkleinegauss5050]

Why should I take such a shift? Just because it is input and in this case my decision is not the timing but the allocation employees to already present shifts.

And my benchmarks do not show a speedup when switching to hours instead of minutes.

That somehow confused me. :)

But thanks to your replies.

[CervEdin]

FWIW, increasing the granularity of the shift durations will necessitate increasing the granularity of the decision variables.
The main problem is the risk that the search space explodes and/or the memory for all the values in the domain ballons.
If you don't see a difference, I'd guess that either your problem is small and/or is heavily constrained to start with.

I think another reason you don't typically model scheduling (or other problems) with extreme granularity is that it often doesn't make sense in the real world. Just think about how meetings are scheduled in calendar. If someone schedules a meeting with me between 12:07-12:23, I would find that weird. Another aspect is the stochastic nature of life, there's usually some built-in slack in a schedule for humans, where you don't expect things to start exactly on the minute. Ofc. there are probably situations where this doesn't apply. Like maybe scheduling train conductors or something where the schedules are much more granular.

I wasn't able to 100% understand your problem as I just skimmed through it.
But if you are wondering on the impact on performance, the best is to benchmark it yourself with your instances, to see the impact. I'd usually look at the total time to run, with a fixed seed (don't remember exactly how to do that), repeat a few times since there's non-determinism when you run CP-SAT w. parallel workers, check how many decision variables/constraints are generated, check how much memory is used and make an analysis based on that.

[lperron]

don't go for 1 min. 15 minute is the bare minimum. At the month level, maybe push to 30 minutes.