Need help figuring out a planning/assignment problem

I'm looking to solve this planning problem. Any pointers or ideas are much appreciated!

You have a number of i individuals i = { 1, 2, ..., n } that need to perform tasks. Tasks are performed in teams, with a fixed and given amount of required individuals per task (2,3 or 4). For each individual it is known which tasks need to be performed how many times in the course of a year. So the crutch of the problem is figuring out a yearly planning such that each individual has performed each required event (task) at least a fixed amount of times. This makes it a minimization problem of the amount of times the combined group of individuals participate in executing a task. One participating individual for each of the planned teams has the cost of 1.

To complicate the problem we have the next constraints

Each individual has one fixed out of three possible ranked qualifications, let's call them: q1 > q2 > q3. A task requiring a team of 2 needs to be performed by a team with at least 1 member having at least a q2 qualification. A task requiring a team of 3 or 4 individuals needs to be performed by a team with at least 1 member having a q3 qualification and at least 1 member with a q2 qualification. Other team slots can be filled up by any other individuals.

Tasks can be performed two times a day on a given amount of machines. A task requires the machines to be in a certain configuration. The configurations of these machines throughout the year is given. One individual requires one machine (hence the cost of 1 per participant). There are no restrictions on which machine the individual utilizes. Machine configurations can be shared by several tasks such that during a period where machines have a certain configuration set up, a collection of tasks that share the same required configuration can be executed.

Each task has the same duration, which is 1 time unit. Of which there are 2 every day.

Each individual has a given availability roster for each of the two time units a day during the whole year. The individual can also only participate in 1 team executing 1 task during each time unit.

Example:

Collection P = {p1, p2, p3, p4, p5} are the individuals. The values of these numbers represent their qualification. p1=q1, p2=q2, p3=q2, p4=q2, p5=q3 Tasks J = {j1,j2,j3} are the tasks with the value of their required amount of machines operated by individuals. So j1=2, j2=3, j3=4 Requirements R = {r1,1, r1,2, r,1,...,..., r1,n, r2,1,... rm,n} are the required amount of times each individual needs to participate in a team, executing the several tasks So if r1,1=2 then individual p1 has to participate in a team executing task j1 at least 2 times during the year.

This can be solved using a greedy approach, doing day by day planning. By suboptimal planning however you get teams executing tasks for the requirement of only 1 team member, inducing extra cost. Also due to the availability of individuals their task scheduling should be skewed towards their availability.

I've been searching a lot for a similar problem formulation without success unfortunately. It's a fun challenge that I've been trying to crack for a while now. I'm very curious to see what the community comes up with.

I have attempted to form this into a minimize cost flow problem, however that does not seem feasible. This because we need to combine individuals into teams, but each individual has their own task completion requirement to meet.

It is possible to formalize as a Mixed Integer Programming (MIP) problem, which does the trick for rather small input sizes. But for a yearly planning of roughly 30 individuals, 7 different tasks and about 8 required for each task and individual combination the problem size gets quite out of hand. I can provide the MIP functions if anybody is interested to see, but would like to keep everyone's perspective as open as possible initially.

Edit: For an approach that I've tested out I've split the problem into two parts. First, combine individuals with their qualifications and tie them to tasks such that each individual accomplishes the required amount of task executions. So the first MIP minimizes the following: $$\min\sum_{c}\sum_{m}X_{c,m} + \frac{1}{10}U_{c,m}$$

Where c stands for a combination of individuals and m is a task. U is a penalty value.

Then the constraints: Ensure that each individual (p in combination c) performs their required amount of tasks yearly. $$\sum_{c \in C_p}X_{c,m} \geq M_{p,m}\ \forall\ p,m$$

I use the penalty variable to ensure combinations of individuals are mixed up $$X_{c,m} - U_{c,m} \leq 1\ \forall\ c,m$$

Then the second part actually attempts to "schedule" the task & individual combinations that are selected by the first MIP. This minimization is focused on the aesthetic of the schedule. Any solution that is found is one that can be worked with.

Objective: w is a time slot and t is a selected individuals & task combination. The penalty variable P in my tests are incremented by 1 for each sequential timeslot. So the MIP solver attempts to finish the schedule as soon as possible. $$\min\sum_{w}\sum_{t}X_{w,t} P_w + U_{w,t}$$

The constraints: To ensure that individuals aren't selected more than once per time slot $$\sum_{t}a_{p,t} X_{w,t} \leq 1\ \forall\ p,w$$

Don't select more individuals than that there are machines to utilize. In this example, only 4 machines are available in each timeslot. $$\sum_{t}X_{w,t} . T_{t} \leq 4\ \forall\ w$$

Make sure each task individual combination is selected in the yearly schedule $$\sum_{w}X_{w,t} = 1\ \forall\ t$$

I've also added a constraint to make sure to penalize if an individual is scheduled in both time slots on a given day. It is allowed but not preferred. $$\sum_{w1,w2}X_{w,t} - U_{w,t} \leq 1\ \forall\ p, day$$

What happens with Google's OR-Tools (single thread solver) MIP solver is that it takes longer than at least half an hour to come up with solutions. I believe that it's largely due to the large amount of symmetry in the solution space.

• MIP is the obvious approach. Have you tried a MIP solver on this, or are you just assuming it won't work based on the number of constraints? Also, some MIP solvers have a way to give you the best solution found so far after a certain amount of time; that would be a reasonable way to deal with the complexity. The problem is complex enough I doubt there's going to be a clean algorithm. – D.W. Aug 10 '18 at 16:31
• I did indeed implement it and used a MIP solver in several variants. You can approach this as a massive problem with all the constraints. But then the problem is huge and unmanageable. Even with a time limit. I believe this is for a large part due to the symmetry of the solution space... Splitting up the problem seems like the way to go. Maybe we could zoom in on individual availability and design a good measure for it? Such that determining which individual should have "priority" at a certain time slot would be more manageable. What do you think? Thanks very much for your considerations! – Mike Aug 11 '18 at 21:50
• Maybe you can edit the question to show what variables you defined in your MIP formulation; that might let us see whether we have any ideas for improvement on that front. Also, when you run it with a time limit, what happens? – D.W. Aug 12 '18 at 3:42
• I've edited the question. Thanks again for thinking about it with me. Apologies for the late reply. – Mike Aug 16 '18 at 12:45