0
$\begingroup$

I have the following question / concern. I have a modeling problem with the decision variable $d_{ptm}$ which indicates whether product $p$ was serviced by machine $m$ in period $t$. It takes the value 1 if so, and 0 otherwise. A product can be serviced by different machine in different periods. In addition, a product may not be serviced for two days and then again, possibly by a different machine. I now want to introduce a binary variable $\rho$ that indicates such a switch in machines a product was serviced by. It should take the value = 1 if there was a machine switch from the last time a product was serviced till the current period. How can I model this? The constraints should not only create a lower bound, but also an upper bound. It should not be compared to the previous period, but to the time $t$ when the last time a product was serviced by a machine. In another thread I already found the solution for a switch compared to previous day, but I would like to have it compared to the last day with a machining. My idea would be to somehow remember the status, but I have no idea how to do it.

My constraints so far (adopted from post mentioned above): $$d_{ptm}-d_{p(t+1)m}\le\rho_{p(t+1)} \\ d_{ptm}+d_{p(t+1)m}+\rho_{p(t+1)}\le 2$$

EDIT: Model shift change using $w_{ptm}$: \begin{align} &d_{ptm}+\sum_{j \neq m} w_{ptj}\le \rho_{pt}+1~&\forall p \in P, m\in M, t\in\{2,\ldots,T\}\\ &w_{ptm}+d_{ptm}+\rho_{pt}\le 2~&\forall p \in P, m\in M, t\in\{2,\ldots,T\} \end{align} Definition of $w_{ptm}$: \begin{align} &w_{ptm}\ge d_{p(t-1)m}~&\forall p\in P, m\in M, t\in\{2,\ldots,T\} \\ &w_{ptm}\ge w_{p(t-1)m}-\sum_{j \in M\setminus\left\{ m \right\}} d_{p(t-1)j} ~&\forall p\in P,m\in M, t\in\{2,\ldots,T\}\\ &\sum_m w_{ptm} = 1 ~&\forall p\in P, t\in \{2,\ldots,T\} \end{align}

$\endgroup$
13
  • $\begingroup$ Hint: introduce a binary decision variable $s_{ptm}$ that indicates whether the last servicing of product $p$ in periods prior to $t$ was on machine $m$. $\endgroup$
    – RobPratt
    Jun 11, 2023 at 17:52
  • $\begingroup$ @RobPratt I added my approach but it is not linear. $\endgroup$ Jun 12, 2023 at 12:05
  • $\begingroup$ I changed it. Sorry my bad, I used the wrong indices $\endgroup$ Jun 13, 2023 at 16:22
  • $\begingroup$ Thanks, i updated my constraints. Why $\sum_t$ and not $\sum_m$? Doesn't it make more sense that there is only one last "service" over all machines? Whenever i use $\sum_t$ the Gurobi model gets infeasible, while using $\sum_m$ it generates a solution. But using $\sum_m$ still comes with the problem, that some of the $w$'s are 1 even though they are actually 0 leading the model to indicate more changes than there actually are. How to enforce $w_{ptm}=0$ whenever $d_{p,t-1,m}=0$? $\endgroup$ Jun 13, 2023 at 17:50
  • $\begingroup$ Yes, sorry. It should be $\sum_m$ for each $p$ and $t$, like in my answer. Your next-to-last constraint mixes $\sum_m$ and $\forall m$; compare to the last constraint in my answer. $\endgroup$
    – RobPratt
    Jun 13, 2023 at 18:26

1 Answer 1

2
$\begingroup$

Following my hint, introduce a binary decision variable $s_{ptm}$ that indicates whether the last servicing of product $p$ in periods prior to $t$ was on machine $m$. You want to enforce $$\rho_{ptm} \iff \lnot s_{ptm} \land d_{ptm},$$ equivalently, $$\rho_{ptm} = (1-s_{ptm}) d_{ptm},$$ which can be linearized in the usual way: \begin{align} \rho_{ptm} &\le 1-s_{ptm} &&\text{for all $p,t,m$} \\ \rho_{ptm} &\le d_{ptm} &&\text{for all $p,t,m$} \\ \rho_{ptm} &\ge (1-s_{ptm}) + d_{ptm} - 1 &&\text{for all $p,t,m$} \end{align}

It remains to enforce the definition of $s_{ptm}$. Let binary decision variable $x_{pt}$ indicate whether no service is performed for product $p$ at time $t$: $$\sum_m d_{ptm} + x_{pt} = 1 \quad \text{for all $p,t$} $$ You want to enforce $$s_{p,t+1,m} \iff d_{ptm} \lor (s_{ptm} \land x_{pt}),$$ equivalently, $$s_{p,t+1,m} = d_{ptm} + s_{ptm} x_{pt},$$ which can be linearized as follows: \begin{align} s_{p,t+1,m} &= d_{ptm} + y_{ptm} &&\text{for all $p,t\not=T,m$} \\ y_{ptm} &\le s_{ptm} &&\text{for all $p,t,m$} \\ y_{ptm} &\le x_{pt} &&\text{for all $p,t,m$} \\ y_{ptm} &\ge s_{ptm} + x_{pt} - 1 &&\text{for all $p,t,m$} \end{align}


It is worth noting that network modeling provides a powerful framework for multiperiod situations like this where you want to capture pairwise interactions between decisions. Let node $(p,t,m)$ represent servicing of product $p$ at time $t$ on machine $m$, and let a directed arc from $(p,t,m)$ to $(p,t',m')$ represent that product $p$ was serviced at times $t$ and $t'$ and no other times between $t$ and $t'$. Now a servicing schedule for product $p$ corresponds to a path in the network. Your $\rho$ variable is then a sum of arc variables for which $m\not= m'$.

$\endgroup$
12
  • $\begingroup$ Thank you very much. That was exactly what I was looking for. One last question. How do I force $\rho_{pt}=0$, like it was done in the mentioned thread? $\endgroup$ Jun 12, 2023 at 15:09
  • $\begingroup$ Glad to help. I made some corrections just now because my $\rho$ variable actually depended on $(p,t,m)$, not just $(p,t)$. The two $\rho_{ptm} \le$ constraints force $\rho_{ptm}=0$ when there is no switch to machine $m$. The sum $\sum_m \rho_{ptm}$, which will take a value in $\{0,1\}$, represents whether there was a switch to some machine or not. $\endgroup$
    – RobPratt
    Jun 12, 2023 at 15:28
  • $\begingroup$ Thank you. Would the same formulation be true if only $\rho_{p,t}$ were valid, that is, if only to show that the machine is different in day $t$. And $p'$ could be replaced with any character, correct? $\endgroup$ Jun 12, 2023 at 15:43
  • $\begingroup$ No, if you omit the $m$ index, the $\rho \ge$ constraint is correct but not the two $\rho \le$ constraints. Yes, $p'$ is just a dummy index, and you could instead use $q$, for example. $\endgroup$
    – RobPratt
    Jun 12, 2023 at 15:57
  • $\begingroup$ Is it then possible to formulate this relation also for $\rho_{pt}$? Or can I formulate $\sum_{m}^{}\rho_{ptm}=\gamma_{pt}$ and then $\gamma_{pt}$ is my switch indicator. Or would that not work because then the sum might not be either 0 or 1. So my primary concern is to find a binary variable that is only valid for $p$ and $t$, so to speak. If you could formulate this for me again, I would be infinitely grateful. $\endgroup$ Jun 12, 2023 at 16:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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