# Unified Genetic Algorithm Approach for Solving Flexible Job-Shop Scheduling Problem
## 3 Unified Candidate Order-Based Genetic Algorithm  
### Existing GAs for the FJSP  
Table 2 provides an example of the FJSP with three jobs (\(J_{1}\), \(J_{2}\), and \(J_{3}\)) and three machines (\(M_{1}\), \(M_{2}\), and \(M_{3}\)). Each job consists of two operations that should be processed in sequence, and \(j\)th operation of \(J_{i}\) (\(i=1\), \(2\), \(3\)) is denoted by \(o_{ij}\). An operation is processed by one of its alternative machines. For example, \(o_{11}\) has three alternative machines (\(M_{1}\), \(M_{2}\), and \(M_{3}\)). Different alternative machines can have different processing times for a single operation. In Table 2, \(M_{2}\) is the SPT machine for \(o_{11}\) such that its processing time is shorter than other machines. In contrast, \(o_{12}\) has only two alternative machines (\(M_{2}\) and \(M_{3}\)), since \(M_{1}\) is not available for this operation. In order to create a schedule for the FJSP, two kinds of decisions are needed. First, each operation should be assigned to one of its alternative machines. Second, operations should be sequenced. Typically, GAs for the FJSP utilize a multichromosome that consists of the OS part and the MS part for representing the operation sequence and machine assignment, respectively. An example of a multichromosome for the FJSP is shown in the upper part of Figure 1. Let \(MS\big{(}o_{ij}\big{)}\) denote the machine to be used to process \(o_{ij}\). It is clear that \(MS\big{(}o_{ij}\big{)}\) must be an element of a set of alternative machines for \(o_{ij}\). In this paper, a sequence of operations indicates the assignment orders. Let \(OS\big{(}o_{ij}\big{)}\) denote the order of \(o_{ij}\) in a sequence of given operations. Note that the encoding scheme for the OS part is the position listing representation, in which each gene specifies an order of the associated item. Thus, the OS part in Figure 1 can be converted into a sequence of given operations, \(\langle o_{511}\), \(os_{12}\), \(os_{21}\), \(os_{31}\), \(os_{32}\), \(os_{22}\)). An operation \(o_{ab}\) is scheduled prior to \(o_{cd}\) if \(OS(o_{ab})<OS(o_{cd})\). For instance, \(o_{11}\) is the first operation to be scheduled in the Gantt chart in the lower part of Figure 1, since \(OS(o_{11})=1\). Moreover, we can start \(o_{11}\) at time \(t=0\) \begin{table}
\begin{tabular}{c c c c c} \hline \hline \multirow{2}{*}{**Job**} & \multirow{2}{*}{**Operation**} & \multicolumn{4}{c}{**Processing Time**} \\ \cline{3-5}  & & \(M_{1}\) & \(M_{2}\) & \(M_{3}\) \\ \hline \multirow{2}{*}{\(J_{1}\)} & \(o_{11}\) & 4 & 3 & 5 \\ \cline{2-5}  & \(o_{12}\) & N/A & 6 & 8 \\ \hline \multirow{2}{*}{\(J_{2}\)} & \(o_{21}\) & 10 & N/A & 8 \\ \cline{2-5}  & \(o_{22}\) & 5 & 6 & 4 \\ \hline \multirow{2}{*}{\(J_{3}\)} & \(o_{31}\) & 7 & 10 & N/A \\ \cline{2-5}  & \(o_{32}\) & 3 & 4 & 5 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: An example of the FJSP. Figure 1: Decoding the multichromosome representation for the FJSP. The order of given operations, \(OS\big{(}o_{ij}\big{)}\)s, must satisfy the precedence relationships among operations within a single job. In other words, \(OS\big{(}o_{ij}\big{)}\) must be smaller than \(OS(o_{ik})\) if \(j<k\). In Figure 1, \(o_{12}\) is the second operation (\(OS(o_{12})=2\)) of a job and its start time is 4, because we can start \(o_{12}\) after its predecessor, \(o_{11}\), is completed. Valid \(MS\big{(}o_{ij}\big{)}\) and \(OS\big{(}o_{ij}\big{)}\) values yield a feasible schedule for the FJSP, which can be represented in the form of a Gantt chart, as shown in Figure 1.  
The crossover operation is the \"backbone\" of the GA, and crossover operators are designed to generate two offspring solutions by recombining the genes of two parent solutions. The offspring solutions inherit the features of their parents. In other words, crossover operators should generate offspring solutions similar to their parents. However, this is difficult to achieve when solving the FJSP by applying a GA based on a multichromosome.