# Model generation for large-sized instances

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: 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? • It takes a day just to generate the constraints (without attempting to solve the model)? What are your dimensions?
– prubin
Feb 15, 2022 at 0:52
• 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$. Feb 15, 2022 at 0:59

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}$$.

• 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! Feb 15, 2022 at 1:35
• I think you might have caught me in the model of an edit. The latest update captures that. Feb 15, 2022 at 1:40
• 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! Feb 15, 2022 at 16:55
• @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.
– prubin
Feb 15, 2022 at 16:57
• Glad to hear that this worked well! Feb 15, 2022 at 17:04