Task $5($Flow Shop Problem: Dannenbring and GA$)$

Consider an instance of the problem $F3||C_{\text{m}\text{a}\text{x}}$ with $5$ jobs and the following processing time matrix:

$P=([7,8,10,5,6],[11,4,7,9,5],[12,9,5,3,8])$

where an element $p_{ij}$ denotes the processing time of job $J_j$ on machine $M_i.$

a$)$ Determine a feasible schedule $S^{DB}$ for this problem by applying the construction scheme according to Danienbring.

b$)$ It can be shown that for Flow Shop problems with $3$ machines, an optimal schedule will always be a permutation schedule. Therefore, a permutation$-$based Genetic Algorithm can be applied.

Two feasible schedules $S^1=(2,3,5,4,1)$ and $S^2=(5,4,3,1,2)$ are given as parents with objective function values $f(S^1)=62$ and $f(S^2)=60.$ Determine two children $S^3$ and $S^4$ by applying a $(3,4)-$order$-$crossover. In addition, a mutation $-$ a $(4-1)-$shift $-$ is induced in the first child. Calculate the objective function values of both offspring and determine the best chromosome in the population.