Modeling sequence dependent setup times via a MIP for flow shop scheduling
Awaiting user input
As part of a Non-Permutation Flowshop Scheduling (NPFS) problem, I would like my MIP model to be able to deal with sequence dependent setup times. That is, for each pair of consecutive jobs, a setup time (which may be 0) may be induced in between.
Modeling:
Partially following the notation from Souiden et al., this means I extend the following inequality:
\[S_{i,k} + \sum_{j=1}^{n}p_{i,j}\cdot x_{i,j,k} \leq \quad S_{i,k+1} \quad \forall i\in\mathcal{M};\forall k\in\mathcal{K}_i\setminus\{k_i\}.\]
In the above, the binary decision variable \(x_{i,j,k}=1\) IFF job \(j\) is assigned to machine \(i\) in the \(k\)'th position on that machine. Variable \(S_{i,k}\) denotes the start time of the job scheduled \(k\)'th on machine \(i\) and \(p_{i,j}\) the processing time of job \(j\) on machine \(i\). In other words, the above inequality states that two consecutive jobs on the same machine should be non-overlapping.
When using setup times, this means that we should add the setup time between the job scheduled \(k\)'th and \(k+1\)'th to the LHS in the above. In case the setup time between job \(j\) and \(j'\) on machine \(i\) is denoted with \(O_{i,j',j}\), my idea was to write setup time as follows:
\[\sum_{j'\in\mathcal{J}}\sum_{j\in\mathcal{J}}x_{i,j',k}\cdot x_{i,j,k+1}\cdot O_{i,j',j}.\]
The reason that I am using this sum of products is that we have to know which jobs are scheduled \(k\)'th and \(k+1\)'th on machine \(i\). Now only for one pair of \((j',j)\) the product \(x_{i,j',k}\cdot x_{i,j,k+1}=1\), hence this term.
Implementation
I implemented my model in \(\texttt{Python}\) and use \(\texttt{Gurobi}\) to solve it. For the line above, I used the code
\(
\texttt{quicksum(x[i, j1, k] * x[i, j2, k + 1] * O[i, j1,j2] for j1 in range(J)}
\)
I tested if model performance would increase if I explicitly linearized the setup term instead of using the \(\texttt{*}\) operator in \(\texttt{Gurobi}\), however this made performance worse (\(\texttt{Gurobi}\) does it in a more clever way apparently).
Observation & Question
I observed that adding this setup term to my model, significantly decreases the model performance, even if the setup times are always the same value (regardless of what pair of consecutive jobs). If I would add that always-the-same value explicitly to the top inequality, model performance is much faster compared to when modeling it implicitly via the last term.
- What can be the reason for the observation above?
- Does anyone have a suggestion for a better way of formulating and/or implementing this, like cuts, ways to tighten the problem?
-
Official comment
-
Gurobi Staff
This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?. -
-
-
Hi Rutger,
I observed that adding this setup term to my model, significantly decreases the model performance, even if the setup times are always the same value (regardless of what pair of consecutive jobs).
You are adding a large amount of bilinear terms and even thou they can be linearized because \(x\) is binary, this still makes the problem way more complex. Thus, it is not very surprising that Gurobi takes more time to solve the new formulation.
If I would add that always-the-same value explicitly to the top inequality, model performance is much faster compared to when modeling it implicitly via the last term.
I don't understand what you mean by "add that always-the-same value explicitly to the top inequality". Could you please elaborate a bit more?
Does anyone have a suggestion for a better way of formulating and/or implementing this, like cuts, ways to tighten the problem?
I guess you already have implemented cuts stating that at most one job can run at \(k^{\text{th}}\) position or that the sum over each machine and each job and each position equals \(1\).
Is the ordering of jobs important? If not then you could model an ordering of the jobs, e.g., \(x_{i,j,k} \leq x_{i,j',k}\) or similar. Reducing the number of freedom regarding something like job/time ordering usually can improve performance.
Best regards,
Jaromił0 -
Post is closed for comments.
Comments
2 comments