# Solving Non-Permutation Flow Shop Scheduling Problem with Time Couplings
## 3 Problem Properties
For example, we can define the swap move for the \(F|\hat{r}_{i},\hat{d}_{i}|C_{\max}\) problem as follows:  
\[\pi^{\prime}=\text{swap}(\pi,i,j,k), \tag{10}\]  
where solution \(\pi^{\prime}\) is created from \(\pi\) by swapping together values of \(\pi_{i}(j)\) and \(\pi_{i}(k)\). The solution \(\pi^{\prime}\) will be called the neighbor of solution \(\pi\). Similarly, the set of all solutions created from \(\pi\) by this move will be called the neighborhood of \(\pi\). We will now formulate an elimination property showing that some moves do not result in immediate improvement of the makespan, similarly to existing elimination properties for the Job Shop Scheduling problem [41]. Let us start with the definition of a _block_. A sequence of operations \(B=(b_{1},b_{2},\ldots,b_{c})\) for \(c>0\) will be called a block if and only if:  
1. All operations from \(B\) are on the same critical path. 2. Operations from \(B\) are performed subsequently on the same machine \(i\). 3. Operations from \(B\) are processed on \(i\) in the order of their appearance in \(B\). 4. The length of \(B\) is maximum i.e., operations from \(i\) that are directly before or after \(B\) cannot be included in it without violating the first three conditions. Moreover, for block \(B=(b_{1},b_{2},b_{3},\ldots,b_{c-2},b_{c-1},b_{c})\) of \(c>2\) operations, we define its _inner block_ as sequence \(B^{\prime}=(b_{2},b_{3},\ldots,b_{c-2},b_{c-1})\). Let block \(B=(b_{1},b_{2},\ldots,b_{c})\) be part of critical path \(K\). Then, \(B\) is called a _right-side block_ (or R-block) if the first operation from \(B\) on \(K\) is \(b_{1}\). Similarly, \(B\) will be called a _left-side block_ (or L-block) if the first operation from \(B\) on \(K\) is \(b_{c}\). Consider the FSSP instance for \(n=5\), \(m=3\) from Table 2. Let us assume the order of jobs \(\pi=((1,2,3,4,5),\)\((2,1,4,3,5),\)\((2,1,3,5,4))\). Solution graph \(G(\pi)\) for this example is shown in Figure 3 with the critical path shown in bolded red. This critical path is composed of three blocks (one for each machine). On the first machine, we have a 4-operation \(R\)-block beginning at operation \((1,1)\) and ending at operation \((1,4)\). On the second machine, we have an L-block of size 3 starting at operation \((2,3)\) and going back to operation \((2,1)\). Finally, on the last machine, we again have an R-block which runs through all five operations of that machine. Let us also note that the sizes of the inner blocks are 2, 1, and 3, respectively. The left-shifted schedule for solution \(\pi\), with \(C_{\max}=26\), is shown as a Gantt chart in Figure 4._  
With the concept of blocks and inner blocks defined, we can formulate the block elimination property for the \(F|\hat{r}_{i},\hat{d}_{i}|C_{\max}\) problem. **Theorem 2**. : _Let \(\pi=(\pi_{1},\pi_{2},\ldots,\pi_{m})\) be a solution to the \(F|\hat{r}_{i},\hat{d}_{i}|C_{\max}\) problem and let \(B=(b_{1},b_{2},\ldots,b_{c}),\,c>2\) be a block on a critical path \(K\) in \(G(\pi)\) consisting of operations from machine \(i\). Next, let \(\pi^{\prime}\) be a solution created from \(\pi\) by swapping any pair of operation from inner block of \(B\) i.e.,:_  
\[\pi^{\prime}=\mathrm{swap}(i,j,k)\quad j,k\in\{b_{2},b_{3},\ldots,b_{c-2},b_{ c-1}\},\ j\
eq k, \tag{11}\]  
_then:_  
\[C_{\max}(\pi^{\prime})\geq C_{\max}(\pi). \tag{12}\]  
Proof. : Due to Property 1 and Corollary 1, there is at least one cycle-free critical path that contains the block \(B\). We arbitrarily choose one of such paths to be our critical path \(K\). It follows that the critical path travels through block \(B\) in one direction (the critical path does not change direction in the middle of \(B\)). Thus, \(B\) is either an L-block or an R-block and we need to prove the elimination property for both types of blocks.