3
$\begingroup$

I have a scheduling model where each job $p$ requires three operations (with fixed precedence and they must happen in a row) for a fixed number of $i$ service sessions (each session on a specific day). The service duration for operations of job $p$ is equal to $S^1_p$, $S^2_p$, and $S^3_p$. An identical machine $n$ can serve multiple jobs at the same time slot $j$ and day $t$, but not two jobs within their first operations, third operations, and first and third operations. In other words, a machine can handle multiple jobs at the same time within their second operations ($S^2_p$), but only one of jobs can be within their first or third operations:

enter image description here

where $a_{pjti}$ is a binary variable indicating job $p$ starts at time slot $j$ on day $t$ for service session $i$, and $y_{pnti}$ is a binary variable indicating job $p$ is being allocated to machine $n$ on day $t$ for its service session $i$.

I have used these constraints in my MILP model and coded it in python (shown below). However, for large-sized instances, it takes one day to generate each of the above constraint sets (on a powerful computer). Do you have any suggestions on how I can implement these constraints?

enter image description here

$\endgroup$
2
  • 2
    $\begingroup$ It takes a day just to generate the constraints (without attempting to solve the model)? What are your dimensions? $\endgroup$
    – prubin
    Commented Feb 15, 2022 at 0:52
  • $\begingroup$ Yes, it takes a day to generate the constraints! $|\mathcal{P}|=150$, $|\mathcal{C}|=3$, $|\mathcal{N}_c|=10$, $|\mathcal{J}|=32$, $|\mathcal{T}|=28$, $|\mathcal{I}|=5$. $\endgroup$
    – mdslt
    Commented Feb 15, 2022 at 0:59

1 Answer 1

6
$\begingroup$

I suggest three major changes:

  1. Omit the $y$ variables.
  2. Replace the $a_{p,j,t,i}$ variables with $a_{p,j,t,i,n}$.
  3. Instead of pairs of jobs, consider much larger subsets of jobs.

The resulting reformulation will have fewer and stronger constraints, all of the form $$\sum_{p,j,t,i} a_{p,j,t,i,n} \le 1 \quad \text{for all $\bar{j},\bar{t},n$},$$ where the summation is over all $(p,j,t,i)$ for which job $p$ starting in slot $j$ on day $t$ for service session $i$ would be in its first or third operation in slot $\bar{j}$ and day $\bar{t}$.

$\endgroup$
10
  • $\begingroup$ I think there is a misunderstanding! Each job requires multiple service sessions, each on a day. Each service session includes the so-called three operations. I will be implementing sth very similar to your suggestion and will evaluate its impact. Anyhow, thank you for the help! $\endgroup$
    – mdslt
    Commented Feb 15, 2022 at 1:35
  • $\begingroup$ I think you might have caught me in the model of an edit. The latest update captures that. $\endgroup$
    – RobPratt
    Commented Feb 15, 2022 at 1:40
  • 1
    $\begingroup$ My problem includes several constraints. The problem that I am aiming to solve is also large. With my previous way of modeling, it could generate small-sized instances pretty fast, but it could take days to find the optimal solution. With your way of solving, for a small-sized instance, it took almost nothing to generate the model and find the optimal solution. For large-sized instances (e.g., the aforementioned instance), it took around 1,000 secs to generate the model using your molding approach, and a few seconds to find the optimal solution. Let me know if you want further information! $\endgroup$
    – mdslt
    Commented Feb 15, 2022 at 16:55
  • 1
    $\begingroup$ @RobPratt I suspect there are fewer constraints, but I couldn't tell -- my eyes watered every time I tried to read the model. :-) Apparently your approach worked gangbusters. $\endgroup$
    – prubin
    Commented Feb 15, 2022 at 16:57
  • 1
    $\begingroup$ Glad to hear that this worked well! $\endgroup$
    – RobPratt
    Commented Feb 15, 2022 at 17:04

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.