How do I define a constraint in such a way that values must be in sequential columns?

Question

I am trying to formulate a linear program for a time scheduling problem.

My variable is simple, $x_{ij}$, which is equal to 1 when job $i$ is done at hour $j$.

Now as a part of this schedule (10 job = 10 rows and 24 hours = 24 columns), I need to define a constraint for job 5, or row 5. I've been using constraints like summation of row 3 should be equal to 5, meaning job 3 requires 5 hours to be devoted to it through the day.

Now, lets say I have job 7, that MUST be done sequentially (it can be done from 3-6 pm, 6-9 pm, anything, it must be sequential is all). But how do I show a constraint in a linear program like that?

Answer 1

Although I do not think this is the best approach, if you really want to stick with your $x_{ij}$ variables, you could do something like this : Introduce binary variables $s_{ij}$ that take value $1$ if job $i$ starts at hour $j$, and add the following constraints :

• Job $7$ can only have $1$ starting time : $$\sum_j s_{7j} =1$$
• If job $7$ starts at hour $j$, then hour $j$ is "active" and accounted for in the objective function : $$ s_{7j} \le x_{7j} \quad\forall j $$
• If job $7$ starts at hour $j$, then hours $j+1$ and $j+2$ must also be active : \begin{align*} s_{7j} + x_{7j} &\le 1 + x_{7j+1}\quad\forall j \\ s_{7j} + x_{7j} &\le 1 + x_{7j+2}\quad\forall j \\ \end{align*} Since variables $x_{ij}$ are minimised in the cost function (I suppose), they will take value $0$ when they can, so this last constraint should be sufficient to guarantee $3$ consecutive active time slots : $x_{7j+k}$ will take value $1$ if and only if $s_{7j}=x_{7j}=1$.