7
$\begingroup$

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?

$\endgroup$
9
$\begingroup$

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

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks. If I want to count the number of idle intervals that have length more than a threshold? $\endgroup$ – zdm Mar 3 at 3:12
  • 2
    $\begingroup$ I updated the answer to include this additional information. $\endgroup$ – RobPratt Mar 3 at 3:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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