Best algorithm for splitting up departments such that the least unique ones are assigned per day

Question

I have a collection of people who need to be assigned to one of 10 dates. Each person is in a specific department. The departments have vastly varying amounts of people (from ten to thousands). Each date can accomodate a set amount of people, let's say 5000. My task is to assign each person to a date such that the amount of departments participating that day is as small as possible AND as average as possible. Basically every time you put a new department in a day it adds a lot of overhead (adding people doesn't) which means that doing a lot of departments in a single day is really bad. So for example, 1 huge department being assigned day 1 and 15 small ones being assigned day 2 is undesirable, it's better to do half of department 1 one day, and half on the other and then splitting the small ones such that its basically 7.5 one day and 8.5 on the other. But the less departments particpating in a day, the better. So if you had 3 days and 3 equal departments it would be undesirable to have 3 departments (1/3 of the employees of that department) participating each day, it would be better to have each department on a single day. The 'spots' have to be filled up, that is each day MUST have 5000 participants. Any ideas on how to approach this?

My first thought is to minimize the maximum, that is find a solution such that the highest amount of departments per day is the lowest it can be. Is this the best solution?

Answer 1

The first problem to solve is defining the problem.

In general, you have an optimisation problem. What you have not yet defined is the objective function, meaning what you want to optimise (precisely).

Based on what you describe, you might define the objective function as the max number of participants, but this is not great since for example a solution (2,2,5) (2 departments on day 1, 2 on day 2, 5 on day 2) is equal to a solution (1,1,5); such an objective function doesn't distinguish, e.g., unnecessarily splitting two departments over the first two days.

Another option is sum, but that does not help in the case of distinguishing (1,15) and (7.5,8.5).

Perhaps another option that seems to go in the direction you want is to minimise, for example, the sum of the squares, which prefers (1,1,5) over (2,2,5) and (7.5,8.5) to (1,15). But why raise to the power of 2 and not some other value greater than 1?

These are all application-dependent choices that you have to make.

---

The second problem is the difficulty. You have many options and you want to find the best option according to your objective function. Your general problem is an NP optimisation problem, so you may need to consider approximations. But again, the need to consider approximations depends on the size of your data, the values you choose, how you define the optimisation function, what is the relative cost of computation versus the cost of not finding an optimal solution, and so forth.

So after you define your objective function, you will need to think about what sort of approximation (if any) is cost effective.