Problem with defining the proper planning entity

[jbarus]

Hi,

I'm currently working on a side project and need some advice because every approach I take leads to a dead end. My task is to assign clerks and applicants to committees. My input data is a list of clerks, where each entry consists of personal data such as first and last name, the ability to lead a committee, available time slots, preferred time for one applicant, and a list of applicants who need to be in this person's committee. A single entry should look something like this:

Clerk 1:

First name: John
Last name: Doe
Can lead committee: Yes
Available time slot: 11:00 AM - 3:00 PM
Preferred time per applicant: 30 minutes
Applicants that must be in this clerk's committee: John Q. Public

And so on. I also have a list of applicants, which is a lot simpler and consists of just their first and last names. The basic task is to assign them to committees, each consisting of three clerks (this should be configurable, but for simplicity, we can skip that for now) and a list of applicants. The main constraints are:

• Clerks must work only within their designated time slots (start time < number of applicants * time for one applicant < end time).
• Clerks may prefer to work with specific colleagues.
• Clerks may prefer to avoid certain people in committees.
• At least one clerk who can lead a committee must be present.
• The time for one applicant may vary, and the longest time in the committee should be chosen.

This sums up the problem definition, and here’s why I’m struggling with it. The committee should look something like this:

Committee 1:

Clerk 1: Alick Isbell, Can Lead: Yes
Clerk 2: Domenic Bramall, Can Lead: No
Clerk 3: Codie McPhaden, Can Lead: No
Applicants: Stanislas Caldero, Kahlil Beathem, Gwenneth Mohan, Celestina Karby (must be in Alick Isbell's committee), Farica Devey (must be in Domenic Bramall's committee), Jeffrey Paradine (must be in Alick Isbell's committee)

The main problem is that I can't figure out a proper way to form these committees. Every approach I take fails sooner or later.

To begin with, I started with a list as a planning variable. This way, I could have dynamic committee sizes and attach applicants to their clerks, then fill any remaining free time with those who don’t have specified clerks. I realized pretty quickly that a list variable isn’t suitable for this. If any clerk with many applicants ends up at the beginning of the list, the solution will break due to time constraints and won’t find a feasible one.

My next idea was to use three planning variables, but I think that’s pretty inefficient. Each variable would have its own list of possible clerks, which would dramatically increase the complexity of the problem. This is because I would need to triple the number of variables and implement additional checks to ensure that clerks aren’t duplicated. I also thought of assigning each applicant to a committee, but that seemed even more complex.

Now I’m wondering if this problem can be solved with Timefold without resorting to additional calculations or duplicating unnecessary facts. Do any of you know of a possible solution to my problem? I’m not asking for a ready-made solution, but any guidance on how to approach this would be greatly appreciated. I noticed that the Timefold section of Stack Overflow is quite inactive, so I decided to ask here. If anything is unclear, I can explain it further because I could really use some help. I also don't think that any piece of code would help because this problem is more of a conceptual one

[triceo]

Hello!

To begin with, I started with a list as a planning variable. This way, I could have dynamic committee sizes and attach applicants to their clerks, then fill any remaining free time with those who don’t have specified clerks. I realized pretty quickly that a list variable isn’t suitable for this. If any clerk with many applicants ends up at the beginning of the list, the solution will break due to time constraints and won’t find a feasible one.

List variable is the wrong choice here, because the list is used to define a "happens-before" relationship. Unless you're trying to model a situation such as a vehicle delivering packages customers, do not use list variable for this.

My next idea was to use three planning variables, but I think that’s pretty inefficient. Each variable would have its own list of possible clerks, which would dramatically increase the complexity of the problem. This is because I would need to triple the number of variables and implement additional checks to ensure that clerks aren’t duplicated. I also thought of assigning each applicant to a committee, but that seemed even more complex.

This would probably be the way I'd go. As you say, it introduces some inefficiencies, but those can be mitigated by either selection filtering, custom moves or a combination of the two. Wrt. assigning applicants, value ranges on entities may help. You can write it so that only the applicable values are chosen.

Now I’m wondering if this problem can be solved with Timefold without resorting to additional calculations or duplicating unnecessary facts. Do any of you know of a possible solution to my problem? I’m not asking for a ready-made solution, but any guidance on how to approach this would be greatly appreciated.

I'm sure Timefold Solver can solve this problem, but with growing complexity of the domain, the amount of tweaks and sometimes even hacks you have to use will grow. The solution with three variables will likely work, but the effort to get there will be significant. Whether some other tool can help here, that depends - if the data set size isn't to bad, maybe some exhaustive algorithm will work?

I noticed that the Timefold section of Stack Overflow is quite inactive, so I decided to ask here.

Arguably both are exactly as active, because it is generally the same people answering both. :-)