# Solving Non-Permutation Flow Shop Scheduling Problem with Time Couplings
## 5 Computer Experiments  
In order to verify the effectiveness of the proposed elimination property, we have prepared a set of computer experiments using solving methods described in Section 4 as well as a number of benchmark problem instances. We will start by describing the benchmark instances. Such benchmarks for basic scheduling problems are available in the literature with one of the most well-known being benchmarks proposed by [PERSON] [46], which include a set of instances for the FSSP. However, [PERSON]'s benchmarks do not account for our concept of time couplings. Thus, we have decided to employ our own instance generator, which is based closely on the generator proposed by [PERSON]. The pseudocode of the instance generation procedure is shown in Algorithm 2. The procedure input is the seed (\(s\)), problem size (\(n\) and \(m\)), and range of processing and coupling times given by lower (\(L\)) and upper (\(U\)) bounds. Lines 1-4 are identical to basic [PERSON]'s generator except that [PERSON] simply assumes \(L=1\) and \(U=99\). Lines 5-12 are used to generate values \(\hat{r}_{i}\) and \(\hat{d}_{i}\) and ensure that \(\hat{r}_{i}\leq\hat{d}_{i}\). ```
Data:\(s\), \(n\), \(m\), \(L\), \(U\) \(g\leftarrow\) TaillardGenerator(\(s\), \(U\)); for\(i=1,2,\ldots,m\)do for\(j=1,2,\ldots,n\)do \(p_{i,j}\gets g.\)nextInt(); \(v_{1}=\leftarrow\)\(g.\)nextInt(); \(v_{2}=\leftarrow\)\(g.\)nextInt(); if\(v_{1}<v_{2}\)then \(\hat{r}_{i}\gets v_{1}\); \(\hat{d}_{i}\gets v_{2}\); else \(\hat{r}_{i}\gets v_{2}\); \(\hat{d}_{i}\gets v_{1}\);
```  
**Algorithm 2**Instance generation procedure. We have prepared two sets of testing instances: A and B. The first set contains instances of small size, which we will use to test the effectiveness of the TS metaheuristic by comparing it to the exact B&B method. The second set contains larger instances meant to represent a more practical setting. For the set B, we employ an approach similar to [PERSON]'s: there are 12 size groups from \(20\times 5\) to \(500\times 20\), with 10 instances per group. We use the same seeds as the ones proposed by [PERSON]. However, while [PERSON] assumed processing times from range 1 to 99 only, we decided to use five groups of processing times and minimum/maximum machine idle times: (1) 1-99, (2) 10-90, (3) 30-70, (4) 40-60, (5) 45-55. Thus, set B contains \(12\times 10\times 5=600\) instances in total. Our next point of interest is establishing a measure of quality that will allow for comparing instances of different sizes and different goal function values. In our case, that measure is Percentage Relative Deviation (\(PRD\)). Let \(\pi(I)\) be the solution obtained by the considered algorithm for instance \(I\) and \(\pi^{*}(I)\) be a reference solution for that instance. Then, \(PRD(I)\) is defined as follows:  
\[PRD(I)=\frac{C_{\max}(\pi(I))-C_{\max}(\pi^{*}(I))}{C_{\max}(\pi^{*}(I))}\cdot 100\%. \tag{19}\]  
In practice, the value of \(C_{\max}(\pi^{*}(I))\) was either the optimal solution (obtained through the B&B method) or the best known solution (i.e., the best of tested algorithms for that instance) if an optimal solution was not known. All experiments were conducted on a machine with an AMD Ryzen Threadripper 3990X processor @ 3.8 GHz with 63 GB of RAM using Windows Subystem for Linux. The TS method was written in C++ and compiled with g++ 9.3.0 using the -03 compilation flag. The GA method was run using Python3 version 3.8.2. In the first experiment, we compared TS and B&B methods for instance set A. The results are shown in Table 3. For a given instance size, \(T_{f}\) is the running time of B&B for subgroup \(f\), with different subgroups having different values of \(L\) and \(U\) as described earlier. We observe that, while the running time of B&B increases with problem size, it also decreases with the subgroup number. For size group \(5\times 5\), the B&B method in subgroup 5 is over 280 times faster than for subgroup 1. This means instances with a smaller range of processing and machine idle times are much easier to solve.