# Formulation of Assignment problem as integer programming

We need to maintain as quickly as possible a complex system. In particular, we need to replace six of its components $$\{P_1,\ldots,P_6\}$$. We have three 3D printers $$\{M_1,M_2,M_3\}$$ which we can use to fabricate the six components. The following table/matrix states how long it takes (in minutes) the $$i$$th printer to print the $$j$$th component:

$$\begin{array}{ccccccc} \hline & P_1& P_2&P_3&P_4&P_5&P_6 \\ \hline M_1 & 23 & 42 & 12 & 32 & 47 & 60\\ M_2 & 25& 37& 13& 37& 51& 64\\ M_3 & 27 &51 &15& 41 &57 &55\\ \hline \end{array}$$

The complex system will work again only when all the components have been printed. Clearly more components can (and have to be) assigned to single machines and they are made in a sequence, one after the other, and 3D printers can work in parallel. However, you have only two operators and therefore you can only use two machines. How to formulate the problem as a linear (but combinatorial) optimization problem to allocate components to (two out of three) 3D printers so that the maintenance time is minimized.

So far I have tried the following, but I am not quite sure (Please I need help if I was mistaken):

Let $$x_{ij}= 1$$ if machine $$i$$ is assigned to component $$j$$, $$0$$ otherwise. The model is \begin{align}\min&\quad23x_{11}+42x_{12}+...+55x_{36}\\\text{s.t.}&\quad x_{11}+x_{12}+x_{13}+x_{14}+x_{15}+x_{16} = 2\\&\quad x_{21}+x_{22}+x_{23}+x_{24}+x_{25}+x_{26} = 2\\&\quad x_{31}+x_{32}+x_{33}+x_{34}+x_{35}+x_{36} = 2\\&\quad x_{11}+x_{21}+x_{31} \ge 1\\&\quad x_{12}+x_{22}+x_{32} \ge 1\\&\quad x_{13}+x_{23}+x_{33} \ge 1\\&\quad x_{14}+x_{24}+x_{34} \ge 1\\&\quad x_{15}+x_{25}+x_{35} \ge 1\\&\quad x_{16}+x_{26}+x_{36} \ge 1\\&\quad x_{ij}\,\,\text{is binary}.\end{align}

• "The complex system will work again only when all the components have been printed." Does that mean you'd like the system to end as soon as possible? (Thinking of the objective function here). Besides this, I think this could better be formulated as a scheduling problem on parallel machines, with the additional constraint that only 2 of the 3 machines are used. Jul 2 '20 at 13:37
• The Generalized Assignment Problem can serve as inspiration to continue, it's the same you are doing but change the first 3 constraints where every machine is made to print 2 components. First of all, the objective function is total working time of the machines. Instead you want to minimize the makespan (maximum time to finish all jobs), so that system can work again as soon as possible. Second, you may add binary variables $z_i = 1$ if machine $i$ is used, with additional constraints for $\sum_i z_i = 2$ and linking $x$ and $z$. Jul 2 '20 at 15:30
• Are you assuming that one machine will never be used, or that operators will move among machines such that all machines might be used at some point, but never more than two running at any given time? Jul 2 '20 at 15:57
• @user3752, as dhasson mentioned, it sounds like a parallel machine scheduling problem. Would you see this link? Jul 3 '20 at 10:41

Since you mention that you want to operate two out of three machines, it boils down to a problem where you first pick two machines and then perform a standard $$R2||C_{\max}$$ parallel machine scheduling problem with the two machines that you selected. Such problems are very suitable for dynamic programming/column generation approaches, but your instance is so small that a IP will work fine. And since you ask for an IP, let us consider a straightforward way to model it.
For a formulation, consider the following decision variables: $$y_j = \left\{ \begin{array}{ll} 1 & \mbox{ if } M_j \mbox{ is being operated } \\ 0 & \mbox{otherwise} \end{array} \right.$$ and $$x_{ij} = \left\{ \begin{array}{ll} 1 & \mbox{ if } P_i \mbox{ is made on } M_j \\ 0 & \mbox{otherwise} \end{array}\right.$$ Also, let's assume that $$a_{ij}$$ is the time needed to produce $$P_i$$ on $$M_j$$.
Now the following IP can be formulated: $$\begin{array}{llll} \min & z \\ \mbox{s.t.} & \sum_{j} y_j & \leq K \\ & \sum_{j} x_{ij} & = 1 & \forall i \\ & x_{ij} & \leq y_j & \forall i \forall j \\ & \sum_i a_{ij} x_{ij} & \leq z & \forall j \\ & x_{ij} \in \{0,1\} & & \forall i \forall j \\ & y_j \in \{0,1\} & & \forall j \\ & z \in \mathbb{R} \end{array}$$ Where the objective variable $$z$$ represents the makespan, the first constraint states that at most $$K$$ machines can be used (in your instance, $$K=2$$, i.e. $$K$$ is the number of operators), the second constraint states that each $$P_i$$ must be executed on exactly one $$M_j$$, the third constraint states that a $$P_i$$ can only be produced on a $$M_j$$ if that $$M_j$$ is being operated and the fourth constraint states that the makespan $$z$$ should be at least the time spent on each individual machine.