# Solving Non-Permutation Flow Shop Scheduling Problem with Time Couplings
## 3 Problem Properties
Moreover, the value \(C_{\max}(\pi)\) for the schedule \(S\) can be determined in time \(O(nm)\)._  
Proof: The proof is based on Algorithm 1. Here, we will describe it, including its computational complexity. The algorithm consists of \(m\) phases. In phase \(i\), we determine the completion times for all operations on machine \(i\). Every time a completion time \(C_{i,j}\) is computed or updated, we also set \(S_{i,j}=C_{i,j}-\rho_{i,j}\). By doing so, we met the constraint (1) at all times throughout the algorithm. ```
1\(C_{1,1}\leftarrow\rho_{1,1}\);
2 for\(j=2,3,\dots,n\)do
3\(C_{1,j}\leftarrow C_{1,j-1}+\hat{r}_{0}+\rho_{1,j}\);
4 for\(i=2,3,\dots,m\)do
5\(C_{i,1}\leftarrow C_{i-1,\pi_{i-1}^{-1}(\pi_{i}(1))}+\rho_{j,1}\);
6 for\(j=2,3,\dots,n\)do
7\(C_{i,j}\leftarrow\max\{C_{i,j-1}+\hat{r}_{i},C_{i-1,\pi_{i-1}^{-1}(\pi_{i}(j)) }\}+\rho_{i,j}\);
8 for\(j=n-1,n-2,\dots,1\)do
9\(C_{i,j}\leftarrow\max\{C_{i,j},C_{i,j+1}-\rho_{i,j+1}-\hat{d}_{i}\}\);
```  
**Algorithm 1**Constructing left-shifted schedule. Phase 1 corresponds to lines 1-3 of the algorithm. In line 1, we set \(C_{i,j}=\rho_{1,1}\), since the first operation on the first machine has no constraints. Then, in lines 2 and 3, we set completion times for subsequent remaining operations on this machine. Constraints (2) and (3) for this machine will be met because \(\hat{d}_{1}\geq\hat{r}_{1}\) and operations on machine 1 have no technological predecessors. The schedule on machine 1 is thus set, feasible and left-shifted, as scheduling any operation earlier would violate either the left side of constraint (2) or make \(S_{1,1}\) a negative number. From the pseudocode, it is also easy to see that this phase is computed in time \(O(n)\). Let us now consider phases \(i>1\) (lines 4 to 9). We always complete phase \(i\) before starting phase \(i+1\) (line 4). Each such phase is executed in a similar manner. First, in line 5, we _tentatively_ set \(C_{i,1}\), similarly to line 1, except we also consider the technological predecessor of that operation. Then, in lines 6-7, we _tentatively_ set completion times of subsequent operations, taking into account technological predecessor, machine predecessor, and minimal idle time \(\hat{r}_{i}\). By now, the only constraint operations on machine \(i\) might still violate is the right side of constraint (2). In order to mitigate that, in lines 8-9, we perform similar operation to lines 6-7, but in reverse order (from operation \(n-1\) down to 1). In particular, if \(C_{i,j}\) and \(C_{i,j+1}\) are such that the right side of constraint (2) is violated, then we shift \(C_{i,j}\) to the right just enough to meet the constraint, after which the value of \(C_{i,j}\) is final. During this procedure, some of the operations might be rescheduled to start later, thus this change will not violate any constraints. Moreover, now the constraint (2) is guaranteed to hold. The schedule on machine \(i\) is thus feasible and left-shifted. Indeed, if no operation was shifted to be scheduled later during the correction procedure, then we cannot shift any operation to schedule earlier because this would violate either the left side of constraint (2) or constraint (3). Similarly, if an operation was shifted during the correction, then the shift was the smallest that met the right side of constraint (2). Any smaller shift would create infeasible schedule, so shifting the operation to start any earlier is not possible. We also see from the pseudocode that each phase \(i>1\) can by completed in time \(O(n)\). Thus, all \(m\) phases can be computed in time \(O(nm)\), allowing us to obtain a feasible left-shifted schedule for any \(\pi\) with \(C_{\max}=C_{m,n}\). From the above theorem, it follows that all solutions \(\pi\) are feasible. However, we will show that some of the feasible solutions can be disregarded. Particularly, many solving methods use the concept of a _move_.