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

Question

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.

Answer 1

Here is a way to model sequence-dependent setup times for a time-indexed formulation:

$$ \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}$)

This formulation has no big-M constraint but may contain a large number of constraints.

I'm not fully familiar with MILP formulations for scheduling problems, so I don't know if it's the standard and best way to model this.