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