How to find the idle intervals in integer programming?

Question

I have a scheduling problem with one machine and one job. I defined a binary variable $z_t$ that is 1 iff the job is scheduled at time $t$ (the job can be served in multiple times that are not consecutive). I would like to find the intervals where the machine is idle.

For example, if the job is scheduled at $t=1$, $t=4$, $t=8$, and $t=11$, then the machine is idle between $t=2$ and $t=3$, which gives an interval of length $2$. It is idle between $t=5$ and $t=7$, which gives an interval of length $3$. And, it is idle between $t=9$ and $t=10$, which gives an interval of length $2$.

How can I write this using the variable $z_t$? Say, I would like to enforce a constraint that says that the machine must be idle for intervals whose length are shorter than a threshold?

Answer 1

To disallow an idle interval of length $k$, you want to enforce the logical proposition $$\neg \bigwedge_{t=s}^{s+k-1} \neg z_t,$$ equivalently, $$\bigvee_{t=s}^{s+k-1} z_t,$$ for each starting time $s$. You can do this via linear constraints $$\sum_{t=s}^{s+k-1} z_t \ge 1.$$

To instead count the number of idle intervals of length $\ge k$, introduce another binary variable, say $x_s$, that will indicate the start of the interval. To enforce $$x_s\implies \left(z_{s-1} \land \bigwedge_{t=s}^{s+k-1} \neg z_t\right),$$ impose linear constraints \begin{align} x_s &\le z_{s-1} &&\text{for all $s$}\\ x_s &\le 1- z_t &&\text{for all $s$, $t\in\{s,\dots,s+k-1\}$}\\ \end{align} To enforce the converse $$\left(z_{s-1} \land \bigwedge_{t=s}^{s+k-1} \neg z_t\right)\implies x_s,$$ impose linear constraints \begin{align} z_{s-1} + \sum_{t=s}^{s+k-1} (1 - z_t) - k &\le x_s &&\text{for all $s$} \end{align} Now $\sum_s x_s$ counts the number of idle intervals of length $\ge k$.