0

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}

marvelfab12
  • 69
  • 6
  • 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$. – RobPratt Jun 11 '23 at 17:52
  • @RobPratt I added my approach but it is not linear. – marvelfab12 Jun 12 '23 at 12:05
  • I changed it. Sorry my bad, I used the wrong indices – marvelfab12 Jun 13 '23 at 16:22
  • 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$? – marvelfab12 Jun 13 '23 at 17:50
  • 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. – RobPratt Jun 13 '23 at 18:26
  • You might wanna have a final look at the constraints now. Do these now work? This leaves the problem of forcing $w_{ptm}=0$ still open however. – marvelfab12 Jun 13 '23 at 18:44
  • I had an error, now corrected. Your $j\in M$ should be $j\in M \setminus {m}$. – RobPratt Jun 13 '23 at 18:57
  • Thanks. I updated the code. Sadly it still doesnt work. Any other ideas? – marvelfab12 Jun 13 '23 at 19:47
  • After further testing, I updated my answer, and it seems to be behaving properly now. – RobPratt Jun 13 '23 at 20:41
  • Thanks it works. One final question. I already have the binary variable $r_{pt}$ which indicates whether a product was serviced on day $t$. Can i replace $x_{pt}$ with $(1-r_{pt})$, since $x_{pt}$ is the counterpart to $r_{pt}$? EDIT: I just tried and it also worked, but somehow the periods of the changes differ. Do you have an idea why? – marvelfab12 Jun 14 '23 at 11:07
  • Yes, you can replace $x$ with $1-r$ throughout. If there are multiple optimal solutions, even this slight modification can affect which one is returned by the solver. – RobPratt Jun 14 '23 at 11:29
  • I still have problem to identify for what $t\in T$ every constraint is defined. Would you mind adding it to all of them? My model still gets mixed up and indicates a change from $t=1$ till $t=2$ even though $d_{p1m}=0$ – marvelfab12 Jun 14 '23 at 12:05
  • Thank. Can this model then be considered LP or rather MIP? – marvelfab12 Jun 16 '23 at 15:22

1 Answers1

2

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

RobPratt
  • 32,006
  • 1
  • 44
  • 84
  • 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? – marvelfab12 Jun 12 '23 at 15:09
  • 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. – RobPratt Jun 12 '23 at 15:28
  • 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? – marvelfab12 Jun 12 '23 at 15:43
  • 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. – RobPratt Jun 12 '23 at 15:57
  • 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. – marvelfab12 Jun 12 '23 at 16:07
  • Yes, you can introduce $\gamma_{pt}$, and that sum constraint, and $\gamma$ will automatically take values in ${0,1}$ because $\sum_m d_{ptm}=1$. – RobPratt Jun 12 '23 at 17:13
  • Thanks, that means $\gamma_{pt}=1$ indicates a change in machine from the last time a a product was serviced by a machine and $\gamma_{pt}=0$ indicates there was no change, correct? – marvelfab12 Jun 12 '23 at 17:19
  • Yes, that is correct. – RobPratt Jun 12 '23 at 17:25
  • "formulation did not yield any success": Please be more specific about what went wrong, preferably with an explicit solution that satisfies the constraints but violates the intended behavior. – RobPratt Jun 13 '23 at 14:37
  • The prior comment since i accedentially deleted it. Unfortunately, the formulation did not yield any success for me. I came up with this formulation online (combined with the other thread) (see EDIT) and it works almost perfectly, except for one catch. Unfortunately, the constraints shown do not force $w_{ptm}=0$, so it still models a change. Which constraints do I need in addition. New: Well, i use the constraints in Gurobi but it lead to the model being infeasible. Do you have any ideas regarding on what to add to the constraints in the topic? – marvelfab12 Jun 13 '23 at 14:44