# How to define the sequence depending setup time based on a time index formulation

I am working on a scheduling problem in which I have used two different MIP formulations and also based on the time index variable. My problem is in the class $$P_{j} | \ r_{j}, SDST \ | C_{Max}$$.

Without having $$SDST$$, both formulations work well, but it makes an issue when I want to add the related constraints. Actually, the problem is solved, but the resulting schedule does not make sense against the $$SDST$$ limitation. The constraint I have used is in the following form:

$$\sum_{i_{i\neq j}} \sum_{tt=t+p_{j}}^{t+p_{j}-s_{j,i}-1} x_{i,m,tt} \leq M.(1-x_{j,m,t}) \quad \forall j \in J, m \in M, t \in T$$

where the binary variable $$x_{j,m,t}$$ is equal to $$1$$ if task $$j$$ is being assigned on machine $$m$$ at time slot $$t$$, otherwise $$0$$. I was wondering if, how can I fix my issue w.r.t the mentioned constraint and if there is another efficient way to do that.

• Is this the only constraint concerning the SDST that you have added? Also, concerning the second sum, $t+p_j > t+p_j-s_{j,i}-1$, so it is an empty sum right? Commented Sep 27, 2023 at 14:52
• Maybe, for all $i, j$, $i \neq j$, for all $m$, for all $t$, $x_{j, m, t} + \sum_{t' = t + p_j}^{t + p_j + s_{ij}} x_{i, m, t'} \le 1$. But that's a lot of constraints Commented Sep 27, 2023 at 15:22
• Dear @PeterD, thanks. It makes sense. Let me check that. đź‘Ť Commented Sep 27, 2023 at 18:27
• Dear @fontanf, It is so interesting. I think what you proposed has a tighter relaxation than what I wrote. It seems it can also have TU condition. Would you please, add your comments as an answer? (đź‘Ť) Commented Sep 27, 2023 at 18:30
• @PeterD, your point is totally right. Thanks once again. Commented Sep 29, 2023 at 9:45

$$\forall j, j' \in J, j \neq j' \quad \forall m \in M, \quad \forall t \in T, \qquad x_{j, m, t} + \sum_{t' = t + p_j}^{t + p_j + s_{j, j'} - 1} x_{j', m, t'} \le 1$$
This formulation assumes that the the setup times satisfy the triangular inequality ($$s_{j_1, j_2} + s_{j_2, j_3} \ge s_{j_1, j_3}$$)