Column generation: Proper Aggregating of identical machines
I have the following follow-up question to [this post][1]. One of the answers here confirmed that I can aggregate identical machines \(j\in J\) into a single machine profile. In my specific model, I now aggregate all machines for which the characteristics \(Q_{jk}~~\forall j\in J, k\in K\) are identical. This results in the set \(\tilde{j}\in \tilde{J}\), with the new capacities \(\tilde{Q}_{jk}\) which now have the sum of the capacities of all these machines contained in the profile. Assuming I have these original machines \(|J|=5\):
- \(j=1\) mit \(Q_{11}=2,Q_{12}=2,Q_{13}=0,Q_{14}=2,Q_{15}=2\)
- \(j=2\) mit \(Q_{21}=0,Q_{22}=2,Q_{23}=0,Q_{24}=2,Q_{25}=2\)
- \(j=3\) mit \(Q_{31}=1,Q_{32}=2,Q_{33}=0,Q_{34}=2,Q_{35}=2\)
- \(j=4\) mit \(Q_{41}=2,Q_{42}=0,Q_{43}=0,Q_{44}=1,Q_{45}=2\)
- \(j=5\) mit \(Q_{51}=2,Q_{52}=2,Q_{53}=0,Q_{54}=2,Q_{55}=2\)
Accordingly, \(j=1,j=5\) are identical and the others are all different. Now, after aggregation, I have \(|\tilde{Q}|=4\) with
- \(\tilde{j}=1\) mit \(Q_{11}=4,Q_{12}=4,Q_{13}=0,Q_{14}=4,Q_{15}=4\)
- \(\tilde{j}=2\) mit \(Q_{21}=0,Q_{22}=2,Q_{23}=0,Q_{24}=2,Q_{25}=2\)
- \(\tilde{j}=3\) mit \(Q_{31}=1,Q_{32}=2,Q_{33}=0,Q_{34}=2,Q_{35}=2\)
- \(\tilde{j}=4\) mit \(Q_{41}=2,Q_{42}=0,Q_{43}=0,Q_{44}=1,Q_{45}=2\)
When I implement this in my CG code, however, I get different solutions compared to the version without aggregation; tend to be lower solutions. Upon prior conversation about this topic, my Aggregation in the MP is incorrect, as some further modifications to the convexity constraints need to be made, but I don't know which.
Master problem:
$$\begin{align}
&\sum_{i\in I}\sum_{j\in J}\sum_{k\in K}C_{ijk}X^a_{ijk} \lambda_i^a\\
&\text{s.t.}\\
&\sum_{a\in A}\sum_{i\in I}X^a_{ijk}\lambda^a_i\leq \tilde{Q}_{jk}~\forall j\in J, k\in K\\
&\sum_{a\in A}\lambda_i^a= N_i~~\forall i\in I\\
&\lambda_i^a\in \mathbb{N}_{\geq 0}
\end{align}$$
Here, \(a\) are the columns, \(X_{ijk}^a\) the parameters obtained from the subproblems, \(N_i\) the number of orders per profile, \(C_{ijk}\) a cost parameter, and \(\lambda_i^a\) the decision variable.
My idea would be to replace \(\lambda_{i}^a\) with \(\lambda_{ij}^a\) in the whole model and then add this constraint.
$$\sum_{a\in A}\sum_{i\in I}\lambda_{ij}^a\leq N_j\quad \forall j\in J$$
Where \(N_j\) reflects the number of machines in each profile. Would this then also lead to a SP objective modification?
EDIT:
This is my comapct model, where the sets \(I\) (order), \(J\) (maschines) and \(K\) (periods) exist.
$$\begin{align}
&\min \sum_{i \in I} \sum_{j \in J} \sum_{k \in K} c_{ij} x_{ijk}\\
&\text{subject to:}\\
&\text{Assignment constraint: Each order is processed exactly once
}\\
&\sum_{j \in J} \sum_{k \in K} x_{ijk} = 1 \quad \forall i \in I\\
& \text{Capacity constraint: At most \(C_{jk}\) order per machine per time slot}\\
&\sum_{i \in I} x_{ijk} \leq C_{jk} \quad \forall j \in J, \, k \in K\\
& \text{Release date constraint: Order \(i\) cannot start before its release time \(r_i\)}\\
&\sum_{j \in J} x_{ijk} = 0 \quad \forall i \in I, \, k < r_i\\
&\text{Due date constraint: Order \(i\) must finish by its due date \(d_i\) (assuming processing time is one slot)}\\
&\sum_{j \in J} x_{ijk} = 0 \quad \forall i \in I, \, k > d_i\\
& \text{Pause periods (machine unavailable periods): Machine \(j\) unavailable in slots \(U_j\)}\\
&\sum_{i \in I} x_{ijk} = 0 \quad \forall j \in J, \, k \in U_j\\
& \text{Machine eligibility: Order \(i\) can only be processed on eligible machines \(M_i\)}\\
&x_{ijk} = 0 \quad \forall i \in I, \, j \notin M_i, \, k \in K\\
&
x_{ijk} \in \{0,1\} \quad \forall i \in I, \, j \in J, \, k \in K
\end{align}$$
I would naturally decompose it with the capacity constraint in the MP and the remaining in the \(i\) individual SPs. I havent performed any aggregation in the compact model, but an order aggregation in my decomposed model above.
If i were to also aggregate my machines, would i need 'new' machine subproblems, or can i handle the aggregation in the MP?
Please sign in to leave a comment.
Comments
0 comments