# Requiring exactly $n_j$ slots for job $j$ (if scheduled)

Let $$x_{j}(t)=1$$ iff job $$j$$ is scheduled at time $$t$$. I want to say that if the job is scheduled at all, then it is scheduled at $$n_j$$ slots. I wrote this as:

$$x_{j}(t)\sum_{s=1}^{T}x_{j}(s)=n_jx_{j}(t).$$

Is it possible to write this as linear constraints?

If I am maximizing the number of jobs to be scheduled, can we do any better?

• I don't understand why you multiplied the left side by $x_j(t)$. I think it's not necessary. BTW, are $n_j$ constant values? If yes, you have a linear constraint, if no what is the domain for that values? Apr 22 '20 at 0:45
• If I don't add the term in the left and $x_j(t)=0$, then $\sum\limits_{s=1}^{T}x_j(s)=0$ and the job will never be scheduled.
– zdm
Apr 22 '20 at 2:20
• You did not specify whether the slots need to be consecutive. The solutions from Rob and Siong do not require the slots to be consecutive, which hopefully is okay in the context of your problem. Apr 22 '20 at 15:30
• @prubin Requiring $n_j$ to be consecutive cannot be guaranteed with this formulation right? I mean I must redefine the variables $x_j(t)$? For example, $x_j(t)=1 \iff$ job $j$ is scheduled from $t$ to $t+n_j$?
– zdm
Apr 22 '20 at 17:45

If you need consecutive slots, one way to model it is to redefine $$x_j(t)$$ to indicate the start at time $$t$$ of $$n_h$$ consecutive slots occupied by $$j$$. The "$$n_j$$ or none" constraint then becomes $$\sum_{t=1}^{T-n_j+1} x_j(t)\le 1\quad\forall j$$or, if you need a binary indicator $$y_j$$ for whether $$j$$ gets scheduled, $$\sum_{t=1}^{T-n_j+1}x_j(t)=y_j\quad\forall j.$$

Introduce a binary variable $$y_j$$ to indicate whether $$x_j(t)>0$$ for some $$t$$, and impose linear constraints: $$\sum_{t=1}^T x_j(t) = n_j y_j$$

We need an indicator of whether a job is ever scheduled at all.

$$y_j=\begin{cases} 1, & \sum\limits_{t=1}^Tx_j(t)>0 \\ 0, &\sum\limits_{t=1}^Tx_j(t)=0\end{cases}$$

$$\sum_{t=1}^T x_j(t) = n_jy_j$$

Furthermore, you want to maximize the number of jobs.

\begin{align}\max&\quad\sum_j y_j\\\text{s.t.}&\quad\sum_{t=1}^T x_j(t) = n_jy_j\\&\quad x_j(t), y_j \in \{0,1\}.\end{align}