3
$\begingroup$

We need to maintain as quickly as possible a complex system. In particular, we need to replace six of its components $\{P1,...,P6\}$. We have three 3D printers $\{M1,M2,M3\}$ 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 & P1& P2&P3&P4&P5&P6 \\ \hline \text{M1} & 23 & 42 & 12 & 32 & 47 & 60\\ \text{M2} & 25& 37& 13& 37& 51& 64\\ \text{M3} & 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.

Model:

Minimize $23x_{11}+42x_{12}+...+55x_{36}$

subject to :

$$x_{11}+x_{12}+x_{13}+x_{14}+x_{15}+x_{16} = 2$$ $$x_{21}+x_{22}+x_{23}+x_{24}+x_{25}+x_{26} = 2$$ $$x_{31}+x_{32}+x_{33}+x_{34}+x_{35}+x_{36} = 2$$ $$x_{11}+x_{21}+x_{31} >= 1$$ $$x_{12}+x_{22}+x_{32} >= 1$$ $$x_{13}+x_{23}+x_{33} >= 1$$ $$x_{14}+x_{24}+x_{34} >= 1$$ $$x_{15}+x_{25}+x_{35} >= 1$$ $$x_{16}+x_{26}+x_{36} >= 1$$ $$x_{ij}=binary$$

Thanks in Advance!

$\endgroup$
  • 1
    $\begingroup$ "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. $\endgroup$ – dhasson Jul 2 at 13:37
  • $\begingroup$ 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$. $\endgroup$ – dhasson Jul 2 at 15:30
  • 1
    $\begingroup$ 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? $\endgroup$ – prubin Jul 2 at 15:57
  • $\begingroup$ @user3752, as dhasson mentioned, it sounds like a parallel machine scheduling problem. Would you see this link? $\endgroup$ – A.Omidi Jul 3 at 10:41
1
$\begingroup$

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.

If you want to allow operators to switch between machines, the problem becomes more complicated, as you need to make sure that both an operator and a machine is available when you produce an item; you probably need to keep track of both the operator and the machine resources in your model and define constraints to avoid conflicts for which you may or may not need to determine an order as well.

| improve this answer | |
$\endgroup$

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.