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

Question

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?

Answer 1

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}$.

Answer 2

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.

Answer 3

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

Answer 4

• 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

Answer 5

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).