# Solving Non-Permutation Flow Shop Scheduling Problem with Time Couplings
## 4 Solving Methods
### Tabu Search  
Tabu search (or TS) is one of the most well-known local search metaheuristics [23]. In each iteration, we search the _neighborhood_ of the current solution. The neighborhood \(\mathcal{N}(\pi)\) of solution \(\pi\) is defined as all solutions \(\pi^{\prime}\) that can be obtained from \(\pi\) by applying a pre-defined _move_ function. In our implementation, we considered three types of moves:  
1. Swap move \(\mathtt{S}(\pi,i,j,k)\). Neighboring solution \(\pi^{\prime}\) is obtained by swapping together values \(\pi_{i}(j)\) and \(\pi_{i}(k)\), where \(i\in\mathcal{M}\), \(j\in\mathcal{J}\), \(k\in\mathcal{J}\setminus\{j\}\). This neighborhood has exactly \(\frac{n(n-1)}{2}m\) solutions. 2. Adjacent swap move \(\mathtt{A}(\pi,i,j)\). Neighboring solution \(\pi^{\prime}\) is obtained by swapping together values \(\pi_{i}(j)\) and \(\pi_{i}(j+1)\), where \(i\in\mathcal{M}\), \(j\in\mathcal{J}\setminus\{n\}\). This neighborhood has exactly \((n-1)m\) solutions. 3. Block swap move \(\mathtt{B}(i,j,k)\). This move is similar to \(\mathtt{S}(\pi,i,j,k)\), except it takes into account the results of Theorem 2. Specifically, if \(\mathcal{B}_{i}\) is an inner block on machine \(i\), then the move is only performed when either \(j\in\mathcal{B}_{i}\wedge k\
otin\mathcal{B}_{i}\) or \(j\
otin\mathcal{B}_{i}\wedge k\in\mathcal{B}_{i}\). The size of this neighborhood is dynamic, based on on the size of blocks in \(\pi\), but its size is between the sizes of neighborhoods generated by moves A and S with \(\frac{n^{2}m}{8}\) solutions on average. Let us also note that all of the above move types are involutions. **Example 3**. : _Let us consider the solution from the graph in Figure 3 for \(n=5\) and \(m=3\). For the adjacent swap move, the neighborhood size is 12. This is because we swap only adjacent operations; thus, on the first machine, we can swap operation 1 with 2, 2 with 3, 3 with 4 or 4 with 5. This can be applied to any machine, hence \(3\times 4=12\) possible moves. In the case of the swap move, for each of five machine operations, we can swap it with any of the remaining four operations, yielding 20 possible swaps on machine and 60 moves in total. Finally, for the block swap move, the number of possible swap moves on machine \(i\) is given as \((c_{i}-2)(n-c_{i}+2)\), for \(c_{i}>2\) and 0 for \(c_{i}\leq 2\), where \(c_{i}\) is the size of the block on machine \(i\). This is because we can swap any operation from the inner block (which has size \(c_{i}-2\)) with any operation out of the inner block (which means \(n-(c_{i}-2)=n-c_{i}+2\) operations). In our example, the block sizes are 4, 3, and 5, which yields \(6+4+6=16\) possible swap moves._  
In each iteration \(i\) of the TS algorithm, we generate the neighborhood of the current solution \(x_{i}\) (according to the chosen move type) and then evaluate (i.e., compute \(C_{\max}\)) all resulting solutions. The best of those solutions will become the current solution in the next iteration (\(x_{i+1}\)). In addition, if the best neighbor \(x_{\mathcal{N}}\) is better then the best known global solution \(x_{g}\), we replace \(x_{g}\) with \(x_{\mathcal{N}}\). The initial solution (\(x_{1}\)) is either random or generated using a simple greedy heuristic. One of the well-known drawbacks of such neighborhood search strategy is that the algorithm quickly reaches a local optimum and a cycle of solutions is repeated indefinitely. In order to alleviate this, the TS metaheuristic has a short-term memory, usually called tabu list, which is used to define which moves are _forbidden_ (or _tabu_). Solutions obtained by forbidden moves are generally ignored when choosing \(x_{\mathcal{N}}\). One exception to this rule is when the forbidden neighbor improves \(x_{g}\); such a neighbor can be chosen as \(x_{\mathcal{N}}\), despite being forbidden. When the move is performed, we store its attributes \(i,j\) and \(k\) on the tabu list for the subsequent C iterations, where C is a parameter called cadence.