## 6 Computational Results
### PFSSP Computational Results  
For PFSSP with 10 jobs, 6 machines, processing times from the TABLE section (it corresponds to the first benchmark in Table 1) and the model given by Equations (84)-(89), the program code in GAMS can be, e.g., as follows:  
* $ITILE permutation flow shop scheduling problem
* $OFFSETMREF
* $OFFSETLLIST
* $OFFSETLREF
* OPTION ITERLIM=200,000
* ITERLIM number of iterations OPTION OPTCR=0.00001
* OPTION OPTCR=0.001
* OPTCR stopping in MIP in case the best solution is within the limits
* 100*OPTCR% of the global\"extreme
* section defining indexes SETS
* I jobs /1*10/ K machines /1*6/;ALIAS(I,J);
* position of the job in the permutation  ALIAS(K,R);
* input data section  PARAMETERS  N,M;  N=CARD(I);  M=CARD(K);  TABLE P(I,K)  1 2 3 4 5 6  1 333 991 996 123 145 234  2 333 111 663 456 785 532  3 252 222 222 789 214 586  4 222 204 114 876 752 532  5 255 477 123 543 143 142  6 555 566 456 210 698 573  7 558 899 789 124 532 12  8 888 965 876 537 145 14  9 889 588 543 854 247 527  10 999 889 210 632 451 856;
* on machine k, while machine k+1 becomes free  Cmax total processing time for all tasks (makespan);  BINARY VARIABLE X;  NONNEGATIVE VARIABLE V;  NONNEGATIVE VARIABLE W;
*section describing the system of (in)equalities  EQUATIONS  EQ1(I)  EQ2(J)  EQ3(K)  EQ4(K)  EQ5(I,K)  OBJFCE(K);  EQ1(I)... SUM(J,X(I,J)) =E- 1;  EQ2(J)... SUM(I,X(I,J)) =E- 1;  EQ3(K)$(ORD(K) L (M-1)).. W('1',K) =E- 0;  EA4(K) $(ORD(K) GE 2).... V('1'',K) =E- SUM((R,I)$(ORD(R) LE (ORD(K)-1)),P(I,R)*X('1'',I));  EQ5(I,K)$((ORD(I) LE (N-1)) AND (ORD(K) LE (M-1))) .. V(I+1,K)+SUM(J,P(J,K)*X(I+,J))+W(I+1,K) =E-  W(I,K)+SUM(J,P(J,K+1)*X(I,J))+V(I+1,K+1);  OBJFCE(K)$(ORD(K) EQ M).. Cmax =E- SUM(I,V(I,K)+SUM(J,P(J,K)*X(I,J)));
*description of the model, running the solver, and displaying the results  MODEL FLOWShopP /ALL/;  SOLVE FLOWShopV USING MIP MINIMIZING Cmax;  DISPLAY X.L, V.L, W.L, Cmax.L;  
The ability to compute optimal solutions was checked using standard benchmarks from OR-Library (OR = Operations Research) accessible at Brunel University London [80], originally described in [81]. The computational results are summarised in Table 1. For instances with 30 or more jobs, GAMS does not find the optimal solution in the 1000 s time limit, but only a \"close\" approximation, which, however, differs by less than 10% even for the last instance \(75\times 20\), where the optimal value is unknown due to the huge size of the search space and is only estimated by the interval. For such cases, we at least suggest a solution method using the genetic algorithm [82]. To do this, we will need a model that builds an appropriate schedule for the permutation. The genetic algorithm will then select a promising part of the search space of permutations in which a good approximation of the optimum can be found in a reasonable amount of time. If we have processing times \(p_{ij}\) for job \(i\) on machine \(j\), and a job permutation \(J_{1},J_{2},\,\ldots,\,J_{n}\), then we can calculate the completion times \(C_{I_{i},j}\) as follows:  
\[C_{I_{1},1} = p_{I_{1},1} \tag{90}\] \[\forall i\in J-\{1\}:C_{I_{2},1} = C_{I_{1}-1,1}+p_{I_{2},1}\] (91) \[\forall k\in M-\{1\}:C_{I_{1},k} = C_{I_{1},k-1}+p_{I_{1},k}\] (92) \[(\forall i\in J-\{1\})(\forall k\in M-\{1\}):C_{I_{1},k} = \max\left\{C_{I_{1}-1,k},\,C_{I_{1},k-1}\right\}+p_{I_{1},k}\] (93) \[C_{\max} = C_{I_{n},m} \tag{94}\]  
As the genetic algorithms [79] are well known, we only summarise parameter settings and describe only the problem-specific operators in more detail. The fitness function is inversely proportional to the makespan, the smaller the makespan, the higher the value of the fitness function. The number of individuals in the population was set to 50 and the number of iterations to \(10n^{2}\). The initial population was generated randomly, and the parents for the crossover operation were determined by binary tournament selection. As to the _crossover_ operation, we cannot use the traditional two-point crossover, because it would lead to infeasible solutions.