12
$\begingroup$

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?

$\endgroup$
5
  • 1
    $\begingroup$ Please provide the data for your 21-machine example. $\endgroup$
    – RobPratt
    Jan 20 at 13:30
  • $\begingroup$ @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. $\endgroup$ Jan 20 at 14:32
  • $\begingroup$ 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. $\endgroup$
    – RobPratt
    Jan 20 at 15:55
  • $\begingroup$ @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 dipak.narayanan@gmail.com. $\endgroup$ Jan 20 at 16:04
  • $\begingroup$ Your question sounds like Fermat-Torricelli-Steiner Problem ... $\endgroup$ Jan 20 at 17:30

5 Answers 5

13
$\begingroup$

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

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

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.

$\endgroup$
2
  • $\begingroup$ thanks. I modeled exactly in the same way. But still my solver is taking too much time!' $\endgroup$ Jan 20 at 19:56
  • $\begingroup$ Please edit your question to include your code and log. $\endgroup$
    – RobPratt
    Jan 20 at 19:57
6
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center. $\endgroup$
    – Community Bot
    Jan 20 at 17:04
5
$\begingroup$
  • 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

$\endgroup$
4
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ Jan 20 at 12:12
  • $\begingroup$ please see my edit. $\endgroup$ Jan 20 at 12:23
  • 1
    $\begingroup$ I tried your heuristic (which is very fast) against a couple of GA variations (one based on minimizing the range of group values, the other minimizing the mean squared deviation). The GAs outperformed your heuristic, but your heuristic was not bad. For instance, in one run your heuristic had a spread of 2.476 between most and least productive group, where the first GA had a spread of 2.009. $\endgroup$
    – prubin
    Jan 24 at 17:42
  • 1
    $\begingroup$ It turns out my experimental results for minimizing range or MSD may not be meaningful. I tried minimizing the mean absolute deviation (MAD), which is more sensitive to inequality among groups, using the proposed heuristic, a GA and a MIP model (yielding a provably optimal solution). The MAD of the heuristic was around six times the optimal MAD in multiple runs. The GA did a bit better, but still tended to have an MAD around twice the optimal value. $\endgroup$
    – prubin
    Jan 24 at 22:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.