5
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$ – Oguz Toragay Apr 22 '20 at 0:45
  • $\begingroup$ 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. $\endgroup$ – zdm Apr 22 '20 at 2:20
  • $\begingroup$ 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. $\endgroup$ – prubin Apr 22 '20 at 15:30
  • $\begingroup$ @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$? $\endgroup$ – zdm Apr 22 '20 at 17:45
2
$\begingroup$

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

Improve this answer
$\endgroup$
6
$\begingroup$

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

Improve this answer
$\endgroup$
5
$\begingroup$

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}

Improve this answer
$\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.