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$?


1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.