# Unified Genetic Algorithm Approach for Solving Flexible Job-Shop Scheduling Problem
## 1 Introduction  
Production scheduling is one of the most important decision-making procedures on manufacturing shopfloors, as it helps to utilize resources efficiently and maintain competitiveness in manufacturing companies [1, 2, 3]. Most production scheduling problems are NP-hard combinatorial optimization problems such that the optimal schedules are hard to find in polynomial time [4]. In this context, metaheuristic algorithms that can be used to find near optimal schedules in practical time are popular in production scheduling literature [5]. Examples of metaheuristic algorithms for solving production scheduling problems are the genetic algorithm (GA) [6], tabu search (TS) [7], simulated annealing (SA) [8], and particle swarm optimization (PSO) [9]. This paper aims to develop a novel GA for solving the flexible job-shop scheduling problem (FJSP). The classical job-shop scheduling problem (JSP) is one of the most well-known production scheduling problems. It consists of \(m\) machines and \(n\) jobs. A job contains a number of operations to be processed in a fixed order. In the JSP, each operation can be processed by one specific machine [10, 11]. The FJSP is an extension of the classical JSP, which allows an operation to be processed by one of two or more machines. In other words, an operation is processed by one of alternative machines in the FJSP [12]. Since a machine for a specific operation is predetermined, the JSP can be solved by specifyingthe priorities of given operations such that a high-priority operation precedes others with lower priorities in the queue for given machines. Thus, the JSP can be regarded as a sequencing problem [13; 14]. In comparison with the JSP, the FJSP requires an additional decision related to which machine is used to process a specific operation. Consequently, two kinds of decisions, i.e., operation sequencing and machine selection, are required to solve the FJSP [1]. GA has been a popular metaheuristic algorithm for solving the JSP and FJSP in recent decades [10; 11; 12; 15]. In order to apply GA, a solution of the given problem must be encoded in the form of a string, known as a chromosome [6]. One issue is that a chromosome for the FJSP must consist of two subchromosomes to account for the operation sequence (OS) part and the machine selection (MS) part. In other words, existing GAs for the FJSP are based on a multichromosome. Typically, the MS part is represented by a string of categorical values, whereas the OS part forms a sequence of given operations. Since the MS and OS parts have quite different structures, it is difficult to apply an identical genetic operator to both of them. Consequently, the MS and OS parts are separately evolved by different kinds of genetic operators in existing GAs for the FJSP. This traditional approach has the following limitations: First, it makes the GA hard to implement since different kinds of genetic operators should be applied. In particular, crossover operators for sequencing problems are a lot more complicated than simple one-point or two-point crossovers [16]. Second, there is no correlation between the order and machine in a single operation. In other words, the evolution of the MS part occurs independently from that of the OS part. Assume that an operation has the optimal order and is assigned to the optimal machine in a chromosome. Then, it is desirable that this combination of order and machine should also be maintained in the chromosome's offspring, which is hard to achieve using the traditional approach. Consequently, the traditional approach can cause a loss of good combinations in chromosomes and unnecessary diversity in the population. To this end, this paper poses two research questions: how can we reduce the number of genetic operators in the GA for the FJSP, which will have a significant impact on the complexity of the GA? Can the GA with a reduced number of genetic operators, designed to maintain good combinations of OS and MS genes, deal with the FJSP effectively?