# Two NEH Heuristic Improvements for Flowshop Scheduling Problem with Makespan Criterion
## 3 First Improvement Method, NEH-SS1
### Factorial Basis Decomposition
When the number of jobs \(j\) concerned with permutations is greater than or equal to 3, it proceeds in the same way because the rest of the division is between 0 and \((j!-1)\) and yields exactly \(j!\) possibilities to arrange \(j\) jobs. In order to perfectly understand how it is possible to describe all the possible permutations for a number of jobs greater than or equal to 4, the complete matching table between the numbers and the 24 permutations of a set of 4 elements are presented in the Table 1. To build the permutation corresponding to a given number, it is decomposed on the basis of all precedent factorials. For example, the equality \(14=2\times 3!+1\times 2!+0\times 1!\) links the value 14 to the permutation **cbad**. Indeed, to recompose the corresponding permutation, the four values from the order (abcd) are taken, and are counted from 0 to 3 for the first set (of four values), from 0 to 2 for the second set (of three values), and from 0 to 1 for the third set (of two values). Then, the element corresponding to the value **2** is extracted first (i.e., **c**). Then, the element corresponding to the value **1** in the remaining sequence set (**b**), is extracted. Then, the element corresponding to the value **0** in the remaining sequence (**a**), is extracted. At the end of extraction process, the last element (**d**) remains, which is put at the end of the permutation. It can be noticed that there is a complete bijection between a number \(j\) and its permutation, and it can also thus be easily understand how the remaining Euclidian division by \(j!\) is directly linked to a unique permutation inside a group of \(j\) jobs. To conclude this example, to finally see which permutation corresponds to the number \(n=75\), the values of the remaining Euclidian divisions are re-attributed to the correct groups of jobs. In this way, (1 1 0 1 4) becomes (1 4 1 0 1). It only remains to perform permutations for all groups of jobs as a function of their corresponding numbers. Then, the following permutation comes:  
\[75 = 1 4 1 0 1\] \[\text{Permutation:}\] \[\text{(J13 -J7)}-\text{(J14 -J6 -J10)}-\text{(J42 -J39)}-\text{(J12 -J29)}-\text{(J41 -J40)}\] \begin{table}
\begin{tabular}{c c c c c c c c c c} \hline \hline
**Number** & 3! & 2! & 1! & 1! & **Permutation** & **Number** & **3!** & **2!** & **1!** & **1!** & **Permutation** \\ \hline
0 & 0 & 0 & 0 & abcd & 12 & 2 & 0 & 0 & cabd \\
1 & 0 & 0 & 1 & abdc & 13 & 2 & 0 & 1 & cadb \\
2 & 0 & 1 & 0 & acbd & 14 & 2 & 1 & 0 & cbad \\
3 & 0 & 1 & 1 & acdb & 15 & 2 & 1 & 1 & cbda \\
4 & 0 & 2 & 0 & adbc & 16 & 2 & 2 & 0 & cdb \\
5 & 0 & 2 & 1 & adcb & 17 & 2 & 2 & 1 & cbda \\
6 & 1 & 0 & 0 & bacd & 18 & 3 & 0 & 0 & dabc \\
7 & 1 & 0 & 1 & badc & 19 & 3 & 0 & 1 & dacb \\
8 & 1 & 1 & 0 & bcad & 20 & 3 & 1 & 0 & dba \\
9 & 1 & 1 & 1 & bcda & 21 & 3 & 1 & 1 & dbea \\
10 & 1 & 2 & 0 & bdac & 22 & 3 & 2 & 0 & dcab \\
11 & 1 & 2 & 1 & bdca & 23 & 3 & 2 & 1 & dcba \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Illustration of the factorial basis decomposition of the 24 possible permutations of the group of four elements [a,b,c,d]. This way of describing all available equivalent possible jobs orders is not only useful for describing all possible orders (for numbers of jobs up to 50), but also for choosing a few orders from a large number (i.e., numbers of jobs higher than 100). It is sufficient to apply a random number to obtain a new jobs order to test.