Machine scheduling: Maintenance and maximum runlength

In [1] a problem is posed that deals with a maximum run-length (6 days) before the machine needs to be taken off-line for maintenance (1 day).  Consider the binary decision variable:

\[\color{darkred}y_t = \begin{cases} 1 & \text{if machine is online at period $t$} \\ 0 & \text{otherwise} \end{cases} \]

In [1] a scheme is proposed as follows. Introduce an integer variable \(\color{darkred}z_t\) that has the cumulative days the machine is running. Then apply the rule: 

if \(\color{darkred}z\gt 6\) then \(\color{darkred}y:=0,\color{darkred}z:=0\)

This approach needs a bit of repair to make it work for a MIP model. A MIP model can not contain assignments, and decision variables are part of a system of linear equations. I.e., all decision variables are essentially calculated at the same time (a notion which can be foreign for computer programmers who think in sequential assignment statements). We can write:\[\begin{align} & \color{darkred}y_t = 1 \Rightarrow \color{darkred}z_t  = \color{darkred}z_{t-1} + 1 \\ & \color{darkred}y_t = 0 \Rightarrow \color{darkred}z_t  = 0 \\ & \color{darkred}z_t \in \{0,\dots,6\}\end{align}\] This is in the form of implications that can be used directly with (advanced) solvers that support indicator constraints (i.e., a binary variable on the left and a linear constraint on the right). Note that we don't do anything special when \(\color{darkred}z_t\) becomes 7. We just forbid that from happening by setting an upper bound of 6. The initial value \(\color{darkblue}z_0\) is the number of periods the machine is already online at the beginning of the planning period. 

If your solver or modeling tool does not have support for indicator constraints, we can rewrite things as: \[\begin{align}& \color{darkblue}z_t^{up} := 6  \\ & \color{darkred}z_t \le \color{darkred} y_t \cdot \color{darkblue}z_t^{up}\\  & \color{darkred}z_t \le   \color{darkred}z_{t-1} + 1 \\ & \color{darkred}z_t \ge   \color{darkred}z_{t-1} + 1 - (1-\color{darkred}y_t ) \cdot (\color{darkblue}z_t^{up}+1)\\  & \color{darkred}z_t \in \{0,\dots,\color{darkblue}z_t^{up} \}\end{align}\] Here \( \color{darkblue}z_t^{up} =6\) is the upper bound on \( \color{darkred}z_t\). This formulation requires a little bit of thinking. Finally, I want to mention that \( \color{darkred}z_t\) can be declared as a continuous variable: it will be integer automatically. 

A simpler alternative formulation is to just forbid any sequence of 7 consecutive 1's for \(\color{darkred}y\). I.e. \[\color{darkred}y_t+\color{darkred}y_{t+1}+\color{darkred}y_{t+2}+\color{darkred}y_{t+3}+\color{darkred}y_{t+4}+\color{darkred}y_{t+5}+\color{darkred}y_{t+6} \le 6\] It may be easier to look backward: \[\color{darkred}y_t+\color{darkred}y_{t-1}+\color{darkred}y_{t-2}+\color{darkred}y_{t-3}+\color{darkred}y_{t-4}+\color{darkred}y_{t-5}+\color{darkred}y_{t-6} \le 6\] The terms \(\color{darkred}y_{t-k}\) can have a non-positive index \(t-k\) which means this is historic data, from before our planning period. In other words \(\color{darkblue}y_0,\color{darkblue}y_{-1},\color{darkblue}y_{-2},\dots\) is data.

Conclusion

This is a good example where we can achieve the same result using two very different approaches. It may make sense to choose the simplest formulation.

References

1. Linear Programming - Re-setting a variable based on it's cumulative count, https://stackoverflow.com/questions/64930027/linear-programming-re-setting-a-variable-based-on-its-cumulative-count