1
$\begingroup$

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 András Salamon) \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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – András Salamon Jan 6 '15 at 14:00
  • $\begingroup$ @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. $\endgroup$ – Thomas Kalinowski Jan 6 '15 at 21:22
2
$\begingroup$

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

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

$\endgroup$

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.