# Hybrid Flow Shop Scheduling Problems Using Improved Fireworks Algorithm for Permutation
## 3 Fireworks Algorithm
### The Improved Fireworks Algorithm
By the integer coding based on the sequence of the jobs, the position of the individual fireworks is encoded as the machining sequence of the jobs. The PFSP with seven jobs is taken to explain the mapping rule from continuous space to discrete space. If the randomly generated fireworks are sorted by size and the position sequence is (3, 5, 4, 6, 1, 7, 2), the processing order of the jobs is \(\{j_{3}\to j_{5}\to j_{4}\to j_{6}\to j_{1}\to j_{7}\to j_{2}\}\). In this way, the sparks in continuous space are uniquely mapped to a solution in discrete space. ### Hybrid Flow Shop Scheduling Problems

In the HFSP, the \(m\) jobs are processed through \(n\) stages (\(n\geq 1\)) and there is at least one stage that has more than one parallel machine [49]. The minimum makespan is chosen as the optimization objective of the HFSP. The assumptions of HFSP are as follows [50]:

1. Each machine can process only one job at a time;

Figure 3: The layout of permutation flow shop scheduling. Each job is processed on one machine at a time;
3. Each job is processed at each stage in the same order;
4. The parallel machines in each stage are independent;
5. The processing time of the jobs is related to machines and process, and is known;
6. Pre-emption, lot streaming, and backlogging are not allowed [51]. The layout of the HFSP is presented in Figure 4. There are \(N_{j}\) parallel machines at stage \(j\). All jobs are completed when the process stage \(n\) of the last job is completed. The mathematical model of the HFSP is shown from Equations (14) to (16) [52]. The optimization goal is shown in Equation (17). Figure 2:0 Figure 2:1

Figure 2:2 Figure 2:3

Figure 2:4 Figure 2:5

Figure 2:6

where \(N_{jk}\) represents the number of jobs processed on machine \(k\) at stage \(j\). \(T_{ijk}\) denotes the processing time when job \(i\) is processed on machine \(k\) at stage \(j\). \(S_{ijk}\) and \(C_{ijk}\) represent the start and end time of job \(i\) on machine \(k\) at stage \(j\). \(S_{h_{jk}}\) and \(C_{h_{jk}}\) represent the start and end time of the \(h\)th job on machine \(k\) at stage \(j\). The solution is decoded by scheduling matrix. The scheduling matrix \(A\) is composed of \(m\) rows and \(n\) columns. Moreover, each element in matrix \(A\) is a random number limited by the number of parallel machines. The matrix \(A\) is depicted as follows. \[A_{m\times n}=\left[ \begin{array}{cccc}a_{11}&a_{12}&\cdots&a_{1n}\\ a_{21}&a_{22}&\cdots&a_{2n}\\ \vdots&\vdots&\vdots&\vdots\\ a_{m1}&a_{m2}&\cdots&a_{mn}\end{array} \right] \tag{18}\]

where \(a_{ij}\) is a random value between the interval \((1,N_{j}+1)\). It shows that the \(i\)th job would be processed on machine \(\mathrm{int}(a_{ij})\) at stage \(j\), (\(\mathrm{int}(a_{ij})\) means the integer components of \(a_{ij}\)). Furthermore, the priority

Figure 4: The layout of the hybrid flow shop scheduling problem (HFSP). of the jobs is determined by the size of the \(a_{ij}\). An example to determine the process priority of the jobs by matrix \(A_{3\times 3}\) is shown as follows:

\[A_{3\times 3}=\left[ \begin{array}{ccc}1.3&2.5&3.3\\ 2.5&1.8&2.8\\ 2.2&1.1&1.2\end{array} \right]\]

Matrix \(A\) shows that three jobs are processed through three process stages and the number of machines in each stage is two, two, and three. According to the stated rules, the first column of matrix \(A\) shows that three jobs are processed at stage one. The first job is processed on the first machine at stage one. The second job and the third job are processed on the second machine at stage one. The job with small \(a_{ij}\) would be processed preferentially, so the third job would be processed first. From the second column of matrix \(A\), the first job is processed on the second machine at stage two. The second job and the third job are processed on the first machine at stage two, but the third job would be processed first. The processing sequence of the jobs in process stage three are determined similarly.