# Two NEH Heuristic Improvements for Flowshop Scheduling Problem with Makespan Criterion
## 3 First Improvement Method, NEH-SS1
### Results and Discussion  
The results obtained with this new improvement method (NEH-SS1) are presented in Table 3. For SS1, all possible configurations numbered in Table 2 for the problems of 20 and 50 jobs were tested. For a higher number of jobs, it would be impossible to test all possibilities for each problem instance. This is why only some, randomly chosen thanks to factorial basis decomposition, are tested. In order to limit the execution time of this method, it was limited to three times the execution time of the classic NEH heuristic for problems with 100 and 200 jobs, and to two times this execution time for problems with 500 jobs. Computational experiments were performed using Dev-C++ 4.9.9.2 software with a laptop Acer TravelMate 6292 with a 2 GHz Core 2 Duo T7300 processor and 2 Gb DDR2 RAM. Results presented in Table 3 give the average relative percentage deviation (ARPD) over optimum, of classic NEH and NEH-SS1 heuristics. The average CPU times of heuristics, presented in seconds, are those measured on the computer noted above. The final column of Table 3 presents the improvement percentage obtained with the NEH-SS1 method with regard to NEH initial results, thanks to the following equation:  
\[\text{Improvement}=(\text{NEH}-\text{NEH-SS1})/(\text{NEH}) \tag{3}\] \begin{table}
\begin{tabular}{c c c c c c c c c c c} \hline \hline \(\mathbf{J}\)/\(\mathbf{M}\) & \(\mathbf{Ta_{\cdot}}\) & \(\mathbf{1}\) & \(\mathbf{2}\) & \(\mathbf{3}\) & \(\mathbf{4}\) & \(\mathbf{5}\) & \(\mathbf{6}\) & \(\mathbf{7}\) & \(\mathbf{8}\) & \(\mathbf{9}\) & \(\mathbf{10}\) \\ \hline
20/5 & 00x & 1 & 8 & 2 & 2 & 1 & 1 & 2 & 4 & 1 & 1 \\
20/10 & 01x & 1 & 4 & 1 & 2 & 1 & 1 & 1 & 1 & 1 & 6 \\
20/20 & 02x & 1 & 1 & 2 & 1 & 1 & 1 & 2 & 1 & 4 & 2 \\
50/5 & 03x & 16 & 16 & 16 & 384 & 16 & 96 & 2304 & 64 & 64 & 64 \\
50/10 & 04x & 16 & 4 & 32 & 4 & 16 & 4 & 48 & 4 & 16 & 8 \\
50/20 & 05x & 8 & 1 & 8 & 16 & 4 & 4 & 2 & 64 & 1 & 2 \\
100/5 & 06x & \(1.2\times 10^{10}\) & \(8.8\times 10^{5}\) & \(2.8\times 10^{7}\) & 147,456 & 524,288 & \(4.7\times 10^{6}\) & \(3.4\times 10^{8}\) & 512 & 73,728 & 73,728 \\
100/10 & 07x & 16,384 & 55,296 & 384 & 9216 & 24,576 & 55,296 & 9216 & 4096 & 18,432 & \(7.1\times 10^{6}\) \\
100/20 & 08x & 2048 & 16 & 512 & 12,288 & 1024 & 512 & 48 & 3072 & 192 & 32 \\
20/10 & 09x & \(4.3\times 10^{16}\) & \(6.5\times 10^{16}\) & \(8.9\times 10^{13}\) & \(1.8\times 10^{16}\) & \(2.0\times 10^{14}\) & \(2.2\times 10^{16}\) & \(2.2\times 10^{13}\) & \(2.3\times 10^{18}\) & \(9.6\times 10^{16}\) & \(7.2\times 10^{13}\) \\
20/20 & 10x & \(4.0\times 10^{15}\) & \(3.5\times 10^{11}\) & \(2.4\times 10^{15}\) & \(5.2\times 10^{11}\) & \(2.2\times 10^{16}\) & \(5.2\times 10^{11}\) & \(2.5\times 10^{13}\) & \(5.8\times 10^{10}\) & \(3.6\times 10^{9}\) & \(5.7\times 10^{12}\) \\
50/20 & 11x & \(1.0\times 10^{27}\) & \(6.0\times 10^{68}\) & \(4.3\times 10^{76}\) & \(6.1\times 10^{72}\) & \(2.9\times 10^{65}\) & \(1.2\times 10^{73}\) & \(1.7\times 10^{99}\) & \(2.8\times 10^{99}\) & \(1.9\times 10^{70}\) & \(1.2\times 10^{70}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Possible orders of [PERSON]’s benchmark after jobs ranking in the NEH heuristic. Percentages calculated above the line in Table 3 were calculated with regard to optimal values, and those calculated below the line were calculated with regard to a lower bound. The sorting methods employed in the classic NEH and the new (NEH-SS1) methods are identical. This has little influence on the first sorting because in SS1 all possibilities are tested. However, it is important to note that the computation is equivalent in the second part of both of the NEH heuristic runs.