<p>Here's a paper that considers a more general variant of the problem (multiple machines, job dependent demands etc.): </p>

<p>Rohit Khandekar, Baruch Schieber, Hadas Shachnai, Tami Tamir.
Real-time scheduling to minimize machine busy times.
Journal of Scheduling 18(6), 561-573, 2015.
doi:<a href="https://doi.org/10.1007/s10951-014-0411-z" rel="nofollow noreferrer">10.1007/s10951-014-0411-z</a></p>

<p>In particular, their results give a polynomial time algorithm for the case described in my question.</p>

CC BY-SA 3.0
2017-05-14T23:18:46.687Z
2017-05-14T23:18:46.687Z
Thomas Kalinowski
<p>In the context of scheduling maintenance jobs on arcs of a flow network I came across the problem to schedule jobs, indexed by $j$, and given by triples $(r_j,d_j,p_j)$ of (integer) release time, due time and processing time such that the total time in which no job is processed is maximized. A schedule is given by start times $x_j\in S_j:=\{r_j,r_j+1,\ldots,d_j-p_j+1\}$. For instance, for five jobs with $(r_j,d_j,p_j)$ equal to 
\[(1,3,3),\ (20,22,3),\ (10,11,2),\ (1,18,5),\ (8,26,5)\]
and a time horizon of 30, the first three jobs are fixed starting at times $x_1=1$, $x_2=20$ and $x_3=10$, and for the last two jobs it is optimal to start both of them at the same time $x_4=x_5\in\{8,9,10\}$. The objective value (number of time periods without any job) is 
\[30-3-5-3=19.\]</p>

<p>The straightforward binary program for $n$ jobs looks as follows ($y_t$ is the indicator variable for the activity of the "plant" machine suggested in the comment by András Salamon)
\begin{align*}
\text{minimize}\ \sum_{t=1}^Ty_t&amp;\\
\text{subject to}\qquad \sum_{t\in S_j}x_{jt} &amp;=1 &amp;&amp; j\in[n], \\
y_t-\sum_{t'\in S_j\cap[t-p_j+1,t]}x_{jt'} &amp;\geqslant 0  &amp;&amp; t\in[T],\ j\in J_t,\\
x_{jt}&amp;\in\{0,1\} &amp;&amp; j\in[n],\ t\in S_j,\\
y_t &amp;\in\{0,1\} &amp;&amp; t\in[T].
\end{align*}
Here $J_t=\{j\ :\ r_j\leqslant t\leqslant d_j\}$ denotes the set of jobs that can be "active" at time $t$. Interestingly, the constraint matrix is not totally unimodular in general, but the LP relaxation seems to have always integer optimal solutions. Writing down the dual also yields a problem which can be interpreted combinatorially, but so far I haven't been able to turn this into an integrality proof.</p>

<p>One can look at variants of the problem where the number of jobs that can be processed simultaneously is bounded, or there is a given partition of the job set such that no two jobs from the same part can be processed at the same time. 
Has this kind of objective function been studied in the scheduling literature? Or is there any other related problem? </p>

CC BY-SA 3.0
2015-01-06T14:00:02.460Z
It seems you are looking at maximizing a kind of "plant idle time" measure, or minimizing the amount of time that at least some of the machines are in use, while meeting the deadlines.  It might be possible to create a single "plant" machine, which is active whenever any machine is active, and then minimize its running time.
András Salamon
CC BY-SA 3.0
2015-01-06T21:22:15.833Z
@AndrásSalamon Thanks for your comment. The "plant machine" is indeed a natural idea. I've added some details along these lines to the question.
Thomas Kalinowski
<ds.algorithms><co.combinatorics><scheduling><packing>
Scheduling to maximize idle time
Thomas Kalinowski
# Scheduling to maximize idle time

(Asked by: username_0 on 2015-01-04)

In the context of scheduling maintenance jobs on arcs of a flow network I came across the problem to schedule jobs, indexed by $j$, and given by triples $(r\_j,d\_j,p\_j)$ of (integer) release time, due time and processing time such that the total time in which no job is processed is maximized. A schedule is given by start times $x\_j\in S\_j:=\{r\_j,r\_j+1,\ldots,d\_j-p\_j+1\}$. For instance, for five jobs with $(r\_j,d\_j,p\_j)$ equal to
\[(1,3,3),\ (20,22,3),\ (10,11,2),\ (1,18,5),\ (8,26,5)\]
and a time horizon of 30, the first three jobs are fixed starting at times $x\_1=1$, $x\_2=20$ and $x\_3=10$, and for the last two jobs it is optimal to start both of them at the same time $x\_4=x\_5\in\{8,9,10\}$. The objective value (number of time periods without any job) is
\[30-3-5-3=19.\]

The straightforward binary program for $n$ jobs looks as follows ($y\_t$ is the indicator variable for the activity of the "plant" machine suggested in the comment by username_1)
\begin{align\*}
\text{minimize}\ \sum\_{t=1}^Ty\_t&\\
\text{subject to}\qquad \sum\_{t\in S\_j}x\_{jt} &=1 && j\in[n], \\
y\_t-\sum\_{t'\in S\_j\cap[t-p\_j+1,t]}x\_{jt'} &\geqslant 0 && t\in[T],\ j\in J\_t,\\
x\_{jt}&\in\{0,1\} && j\in[n],\ t\in S\_j,\\
y\_t &\in\{0,1\} && t\in[T].
\end{align\*}
Here $J\_t=\{j\ :\ r\_j\leqslant t\leqslant d\_j\}$ denotes the set of jobs that can be "active" at time $t$. Interestingly, the constraint matrix is not totally unimodular in general, but the LP relaxation seems to have always integer optimal solutions. Writing down the dual also yields a problem which can be interpreted combinatorially, but so far I haven't been able to turn this into an integrality proof.

One can look at variants of the problem where the number of jobs that can be processed simultaneously is bounded, or there is a given partition of the job set such that no two jobs from the same part can be processed at the same time.
Has this kind of objective function been studied in the scheduling literature? Or is there any other related problem?

**Tags:** ds.algorithms, co.combinatorics, scheduling, packing

> **Comments:**
> **username_1**: It seems you are looking at maximizing a kind of "plant idle time" measure, or minimizing the amount of time that at least some of the machines are in use, while meeting the deadlines.  It might be possible to create a single "plant" machine, which is active whenever any machine is active, and then minimize its running time.  
> **username_0**: @AndrásSalamon Thanks for your comment. The "plant machine" is indeed a natural idea. I've added some details along these lines to the question.  

---

## 1 answers

### Answer by username_0 on 2017-05-14. Score: 2 | Accepted answer

Here's a paper that considers a more general variant of the problem (multiple machines, job dependent demands etc.):

Rohit Khandekar, Baruch Schieber, Hadas Shachnai, Tami Tamir.
Real-time scheduling to minimize machine busy times.
Journal of Scheduling 18(6), 561-573, 2015.
doi:[10.1007/s10951-014-0411-z](https://doi.org/10.1007/s10951-014-0411-z)

In particular, their results give a polynomial time algorithm for the case described in my question.


---

