# Solving Non-Permutation Flow Shop Scheduling Problem with Time Couplings
## 3 Problem Properties
Let us notice that the \"downwards\" arc entering \(B\) from the previous machine (if \(i>1\)) always enters \(B\) either at the beginning (at operation \(b_{1}\)) or at the end (at operation \(b_{c}\)) of \(B\), making the \(B\) and R- and L-block, respectively. The same happens for the arc exiting the \begin{table}
\begin{tabular}{l c c c c c c c} \hline \(a\) & \(p_{a,1}\) & \(p_{a,2}\) & \(p_{a,3}\) & \(p_{a,A}\) & \(p_{a,5}\) & \(\hat{r}_{a}\) & \(\hat{d}_{a}\) \\ \hline
3 & 2 & 4 & 2 & 1 & 2 & 2 & 2 \\ \hline \end{tabular}
\end{table} 
Table 2: Problem instance from Example 2 for \(n=5\) and \(m=3\). Figure 4: The left-shifted schedule for the instance from Example 2 and \(\pi=((1,2,3,4,5)\). \((2,1,4,3,5),\)\((2,1,3,5,4))\). Figure 3: Solution graph for the instance from Example 2 and \(\pi=((1,2,3,4,5),\)\((2,1,4,3,5),\)\((2,1,3,5,4))\). block \"downwards\" onto the next machine (for \(i<m\)): that arc exits from \(b_{1}\) for an L-block and and from \(b_{c}\) for an R-block. Let us assume that operations \((b_{1},b_{2},\ldots,b_{c})\) of \(B\) are operations from jobs \(j\), \(j+1,\ldots,k-1,k\), respectively. Let \(\alpha\) and \(\gamma\) be the lengths of the longest paths ending and starting at vertex \((i,j)\), without the weight of that vertex. Similarly, let \(\beta\) and \(\delta\) be the lengths of the longest path ending and starting at vertex \((i,k)\) without the weight of that vertex. The relevant part of graph \(G(\pi)\), including block \(B\) and paths \(\alpha\), \(\beta\), \(\gamma\) and \(\delta\) is shown in Figure 5.  
Let us start with the R-block case. The length of the critical path will be:  
\[\alpha+\rho_{i,j}+\rho_{i,j+1}+\ldots+\rho_{i,k-1}+\rho_{i,k}+\hat{r}_{i}(k-j) \hat{r}_{i}+\delta. \tag{13}\]  
The inner block for \(B\) is \(B^{\prime}=(b_{2},b_{3},\ldots,b_{c-1})\). Now, let us consider swapping any two operations \(b_{x},b_{y}\in B^{\prime}\), with \(x\
eq y\). Such a swap will not affect the lengths of paths \(\alpha\) and \(\delta\). It will also not change values \(\rho_{i,j}\) and \(\rho_{i,k}\), as vertices \((i,j)\) and \((i,k)\) are outside of the inner block. Values \(\hat{r}_{i}\) are unaffected as well. The swap of operations \(b_{x}\) and \(b_{y}\) will change the order of the values \(\rho_{i,j+1}\) through \(\rho_{i,k-1}\), but their sum will remain unchanged. The length of the considered critical path will thus remain the same. Thus, graph \(G(\pi^{\prime})\) will contain a path with the length at least as large as the length of path \(K\) in \(G(\pi)\) and in conclusion:  
\[C_{\max}(\pi^{\prime})\geq C_{\max}(\pi). \tag{14}\]  
Now, let us consider the L-block case. The length of the critical path is then:  
\[\beta+\rho_{i,j}+\rho_{i,j+1}+\ldots+\rho_{i,k-1}+\rho_{i,k}+\hat{D}_{i,j}+ \hat{D}_{i,j+1}+\ldots+\hat{D}_{i,k-1}+\gamma. \tag{15}\]  
Once again, we consider swapping operations \(b_{x}\) and \(b_{y}\) from inner block of \(B\). The length of paths \(\beta\) and \(\gamma\) does not change, similar to weights of vertices \((i,j)\) and \((i,k)\) because they are outside the inner block. The swapping of \(b_{x}\) and \(b_{y}\) will also not affect the sum of weights of vertices \((i,j+1)\) to \((i,k-1)\) as they will all still be a part of the inner block after the swap, just in a different order. All that is left to consider are the arc weights \(\hat{D}_{i,j}\) through \(\hat{D}_{i,k-1}\). Part of those weights are the \(\hat{d}_{i}\) terms which will not change as they are independent from solution \(\pi\) (or \(\pi^{\prime}\)). Values \(\rho_{i,j}\) and \(\rho_{i,k}\) that are part of weights \(\hat{D}_{i,j}\) and \(\hat{D}_{i,k-1}\) will not change because they are dependent on weights of vertices \((i,j)\) and \((i,k)\), which were unaffected by the swap. The last remaining contribution to weights \(\hat{D}_{i,z}\) for \(z\) from \(j\) through \(k-1\) are the values \(-\rho_{i,z}\) and \(-\rho_{i,z+1}\). Those values are dependent on vertex \((i,z)\) and its weight of \(\rho_{i,z}\).