# Solving Non-Permutation Flow Shop Scheduling Problem with Time Couplings
## 3 Problem Properties  
In this section, we will discuss several properties for the \(F|\hat{r}_{i},\hat{d}_{i}|C_{\text{max}}\) problem including: feasibility of solutions, computational complexity of determining the goal function, and an elimination property based on blocks. **Property 1**. : _For any solution \(\pi\in\Pi\), the solution graph \(G(\pi)\) for \(\Gamma|\hat{r}_{i},\hat{d}_{i}|C_{\text{max}}\) does not contain cycles of positive length._  
Proof. : Let us notice that graph \(G(\pi)\) does not contain arcs going \"upwards\" (i.e., no arcs from vertex \((i,j)\) to \((k,j)\) for \(k<i\)). Thus, cycles can only be created with the use of \"horizontal\" arcs. Let us consider a cycle consisting of two adjacent vertices \((i,j)\) and \((i,j+1)\). Those vertices have weights \(\rho_{i,j}\) and \(\rho_{i,j+1}\), while the arcs connecting them have weights \(\hat{r}_{j}\) and \(\hat{D}_{i,j}=-\rho_{i,j}-\rho_{i,j+1}-\hat{d}_{i}\). After adding the weights together, the length of such a cycle is equal to \(\hat{b}_{j}-\hat{d}_{i}\leq 0\). Now, let us generalize this result to cycles consisting of \(k>2\) subsequent vertices in one \"row\". Such a cycle contains (for some \(i\) and \(j\)) vertices from \((i,j)\) to \((i,j+k-1)\), as well as \(k-1\) \"forward\" arcs with weights \(\hat{r}_{j}\) and \(k-1\) \"return\" arcs. Let us now compute the length of such a cycle. Without loss of generality, we can assume that the cycle begins in vertex \((i,j+k-1)\). Let us consider the inner vertices of this cycle i.e., vertices from \((i,j+1)\) to \((i,j+k-2)\). Let \((i,c)\) denote one such inner vertex. We pass each vertex \((i,c)\) twice during the cycle, thus adding weight \(2\rho_{i,c}\) to the cycle length. Moreover, when passing through vertex \((i,c)\), we add the weight \(-\rho_{i,c}\) twice: once from \"return\" arc ending at \((i,c)\) and once from \"return\" arc starting at \((i,c)\). Thus, so far, the cycle length is \(0\), as all weights \(2\rho_{i,c}\) and \(-2\rho_{i,c}\) add up to \(0\). The above is thus equal to a situation where vertices \((i,j+1)\) to \((i,j+k-2)\) have weights 0 and \"return\" arcs have only term \(\hat{d}_{i}\) in their weight. The only exceptions are the \"return\" arc starting at vertex \((i,j+k-1)\) and the \"return\" arc ending at vertex \((i,j)\). Those two arcs still have the terms \(-\rho_{i,j+k-1}\) and \(-\rho_{i,j}\) in their weights, respectively. However, it is easy to see that those two terms will be negated by the weights of vertices \((i,j)\) and \((i,j+k-1)\) as we pass those vertices only once during the cycle. Thus, we can compute the cycle length as if all cycle vertices had weights 0 and its \"return\" arcs had weights with term \(\hat{d}_{i}\) only. The cycle length is then \((k-1)(\hat{r}_{i}-\hat{d}_{i})\leq 0\). Therefore, all cycles in \(G(\pi)\) are of non-positive length. When computing the value of the makespan, we can ignore those cycles as per the following observation. Corollary 1: _For any solution \(\pi\), if solution graph \(G(\pi)\) for the \(F|\hat{r}_{i},\hat{d}_{i}|C_{\max}\) problem contains a path \(p\) with length \(\operatorname{len}(p)\) such that \(p\) contains a cycle, then \(G(\pi)\) also contains a path \(P\) without a cycle, such that:_  
\[\operatorname{len}(P)\geq\operatorname{len}(p). \tag{9}\]  
Thus, if a path \(p\) in \(G(\pi)\) contains a cycle, then either: (1) it is not the longest path in \(G(\pi)\) (at least one cycle in \(p\) has negative length) or (2) we can construct another path starting and ending at the same vertices and with the same length as \(p\), but not containing a cycle (all cycles in \(p\) have length 0). We will now present the algorithm for determining the left-shifted feasible schedule \(S\) (and thus the makespan \(C_{\max}\)), based on the solution \(\pi\). We will also provide the computational complexity of this algorithm. Theorem 1: _For any solution \(\pi\), there exists a feasible left-shifted schedule \(S\) for the \(F|\hat{r}_{i},\hat{d}_{i}|C_{\max}\) problem.