Find the number of idle intervals with weights

Question

We have one job $i$ and one machine. Let $\mathbf{x}_i=[x_{i,1},x_{i,2},\ldots,x_{i,T}]$ be a binary vector where $x_{i,t}=1\iff$ job $i$ is scheduled at time $t$. Let $u$ be a positive number. I would like to find the idle intervals of length $u$ or more. An interval $k=\{s,s+1,\ldots,s'\}$ is idle if $x_{i,s}=x_{i,s+1}=\cdots=x_{i,s'}=0$. The length of the interval $k=\{s,s+1,\ldots,s'\}$ is $l_k:=s'-s+1$. An idle interval $k$ of length $l_k$, is associated a weight $w_k$. The objective is to minimize the summation $\sum_{k}w_k$, e.g., if $w_k=1$ for all $k$, then the objective is to minimize the number of idle intervals.

For example, for $\mathbf{x}_i=[1,0,0,0,0,1,0,0,0,1]$, then, we have two idle intervals; one of length $4$ (say, with weight $2$) and one of length $3$ (say, with weight $1$). Thus, we count the objective as $3$.

How can I write the objective using the variable $\mathbf{x}_i$ in linear formulation? In other words, how to find the idles intervals using $\mathbf{x}_i$?

Answer 1

You can modify the formulation given in my answer to your related question. In terms of that formulation, refine the variable $x_s$ that indicates the start at time $s$ of an idle interval with variables $x_{s,r}$ that indicate the start at time $s$ of an idle interval of length $r$.

---

An alternative approach is to think of this in terms of a time-based network, with arc variables $y_{i,j,k}$ that indicate that job $i$ is scheduled at times $j$ and $k$ and not in between; that is, $$y_{i,j,k} \iff \left(x_{i,j} \land x_{i,k} \land \bigwedge_{t=j+1}^{k-1} \neg x_{i,t}\right)$$ This way, you can implicitly impose constraints by omitting arcs.