# Dividing machines into groups of equal sizes so that each group has approximately same productivity

I have set of machines with varying productivity.

I want put the machines in different groups so that the groups have approximately equal productivity.

Lets say, we have $$M$$ machines.

and we want to divide them into $$G$$ groups of equal size.

Size of a group, $$S=M/G$$.

The productivity of machine $$m$$ is given by $$P_m\ge 0$$ (some machine may have zero productivity).

What is an easy LP formulation?

$$\textbf{Tried...}$$

Let $$x_{g,m}$$ be a binary indicator. If $$x_{g,m}=1$$, machine $$m$$ belongs to group $$g$$.

So, we have $$\sum_{m=1}^Mx_{g,m}=S, \forall g$$

The productivity of group $$g$$ is given by

$$T_g=\sum_{m=1}^MP_m*x_{g,m},\forall g$$

I prefer $$T_1\approx T_2 \approx T_3 \approx \cdots\approx T_G$$

What would be a good objective function?

Let $$\phi$$ is a variable.

$$\phi=\frac{T_a}{T_b}$$

maximize $$\phi$$?

I am looking for an efficient implementation...

$$\bf{EDIT}$$

All the solutions proposed are hard to solve. I am rather looking for some greedy heuristic approach to solve this problem.

This is what I have tried so far...

1. Choose $$G$$ machines (machines with the G largest productivity) as the group head.

2. Then I follow an iterative steps for the the remaining $$M-G$$ machines. For a given machine, it is attached to a group that has the smallest productivity.

Do you think it a good heuristic?

Any suggestion with better heuristic?

• Please provide the data for your 21-machine example. Jan 20, 2022 at 13:30
• @RobPratt you can generate the productivity of individual machines with integer $I, 0\le I\le 10$. I have 21 machines. The group size is 3. So, there will be 7 groups.
– KGM
Jan 20, 2022 at 14:32
• When I generate random uniform productivity in [0,10] for 21 machines and specify group size 3, the min-max, max-min, and min range MILP formulations all solve instantly. Jan 20, 2022 at 15:55
• @RobPratt I am using MOSEK to solve. I am not sure if my implementation is incorrect. Would you please share your script here or at [email protected].
– KGM
Jan 20, 2022 at 16:04
• Your question sounds like Fermat-Torricelli-Steiner Problem ... Jan 20, 2022 at 17:30

Here are two ideas:

1. Minimize $$\max_g T_g$$. This will naturally even out the productivities of each group. To do this you can minimize a variable $$z$$ and add the constraint $$z \ge T_g \; \forall g$$.
2. Add constraints $$T_{min} \le T_g \le T_{max}$$ where $$T_{min}$$ and $$T_{max}$$ are lower and upper bounds on $$T_g$$, respectively. You will have to determine a "good" set of values for these parameters, by iteratively tweaking them.

You could try and mix both approaches. Try the first one, and use the value of the objective function for $$T_{max}$$. If the values are not evened out enough, iteratively increase $$T_{min}$$.

• Or make $T_\min$ and $T_\max$ variables and minimize the range $T_\max-T_\min$. Jan 19, 2022 at 13:57
• aha yes, that is even better. thanks for the tip Jan 19, 2022 at 14:11
• Or maximize $T_\min$. Jan 19, 2022 at 17:09

By request, here's the SAS code I used for three different objectives (the first two are commented out with /* and */ delimiters):

proc optmodel;
num numMachines = 21;
num groupSize = 3;
set MACHINES = 1..numMachines;
set GROUPS = 1..numMachines/groupSize;
call streaminit(1);
num p {MACHINES} = rand('INTEGER',0,10);
print p;

var X {MACHINES, GROUPS} binary;
con OneGroup {m in MACHINES}:
sum {g in GROUPS} X[m,g] = 1;
con Cardinality {g in GROUPS}:
sum {m in MACHINES} X[m,g] = groupSize;
impvar GroupSum {g in GROUPS} = sum {m in MACHINES} p[m]*X[m,g];
/*   min MinMax = max {g in GROUPS} GroupSum[g];*/
/*   max MaxMin = min {g in GROUPS} GroupSum[g];*/
min Range = max {g in GROUPS} GroupSum[g] - min {g in GROUPS} GroupSum[g];

solve linearize;
print X;
print GroupSum;
quit;


Note that the LINEARIZE option in the SOLVE statement automatically performs the linearization that other answers have already described explicitly.

• thanks. I modeled exactly in the same way. But still my solver is taking too much time!'
– KGM
Jan 20, 2022 at 19:56

This is a well-known problem with existing heuristics: https://en.wikipedia.org/wiki/Multiway_number_partitioning

Edit: For partitioning into groups of limited sizes (eg. $$S_{max} \le M/G+1$$) see https://en.wikipedia.org/wiki/Balanced_number_partitioning

and in the special case of partitioning into groups of $$S \le 3$$ see: https://en.wikipedia.org/wiki/Balanced_number_partitioning#Balanced_triplet_partitioning

– Community Bot
Jan 20, 2022 at 17:04
• Minimize the greatest $$T_g$$:

\begin{align}\min&\quad T_\text{max}\\&\quad T_g \le T_\text{max} \qquad \forall g\end{align}

The drawback is that it will minimize $$T_g$$, and maybe it is not what you want

• As @RobPratt suggested in the comments, minimize the difference between the greatest and the smallest $$T_g$$:

\begin{align}\min&\quad T_\text{max} - T_\text{min}\\&\quad T_g \le T_\text{max} \qquad \forall g\\&\quad T_g \ge T_\text{min} \qquad \forall g \end{align}

The drawback is that it might be harder to solve

Let $$\overline{P}$$ be the average (mean) productivity of all machines. The average productivity of a group will be $$S\overline{P}$$. Let $$y_g$$ be nonnegative variables defined by the constraints $$y_g \ge T_g - S\overline{P}$$ and $$y_g \ge S\overline{P} - T_g$$ for all $$g$$. In the solution, $$y_g$$ will be $$\vert T_g - S\overline{P}\vert$$. You can minimize $$\sum_g y_g$$ or $$\max_g y_g$$. You can also minimize $$\sum_g y_g^2$$.

Addendum: If a heuristic is desired, one possibility is a permutation-type genetic algorithm. Each chromosome is a permutation of $$1,\dots,M$$. You decode a chromosome $$x$$ into a solution by making one group with machines $$x_1,\dots,x_S$$, the next group with machines $$x_{S+1},\dots,x_{S+G}$$, and so on. Use whichever criterion you like as the fitness value (with the understanding that you want to maximize, not minimize, fitness).

• all of the solutions are very hard to solve. I believe greedy heuristic would be better. I have 21 machines and productivity of the machines lie within [0 10]. The group size is 3.
– KGM
Jan 20, 2022 at 12:12