Binary integer LP problem

Question

Joe Henderson runs a small metal parts shop. The shop contains three machines – a drill press, a lathe, and a grinder. Joe has three operators, each certified to work on all three machines. However, each operator performs better on some machines than on others. The shop has contracted to do a big job that requires all three machines.
The times (in minutes) required by the various operators to perform the required operations on each machine are summarized in the table below. Joe wants to assign one operator to each machine so that the total operating time for all three operators is minimized.
$$\begin{array}{c|c|c|} & \text{Drill} & \text{Lathe} & \text{Grinder} \\ \hline \text{Operator 1} & 18 & 22 & 35\\ \hline \text{Operator 2} & 30 & 41 & 28 \\ \hline \text{Operator 3} & 36 & 25 & 18 \\ \hline \end{array}$$

I defined binary variables $D_i, L_i, G_i$ where they represent the pairing of operator $i$ with each of the three machines.
Specifically, $$D_i = 1$$ if the operator is on that machine and $$D_i = 0$$ if the operator is not on that machine.

So far, my constraints using these binary variables are:

$$D_1 + L_1 + G_1 <= 1$$ $$D_2 + L_2 + G_2 <= 1$$ $$D_3 + L_3 + G_3 <= 1$$ $$D_1 + D_2 + D_3 >= 1$$ $$L_1 + L_2 + L_3 >= 1$$ $$G_1 + G_2 + G_3 >= 1$$

My concern is finding the relationship between the numerical hours and the logical relationship of one operator per machine and one machine per operator. Any insights?

Answer 1

In general I would prefer double indexed variables. This has the advantage, that you can use the sigma sign.

$x_{ij}=\begin{cases} 1, \ \texttt{if operator i is assigned to machine j} \\ 0, \ \texttt{else} \end{cases}$

$t_{ij}:$ Operating time of operator i and machine j.

$i,j \in \{1,2,3\}$

Every machine is assigned to exact one operator

$\sum_{j=1}^3 x_{ij}=1 \quad \forall i$

This is corresponds to your three first constraints, except the equality-sign. It doesn´t makes sense, that a machine has no operator.

Every operator is assigned to exact one machine

$\sum_{i=1}^3 x_{ij}=1 \quad \forall j$

The objective function has to be minimized. You have to sum up all operating times. The opterating times are linked to the binary variables by multiplication.

$\texttt{min} \ \ \sum_{i=1}^3 \sum_{j=1}^3 t_{ij} \cdot x_{ij}$

The explicit form of the objective function is

$18\cdot x_{11}+22\cdot x_{12}+35\cdot x_{13}+30\cdot x_{21}+ 41\cdot x_{22} + 28\cdot x_{23}+ 36\cdot x_{31}+ 25\cdot x_{32}+ 18\cdot x_{33}$

Answer 2

Your restrictions already address the requirements

1. Each machine must be operated. This is represented by the restrictions of the form $D_1+D_2+D_3 \ge 1$ (at least one of the $D$'s must take on the value $1$).

2. Each operator must be assigned to only one machine. This is represented by the restrictions of the form $D_1+L_1+G_1 \le 1$ (at most one of the variables related to the same operator can take on the value $1$).

What remains is to express what you want to minimize in terms of your decision variables. In this case, you must minimize the total operating time $T$.

This is how you go about defining $T$. If you choose to assign operator 1 to the drill, the total operating time (which I interpret to be the sum) will increase by $18$, but it won't increase by that amount otherwise. In other words, the value of $D_1$ will trigger the addition of $18$ minutes: the total time is affected by $18 D_1$.

Following this way of reasoning, an appropriate expression for the total time is $$T = 18D_1 + 22 L_1 + 35G_1 + \dots + 36D_3 +25L_3+18G_3.$$