## Wednesday, June 7, 2017

### Minimum down- and up-time

In machine scheduling models we sometimes want to impose minimum up-time and minimum down-time restrictions. E.g., from (1):

My question is how do I add in additional constraints that if the factory switches off then its needs to stay off for 3 months, and if it switches back on then it needs to stay on for 4 months?

One possible solution is the following. Let us define our binary decision variable by

 $x_{i,t} = \begin{cases}1 & \text{if factory i is operating in month t} \\ 0&\text{otherwise} \end{cases}$
##### Method 1

We really want to forbid short run patterns such as 010 (i.e. off-on-off), 0110, 01110 and 101, 1001. Forbidding patterns 010, 0110, 01110 will ensure a factory is up at least 4 consecutive periods. By not allowing 101,1001 we really make sure that a down time period is at least three months. We can model these restrictions in a linear fashion as follows (2):

 Forbid 010 $$-x_{i,t}+x_{i,t+1}-x_{i,t+2}\le 0$$ Forbid 0110 $$-x_{i,t}+x_{i,t+1}+x_{i,t+2}-x_{i,t+3}\le 1$$ Forbid 01110 $$-x_{i,t}+x_{i,t+1}+x_{i,t+2}+x_{i,t+3}-x_{i,t+4}\le 2$$ Forbid 101 $$x_{i,t}-x_{i,t+1}+x_{i,t+2}\le 1$$ Forbid 1001 $$x_{i,t}-x_{i,t+1}-x_{i,t+2}+x_{i,t+3}\le 1$$
##### Method 2

A different approach is as follows. First define binary variables:

 \begin{align} &\delta^{\mathit{on}}_{i,t} = \begin{cases}1 & \text{if factory i is turned on in month t} \\ 0&\text{otherwise} \end{cases}\\ &\delta^{\mathit{off}}_{i,t} = \begin{cases}1 & \text{if factory i is turned off in month t} \\ 0&\text{otherwise} \end{cases} \end{align}

Mathematically we write this as:

 \begin{align} &\delta^{\mathit{on}}_{i,t} = (1-x_{i,t-1})\cdot x_{i,t}\\ &\delta^{\mathit{off}}_{i,t} = x_{i,t-1}\cdot (1-x_{i,t})\\ \end{align}

We can linearize these non-linear equations by:

 \begin{align} &\delta^{\mathit{on}}_{i,t} \le 1-x_{i,t-1}\\ &\delta^{\mathit{on}}_{i,t} \le x_{i,t}\\ &\delta^{\mathit{on}}_{i,t} \ge x_{i,t}-x_{i,t-1}\\ &\delta^{\mathit{off}}_{i,t} \le x_{i,t-1}\\ &\delta^{\mathit{off}}_{i,t} \le 1-x_{i,t}\\ &\delta^{\mathit{off}}_{i,t} \ge x_{i,t-1}-x_{i,t}\\ \end{align}

With these variables we can implement the implications:

 \begin{align} &\delta^{\mathit{on}}_{i,t} = 1 \implies x_{i,t} + x_{i,t+1} + x_{i,t+2} + x_{i,t+3} = 4 \\ &\delta^{\mathit{off}}_{i,t} = 1 \implies x_{i,t} + x_{i,t+1} + x_{i,t+2} = 0 \end{align}

This can be linearized as:

 \begin{align} & x_{i,t+1} + x_{i,t+2} + x_{i,t+3} \ge 3 \delta^{\mathit{on}}_{i,t} \\ & x_{i,t+1} + x_{i,t+2} \le 2 (1-\delta^{\mathit{off}}_{i,t}) \end{align}

Note that I dropped $$x_{i,t}$$ in both inequalities. These are already known from the definition of $$\delta^{\mathit{on}}_{i,t}$$ and $$\delta^{\mathit{off}}_{i,t}$$.

In the comments it is mentioned by Rob Pratt that we can strengthen this a bit (the math does not look very good in a comment, so I repeat it here):

 \begin{align} & x_{i,t+1} \ge \delta^{\mathit{on}}_{i,t}\\& x_{i,t+2} \ge \delta^{\mathit{on}}_{i,t}\\& x_{i,t+3} \ge \delta^{\mathit{on}}_{i,t}\\& x_{i,t+1} \le 1-\delta^{\mathit{off}}_{i,t} \\& x_{i,t+2} \le 1-\delta^{\mathit{off}}_{i,t} \end{align}
##### References
1. How do I add a constraint to keep a factory switched on or off for a certain period of time in PuLP? https://stackoverflow.com/questions/44281389/how-do-i-add-a-constraint-to-keep-a-factory-switched-on-or-off-for-a-certain-per/44293592
2. Integer cuts, http://yetanothermathprogrammingconsultant.blogspot.com/2011/10/integer-cuts.html