Does Timefold fit my Tiered Priority use Case?

[lepsch22]

Hey all, I'm fairly new to Timefold, and I was wondering if my use case is a good fit for it.

I have a use case where I need to deconflict a bunch of meetings for a client. meaning I would receive many meetings and I would need to produce a finalized meeting plan for the client. These meetings are very simple PlanningEntities with a vlauerange of PossibleIntervals for when the meeting can happen and a priority value. The @PlanningVariable would simply select one of these intervals.

I would be using an over-constrained problem with a HardMediumSoftScore, where the hard constraint ensures that no assigned meetings overlap. The medium constraint penalizes unassigned meetings as a factor of their priority.

constraintFactory.from(Meeting.class)
    .filter(meet -> meet.getTimeslot() == null)
    .penalize("Unassigned Meeting Penalty", HardMediumSoftScore.ofMedium(1),
        meet -> meet.getPriority());

However, this isn't quite the behavior I'm looking for. The priority on the meeting shouldn't be outscored additively by multiple lower-priority meetings. As my constraint works right now, a meeting with a priority of 2 could potentially be left unassigned if it overlaps with two or more meetings with a priority of 1. Ideally, the priority should work more like distinct tiers, where priority 2 should always outweigh any number of priority 1 meetings.

I looked into using BendableScore, but it seemed suitable only if I had a fixed number of priority tiers (e.g., six). In my case, the priority could theoretically range from 1 to any large number, so that solution didn't seem viable.

I've been struggling to think of an approach that would solve this. I tried a hard constraint that penalizes cases where a lower-priority meeting is scheduled while a higher-priority meeting is left unassigned. However, that approach failed in a scenario like the following:

We have three meetings: e1 (highest priority), e2 (second highest), and e3 (lowest priority).
e1 overlaps with e2, and e2 overlaps with e3.
Ideally, e1 should be scheduled over e2 because it has a higher priority. Similarly, e3 should be scheduled over e2, because e2 is blocked by something with an even higher priority, despite e3 having a lower priority than e2.

This situation is where I get stuck. I'm not sure if my use case is poorly suited for Timefold because the priority is more like a tiered system that shouldn't be volatile to penalties from lower-priority meetings. Alternatively, it could be that my use case is a good fit and I'm missing a key concept that would help me solve this problem.

Please feel free to ask for clarification if something doesn't make sense. Thanks!

[greyhairredbear]

Hi!

I think Timefold should be a good fit for your problem. For the hard constraint, you could introduce a shadow variable that keeps track on if a meeting is blocked by another meeting of higher priority. You then could check for this value when deciding whether you have a hard constraint violation or not. I'm not sure that this would be the computationally most efficient way, but it's an idea.

Maybe someone from the Timefold team has a better idea here :)

Another note: Is the number of priorities really arbitrary here in reality? How many meetings do you schedule? Could it be an acceptable simplification to limit the number of priorities to something that can be modelled with a bendable score?

[greyhairredbear]

Another idea: You could calculate beforehand for all intervals on your entities what intervals of meetings with higher priorities are conflicting. That is not going to change during planning, so you wouldn't have to do these calculations all over again when solving.

[TomCools]

It's often freedoms like this (almost endless tiers) which make modeling hard. In practice, I've not seen anyone go beyond 10 tiers (and that's already pushing it). Nobody is going to manage that many levels of priorities.

If you feel you need more tiers, there is often some other constraints hidden in there which you are trying to solve with priorities ex:

• Maybe you want higher tiers to assign a higher priority to meetings with more people?
• Maybe when a certain person is in the meeting, the priority should be higher?

[lepsch22]

Honestly this makes the most sense to me. There isnt a good way to do this idea of tiered priority, because it really is the job of the solver/constraints to figure out the priority. Because ideally we configure our constraints and weights to match what we do as a human to identify when something is higher priority. Seems like my "problem" is more of a problem relating to not having good enough constraints, so the priority is inherit in the solver.

[TomCools]

We see this all the time, where 1 form of constraints becomes a "funnel" through which other constraints are implicitly modeled. These are often called "priority" or "tags" or some other element which allows you to add more than it was designed to do.

Try to be more explicit in the constraints, it also allows you to put another weight on them. (constraint weight is what some people would refer to as "solver priority")

[greyhairredbear]

Because ideally we configure our constraints and weights to match what we do as a human to identify when something is higher priority

That's a good approach to look at it. I'd try to manually do a schedule (together with a domain expert if that's possible) and find out what kind of constraints I might have been missing. What's also very nice when being more explicit with your constraints (as Tom put it) is that you also get the benefit of a better explanation of your score (via constraint matches and indictments). Which you then can use to get hints on how to improve your model by comparing the score explanation of your desired solution to the current result of your model.