2
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ 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? $\endgroup$
    – PeterD
    Commented Sep 27, 2023 at 14:52
  • 2
    $\begingroup$ 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 $\endgroup$
    – fontanf
    Commented Sep 27, 2023 at 15:22
  • $\begingroup$ Dear @PeterD, thanks. It makes sense. Let me check that. 👍 $\endgroup$
    – A.Omidi
    Commented Sep 27, 2023 at 18:27
  • $\begingroup$ 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? (👍) $\endgroup$
    – A.Omidi
    Commented Sep 27, 2023 at 18:30
  • $\begingroup$ @PeterD, your point is totally right. Thanks once again. $\endgroup$
    – A.Omidi
    Commented Sep 29, 2023 at 9:45

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Dear @fontanf, thank you so much. $\endgroup$
    – A.Omidi
    Commented Sep 29, 2023 at 9:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.