# Recent Research Trends in Genetic Algorithm Based Flexible Job Shop Scheduling Problems

Authors: Muhammad Kamal Amjad; Shahid Ikramullah Butt; Rubeena Kousar; Riaz Ahmad; Mujtaba Hassan Agha; Zhang Faping; Naveed Anjum; Umer Asgher
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

Flexible Job Shop Scheduling Problem (FJSSP) is an extension of the classical Job Shop Scheduling Problem (JSSP). The FJSSP is known to be NP-hard problem with regard to optimization and it is very difficult to find reasonably accurate solutions of the problem instances in a rational time. Extensive research has been carried out in this area especially over the span of the last 20 years in which the hybrid approaches involving Genetic Algorithm (GA) have gained the most popularity. Keeping in view this aspect, this article presents a comprehensive literature review of the FJSSPs solved using the GA. The survey is further extended by the inclusion of the hybrid GA (hGA) techniques used in the solution of the problem. This review will give readers an insight into use of certain parameters in their future research along with future research directions.


---

## Body

## 1. Introduction

The share of manufacturing sector in the Gross Domestic Product (GDP) of the world is up to 18% thus making it extremely important to the worldwide economy [1]. Efficient manufacturing leads to improvement in profits, market share, and ultimately a competitive advantage in new product launch time [2]. Manufacturing needs to have efficient and optimal operations of the facility which were later termed as “scheduling.” Owing to the importance of the subject, huge amount of research has been conducted to formulate techniques, separately for each shop type, which can effectively handle the complex problem of scheduling.Genetic Algorithm has proven to be one of the most effective evolutionary techniques for solving Job Shop Scheduling Problem (JSSP) and consequently Flexible Job Shop Scheduling Problem (FJSSP). Çaliş and Bulkan [3] pointed out that 26.4% of the research studies for solution of JSSP have been conducted using GA. This is the highest percentage of any artificial intelligence based technique used for the solution of the said problem which became motivation for this review paper.This paper critically analyzes the state-of-the-art Flexible Job Shop Scheduling Problem (FJSSP) solution techniques belonging to the GA class. In this review paper, Section2 introduces the machine layouts and a classification scheme. FJSSP is then presented along with formulation and complexity along with scheduling algorithms. Section 3 gives an insight to the Genetic Algorithms (GA), basic elements, and their adaptation for the solution of FJSSP. Section 4 presents the schematic review of literature for obtaining solution of FJSSP with GA, advanced GA, and hybrid GA (hGA) approaches. Section 5 provides analysis and discussion and afterwards Section 6 presents the conclusion. Notations are widely used in this paper for clutter-free presentation of literature, which have been summarized in Notations. All other abbreviations are explained in paper where they appear for the very first time.


## 2. Manufacturing Scheduling

### 2.1. Scheduling

Scheduling refers to the allocation of tasks (e.g., jobs, parts, and operations) to resources (e.g., machines) in such a way that they can be processed and/or manufactured in an optimal manner [4]. The consumer wants to get the product delivered at required time and hence scheduling becomes a critical factor in meeting this demand [5] and plays a vital role in the operation of any manufacturing environment. The scheduling problem aims to formulate a processing order that can achieve a desired objective in an optimal manner which can be total time required for completing all operations, maximum lateness, maximum earliness, and so on. Therefore schedules can be generated to attain various performance measures of the shop floor. Scheduling can be of the following two types:(i)
Static: jobs arrive at an idle machine after a fixed time interval.
(ii)
Dynamic: jobs arrive in random manner.Dynamic scheduling is considered a situation when any disruption occurs in the manufacturing environment in contrast to the static scheduling. This may require necessary changes in the schedule so that it can remain optimal. Such problems are classified as job and/or recourse related [6]. Due to the importance of scheduling in manufacturing environments, handsome literature is published in this area. Some of the salient works on scheduling in a general context are included in references [7–12], whereas the classification of scheduling problem is presented in Figure 1 [13].Figure 1
Classification of scheduling problem.


### 2.2. Classification of Machine Layouts

Based upon the requirement of manufacturing process and product requirements, the machine shops have been classified in various layouts. Figure2 presents a schematic classification of the machine layout with emphasis on the Job Shop. The JSSP is a classical combinatorial optimization problem which has been attracting research interest since 1950s [14, 15]. JSSP has the following salient features:(i)
It deals with the sequencing of a number of operations on fixed machines.
(ii)
Every job can have a different processing time.
(iii)
Each job must undergo a set of tasks performed in a given manner on different machines in order to be completed.Figure 2
Classification of shop layouts.The FJSSP is a further extension of JSSP in which the operations can be performed on any machine which can be selected from a finite number of given set of machines in a flexible manufacturing cell. Thus the problem is intricate in a sense that it also involves machine assignment problem for each operation and thus it is subdivided into following two parts:(i)
Routing, through which the jobs should be processed on available set of machines
(ii)
Sequencing, that is, the order in which the jobs should be processed on the selected machines.Thus there is inherent “flexibility” in the FJSSP in contrast to the JSSP, which may be used as advantage for processing various types of parts, both through routing and sequencing. Flexibility has been introduced in the classical JSSP in some of the following ways:(i)
The idea of FJSSP was first adapted by Brucker and Schlie [16] as multipurpose machines equipped with different tools.
(ii)
Barnes and Chambers [17] argued that a JSSP can be converted into FJSSP by incorporating multiple instances of a single machine where a bottleneck is encountered during the scheduling process. This concept is sometimes called parallel machine FJSSP.
(iii)
Najid et al. [18] argued that flexibility is brought in the JSSP with the condition that one machine may be able to perform more than one type of operation.Kacem et al. [19] classify the FJSSPs into the following types:(i)
Total FJSSP (T-FJSSP): in this type, required operation can be performed on any of the available identical machines in the machine cell; thus complete flexibility has been achieved.
(ii)
Partial FJSSP (P-FJSSP): in this type, some operations can only be performed on specific machines and remaining operations can be executed on any of the machines in the machine cell.According to Chan et al. [20], there are the following two types of FJSSP:(i)
Type I FJSSP: in this type, jobs under consideration have different operation sequences and identical/nonidentical machines for each operation. In this problem, the interest is to find the operation’s sequence and job processing order.
(ii)
Type II FJSSP: in this type, jobs under consideration have fixed operation sequences, but different identical or nonidentical machines for each operation. In this problem, the interest is to arrange jobs on machines according to their operation sequences.


### 2.3. Optimization

A schedule for any manufacturing product has to be optimum in order to obtain effectiveness. Optimization refers to obtaining the best solution in a solution space with respect to some predefined criteria [21, 22]. The criterion to be minimized or maximized is called objective function. For constrained optimization, the objective function is to be optimized keeping in view the constraints which govern the system. When viewed from a manufacturing system perspective, optimized process produces maximum output with minimum input, or vice versa, as desired. Figure 3 presents a flow of a generic optimization process.Figure 3
A generic optimization process.A general optimization problem can be defined as follows:(1)
M
i
n
i
m
i
z
e
/
m
a
x
i
m
i
z
e
o
b
j
e
c
t
i
v
e
f
u
n
c
t
i
o
n
z
=
f
x
S
u
b
j
e
c
t
t
o
c
o
n
s
t
r
a
i
n
t
s
g
i
x
≤
0
h
i
x
=
0
x
≥
0
;
i
=
1,2
,
…
,
n
,where x is the decision variable and g and h are inequality and equality constraints, respectively. The model presented above is for single objective optimization. The multiobjective optimization problem is formulated as follows:(2)
M
i
n
i
m
i
z
e
/
m
a
x
i
m
i
z
e
o
b
j
e
c
t
i
v
e
f
u
n
c
t
i
o
n
z
=
f
x
=
f
1
x
,
f
2
x
,
…
,
f
k
x
S
u
b
j
e
c
t
t
o
c
o
n
s
t
r
a
i
n
t
s
g
i
x
≤
0
;
i
=
1
,
…
,
p
h
j
x
=
0
;
j
=
1
,
…
,
q
.The function f
(
x
) is a k-dimensional vector of objective functions, where k is the total number of objective functions (
k
≥
2
), p is the number of inequality constraints, and q is the number of equality constraints.Multiobjective optimization is more complex than the single objective optimization due to the fact that simultaneous minimization of two or more functions can lead to a situation where decreasing one function further may cause the other function to increase. To address this optimization issue, the concept of Pareto optimality [23] is used. A Pareto optimal point is such a point in a feasible design space where further decreasing any function beyond that point will result in the increase of other functions. Another approach for multiobjective optimization is to assign weights to different objects and formulate a weighted single objective optimization problem.


### 2.4. FJSSP Formulation and Complexity

The classical JSSP can be formulated as follows [209]:(i)
A set ofn jobs are available to be scheduled on m machines.
(ii)
The set of jobs is denoted byJ (J
=
J
1
,
J
2
,
…
,
J
n).
(iii)
The set of machines is denoted byM (M
=
M
1
,
M
2
,
…
,
M
m).
(iv)
Each jobi consists of a sequence of n
i operations.
(v)
Each operationO
i
,
j of job i has to be processed on one machine, M
k out of the given set of machines, M (i
=
1,2
,
…
,
n
;
j
=
1,2
,
…
,
n
i).
(vi)
The processing time for each operationO
i
,
j is predetermined as t
i
,
j
,
k on each machine.For FJSSP the following additional parameters are added [210]:(i)
Each operation can be processed on oneM
k out of the available machines such that M
k
∈
M
i
,
j and M
i
,
j
⊆
M.
(ii)
For P-FJSSP,M
i
,
j
⊂
M.
(iii)
For T-FJSSP,M
i
,
j
=
M.It is generally assumed for FJSSP that all machines and jobs are available at timet
=
0 and one machine can only process one operation at a time such that jobs are independent from each other; thus no priority restriction exists.Initially, the Job Shop Scheduling Problem (JSSP) either was not solvable or could take excessive time period for obtaining solution. In context of computational complexity, the JSSP is NP-hard [211] and it belongs to one of the most difficult problems in this class [212]. This is due to the fact that, in a JSSP, every job can have a different and separate processing time; thus the complexity of the problem grows with the number of jobs.Framinan et al. [12] have shown that it will take 1.68 billion years to evaluate all possible solutions for 30 jobs to be scheduled on a single machine with a fast running computer at 5 Picohertz (PHz). Similarly in a state-of-the-art survey of JSSP complexity, Brucker et al. [213] pointed out that JSSP can go up to binary NP-hard class. As FJSSP is a further extension of the classical JSSP, it is further complex. A schedule for JSSP with n jobs and m machines will have n
!
m possible sequences [214]. Therefore an exact solution to these problems cannot be found in a reasonable time keeping in view the manufacturing priorities. The computation time increases exponentially for NP-hard problems with a linear increase in size of problems [215].


### 2.5. Scheduling Algorithms

According to Cormen et al. [216], algorithms are a sequence of activities which can transform an input value to a desired output, hence serving as a tool for solving a specified computational problems. The origins of algorithms can be traced back to 8th century when Al-Khwarizmi defined steps for solution of quadratic equations [217]. With the immense increase in the computational power, more and more complex calculations can now be performed to address various issues and thus more advanced algorithms have been developed. Figure 4 presents a classification for the scheduling algorithms. This classification is not exhaustive and only contains a broad view of the algorithm classes.Figure 4
Scheduling algorithms.Exact algorithms guarantee that there will be no better solution after a problem has been solved. However, as mentioned earlier, the complexity of the FJSSP is of extreme nature and there is very limited scope for the use of exact algorithms. In the modern era, approximate algorithms have gained extreme popularity due to the fact that problems have become more complex and the need to reach the solution in a reasonable time has become a prominent research area.


## 2.1. Scheduling

Scheduling refers to the allocation of tasks (e.g., jobs, parts, and operations) to resources (e.g., machines) in such a way that they can be processed and/or manufactured in an optimal manner [4]. The consumer wants to get the product delivered at required time and hence scheduling becomes a critical factor in meeting this demand [5] and plays a vital role in the operation of any manufacturing environment. The scheduling problem aims to formulate a processing order that can achieve a desired objective in an optimal manner which can be total time required for completing all operations, maximum lateness, maximum earliness, and so on. Therefore schedules can be generated to attain various performance measures of the shop floor. Scheduling can be of the following two types:(i)
Static: jobs arrive at an idle machine after a fixed time interval.
(ii)
Dynamic: jobs arrive in random manner.Dynamic scheduling is considered a situation when any disruption occurs in the manufacturing environment in contrast to the static scheduling. This may require necessary changes in the schedule so that it can remain optimal. Such problems are classified as job and/or recourse related [6]. Due to the importance of scheduling in manufacturing environments, handsome literature is published in this area. Some of the salient works on scheduling in a general context are included in references [7–12], whereas the classification of scheduling problem is presented in Figure 1 [13].Figure 1
Classification of scheduling problem.


## 2.2. Classification of Machine Layouts

Based upon the requirement of manufacturing process and product requirements, the machine shops have been classified in various layouts. Figure2 presents a schematic classification of the machine layout with emphasis on the Job Shop. The JSSP is a classical combinatorial optimization problem which has been attracting research interest since 1950s [14, 15]. JSSP has the following salient features:(i)
It deals with the sequencing of a number of operations on fixed machines.
(ii)
Every job can have a different processing time.
(iii)
Each job must undergo a set of tasks performed in a given manner on different machines in order to be completed.Figure 2
Classification of shop layouts.The FJSSP is a further extension of JSSP in which the operations can be performed on any machine which can be selected from a finite number of given set of machines in a flexible manufacturing cell. Thus the problem is intricate in a sense that it also involves machine assignment problem for each operation and thus it is subdivided into following two parts:(i)
Routing, through which the jobs should be processed on available set of machines
(ii)
Sequencing, that is, the order in which the jobs should be processed on the selected machines.Thus there is inherent “flexibility” in the FJSSP in contrast to the JSSP, which may be used as advantage for processing various types of parts, both through routing and sequencing. Flexibility has been introduced in the classical JSSP in some of the following ways:(i)
The idea of FJSSP was first adapted by Brucker and Schlie [16] as multipurpose machines equipped with different tools.
(ii)
Barnes and Chambers [17] argued that a JSSP can be converted into FJSSP by incorporating multiple instances of a single machine where a bottleneck is encountered during the scheduling process. This concept is sometimes called parallel machine FJSSP.
(iii)
Najid et al. [18] argued that flexibility is brought in the JSSP with the condition that one machine may be able to perform more than one type of operation.Kacem et al. [19] classify the FJSSPs into the following types:(i)
Total FJSSP (T-FJSSP): in this type, required operation can be performed on any of the available identical machines in the machine cell; thus complete flexibility has been achieved.
(ii)
Partial FJSSP (P-FJSSP): in this type, some operations can only be performed on specific machines and remaining operations can be executed on any of the machines in the machine cell.According to Chan et al. [20], there are the following two types of FJSSP:(i)
Type I FJSSP: in this type, jobs under consideration have different operation sequences and identical/nonidentical machines for each operation. In this problem, the interest is to find the operation’s sequence and job processing order.
(ii)
Type II FJSSP: in this type, jobs under consideration have fixed operation sequences, but different identical or nonidentical machines for each operation. In this problem, the interest is to arrange jobs on machines according to their operation sequences.


## 2.3. Optimization

A schedule for any manufacturing product has to be optimum in order to obtain effectiveness. Optimization refers to obtaining the best solution in a solution space with respect to some predefined criteria [21, 22]. The criterion to be minimized or maximized is called objective function. For constrained optimization, the objective function is to be optimized keeping in view the constraints which govern the system. When viewed from a manufacturing system perspective, optimized process produces maximum output with minimum input, or vice versa, as desired. Figure 3 presents a flow of a generic optimization process.Figure 3
A generic optimization process.A general optimization problem can be defined as follows:(1)
M
i
n
i
m
i
z
e
/
m
a
x
i
m
i
z
e
o
b
j
e
c
t
i
v
e
f
u
n
c
t
i
o
n
z
=
f
x
S
u
b
j
e
c
t
t
o
c
o
n
s
t
r
a
i
n
t
s
g
i
x
≤
0
h
i
x
=
0
x
≥
0
;
i
=
1,2
,
…
,
n
,where x is the decision variable and g and h are inequality and equality constraints, respectively. The model presented above is for single objective optimization. The multiobjective optimization problem is formulated as follows:(2)
M
i
n
i
m
i
z
e
/
m
a
x
i
m
i
z
e
o
b
j
e
c
t
i
v
e
f
u
n
c
t
i
o
n
z
=
f
x
=
f
1
x
,
f
2
x
,
…
,
f
k
x
S
u
b
j
e
c
t
t
o
c
o
n
s
t
r
a
i
n
t
s
g
i
x
≤
0
;
i
=
1
,
…
,
p
h
j
x
=
0
;
j
=
1
,
…
,
q
.The function f
(
x
) is a k-dimensional vector of objective functions, where k is the total number of objective functions (
k
≥
2
), p is the number of inequality constraints, and q is the number of equality constraints.Multiobjective optimization is more complex than the single objective optimization due to the fact that simultaneous minimization of two or more functions can lead to a situation where decreasing one function further may cause the other function to increase. To address this optimization issue, the concept of Pareto optimality [23] is used. A Pareto optimal point is such a point in a feasible design space where further decreasing any function beyond that point will result in the increase of other functions. Another approach for multiobjective optimization is to assign weights to different objects and formulate a weighted single objective optimization problem.


## 2.4. FJSSP Formulation and Complexity

The classical JSSP can be formulated as follows [209]:(i)
A set ofn jobs are available to be scheduled on m machines.
(ii)
The set of jobs is denoted byJ (J
=
J
1
,
J
2
,
…
,
J
n).
(iii)
The set of machines is denoted byM (M
=
M
1
,
M
2
,
…
,
M
m).
(iv)
Each jobi consists of a sequence of n
i operations.
(v)
Each operationO
i
,
j of job i has to be processed on one machine, M
k out of the given set of machines, M (i
=
1,2
,
…
,
n
;
j
=
1,2
,
…
,
n
i).
(vi)
The processing time for each operationO
i
,
j is predetermined as t
i
,
j
,
k on each machine.For FJSSP the following additional parameters are added [210]:(i)
Each operation can be processed on oneM
k out of the available machines such that M
k
∈
M
i
,
j and M
i
,
j
⊆
M.
(ii)
For P-FJSSP,M
i
,
j
⊂
M.
(iii)
For T-FJSSP,M
i
,
j
=
M.It is generally assumed for FJSSP that all machines and jobs are available at timet
=
0 and one machine can only process one operation at a time such that jobs are independent from each other; thus no priority restriction exists.Initially, the Job Shop Scheduling Problem (JSSP) either was not solvable or could take excessive time period for obtaining solution. In context of computational complexity, the JSSP is NP-hard [211] and it belongs to one of the most difficult problems in this class [212]. This is due to the fact that, in a JSSP, every job can have a different and separate processing time; thus the complexity of the problem grows with the number of jobs.Framinan et al. [12] have shown that it will take 1.68 billion years to evaluate all possible solutions for 30 jobs to be scheduled on a single machine with a fast running computer at 5 Picohertz (PHz). Similarly in a state-of-the-art survey of JSSP complexity, Brucker et al. [213] pointed out that JSSP can go up to binary NP-hard class. As FJSSP is a further extension of the classical JSSP, it is further complex. A schedule for JSSP with n jobs and m machines will have n
!
m possible sequences [214]. Therefore an exact solution to these problems cannot be found in a reasonable time keeping in view the manufacturing priorities. The computation time increases exponentially for NP-hard problems with a linear increase in size of problems [215].


## 2.5. Scheduling Algorithms

According to Cormen et al. [216], algorithms are a sequence of activities which can transform an input value to a desired output, hence serving as a tool for solving a specified computational problems. The origins of algorithms can be traced back to 8th century when Al-Khwarizmi defined steps for solution of quadratic equations [217]. With the immense increase in the computational power, more and more complex calculations can now be performed to address various issues and thus more advanced algorithms have been developed. Figure 4 presents a classification for the scheduling algorithms. This classification is not exhaustive and only contains a broad view of the algorithm classes.Figure 4
Scheduling algorithms.Exact algorithms guarantee that there will be no better solution after a problem has been solved. However, as mentioned earlier, the complexity of the FJSSP is of extreme nature and there is very limited scope for the use of exact algorithms. In the modern era, approximate algorithms have gained extreme popularity due to the fact that problems have become more complex and the need to reach the solution in a reasonable time has become a prominent research area.


## 3. Genetic Algorithms

GA belongs to the evolutionary algorithms class and its development was inspired through the process of natural genetic evolution. The original work on natural evolution was contributed by Darwin [218] in which he claimed that natural populations evolve according to the process of natural selection on the basis of “survival of the fittest” rule. Initial work on GA was conducted by Holland [219] in 1975, which was then extended majorly by Goldberg [220].Giraffes use their long necks to eat the leaves at higher parts of the plants. Thus as per the rule of the survival of the fittest, giraffes have evolved with generations having longer necks. The GAs can be used to mimic this natural process of genetic evolution on the principal of survival of the fittest to obtain solutions to the engineering problems. The beauty of GA lies in its adaptive nature; that is, it can change/fit itself according to the changing environment. Next section explains basic working of GA.


### 3.1. Basic Elements of GA

The basic working element of GA is gene, a group of which constitutes a chromosome. The chromosomes contain the current state data coded in the form of binary digits 0 or 1 which is distinctively stored in a gene. This structure represents a candidate solution to the problem in consideration. GA works on these coded forms of the data instead of working on actual data elements. The chromosomes combine to form a population which in turn formulates a generation. GA is an iterative evolutionary process which formulates a generation after each iteration. Figure5 represents the schematic representation of the relation of these elements.Figure 5
Basic elements of GA.


### 3.2. Genetic Operators

Each generation is subjected to the genetic operators to obtain a new generation. The new generation is theoretically better than the previous generation, as the new generation is generated after implementing the principle of “survival of the fittest” and thus it replaces the older generation. During this process, either the whole population can be changed or only the worst chromosome can be replaced [221]. Obviously, these are two extreme methods and several strategies for new population can be formulated.The iterations are guided in a way that they satisfy a fitness criterion and they are repeated to obtain an acceptable generation. The genetic operators are used to bring in the beauty of randomization in the algorithm. Standard GA operators are presented in the following.


#### 3.2.1. Selection

Selection operator is used to select chromosomes in a generation based upon fitness. The chromosomes satisfying the fitness criteria are likely to be selected in each newer generation. Generally used selection criteria are as follows:(i)
Roulette wheel selection: the selection probability of a chromosome is directly proportional to its fitness as assessed by the fitness criteria. Thus a chromosome with higher fitness will have more probability to be selected; however, lower fitness chromosomes may also be selected.
(ii)
Rank based fitness assignment: this method associates relative fitness between individual chromosomes, hence preventing a generation from containing an all-fit chromosome structure. The method is mainly used to maintain diversity in the population.
(iii)
Tournament selection:a set of chromosomes are selected randomly and then the fittest chromosomes are selected for further operation. This method is completely random.
(iv)
Elitism: the crux of this method is that it maintains a fixed number of fittest chromosomes and the rest of the population is generated by using any of the preferred selection methods. Thus this method not only ensures that the best solutions remain in the population, but also ensures the diversification of the population by selecting chromosomes from the entire solution space.


#### 3.2.2. Crossover

The crossover operator is applied on the genes of two parent chromosomes to produce two offsprings which contain distinctiveness of the parent chromosomes. These offsprings have more probability of survival than their parents as they are fit as compared to their parents. Consider two parent chromosomes having 4 genes each. Crossover can be applied to these chromosomes at third gene (at pointed arrows) to obtain two offsprings as presented in Figure6. This technique is known as single-point crossover. Many modified crossover techniques have been proposed in literature which will be identified in this review.Figure 6
A typical crossover.


#### 3.2.3. Mutation

Mutation operator is applied on a single chromosome for the purpose of changing a gene at its respective location. The gene 1011 can be mutated as 1111, as the gene at location 2 is flipped from 0 to 1. The mutation operator is used to change some information in a selected chromosome or diversify the solution space for further exploration. Many modified mutation techniques have been proposed in literature which will be identified in this review.


### 3.3. A Simple GA

First of all, the problem is coded in such a way that it can be represented in the form of binary numbers in a chromosome. As GA requires an initial candidate solution for its initiation, the initial solution is generated by randomization or diversification. The solution is then subjected to genetic operators (selection, crossover, and mutation) until the termination criteria are met. Algorithm1 represents a typical GA.Algorithm 1:A simple GA.
Start
Encode initial solutions in chromosomes
Randomly generate an initial population of chromosomes
Compute fitness for each chromosome in the population
Repeat the following until number of offsprings <= number of chromosomes,
(i) Select a pair of parent chromosomes using selection method
(ii) Crossover the selected pair with the crossover probability at randomly chosen point to form two offsprings
(iii) Mutate the offsprings with mutation probability at all locations
Obtain new set of chromosomes
Replace the current population with new population using replacement strategy
Compute fitness
Generate new population until the fitness criteria is met
End


### 3.4. General Approaches for FJSSP Solution Using GA

Keeping in view the combinatorial nature of the FJSSP, evolutionary algorithms have proven to be highly effective in providing acceptable solutions. Mesghouni et al. [222] were the first to use GA for the solution of FJSSP by proposing parallel job and parallel machine representation. In literature, the approaches for FJSSP solution can be classified as follows:(i)
Hierarchical approach: this approach aims to solve the FJSSP by decomposing into two parts and solving them separately according to its structure, that is, machine selection problem and operation sequencing problem. Examples include the classical work of Brandimarte [223].
(ii)
Integrated approach: this approach solves the two subproblems of FJSSP simultaneously instead of dealing with them in a separate way. Examples include state-of-the-art works of Dauzère-Pérès and Paulli [224], Hurink et al. [225], and Mastrolilli and Gambardella [226].The scheduling problem cannot be solved without efficient solution aids due its difficult nature. Therefore, scheduling modules/systems have been designed to handle the problem. These types of systems help in performing experiments and also prove very helpful in debugging and validation of the scheduling algorithm. A modular and schematic representation of such scheduling system architecture with GA is presented in Figure7.Figure 7
An architecture for FJSSP scheduler.


## 3.1. Basic Elements of GA

The basic working element of GA is gene, a group of which constitutes a chromosome. The chromosomes contain the current state data coded in the form of binary digits 0 or 1 which is distinctively stored in a gene. This structure represents a candidate solution to the problem in consideration. GA works on these coded forms of the data instead of working on actual data elements. The chromosomes combine to form a population which in turn formulates a generation. GA is an iterative evolutionary process which formulates a generation after each iteration. Figure5 represents the schematic representation of the relation of these elements.Figure 5
Basic elements of GA.


## 3.2. Genetic Operators

Each generation is subjected to the genetic operators to obtain a new generation. The new generation is theoretically better than the previous generation, as the new generation is generated after implementing the principle of “survival of the fittest” and thus it replaces the older generation. During this process, either the whole population can be changed or only the worst chromosome can be replaced [221]. Obviously, these are two extreme methods and several strategies for new population can be formulated.The iterations are guided in a way that they satisfy a fitness criterion and they are repeated to obtain an acceptable generation. The genetic operators are used to bring in the beauty of randomization in the algorithm. Standard GA operators are presented in the following.


### 3.2.1. Selection

Selection operator is used to select chromosomes in a generation based upon fitness. The chromosomes satisfying the fitness criteria are likely to be selected in each newer generation. Generally used selection criteria are as follows:(i)
Roulette wheel selection: the selection probability of a chromosome is directly proportional to its fitness as assessed by the fitness criteria. Thus a chromosome with higher fitness will have more probability to be selected; however, lower fitness chromosomes may also be selected.
(ii)
Rank based fitness assignment: this method associates relative fitness between individual chromosomes, hence preventing a generation from containing an all-fit chromosome structure. The method is mainly used to maintain diversity in the population.
(iii)
Tournament selection:a set of chromosomes are selected randomly and then the fittest chromosomes are selected for further operation. This method is completely random.
(iv)
Elitism: the crux of this method is that it maintains a fixed number of fittest chromosomes and the rest of the population is generated by using any of the preferred selection methods. Thus this method not only ensures that the best solutions remain in the population, but also ensures the diversification of the population by selecting chromosomes from the entire solution space.


### 3.2.2. Crossover

The crossover operator is applied on the genes of two parent chromosomes to produce two offsprings which contain distinctiveness of the parent chromosomes. These offsprings have more probability of survival than their parents as they are fit as compared to their parents. Consider two parent chromosomes having 4 genes each. Crossover can be applied to these chromosomes at third gene (at pointed arrows) to obtain two offsprings as presented in Figure6. This technique is known as single-point crossover. Many modified crossover techniques have been proposed in literature which will be identified in this review.Figure 6
A typical crossover.


### 3.2.3. Mutation

Mutation operator is applied on a single chromosome for the purpose of changing a gene at its respective location. The gene 1011 can be mutated as 1111, as the gene at location 2 is flipped from 0 to 1. The mutation operator is used to change some information in a selected chromosome or diversify the solution space for further exploration. Many modified mutation techniques have been proposed in literature which will be identified in this review.


## 3.2.1. Selection

Selection operator is used to select chromosomes in a generation based upon fitness. The chromosomes satisfying the fitness criteria are likely to be selected in each newer generation. Generally used selection criteria are as follows:(i)
Roulette wheel selection: the selection probability of a chromosome is directly proportional to its fitness as assessed by the fitness criteria. Thus a chromosome with higher fitness will have more probability to be selected; however, lower fitness chromosomes may also be selected.
(ii)
Rank based fitness assignment: this method associates relative fitness between individual chromosomes, hence preventing a generation from containing an all-fit chromosome structure. The method is mainly used to maintain diversity in the population.
(iii)
Tournament selection:a set of chromosomes are selected randomly and then the fittest chromosomes are selected for further operation. This method is completely random.
(iv)
Elitism: the crux of this method is that it maintains a fixed number of fittest chromosomes and the rest of the population is generated by using any of the preferred selection methods. Thus this method not only ensures that the best solutions remain in the population, but also ensures the diversification of the population by selecting chromosomes from the entire solution space.


## 3.2.2. Crossover

The crossover operator is applied on the genes of two parent chromosomes to produce two offsprings which contain distinctiveness of the parent chromosomes. These offsprings have more probability of survival than their parents as they are fit as compared to their parents. Consider two parent chromosomes having 4 genes each. Crossover can be applied to these chromosomes at third gene (at pointed arrows) to obtain two offsprings as presented in Figure6. This technique is known as single-point crossover. Many modified crossover techniques have been proposed in literature which will be identified in this review.Figure 6
A typical crossover.


## 3.2.3. Mutation

Mutation operator is applied on a single chromosome for the purpose of changing a gene at its respective location. The gene 1011 can be mutated as 1111, as the gene at location 2 is flipped from 0 to 1. The mutation operator is used to change some information in a selected chromosome or diversify the solution space for further exploration. Many modified mutation techniques have been proposed in literature which will be identified in this review.


## 3.3. A Simple GA

First of all, the problem is coded in such a way that it can be represented in the form of binary numbers in a chromosome. As GA requires an initial candidate solution for its initiation, the initial solution is generated by randomization or diversification. The solution is then subjected to genetic operators (selection, crossover, and mutation) until the termination criteria are met. Algorithm1 represents a typical GA.Algorithm 1:A simple GA.
Start
Encode initial solutions in chromosomes
Randomly generate an initial population of chromosomes
Compute fitness for each chromosome in the population
Repeat the following until number of offsprings <= number of chromosomes,
(i) Select a pair of parent chromosomes using selection method
(ii) Crossover the selected pair with the crossover probability at randomly chosen point to form two offsprings
(iii) Mutate the offsprings with mutation probability at all locations
Obtain new set of chromosomes
Replace the current population with new population using replacement strategy
Compute fitness
Generate new population until the fitness criteria is met
End


## 3.4. General Approaches for FJSSP Solution Using GA

Keeping in view the combinatorial nature of the FJSSP, evolutionary algorithms have proven to be highly effective in providing acceptable solutions. Mesghouni et al. [222] were the first to use GA for the solution of FJSSP by proposing parallel job and parallel machine representation. In literature, the approaches for FJSSP solution can be classified as follows:(i)
Hierarchical approach: this approach aims to solve the FJSSP by decomposing into two parts and solving them separately according to its structure, that is, machine selection problem and operation sequencing problem. Examples include the classical work of Brandimarte [223].
(ii)
Integrated approach: this approach solves the two subproblems of FJSSP simultaneously instead of dealing with them in a separate way. Examples include state-of-the-art works of Dauzère-Pérès and Paulli [224], Hurink et al. [225], and Mastrolilli and Gambardella [226].The scheduling problem cannot be solved without efficient solution aids due its difficult nature. Therefore, scheduling modules/systems have been designed to handle the problem. These types of systems help in performing experiments and also prove very helpful in debugging and validation of the scheduling algorithm. A modular and schematic representation of such scheduling system architecture with GA is presented in Figure7.Figure 7
An architecture for FJSSP scheduler.


## 4. FJSSPs Involving GA

Many different approaches have been applied to solve the problem due to its difficult nature. Some of the very recent approaches include biogeography based optimization [227], firefly algorithm [228], heuristics [229], invasive weed optimization [230], and differential evolution [231]. However, GA remains the most used algorithm for the FJSSP [3, 232]. This section presents the literature survey of the FJSSP solved using GA. First the methodology and scope are defined and then the literature survey is presented in following three areas:(i)
FJSSP solved using only GA and NSGA
(ii)
FJSSP solved using advanced forms of GA
(iii)
FJSSP solved using hGA.


### 4.1. Methodology and Scope

For the purpose of literature review, databases of Elsevier, Springer, Taylor and Francis, IEEE, and Hindawi are searched with the phrases “Flexible Job Shop Scheduling” and “Genetic Algorithm”. Both conference and journal papers have been reviewed; however, emphasis has been laid on the journal publications. Book sections, thesis, and technical reports have not been included. The publications occurring after 2001 have been considered in this review. Data has been collected manually from selected publications using EndNote®.


### 4.2. Available Reviews

JSSP is a classical optimization problem, so the reviews of this problem can be traced back to 1966 [214]. However, the review papers aiming at the survey of FJSSP have appeared after 2000. Some of the salient features of reviews are outlined below.(i)
Gen and Lin [233] have presented the survey of multiobjective evolutionary algorithms for JSSP. They have reviewed FJSSP in this paper along with other shop layouts and identified various evolutionary strategies for achieving the solution of the said problem.
(ii)
Vincent and Durai [234] have presented a survey of optimization techniques for multiobjective FJSSP. They have compared five algorithms and their performance results have been summarized.
(iii)
Çaliş and Bulkan [3] have reviewed the artificial intelligence based approaches for JSSP. They have also included some instances of FJSSP in their survey.
(iv)
Chaudhry and Khan [232] have presented a survey on all available solution strategies for FJSSP. They have segregated the literature based upon the solution techniques and provided insight to the research directions in FJSSP.
(v)
Genova et al. [210] have also presented the solution approaches for multiobjective FJSSP.It can be concluded from the data presented above that there is a need to assess the application and implementation of GA based approaches as they have not been addressed in a separate manner.


### 4.3. Objective Functions of FJSSP

The aim of solving the FJSSP is to satisfy a predefined performance criterion in order to obtain an optimal schedule. Therefore the FJSSP is essentially an optimization problem with a cost function which is required to be either minimized or maximized. Several optimization criteria have been formulated as a result and researchers have carried out single objective and multiobjective optimization with these criteria.Table1 presents a summary of commonly used objective functions in FJSSP along with their impact and applicability with respect to the production environment. Obviously, this list is not exhaustive and many other objective functions can be found in the literature.Table 1
Commonly used FJSSP objective functions.
Measure
Symbol
Formula
Meaning
Impact/applicability
Makespan
C
m
a
x
max
1
≤
j
≤
n
⁡
C
j
The time taken to complete all jobs
Minimizing makespan will directly minimize the production cost
Mean completion time
C
-
∑
j
=
1
n
C
j
n
Average time required for completion of a single job
Minimizing this will directly reduce the production cost
Maximum Flowtime
F
j
max
1
≤
j
≤
n
⁡
F
j
The time that a jobj spends in a shop while the processing takes place or while waiting
The longer the time a job spends on the production floor, the bigger its cost
Total tardiness
T
∑
j
=
1
n
T
j
The positive difference between the completion time and due date of all jobs
Applicable when early jobs do not give a reward but late jobs are penalized
Average tardiness
T
-
∑
j
=
1
n
T
j
n
Average difference between the completion time and due date of a single job
Applicable when overall production is required to be completed in a stipulated time
Total weighted tardiness
T
w
t
∑
i
=
1
n
α
i
T
i
Sum of weighted difference between the completion time and due date of a job
Applicable when some jobs are more important than others
Maximum lateness
L
m
a
x
max
1
≤
j
≤
n
⁡
L
j
The maximum slack of a job with respect to its due date
Applicable when early jobs give a reward
Number of tardy jobs
n
T
∑
j
=
1
n
U
j
Number of jobs that are late
Directly affects the production cost and machine availability
Total workload of machines
W
T
∑
j
=
1
n
W
j
The total working time on all machines
Ensures maximum utilization of machines


### 4.4. Benchmark Problems

A number of benchmark problems have been formulated for FJSSP in order to compare the performance of new scheduling algorithms. The validation of a newly developed scheduling algorithm is done by the stated comparison. Various benchmark problems/data sets for FJSSP have been published. However this article reviews the benchmark data published by Fisher and Thompson [235], Lawrence [236], Tillard [237], Brandimarte [223], Hurink et al. [225], Lee and DiCesare [238], Barnes and Chambers [17], Dauzère-Pérès and Paulli [224], Kacem et al. [19, 133], and Fattahi et al. [239]. A detailed benchmark instances data has been presented by Dennis and Geiger [240].


### 4.5. FJSSP with GA and NSGA

GA has been used for solution of JSSP for above thirty years now; for example, Lawrence [241] has used GA for the solution of JSSP in 1985. However, the implementations of GA in FJSSP started after 1990 when Brucker and Schlie [16] presented their study in this area. Since then, there has been an immense increase in the research interest in this area. Table 2 presents the year-wise literature review. The single objective functions solved using GA have been included. Furthermore, the algorithms for multiobjective optimization are also included in this section. These problems are primarily solved with Nondominated Sorting Genetic Algorithm (NSGA) and similar approaches.Table 2
FJSSP with GA and NSGA.
Ref
Year
Article type
Algorithm details
Objective
GA parameters
Benchmark
Mutation
Crossover
Selection
[24]
2001
C
GA
C
m
a
x
,
W
M
,
W
T
Genetic mutation
Sequencing crossover, sequencing and ACX
-
KA
[25]
2001
J
GA
T
Operator for routing selection, operator for machine selection, operator for operation processing sequence
Operators for routing selection, operators for machine selection, operators for operations processing sequence
Fittest
Other
[26]
2002
C
NSGA II
C
m
a
x
,
W
M
,
W
T
Directed mutation
OPX
Elitism
Other
[27]
2003
J
GA
T
Bit mutation
TPX
Fittest
LA
[28]
2003
C
GA
C
m
a
x
,
W
M
,
W
T
AssM, IM
ACX, POX
Fittest
KA
[29]
2004
C
GA
C
m
a
x
Two-part mutation
TPX
-
KA
[30]
2005
CP
GA
C
m
a
x
,
T
w
q
Genes pair mutation, specific gene mutation
Dominant gene crossover
Elitism
LD, other
[31]
2005
C
GA
C
m
a
x
Reverse mutation
SPX, TPX, SXX
NA
KA
[32]
2006
C
GA
C
m
a
x
,
W
M
,
W
T
PPS
POX
Elitism
KA
[33]
2008
J
GA
C
m
a
x
AssM, reordering mutation
POX, ACX
Roulette wheel
FH
[34]
2008
J
GA
C
m
a
x
PPS, AssM, assignment IM
POX, ACX
Binary tournament, linear ranking
BR, DP, BC, HU
[35]
2008
C
GA
C
m
a
x
Random
Modified OPX
Random
Other
[36]
2008
C
GA
C
m
a
x
Two-point EM
Linear order crossover
Roulette wheel, elitism
Other
[37]
2009
J
GA
C
m
a
x
SM
Edge crossover
Roulette wheel
BR
[38]
2009
C
GA
C
m
a
x
PPS
POX
Roulette wheel
Other
[39]
2009
J
GA
S
T
,
J
w
EM
SPX, TPX
-
Industry
[40]
2009
C
GA
C
m
a
x
,
W
T
Weak link effect based mutation
Select mechanism crossover
-
KA
[41]
2009
C
GA
C
m
a
x
,
W
M
,
W
T
SM
Linear order crossover
Roulette wheel
KA
[42]
2010
J
GA
C
m
a
x
Local mutation, global mutation
TPX
Linear ranking
FT, HU, LA
[43]
2010
J
GA
E
m
i
n
,
S
s
Random
POX, ACX
Tournament selection
Other
[44]
2010
C
GA
C
m
a
x
,
W
M
,
W
T
Individual mutation, AllM, SM
TPX
Random
KA
[45]
2010
C
GA
Max average agreement index, FuzzyC
m
a
x
,
W
T
InsM, replace mutation
Precedence operation crossover (POX), multipoint crossover
Elitism, tournament selection
KA
[46]
2010
J
GA
C
m
a
x, minimum total load of machines, minimize the maximum load of machines
SM
MPPX, MGOX, MGPMX1, MGPMX2
Tournament selection
KA
[47]
2010
C
GA
C
m
a
x
Random
TPX
Tournament selection
LA
[48]
2010
C
GA
C
m
a
x
,
W
M
,
W
T
Random
TPX
-
KA
[49]
2010
J
GA
C
m
a
x
Random
TPX
Elitism
KA
[50]
2011
J
GA
C
m
a
x
MBM, modified PBM
Modified POX
Roulette wheel, tournament
KA, BR
[51]
2011
J
NSGA
C
m
a
x
,
W
M
,
W
T
,
T
Preference mutation, machine mutation
Preference crossover, machine crossover
-
KA
[52]
2011
C
GA
C
m
a
x
,
C
p
SM
MPPX, MGOX, MGPMX1, MGPMX2
Tournament
KA
[53]
2011
J
GA
C
m
a
x
Random
PMX
-
Industry
[54]
2011
C
GA
C
m
a
x
Random
Modified crossover
Binary tournament selection
LA
[55]
2011
J
NSGA-II
C
m
a
x, min of the system unavailability
Random
TPX, RX
Roulette wheel, tournament selection
BC, BR, DP, HU
[56]
2011
J
NSGA-II
C
m
a
x
,
W
M
,
W
T
Frame shift mutation, translocation mutation, inversion mutation
Uniform order-based crossover, precedence preservative crossover
Tournament selection
FT
[57]
2011
C
GA
C
m
a
x, mean tardiness, mean flow time
Reciprocal EM
TPX
Elitism
Other
[58]
2011
C
NSGA
C
m
a
x
,
W
M
,
W
T
Self-adaptive mutation
Precedence crossover, machine crossover
Niche selection
Other
[59]
2011
J
GA
C
m
a
x
Random
TPX, UX, POX
Roulette wheel
BR, BC, DP
[60]
2012
C
GA
C
m
a
x
Inverted mutation, random
TPX, random
-
Other
[61]
2012
C
GA
C
m
a
x
SM
TPX
Linear ranking
KA
[62]
2012
J
GA
C
m
a
x
,
W
M
,
W
T
SM, EM
TPX, POX
Random selection
FT
[63]
2012
J
NSGA-II, NRGA, MOGA, PAES
C
m
a
x
,
C
p
SM, reversion mutation, InsM
OPX
Tournament selection, roulette wheel
BR, other
[64]
2012
J
GA
C
m
a
x
AssM, reordering mutation
POX, ACX
Roulette wheel
Other
[65]
2012
J
GA
C
m
a
x
Modified SM
Hierarchical clustering based crossover
Fuzzy roulette wheel selection
BR
[66]
2012
J
GA
Max of total profit
SM
SPX
Tournament selection
Industry
[67]
2013
C
NSGA-II, SPEA-2
C
m
a
x
,
E
,
T
-
-
-
HU, KA, other
[68]
2013
CP
GA
C
m
a
x
SM, random
OX, UX
-
KA
[69]
2013
J
NSGA, NRGA
C
m
a
x
,
W
M
,
W
T
Random, SM
IPOX, multipoint preservative crossover
Binary tournament
DP, BR
[70]
2013
J
GA
C
m
a
x
SM
TPX
-
BR
[71]
2013
C
GA
C
m
a
x
Modified mutation
Modified crossover
Roulette wheel
Industry
[72]
2014
C
GA
C
m
a
x
Scramble mutation
Active schedule constructive crossover, GOX
High low fit selection
FT
[73]
2014
J
GA
C
m
a
x
SM
TPX, POX
Tournament selection
FH, BC
[74]
2014
J
GA
C
m
a
x
,
W
M
-
-
Tournament
BR
[75]
2014
CP
GA
C
m
a
x
SM
TPX
Roulette wheel
BR
[76]
2014
CP
GA
C
m
a
x
SM, IM
POX, UX
Elitism
BR
[77]
2014
J
GA
T
SM
UX
Tournament selection
Other
[78]
2014
C
NSGA-II
C
m
a
x, total production energy costs, total energy costs of maintenance
InsM, SM
SPX, MPX
-
Other
[79]
2014
J
GA
C
m
a
x
SM
TPX, POX
Roulette wheel
Industry
[80]
2014
J
GA
Min of due date mean squared deviation
Shift mutation
TPX
-
Other
[81]
2015
J
GA
C
m
a
x
SM
Position based crossover, OX, PMX
Roulette wheel, tournament selection
LD
[82]
2015
J
GA
C
m
a
x
Random selection, neighborhood search
TPX, UX
Roulette wheel
BR
[83]
2015
J
GA
T
-
Shift mutation, EM
TPX, POX
-
BR
[84]
2015
J
GA
C
m
a
x
Values mutation
UX, POX
Roulette wheel
BR
[85]
2015
J
GA
C
m
a
x
Inversion mutation, random
UX, POX
BR
[86]
2015
CP
GA
C
m
a
x
SM, inversion mutation
TPX, POX
Tournament selection
KA
[87]
2015
J
GA
C
m
a
x
SM
OPX
Other
[88]
2015
J
GA
C
m
a
x
SM
TPX
Tournament selection
Other
[89]
2015
J
GA
C
m
a
x
EM
TPX
Linear ranking
Other
[90]
2015
CP
GA
C
m
a
x
Random
Integer crossover
Roulette wheel
KA
[91]
2016
J
NSGA-II, NRGA
C
m
a
x and stability objectives
Modified PBM, MBM
POX
-
KA, BR
[92]
2016
J
NSGA-II
C
m
a
x, total energy consumption
Deviation-based mutation, reciprocal EM
Intermediate recombination, line recombination
Elitism
Other
[93]
2017
CP
GA
C
m
a
x
RM, SM
POX, MPX
Tournament, elite reservation
Other
[94]
2017
J
GA
C
m
a
x
RM
MPX
Ranking, stochastic universal sampling
Other
[95]
2017
CP
GA
C
m
a
x, lead time
RM
MPX
Roulette wheel
Other
[96]
2017
J
GA
C
m
a
x
SM
POX
Elitism, population diversity strategy
Other
[97]
2017
CP
GA
C
m
a
x
RM
MPX
Roulette wheel
Industry
[98]
2017
CP
GA
C
m
a
x
RM, SM
POX
Tournament selection
BC
[99]
2017
J
GA
C
m
a
x
RM
TPX
Elitism
BR, other
[100]
2017
J
NSGA-II
C
m
a
x
,
W
M
,
W
T
RM, SM, reverse mutation, multipoint mutation
SPX, MPX, POX, JBX
Tournament
KA, DP, BR, BC
[101]
2017
J
GA
C
m
a
x, workload of each machine, W
T
-
-
-
KA
[102]
2017
CP
GA
C
m
a
x
,
W
T
-
POX, MPX
Elitism
Industry


### 4.6. FJSSP with Advanced Forms of GA

With the advancement in computing power and artificial intelligence techniques, various advances have been made in the original GA by incorporation of innovative ideas, majorly learning based evolution. Table3 presents the year-wise literature in this area.Table 3
FJSSP with advanced forms of GA.
Ref
Year
Article type
Algorithm details
Objective
GA parameters
Benchmark
Mutation
Crossover
Selection
[19]
2002
J
Controlled GA
C
m
a
x, sum of machine workloads
Artificial mutation
Modified crossover
Elitism
KA
[103]
2005
J
Multistage operation based GA
C
m
a
x
,
W
M
,
W
T
Local-search mutation
One-cut point crossover
Random
KA
[104]
2005
C
LEGA
C
m
a
x
-
-
-
KA
[20]
2006
J
Iterative GA
C
m
a
x
Random
SPX, job-based order crossover
Roulette wheel
FT, LA
[105]
2006
C
GA with Choquet integral
C
m
a
x
,
W
M
,
W
T
-
-
-
KA
[106]
2007
J
Learning GA
C
m
a
x
Random, algorithm based
TPX, random
Linear scaling, stochastic universal sampling
Mesghouni, BR
[107]
2008
C
TPGA
Min of fuzzyC
m
a
x
Random
GOX, generalization of PPX
Tournament selection
KA
[108]
2008
J
GA with Choquet integral
C
m
a
x
,
W
M
,
W
T, sum of weighted earliness and weighted tardiness, sum of production cost
-
-
-
KA
[109]
2009
C
Course grained parallel GA based on island model parallelization technique
C
m
a
x
Sublot step mutation, Sublot swap mutation, random operation AssM, intelligent operations AssM, operations sequence shift mutation
SPX-, SPX-2 (SPC-2), operation to machine ACX, job level operations sequence crossover, subplot level operations sequence crossover
Tournament selection
Other
[110]
2009
C
Adaptive GA
C
m
a
x
Adaptive
Adaptive, precedence operation crossover
Roulette wheel
KA
[111]
2010
C
GA with learning by injection of sequences
C
m
a
x
Mutation by direct exchange, mutation by random exchange, mutation by inversion, Mutation by close exchange, mutation by gap of all the elements
SPX
Random
FT, other
[112]
2010
C
Cooperative coevolutionary GA
C
m
a
x
Random, SM
Row crossover, column crossover, precedence order crossover
Roulette wheel
BR
[113]
2010
J
Parallel GA
C
m
a
x
PPS, AssM, IM
ACX, POX
Tournament selection
Other
[114]
2010
C
Matrix coded GA
C
m
a
x
Machine dimension mutation, operation dimension mutation
Machine dimension crossover, operation dimension crossover
Tournament
Other
[115]
2010
J
Decomposition integration GA
C
m
a
x
Swap operator
Generalized position crossover, generalization of PPX
Tournament selection
KA
[116]
2010
J
LEGA
C
m
a
x
Random, operational memory based mutation
TPX, random
Tournament
LA
[117]
2010
C
Adaptive GA
C
m
a
x
Random
OPX, three-point crossover
League selection
Industry
[118]
2010
C
Coevolutionary genetic algorithm
FuzzyC
m
a
x
SMRandom
TPX, discrete crossover
Tournament selection
KA
[119]
2010
C
GA based on immune and entropy principle
C
m
a
x
,
W
T
Random
IPOX, MPX
-
KA
[120]
2011
J
GA with heuristics
C
m
a
x
-
-
Elitism, tournament selection
BR, other
[121]
2011
C
Adaptive GA
C
m
a
x
Random
OPX
Elitism
KA
[122]
2011
C
MSCEA
C
m
a
x
Neighborhood mutation
TPX
Random
BR
[123]
2012
J
Multiobjective GA
C
m
a
x, total machining time
SM
SPX
-
Other
[124]
2012
C
GA with learning
C
m
a
x
Random
OPX
Elitist
LD, BR
[125]
2012
J
Coevolutionary GA
FuzzyC
m
a
x
SM
TPX, extension of PPX
Modified tournament selection
Other
[126]
2012
J
Jumping genes GA
C
m
a
x, flow time of products with AGV, completion of the products
EM
SPX
Tournament selection
Other
[127]
2013
J
Real coded GA
C
m
a
x
Random
Extended intermediate crossover, OPX
Roulette wheel, binary tournament, elitism, replacement
BR
[128]
2014
J
NSGA-II based on blood variation
C
m
a
x, processing cost, energy consumption, cost-weighted processing quality
Modified mutation
Blood relation based crossover
Modified quick sorting ranking
Industry
[129]
2016
CP
Immune GA
Maximization of due time satisfaction, minimize the total processing costs
Random
SPX
Roulette wheel
FT
[130]
2016
J
Extended GA
Maximize satisfaction degree
SM
TPX, POX
Tournament selection
Other
[131]
2016
CP
GA with comprehensive search
C
m
a
x
Random
Operation-based crossover
Roulette wheel
Other


### 4.7. FJSSP with hGA

Although better results have been obtained with the techniques presented in Section4.6, other standalone optimization techniques have also been proposed for the solution of FJSSP. However, researchers have amalgamated some standalone techniques with GA to obtain better solution times and results. These techniques have primarily been used to further improve the solution of a stated GA iteration before starting the new iteration. In this way, optimum solution is reached in a more effective manner. Table 4 presents year-wise literature in this class.Table 4
FJSSP with hGA.
Ref
Year
Article type
Algorithm details
Objective
GA Parameters
Benchmark
Mutation
Crossover
Selection
[132]
2001
C
GA + MILP
C
m
a
x, Min of T
SM
Multipoint crossover
Tournament selection
Other
[133]
2002
J
Controlled GA + fuzzy logic
C
m
a
x
,
W
M
,
W
T
Artificial mutation
Modified crossover
Fittest
KA
[134]
2004
J
GA + priority dispatching rules
Min ratio of tardy jobs, variance of the flow time, amount of mold changes, max efficiency of machines
Priority dispatching rule based mutation
Two-point conical
Tournament selection, elitism
Other
[135]
2004
C
GA + LS + heuristic
C
m
a
x
,
W
M
,
W
T
-
POX
Fittest
Other
[136]
2006
C
GA + TS
T
PPS, random
POX, GOX
-
Other
[137]
2006
J
GA + LS
C
m
a
x
,
W
M
,
W
T
Phenotype based mutation
Phenotype based crossover
Ranking selection
KA
[138]
2006
J
GA + scheduling rules
C
m
a
x
Random
SPX
Roulette wheel
FT
[139]
2006
C
GA + heuristic
C
m
a
x
InsM, SM
OPX with priority list, TPX with priority list, selective machine sequences crossover
-
LA, FT
[140]
2006
C
GA + LS procedure based on shifting bottleneck
C
m
a
x
,
W
M
,
W
T
AllM, ImmM
Exchange crossover, EOX
-
KA
[141]
2006
C
GA + TS
C
m
a
x, maximum lateness
Random (dynamic)
Random (Boolean matrix)
-
LA
[142]
2006
C
GA + heuristic
T
Random sequencing mutation, random AssM, IM
GOX, sequencing and ACX, ACX
-
BR, other
[143]
2007
J
GA + LS procedure based on shifting bottleneck
C
m
a
x
,
W
M
,
W
T
AllM
EOX
-
KA, BR
[144]
2007
J
GA + LS
C
m
a
x
,
W
M
,
W
T
PPS
Preserving order based crossover
Fittest
BR, DP,
[145]
2008
J
GA + variable neighborhood descent
C
m
a
x
,
W
M
,
W
T
AllM, ImmM
EOX, UX
Ranking selection
KA, BR, BC, DP, FT, LA, other
[146]
2008
J
GA + guided LS
C
m
a
x
,
W
M
,
W
T
Random
TPX
Ranking selection
KA, other
[147]
2008
J
GA + MILP
Mean flow time,C
m
a
x, maximum lateness, total absolute deviation from the due dates
Random
OPX, partial matched crossover
Elitist
Other
[148]
2008
C
GA + TS
C
m
a
x
Random
TPX, improved POX
Tournament selection
BR
[149]
2009
J
GA + simulation
C
m
a
x, min of mean tardiness
AssM, sequencing mutation
TPX
Roulette wheel
BR
[150]
2009
C
GA + LS
C
m
a
x
-
-
-
BR
[151]
2010
J
NSGAII + SA
C
m
a
x
,
C
p
Reciprocal swap
UX
Elitism
Other
[152]
2010
J
GA + immune mechanism + SA
C
m
a
x
,
C
p
Adaptive crossover
Adaptive crossover
Fittest
Other
[153]
2010
J
VNS + GA
C
m
a
x
,
W
M
,
W
T
Random
TPX
Fittest
KA
[154]
2010
C
GA + chaotic LS
C
m
a
x
IM, random
GOX, generalized PMX
Binary tournament
BR
[155]
2010
J
GA + hill climbing
C
m
a
x
,
W
M
,
W
T
Random
TPX
Tournament
KA
[156]
2010
J
GA + immune + entropy principle
C
m
a
x
,
W
M
,
W
T
Random
IPOX, multipoint preservative crossover
Tournament selection
KA, BR, DP
[157]
2010
C
PSO + GA
C
m
a
x
Random
SPX
-
Other
[158]
2010
C
GA + VNS
C
m
a
x
,
W
M
,
W
T
Random, swap
TPX, POX
Tournament selection
KA
[159]
2010
C
GA + TS
C
m
a
x
,
W
M
,
W
T
Random
TPX, POX
-
KA
[160]
2011
J
GA + LS
C
m
a
x
PBM, MBM
POX
Roulette wheel, ranking
KA, Mesghouni, LD, BR, BC, DP, HU
[161]
2011
C
TS + SA + GA
C
m
a
x
,
W
M
,
W
T
Random
Combined order and position-based crossover
-
KA, BR
[162]
2011
C
GA + AIS
C
m
a
x
SM
MPPX, MGOX, MGPMX1, MGPMX2
Elitism
Other
[163]
2011
J
GA
Min of maximum workload
SM
UX
Search rate survival
BR, LA
[164]
2011
J
GA + SA
C
m
a
x
,
W
T
Dynamic mutation
Dynamic crossover
Roulette wheel
KA
[165]
2011
C
GA + TS
Min time, min cost, equipment utilization rate
Random
MPPX, MGOX, MGPMX1, MGPMX2
Elitism
Other
[166]
2011
C
GA + PSO
C
m
a
x
Random, balance load mutate
POX, MPX
-
KA, BR
[167]
2011
J
GA + fuzzy set theory
Optimization of cost, quality and time
Neighborhood mutation
Neighborhood crossover
-
Industry
[168]
2011
J
GA + ACO
C
m
a
x
Inverted mutation, operation assignment machine knowledge
TPX, modified crossover
Linear scaling, stochastic universal sampling
KA, BR
[169]
2012
J
GA + grouping GA
T, total machine idle time, C
m
a
x
-
-
-
Industry
[170]
2012
C
GA + LS
C
m
a
x
Machine replacement
POX
Elitism
Industry
[171]
2012
J
GA + Petri nets
C
m
a
x, total expense, workload of machines
InvM
-
Elitism
Other
[172]
2012
C
GA + LS + TS
C
m
a
x
,
W
M
,
W
T
SM, random
UX, IPOX
Elitism
KA
[173]
2012
C
hGA
Min the total earliness, min of tardiness penalties
SM, SA
POX, job-based machine crossover
Roulette wheel
FT
[174]
2012
J
GA + TS
C
m
a
x, min of mean flow time
AllM
PMX, OX
Tournament selection
Other
[13]
2012
C
GA + PSO
T
-
OPX
Roulette wheel
KA
[175]
2012
C
GA + TS + modified shifting bottleneck procedure
C
m
a
x
SM
SPX
Elitism
Other
[176]
2012
J
Duplicate GA + LS
C
m
a
x, min of total idleness
SM
UX
Roulette wheel
KA
[177]
2012
J
GA + LS based on critical path theory
C
m
a
x
,
W
M
,
W
T
ImmM, modified AssM
POX, TPX
-
KA, BR
[178]
2012
J
GA + TS
C
m
a
x
AssM
SPX
Roulette wheel
Other
[179]
2013
J
GA + VNS with affinity function
C
m
a
x
SM
UX, OPX
Tournament selection
Other
[180]
2013
J
GA + simulation
Total of average flow times
SM
Two-stage crossover
Tournament
Other
[181]
2013
J
GA + SA
Min the total cost including delay costs, setup costs, and holding costs
Intelligent AssM, random AssM, intelligent sequencing mutation 1, intelligent sequencing mutation 2, randomly sequencing mutation
POX, random crossover
Linear ranking
Other
[182]
2013
C
PSO + GA with Cauchy distribution
C
m
a
x
InsM
MPX
-
Other
[183]
2013
J
GA + SA
C
m
a
x
,
W
M
,
W
T
New mutation
New crossover
Elitism
KA
[179]
2013
J
GA + VNS
C
m
a
x
InsM, SM
TPX, modified crossover
Tournament selection
Other
[184]
2013
J
NGSA + knowledge based Algorithm
C
m
a
x, robustness
MBM, ImmM
TPX
-
KA, other
[185]
2013
C
NSGA-II + LS
C
m
a
x
,
W
M
,
W
T
Random
Modified crossover
-
KA, BR
[186]
2013
J
GA + SA
C
m
a
x, sum of std deviation of processing workload for all working centers
InvM
OX
Ranking selection
Other
[187]
2014
J
GA + shifting bottleneck
C
m
a
x
,
W
M
SM
EOX
Elitism
Other
[188]
2014
J
GA + population improvement
C
m
a
x
SM
POX, MPX
Binary tournament selection
BR
[189]
2014
CP
GA + TS
C
m
a
x
SM, alternative mutation
POX, PMX
Tournament selection
KA
[190]
2014
CP
GA + LS
C
m
a
x
Random
POX
-
BR, HU, DP
[191]
2015
CP
GA + TS
C
m
a
x
IM
OX
Elitism
BR, HU
[192]
2015
J
Neighborhood-based GA + TS + LS
C
m
a
x
SM, InvM
UX, IPOX
Fitness neighborhood selection operator
BR, HU
[193]
2015
J
GA + TS
C
m
a
x
-
Job order crossover
Tournament selection
BR, BC, DP, Other
[194]
2015
J
GA + PSO
Minimize sum of holding, setup, production, overtime costs
SM
MPX
Tournament selection
Other
[195]
2015
J
GA + heuristics
C
m
a
x, overtime costs of machines
SM
OX
Ranking
Other
[196]
2015
J
GA + VNS
T
AssM, SM
UX, modified POX
Linear ranking
BR, HU, other
[197]
2016
J
GA + heuristics
Mean tardiness
SM
SPX
-
Other
[198]
2016
J
GA + TS
C
m
a
x
SM
PBX
Tournament
FT, LA
[199]
2016
J
GA + TS
C
m
a
x
SM, neighborhood mutation
POX, JBX, TPX
Elitism, tournament selection
KA, FH, BR, BC, HU, DP
[200]
2016
J
GA + TS
Weighted tardiness, balancing the setup workers load, min the work-in-process
SM
TPX
Ranking
Other
[201]
2016
J
Neighborhood GA + TS
C
m
a
x
SM, InsM
UX, IPOX
Fitness neighborhood selection operator
Other
[202]
2016
CP
GA + LS
C
m
a
x
Uniform mutation, InsM, SM
UX, TPX, POX
Average hamming distance
KA, BR
[203]
2016
J
GA + LS
C
m
a
x
SM
JBX
Elitism, tournament
BR
[204]
2017
J
GA + SA
C
m
a
x, maximizing the total availability of the system, minimizing total energy cost of both production and maintenance operations
RM, SM
UX, POX
Roulette wheel
Other
[205]
2017
CP
GA + VNS
C
m
a
x
IntM
MPX
Elitism
HU
[206]
2017
J
GA + Taguchi
C
m
a
x
RM, IntM
TPX, POX, UX
Tournament, other
BR, other
[207]
2017
J
GA + VNS
C
m
a
x, mean tardiness
RM
POX
Tournament selection
HU
[208]
2017
J
GA + LS
C
m
a
x
SM, RM
POX
Fitness-neighborhood selection
KA, BR, HU, BC


## 4.1. Methodology and Scope

For the purpose of literature review, databases of Elsevier, Springer, Taylor and Francis, IEEE, and Hindawi are searched with the phrases “Flexible Job Shop Scheduling” and “Genetic Algorithm”. Both conference and journal papers have been reviewed; however, emphasis has been laid on the journal publications. Book sections, thesis, and technical reports have not been included. The publications occurring after 2001 have been considered in this review. Data has been collected manually from selected publications using EndNote®.


## 4.2. Available Reviews

JSSP is a classical optimization problem, so the reviews of this problem can be traced back to 1966 [214]. However, the review papers aiming at the survey of FJSSP have appeared after 2000. Some of the salient features of reviews are outlined below.(i)
Gen and Lin [233] have presented the survey of multiobjective evolutionary algorithms for JSSP. They have reviewed FJSSP in this paper along with other shop layouts and identified various evolutionary strategies for achieving the solution of the said problem.
(ii)
Vincent and Durai [234] have presented a survey of optimization techniques for multiobjective FJSSP. They have compared five algorithms and their performance results have been summarized.
(iii)
Çaliş and Bulkan [3] have reviewed the artificial intelligence based approaches for JSSP. They have also included some instances of FJSSP in their survey.
(iv)
Chaudhry and Khan [232] have presented a survey on all available solution strategies for FJSSP. They have segregated the literature based upon the solution techniques and provided insight to the research directions in FJSSP.
(v)
Genova et al. [210] have also presented the solution approaches for multiobjective FJSSP.It can be concluded from the data presented above that there is a need to assess the application and implementation of GA based approaches as they have not been addressed in a separate manner.


## 4.3. Objective Functions of FJSSP

The aim of solving the FJSSP is to satisfy a predefined performance criterion in order to obtain an optimal schedule. Therefore the FJSSP is essentially an optimization problem with a cost function which is required to be either minimized or maximized. Several optimization criteria have been formulated as a result and researchers have carried out single objective and multiobjective optimization with these criteria.Table1 presents a summary of commonly used objective functions in FJSSP along with their impact and applicability with respect to the production environment. Obviously, this list is not exhaustive and many other objective functions can be found in the literature.Table 1
Commonly used FJSSP objective functions.
Measure
Symbol
Formula
Meaning
Impact/applicability
Makespan
C
m
a
x
max
1
≤
j
≤
n
⁡
C
j
The time taken to complete all jobs
Minimizing makespan will directly minimize the production cost
Mean completion time
C
-
∑
j
=
1
n
C
j
n
Average time required for completion of a single job
Minimizing this will directly reduce the production cost
Maximum Flowtime
F
j
max
1
≤
j
≤
n
⁡
F
j
The time that a jobj spends in a shop while the processing takes place or while waiting
The longer the time a job spends on the production floor, the bigger its cost
Total tardiness
T
∑
j
=
1
n
T
j
The positive difference between the completion time and due date of all jobs
Applicable when early jobs do not give a reward but late jobs are penalized
Average tardiness
T
-
∑
j
=
1
n
T
j
n
Average difference between the completion time and due date of a single job
Applicable when overall production is required to be completed in a stipulated time
Total weighted tardiness
T
w
t
∑
i
=
1
n
α
i
T
i
Sum of weighted difference between the completion time and due date of a job
Applicable when some jobs are more important than others
Maximum lateness
L
m
a
x
max
1
≤
j
≤
n
⁡
L
j
The maximum slack of a job with respect to its due date
Applicable when early jobs give a reward
Number of tardy jobs
n
T
∑
j
=
1
n
U
j
Number of jobs that are late
Directly affects the production cost and machine availability
Total workload of machines
W
T
∑
j
=
1
n
W
j
The total working time on all machines
Ensures maximum utilization of machines


## 4.4. Benchmark Problems

A number of benchmark problems have been formulated for FJSSP in order to compare the performance of new scheduling algorithms. The validation of a newly developed scheduling algorithm is done by the stated comparison. Various benchmark problems/data sets for FJSSP have been published. However this article reviews the benchmark data published by Fisher and Thompson [235], Lawrence [236], Tillard [237], Brandimarte [223], Hurink et al. [225], Lee and DiCesare [238], Barnes and Chambers [17], Dauzère-Pérès and Paulli [224], Kacem et al. [19, 133], and Fattahi et al. [239]. A detailed benchmark instances data has been presented by Dennis and Geiger [240].


## 4.5. FJSSP with GA and NSGA

GA has been used for solution of JSSP for above thirty years now; for example, Lawrence [241] has used GA for the solution of JSSP in 1985. However, the implementations of GA in FJSSP started after 1990 when Brucker and Schlie [16] presented their study in this area. Since then, there has been an immense increase in the research interest in this area. Table 2 presents the year-wise literature review. The single objective functions solved using GA have been included. Furthermore, the algorithms for multiobjective optimization are also included in this section. These problems are primarily solved with Nondominated Sorting Genetic Algorithm (NSGA) and similar approaches.Table 2
FJSSP with GA and NSGA.
Ref
Year
Article type
Algorithm details
Objective
GA parameters
Benchmark
Mutation
Crossover
Selection
[24]
2001
C
GA
C
m
a
x
,
W
M
,
W
T
Genetic mutation
Sequencing crossover, sequencing and ACX
-
KA
[25]
2001
J
GA
T
Operator for routing selection, operator for machine selection, operator for operation processing sequence
Operators for routing selection, operators for machine selection, operators for operations processing sequence
Fittest
Other
[26]
2002
C
NSGA II
C
m
a
x
,
W
M
,
W
T
Directed mutation
OPX
Elitism
Other
[27]
2003
J
GA
T
Bit mutation
TPX
Fittest
LA
[28]
2003
C
GA
C
m
a
x
,
W
M
,
W
T
AssM, IM
ACX, POX
Fittest
KA
[29]
2004
C
GA
C
m
a
x
Two-part mutation
TPX
-
KA
[30]
2005
CP
GA
C
m
a
x
,
T
w
q
Genes pair mutation, specific gene mutation
Dominant gene crossover
Elitism
LD, other
[31]
2005
C
GA
C
m
a
x
Reverse mutation
SPX, TPX, SXX
NA
KA
[32]
2006
C
GA
C
m
a
x
,
W
M
,
W
T
PPS
POX
Elitism
KA
[33]
2008
J
GA
C
m
a
x
AssM, reordering mutation
POX, ACX
Roulette wheel
FH
[34]
2008
J
GA
C
m
a
x
PPS, AssM, assignment IM
POX, ACX
Binary tournament, linear ranking
BR, DP, BC, HU
[35]
2008
C
GA
C
m
a
x
Random
Modified OPX
Random
Other
[36]
2008
C
GA
C
m
a
x
Two-point EM
Linear order crossover
Roulette wheel, elitism
Other
[37]
2009
J
GA
C
m
a
x
SM
Edge crossover
Roulette wheel
BR
[38]
2009
C
GA
C
m
a
x
PPS
POX
Roulette wheel
Other
[39]
2009
J
GA
S
T
,
J
w
EM
SPX, TPX
-
Industry
[40]
2009
C
GA
C
m
a
x
,
W
T
Weak link effect based mutation
Select mechanism crossover
-
KA
[41]
2009
C
GA
C
m
a
x
,
W
M
,
W
T
SM
Linear order crossover
Roulette wheel
KA
[42]
2010
J
GA
C
m
a
x
Local mutation, global mutation
TPX
Linear ranking
FT, HU, LA
[43]
2010
J
GA
E
m
i
n
,
S
s
Random
POX, ACX
Tournament selection
Other
[44]
2010
C
GA
C
m
a
x
,
W
M
,
W
T
Individual mutation, AllM, SM
TPX
Random
KA
[45]
2010
C
GA
Max average agreement index, FuzzyC
m
a
x
,
W
T
InsM, replace mutation
Precedence operation crossover (POX), multipoint crossover
Elitism, tournament selection
KA
[46]
2010
J
GA
C
m
a
x, minimum total load of machines, minimize the maximum load of machines
SM
MPPX, MGOX, MGPMX1, MGPMX2
Tournament selection
KA
[47]
2010
C
GA
C
m
a
x
Random
TPX
Tournament selection
LA
[48]
2010
C
GA
C
m
a
x
,
W
M
,
W
T
Random
TPX
-
KA
[49]
2010
J
GA
C
m
a
x
Random
TPX
Elitism
KA
[50]
2011
J
GA
C
m
a
x
MBM, modified PBM
Modified POX
Roulette wheel, tournament
KA, BR
[51]
2011
J
NSGA
C
m
a
x
,
W
M
,
W
T
,
T
Preference mutation, machine mutation
Preference crossover, machine crossover
-
KA
[52]
2011
C
GA
C
m
a
x
,
C
p
SM
MPPX, MGOX, MGPMX1, MGPMX2
Tournament
KA
[53]
2011
J
GA
C
m
a
x
Random
PMX
-
Industry
[54]
2011
C
GA
C
m
a
x
Random
Modified crossover
Binary tournament selection
LA
[55]
2011
J
NSGA-II
C
m
a
x, min of the system unavailability
Random
TPX, RX
Roulette wheel, tournament selection
BC, BR, DP, HU
[56]
2011
J
NSGA-II
C
m
a
x
,
W
M
,
W
T
Frame shift mutation, translocation mutation, inversion mutation
Uniform order-based crossover, precedence preservative crossover
Tournament selection
FT
[57]
2011
C
GA
C
m
a
x, mean tardiness, mean flow time
Reciprocal EM
TPX
Elitism
Other
[58]
2011
C
NSGA
C
m
a
x
,
W
M
,
W
T
Self-adaptive mutation
Precedence crossover, machine crossover
Niche selection
Other
[59]
2011
J
GA
C
m
a
x
Random
TPX, UX, POX
Roulette wheel
BR, BC, DP
[60]
2012
C
GA
C
m
a
x
Inverted mutation, random
TPX, random
-
Other
[61]
2012
C
GA
C
m
a
x
SM
TPX
Linear ranking
KA
[62]
2012
J
GA
C
m
a
x
,
W
M
,
W
T
SM, EM
TPX, POX
Random selection
FT
[63]
2012
J
NSGA-II, NRGA, MOGA, PAES
C
m
a
x
,
C
p
SM, reversion mutation, InsM
OPX
Tournament selection, roulette wheel
BR, other
[64]
2012
J
GA
C
m
a
x
AssM, reordering mutation
POX, ACX
Roulette wheel
Other
[65]
2012
J
GA
C
m
a
x
Modified SM
Hierarchical clustering based crossover
Fuzzy roulette wheel selection
BR
[66]
2012
J
GA
Max of total profit
SM
SPX
Tournament selection
Industry
[67]
2013
C
NSGA-II, SPEA-2
C
m
a
x
,
E
,
T
-
-
-
HU, KA, other
[68]
2013
CP
GA
C
m
a
x
SM, random
OX, UX
-
KA
[69]
2013
J
NSGA, NRGA
C
m
a
x
,
W
M
,
W
T
Random, SM
IPOX, multipoint preservative crossover
Binary tournament
DP, BR
[70]
2013
J
GA
C
m
a
x
SM
TPX
-
BR
[71]
2013
C
GA
C
m
a
x
Modified mutation
Modified crossover
Roulette wheel
Industry
[72]
2014
C
GA
C
m
a
x
Scramble mutation
Active schedule constructive crossover, GOX
High low fit selection
FT
[73]
2014
J
GA
C
m
a
x
SM
TPX, POX
Tournament selection
FH, BC
[74]
2014
J
GA
C
m
a
x
,
W
M
-
-
Tournament
BR
[75]
2014
CP
GA
C
m
a
x
SM
TPX
Roulette wheel
BR
[76]
2014
CP
GA
C
m
a
x
SM, IM
POX, UX
Elitism
BR
[77]
2014
J
GA
T
SM
UX
Tournament selection
Other
[78]
2014
C
NSGA-II
C
m
a
x, total production energy costs, total energy costs of maintenance
InsM, SM
SPX, MPX
-
Other
[79]
2014
J
GA
C
m
a
x
SM
TPX, POX
Roulette wheel
Industry
[80]
2014
J
GA
Min of due date mean squared deviation
Shift mutation
TPX
-
Other
[81]
2015
J
GA
C
m
a
x
SM
Position based crossover, OX, PMX
Roulette wheel, tournament selection
LD
[82]
2015
J
GA
C
m
a
x
Random selection, neighborhood search
TPX, UX
Roulette wheel
BR
[83]
2015
J
GA
T
-
Shift mutation, EM
TPX, POX
-
BR
[84]
2015
J
GA
C
m
a
x
Values mutation
UX, POX
Roulette wheel
BR
[85]
2015
J
GA
C
m
a
x
Inversion mutation, random
UX, POX
BR
[86]
2015
CP
GA
C
m
a
x
SM, inversion mutation
TPX, POX
Tournament selection
KA
[87]
2015
J
GA
C
m
a
x
SM
OPX
Other
[88]
2015
J
GA
C
m
a
x
SM
TPX
Tournament selection
Other
[89]
2015
J
GA
C
m
a
x
EM
TPX
Linear ranking
Other
[90]
2015
CP
GA
C
m
a
x
Random
Integer crossover
Roulette wheel
KA
[91]
2016
J
NSGA-II, NRGA
C
m
a
x and stability objectives
Modified PBM, MBM
POX
-
KA, BR
[92]
2016
J
NSGA-II
C
m
a
x, total energy consumption
Deviation-based mutation, reciprocal EM
Intermediate recombination, line recombination
Elitism
Other
[93]
2017
CP
GA
C
m
a
x
RM, SM
POX, MPX
Tournament, elite reservation
Other
[94]
2017
J
GA
C
m
a
x
RM
MPX
Ranking, stochastic universal sampling
Other
[95]
2017
CP
GA
C
m
a
x, lead time
RM
MPX
Roulette wheel
Other
[96]
2017
J
GA
C
m
a
x
SM
POX
Elitism, population diversity strategy
Other
[97]
2017
CP
GA
C
m
a
x
RM
MPX
Roulette wheel
Industry
[98]
2017
CP
GA
C
m
a
x
RM, SM
POX
Tournament selection
BC
[99]
2017
J
GA
C
m
a
x
RM
TPX
Elitism
BR, other
[100]
2017
J
NSGA-II
C
m
a
x
,
W
M
,
W
T
RM, SM, reverse mutation, multipoint mutation
SPX, MPX, POX, JBX
Tournament
KA, DP, BR, BC
[101]
2017
J
GA
C
m
a
x, workload of each machine, W
T
-
-
-
KA
[102]
2017
CP
GA
C
m
a
x
,
W
T
-
POX, MPX
Elitism
Industry


## 4.6. FJSSP with Advanced Forms of GA

With the advancement in computing power and artificial intelligence techniques, various advances have been made in the original GA by incorporation of innovative ideas, majorly learning based evolution. Table3 presents the year-wise literature in this area.Table 3
FJSSP with advanced forms of GA.
Ref
Year
Article type
Algorithm details
Objective
GA parameters
Benchmark
Mutation
Crossover
Selection
[19]
2002
J
Controlled GA
C
m
a
x, sum of machine workloads
Artificial mutation
Modified crossover
Elitism
KA
[103]
2005
J
Multistage operation based GA
C
m
a
x
,
W
M
,
W
T
Local-search mutation
One-cut point crossover
Random
KA
[104]
2005
C
LEGA
C
m
a
x
-
-
-
KA
[20]
2006
J
Iterative GA
C
m
a
x
Random
SPX, job-based order crossover
Roulette wheel
FT, LA
[105]
2006
C
GA with Choquet integral
C
m
a
x
,
W
M
,
W
T
-
-
-
KA
[106]
2007
J
Learning GA
C
m
a
x
Random, algorithm based
TPX, random
Linear scaling, stochastic universal sampling
Mesghouni, BR
[107]
2008
C
TPGA
Min of fuzzyC
m
a
x
Random
GOX, generalization of PPX
Tournament selection
KA
[108]
2008
J
GA with Choquet integral
C
m
a
x
,
W
M
,
W
T, sum of weighted earliness and weighted tardiness, sum of production cost
-
-
-
KA
[109]
2009
C
Course grained parallel GA based on island model parallelization technique
C
m
a
x
Sublot step mutation, Sublot swap mutation, random operation AssM, intelligent operations AssM, operations sequence shift mutation
SPX-, SPX-2 (SPC-2), operation to machine ACX, job level operations sequence crossover, subplot level operations sequence crossover
Tournament selection
Other
[110]
2009
C
Adaptive GA
C
m
a
x
Adaptive
Adaptive, precedence operation crossover
Roulette wheel
KA
[111]
2010
C
GA with learning by injection of sequences
C
m
a
x
Mutation by direct exchange, mutation by random exchange, mutation by inversion, Mutation by close exchange, mutation by gap of all the elements
SPX
Random
FT, other
[112]
2010
C
Cooperative coevolutionary GA
C
m
a
x
Random, SM
Row crossover, column crossover, precedence order crossover
Roulette wheel
BR
[113]
2010
J
Parallel GA
C
m
a
x
PPS, AssM, IM
ACX, POX
Tournament selection
Other
[114]
2010
C
Matrix coded GA
C
m
a
x
Machine dimension mutation, operation dimension mutation
Machine dimension crossover, operation dimension crossover
Tournament
Other
[115]
2010
J
Decomposition integration GA
C
m
a
x
Swap operator
Generalized position crossover, generalization of PPX
Tournament selection
KA
[116]
2010
J
LEGA
C
m
a
x
Random, operational memory based mutation
TPX, random
Tournament
LA
[117]
2010
C
Adaptive GA
C
m
a
x
Random
OPX, three-point crossover
League selection
Industry
[118]
2010
C
Coevolutionary genetic algorithm
FuzzyC
m
a
x
SMRandom
TPX, discrete crossover
Tournament selection
KA
[119]
2010
C
GA based on immune and entropy principle
C
m
a
x
,
W
T
Random
IPOX, MPX
-
KA
[120]
2011
J
GA with heuristics
C
m
a
x
-
-
Elitism, tournament selection
BR, other
[121]
2011
C
Adaptive GA
C
m
a
x
Random
OPX
Elitism
KA
[122]
2011
C
MSCEA
C
m
a
x
Neighborhood mutation
TPX
Random
BR
[123]
2012
J
Multiobjective GA
C
m
a
x, total machining time
SM
SPX
-
Other
[124]
2012
C
GA with learning
C
m
a
x
Random
OPX
Elitist
LD, BR
[125]
2012
J
Coevolutionary GA
FuzzyC
m
a
x
SM
TPX, extension of PPX
Modified tournament selection
Other
[126]
2012
J
Jumping genes GA
C
m
a
x, flow time of products with AGV, completion of the products
EM
SPX
Tournament selection
Other
[127]
2013
J
Real coded GA
C
m
a
x
Random
Extended intermediate crossover, OPX
Roulette wheel, binary tournament, elitism, replacement
BR
[128]
2014
J
NSGA-II based on blood variation
C
m
a
x, processing cost, energy consumption, cost-weighted processing quality
Modified mutation
Blood relation based crossover
Modified quick sorting ranking
Industry
[129]
2016
CP
Immune GA
Maximization of due time satisfaction, minimize the total processing costs
Random
SPX
Roulette wheel
FT
[130]
2016
J
Extended GA
Maximize satisfaction degree
SM
TPX, POX
Tournament selection
Other
[131]
2016
CP
GA with comprehensive search
C
m
a
x
Random
Operation-based crossover
Roulette wheel
Other


## 4.7. FJSSP with hGA

Although better results have been obtained with the techniques presented in Section4.6, other standalone optimization techniques have also been proposed for the solution of FJSSP. However, researchers have amalgamated some standalone techniques with GA to obtain better solution times and results. These techniques have primarily been used to further improve the solution of a stated GA iteration before starting the new iteration. In this way, optimum solution is reached in a more effective manner. Table 4 presents year-wise literature in this class.Table 4
FJSSP with hGA.
Ref
Year
Article type
Algorithm details
Objective
GA Parameters
Benchmark
Mutation
Crossover
Selection
[132]
2001
C
GA + MILP
C
m
a
x, Min of T
SM
Multipoint crossover
Tournament selection
Other
[133]
2002
J
Controlled GA + fuzzy logic
C
m
a
x
,
W
M
,
W
T
Artificial mutation
Modified crossover
Fittest
KA
[134]
2004
J
GA + priority dispatching rules
Min ratio of tardy jobs, variance of the flow time, amount of mold changes, max efficiency of machines
Priority dispatching rule based mutation
Two-point conical
Tournament selection, elitism
Other
[135]
2004
C
GA + LS + heuristic
C
m
a
x
,
W
M
,
W
T
-
POX
Fittest
Other
[136]
2006
C
GA + TS
T
PPS, random
POX, GOX
-
Other
[137]
2006
J
GA + LS
C
m
a
x
,
W
M
,
W
T
Phenotype based mutation
Phenotype based crossover
Ranking selection
KA
[138]
2006
J
GA + scheduling rules
C
m
a
x
Random
SPX
Roulette wheel
FT
[139]
2006
C
GA + heuristic
C
m
a
x
InsM, SM
OPX with priority list, TPX with priority list, selective machine sequences crossover
-
LA, FT
[140]
2006
C
GA + LS procedure based on shifting bottleneck
C
m
a
x
,
W
M
,
W
T
AllM, ImmM
Exchange crossover, EOX
-
KA
[141]
2006
C
GA + TS
C
m
a
x, maximum lateness
Random (dynamic)
Random (Boolean matrix)
-
LA
[142]
2006
C
GA + heuristic
T
Random sequencing mutation, random AssM, IM
GOX, sequencing and ACX, ACX
-
BR, other
[143]
2007
J
GA + LS procedure based on shifting bottleneck
C
m
a
x
,
W
M
,
W
T
AllM
EOX
-
KA, BR
[144]
2007
J
GA + LS
C
m
a
x
,
W
M
,
W
T
PPS
Preserving order based crossover
Fittest
BR, DP,
[145]
2008
J
GA + variable neighborhood descent
C
m
a
x
,
W
M
,
W
T
AllM, ImmM
EOX, UX
Ranking selection
KA, BR, BC, DP, FT, LA, other
[146]
2008
J
GA + guided LS
C
m
a
x
,
W
M
,
W
T
Random
TPX
Ranking selection
KA, other
[147]
2008
J
GA + MILP
Mean flow time,C
m
a
x, maximum lateness, total absolute deviation from the due dates
Random
OPX, partial matched crossover
Elitist
Other
[148]
2008
C
GA + TS
C
m
a
x
Random
TPX, improved POX
Tournament selection
BR
[149]
2009
J
GA + simulation
C
m
a
x, min of mean tardiness
AssM, sequencing mutation
TPX
Roulette wheel
BR
[150]
2009
C
GA + LS
C
m
a
x
-
-
-
BR
[151]
2010
J
NSGAII + SA
C
m
a
x
,
C
p
Reciprocal swap
UX
Elitism
Other
[152]
2010
J
GA + immune mechanism + SA
C
m
a
x
,
C
p
Adaptive crossover
Adaptive crossover
Fittest
Other
[153]
2010
J
VNS + GA
C
m
a
x
,
W
M
,
W
T
Random
TPX
Fittest
KA
[154]
2010
C
GA + chaotic LS
C
m
a
x
IM, random
GOX, generalized PMX
Binary tournament
BR
[155]
2010
J
GA + hill climbing
C
m
a
x
,
W
M
,
W
T
Random
TPX
Tournament
KA
[156]
2010
J
GA + immune + entropy principle
C
m
a
x
,
W
M
,
W
T
Random
IPOX, multipoint preservative crossover
Tournament selection
KA, BR, DP
[157]
2010
C
PSO + GA
C
m
a
x
Random
SPX
-
Other
[158]
2010
C
GA + VNS
C
m
a
x
,
W
M
,
W
T
Random, swap
TPX, POX
Tournament selection
KA
[159]
2010
C
GA + TS
C
m
a
x
,
W
M
,
W
T
Random
TPX, POX
-
KA
[160]
2011
J
GA + LS
C
m
a
x
PBM, MBM
POX
Roulette wheel, ranking
KA, Mesghouni, LD, BR, BC, DP, HU
[161]
2011
C
TS + SA + GA
C
m
a
x
,
W
M
,
W
T
Random
Combined order and position-based crossover
-
KA, BR
[162]
2011
C
GA + AIS
C
m
a
x
SM
MPPX, MGOX, MGPMX1, MGPMX2
Elitism
Other
[163]
2011
J
GA
Min of maximum workload
SM
UX
Search rate survival
BR, LA
[164]
2011
J
GA + SA
C
m
a
x
,
W
T
Dynamic mutation
Dynamic crossover
Roulette wheel
KA
[165]
2011
C
GA + TS
Min time, min cost, equipment utilization rate
Random
MPPX, MGOX, MGPMX1, MGPMX2
Elitism
Other
[166]
2011
C
GA + PSO
C
m
a
x
Random, balance load mutate
POX, MPX
-
KA, BR
[167]
2011
J
GA + fuzzy set theory
Optimization of cost, quality and time
Neighborhood mutation
Neighborhood crossover
-
Industry
[168]
2011
J
GA + ACO
C
m
a
x
Inverted mutation, operation assignment machine knowledge
TPX, modified crossover
Linear scaling, stochastic universal sampling
KA, BR
[169]
2012
J
GA + grouping GA
T, total machine idle time, C
m
a
x
-
-
-
Industry
[170]
2012
C
GA + LS
C
m
a
x
Machine replacement
POX
Elitism
Industry
[171]
2012
J
GA + Petri nets
C
m
a
x, total expense, workload of machines
InvM
-
Elitism
Other
[172]
2012
C
GA + LS + TS
C
m
a
x
,
W
M
,
W
T
SM, random
UX, IPOX
Elitism
KA
[173]
2012
C
hGA
Min the total earliness, min of tardiness penalties
SM, SA
POX, job-based machine crossover
Roulette wheel
FT
[174]
2012
J
GA + TS
C
m
a
x, min of mean flow time
AllM
PMX, OX
Tournament selection
Other
[13]
2012
C
GA + PSO
T
-
OPX
Roulette wheel
KA
[175]
2012
C
GA + TS + modified shifting bottleneck procedure
C
m
a
x
SM
SPX
Elitism
Other
[176]
2012
J
Duplicate GA + LS
C
m
a
x, min of total idleness
SM
UX
Roulette wheel
KA
[177]
2012
J
GA + LS based on critical path theory
C
m
a
x
,
W
M
,
W
T
ImmM, modified AssM
POX, TPX
-
KA, BR
[178]
2012
J
GA + TS
C
m
a
x
AssM
SPX
Roulette wheel
Other
[179]
2013
J
GA + VNS with affinity function
C
m
a
x
SM
UX, OPX
Tournament selection
Other
[180]
2013
J
GA + simulation
Total of average flow times
SM
Two-stage crossover
Tournament
Other
[181]
2013
J
GA + SA
Min the total cost including delay costs, setup costs, and holding costs
Intelligent AssM, random AssM, intelligent sequencing mutation 1, intelligent sequencing mutation 2, randomly sequencing mutation
POX, random crossover
Linear ranking
Other
[182]
2013
C
PSO + GA with Cauchy distribution
C
m
a
x
InsM
MPX
-
Other
[183]
2013
J
GA + SA
C
m
a
x
,
W
M
,
W
T
New mutation
New crossover
Elitism
KA
[179]
2013
J
GA + VNS
C
m
a
x
InsM, SM
TPX, modified crossover
Tournament selection
Other
[184]
2013
J
NGSA + knowledge based Algorithm
C
m
a
x, robustness
MBM, ImmM
TPX
-
KA, other
[185]
2013
C
NSGA-II + LS
C
m
a
x
,
W
M
,
W
T
Random
Modified crossover
-
KA, BR
[186]
2013
J
GA + SA
C
m
a
x, sum of std deviation of processing workload for all working centers
InvM
OX
Ranking selection
Other
[187]
2014
J
GA + shifting bottleneck
C
m
a
x
,
W
M
SM
EOX
Elitism
Other
[188]
2014
J
GA + population improvement
C
m
a
x
SM
POX, MPX
Binary tournament selection
BR
[189]
2014
CP
GA + TS
C
m
a
x
SM, alternative mutation
POX, PMX
Tournament selection
KA
[190]
2014
CP
GA + LS
C
m
a
x
Random
POX
-
BR, HU, DP
[191]
2015
CP
GA + TS
C
m
a
x
IM
OX
Elitism
BR, HU
[192]
2015
J
Neighborhood-based GA + TS + LS
C
m
a
x
SM, InvM
UX, IPOX
Fitness neighborhood selection operator
BR, HU
[193]
2015
J
GA + TS
C
m
a
x
-
Job order crossover
Tournament selection
BR, BC, DP, Other
[194]
2015
J
GA + PSO
Minimize sum of holding, setup, production, overtime costs
SM
MPX
Tournament selection
Other
[195]
2015
J
GA + heuristics
C
m
a
x, overtime costs of machines
SM
OX
Ranking
Other
[196]
2015
J
GA + VNS
T
AssM, SM
UX, modified POX
Linear ranking
BR, HU, other
[197]
2016
J
GA + heuristics
Mean tardiness
SM
SPX
-
Other
[198]
2016
J
GA + TS
C
m
a
x
SM
PBX
Tournament
FT, LA
[199]
2016
J
GA + TS
C
m
a
x
SM, neighborhood mutation
POX, JBX, TPX
Elitism, tournament selection
KA, FH, BR, BC, HU, DP
[200]
2016
J
GA + TS
Weighted tardiness, balancing the setup workers load, min the work-in-process
SM
TPX
Ranking
Other
[201]
2016
J
Neighborhood GA + TS
C
m
a
x
SM, InsM
UX, IPOX
Fitness neighborhood selection operator
Other
[202]
2016
CP
GA + LS
C
m
a
x
Uniform mutation, InsM, SM
UX, TPX, POX
Average hamming distance
KA, BR
[203]
2016
J
GA + LS
C
m
a
x
SM
JBX
Elitism, tournament
BR
[204]
2017
J
GA + SA
C
m
a
x, maximizing the total availability of the system, minimizing total energy cost of both production and maintenance operations
RM, SM
UX, POX
Roulette wheel
Other
[205]
2017
CP
GA + VNS
C
m
a
x
IntM
MPX
Elitism
HU
[206]
2017
J
GA + Taguchi
C
m
a
x
RM, IntM
TPX, POX, UX
Tournament, other
BR, other
[207]
2017
J
GA + VNS
C
m
a
x, mean tardiness
RM
POX
Tournament selection
HU
[208]
2017
J
GA + LS
C
m
a
x
SM, RM
POX
Fitness-neighborhood selection
KA, BR, HU, BC


## 5. Analysis and Discussion

As obvious from the data presented in Section4, FJSSP is an important research area which is highly published and which has been attended to with continuity over the last twenty years. This is due to the fact that the exact solution of this optimization problem has not been found yet and efforts are still being made to attain good solutions in a reasonable time and with reasonable computational resources.We have reviewed a total of 190 research articles published from 2001 to December, 2017. These articles were narrowed down from a total of 384 articles found on the FJSSP. The articles have strictly been selected if they are on optimization of FJSSP and solved using a variant of GA. Furthermore, data also depicts the use of various types of GA operators (crossover, mutation, and selection) used by the researchers. The following facts have been revealed by this survey.


### 5.1. Source-Wise Distribution

Source-wise distribution of this survey is presented in Table5. We have emphasized the number of journal articles over conference publications. It is evident from Figure 8 presenting the patch-wise distribution that 41% articles have been collected from 2009 to 2012 while 38% articles have been collected from 2013 to 2017. The combined percentage of articles published during years 2009–2017 comes out to be 79% of the total published research. Thus, a major chunk has been published in the last seven years.Table 5
Distribution of article types.
Article type
Quantity
Journal article
108
Conference paper
64
Conference proceedings
18
Total
190Figure 8
Percentage of publications in time—patches.


### 5.2. Year-Wise Distribution

Year-wise distribution of these articles (journal and conference) is presented in Figure9. There has been an increasing trend in the publications in this area from 2009 to 2012 while a constant and healthy trend has been observed in years 2013–2017.Figure 9
Year-wise distribution of research.


### 5.3. Most Published Journals

The journals covering the subject of FJSSP are presented in Table6. A total of 113 journals have given coverage to FJSSP related articles, while the journals publishing more than 2 papers are presented here. The International Journal of Production Research has published most research articles in this area.Table 6
Paper distribution in journals.
Journal name
Number of publications
International Journal of Production Research
13
Computers & Operations Research
6
International Journal of Advanced Manufacturing Technology
5
Expert Systems with Applications
5
Journal of Intelligent Manufacturing
5
Computers & Industrial Engineering
4
International Journal of Production Economics
3


### 5.4. Country-Wise Publication Data

Figure10 presents country-wise publication data. A total of 184 countries have contributed in this area, out of which China has published 43.53% of publications while Iran, France, and Japan have published 11.18%, 10.59%, and 7.06% publications, respectively. Other notable countries are India, Turkey, and Taiwan.Figure 10
Country-wise publication data.


### 5.5. Techniques Used for FJSSP

There are 78 different technique combinations used in the selected papers, out of which only 10 techniques constitute 119 papers (62.63%). A distribution of techniques having at least 3 publications is presented in Table7. It is evident that 70 publications have used GA as a sole technique for solution of FJSSP and GA + TS is the most used hybrid technique. A group-wise division of the whole techniques in Table 8 shows that hybrid techniques constitute a 37.5% of our study, while pure GA based publications amount to 39.5%. It is also evident that GA has been hybridized majorly with local search approaches like TS, SA, and VNS. This technique improves the initial solution of GA routine. There is a need to explore the possibility of hybridizing various other standalone optimization algorithms with GA.Table 7
Algorithms used for FJSSP having at least 3-publication count.
Algorithm details
Publication count
Percentage
GA
70
54.69
GA + TS
13
10.16
NSGA-II
11
8.59
GA + local search
10
7.81
GA + heuristic
5
3.91
GA + SA
5
3.91
GA + VNS
5
3.91
Adaptive GA
3
2.34
GA + PSO
3
2.34
GA with learning
3
2.34Table 8
Group-wise publication count.
Group
Publication count
Percentage
GA
79
39.5
Hybrid
75
37.5
Advanced GA
31
15.5
NSGA
15
7.5


### 5.6. Most Used Objective Functions

A total of 62 objective functions have been optimized in single/multiobjective manner. Table9 summarizes the occurrences and percentages of the objective functions giving at least 02 occurrences. It is evident that makespan is the most sought after objective. Figure 11 shows that 46 different multiobjective functions have been addressed in contrast with 13 different single objective functions.Table 9
Most addressed objective functions.
Objective function
Number of occurrences
Percentage
Makespan
162
71.37
Total workload of machines
32
14.10
Workload of most loaded machine
14
6.17
Total tardiness
7
3.08
Max lateness
2
0.88
Mean flow time
2
0.88
Mean tardiness
2
0.88
Min of fuzzy makespan
2
0.88
Tardiness
2
0.88
Weighted tardiness
2
0.88Figure 11
Division of different single and multiobjective cost functions.Table10 indicates that makespan has been addressed the most as a single objective function, while makespan, workload of most loaded machine, and total workload of machines have been addressed the most as a multiobjective function.Table 10
Occurrences of objective functions.
Objective functions
Nature
Occurrences
Makespan
Single
92
Makespan, workload of most loaded machine, total workload of machines
Multi
28
Total tardiness
Single
4
Makespan, production costs
Multi
4
Makespan, total workload of machines
Multi
4
Min of fuzzy makespan
Single
3


### 5.7. Most Benchmark Problems Attempted

The benchmark problems attempted the most are tabulated in Figure12. The benchmark problems have been addressed 262 times. It is pertinent to mention here that there is a tendency in literature, especially conference papers, to attempt using the selected data sets. Thus if an author has attempted to solve only one of the ten problems of Brandimarte, we have counted it as one instance. The problems of Kacem have been attempted the most with Brandimarte at the 2nd priority. The industrial problems have been addressed only 5% of the time and other than that the research has been inclined towards algorithm development and comparison with benchmark instances.Figure 12
Distribution of benchmark problems attempted.


### 5.8. Software Tools Used

This survey shows that 25 software tools have been used for the competent solution of FJSSP. Table11 depicts that C++ has been the most popular language for programming the problem, with MATLAB being the second most popular.Table 11
Use of software tools for FJSSP solution.
Software tool
Times used
C++
32
MATLAB
28
JAVA
10
C#
7
Visual Basic
5
C
4
Visual C++
3


### 5.9. Special Cases of FJSSP

Although there are many different cases of FJSSP studied in literature, the following cases have received special attention as they have been studied more often than others.(i)
Dual-resource constrained FJSSP, for example, [52, 162]
(ii)
Sequence dependent setup times, for example, [88, 207]
(iii)
Distributed and flexible JSSP, for example, [79, 99]
(iv)
Just-In-Time dynamic scheduling, for example, [80, 83]
(v)
Overlapping in operations, for example, [73, 98]
(vi)
Random machine breakdowns, for example, [91, 184]
(vii)
Dynamic FJSSP, for example, [94, 96].


### 5.10. GA Parameters

It is evident from the literature review presented in Tables2, 3, and 4 that various GA parameters have been used to address the FJSSP. Table 12 presents the major types of mutation and their frequency of use. Similarly, Tables 13 and 14 present the frequency of crossover and selection operators.Table 12
Distribution of mutation schemes.
Mutation type
Times used
Swap mutation
60
Random
53
Inverse mutation
9
Assignment mutation
8
Insertion mutation
7
Precedence preserving shift mutation
7
Intelligent mutation
7
Allele mutation
5
Immigration mutation
4
Neighborhood mutation
4
Exchange mutation
3Table 13
Distribution of crossover schemes.
Crossover type
Times used
Two-point crossover
49
Precedence preserving order-based crossover
44
Uniform crossover
20
Single-point crossover
15
One-point crossover
13
Multipoint crossover
12
Assignment crossover
7
Modified crossover
7
Random
7
Generalized order crossover
5
Order crossover
5
Partially mapped crossover
5
Enhanced order crossover
4
Improved precedence preserving order-based crossover
5Table 14
Distribution of selection schemes.
Selection type
Times used
Tournament
50
Roulette wheel
33
Elitism
30
Fittest
9
Linear ranking
6
Random
6
Ranking selection
8


## 5.1. Source-Wise Distribution

Source-wise distribution of this survey is presented in Table5. We have emphasized the number of journal articles over conference publications. It is evident from Figure 8 presenting the patch-wise distribution that 41% articles have been collected from 2009 to 2012 while 38% articles have been collected from 2013 to 2017. The combined percentage of articles published during years 2009–2017 comes out to be 79% of the total published research. Thus, a major chunk has been published in the last seven years.Table 5
Distribution of article types.
Article type
Quantity
Journal article
108
Conference paper
64
Conference proceedings
18
Total
190Figure 8
Percentage of publications in time—patches.


## 5.2. Year-Wise Distribution

Year-wise distribution of these articles (journal and conference) is presented in Figure9. There has been an increasing trend in the publications in this area from 2009 to 2012 while a constant and healthy trend has been observed in years 2013–2017.Figure 9
Year-wise distribution of research.


## 5.3. Most Published Journals

The journals covering the subject of FJSSP are presented in Table6. A total of 113 journals have given coverage to FJSSP related articles, while the journals publishing more than 2 papers are presented here. The International Journal of Production Research has published most research articles in this area.Table 6
Paper distribution in journals.
Journal name
Number of publications
International Journal of Production Research
13
Computers & Operations Research
6
International Journal of Advanced Manufacturing Technology
5
Expert Systems with Applications
5
Journal of Intelligent Manufacturing
5
Computers & Industrial Engineering
4
International Journal of Production Economics
3


## 5.4. Country-Wise Publication Data

Figure10 presents country-wise publication data. A total of 184 countries have contributed in this area, out of which China has published 43.53% of publications while Iran, France, and Japan have published 11.18%, 10.59%, and 7.06% publications, respectively. Other notable countries are India, Turkey, and Taiwan.Figure 10
Country-wise publication data.


## 5.5. Techniques Used for FJSSP

There are 78 different technique combinations used in the selected papers, out of which only 10 techniques constitute 119 papers (62.63%). A distribution of techniques having at least 3 publications is presented in Table7. It is evident that 70 publications have used GA as a sole technique for solution of FJSSP and GA + TS is the most used hybrid technique. A group-wise division of the whole techniques in Table 8 shows that hybrid techniques constitute a 37.5% of our study, while pure GA based publications amount to 39.5%. It is also evident that GA has been hybridized majorly with local search approaches like TS, SA, and VNS. This technique improves the initial solution of GA routine. There is a need to explore the possibility of hybridizing various other standalone optimization algorithms with GA.Table 7
Algorithms used for FJSSP having at least 3-publication count.
Algorithm details
Publication count
Percentage
GA
70
54.69
GA + TS
13
10.16
NSGA-II
11
8.59
GA + local search
10
7.81
GA + heuristic
5
3.91
GA + SA
5
3.91
GA + VNS
5
3.91
Adaptive GA
3
2.34
GA + PSO
3
2.34
GA with learning
3
2.34Table 8
Group-wise publication count.
Group
Publication count
Percentage
GA
79
39.5
Hybrid
75
37.5
Advanced GA
31
15.5
NSGA
15
7.5


## 5.6. Most Used Objective Functions

A total of 62 objective functions have been optimized in single/multiobjective manner. Table9 summarizes the occurrences and percentages of the objective functions giving at least 02 occurrences. It is evident that makespan is the most sought after objective. Figure 11 shows that 46 different multiobjective functions have been addressed in contrast with 13 different single objective functions.Table 9
Most addressed objective functions.
Objective function
Number of occurrences
Percentage
Makespan
162
71.37
Total workload of machines
32
14.10
Workload of most loaded machine
14
6.17
Total tardiness
7
3.08
Max lateness
2
0.88
Mean flow time
2
0.88
Mean tardiness
2
0.88
Min of fuzzy makespan
2
0.88
Tardiness
2
0.88
Weighted tardiness
2
0.88Figure 11
Division of different single and multiobjective cost functions.Table10 indicates that makespan has been addressed the most as a single objective function, while makespan, workload of most loaded machine, and total workload of machines have been addressed the most as a multiobjective function.Table 10
Occurrences of objective functions.
Objective functions
Nature
Occurrences
Makespan
Single
92
Makespan, workload of most loaded machine, total workload of machines
Multi
28
Total tardiness
Single
4
Makespan, production costs
Multi
4
Makespan, total workload of machines
Multi
4
Min of fuzzy makespan
Single
3


## 5.7. Most Benchmark Problems Attempted

The benchmark problems attempted the most are tabulated in Figure12. The benchmark problems have been addressed 262 times. It is pertinent to mention here that there is a tendency in literature, especially conference papers, to attempt using the selected data sets. Thus if an author has attempted to solve only one of the ten problems of Brandimarte, we have counted it as one instance. The problems of Kacem have been attempted the most with Brandimarte at the 2nd priority. The industrial problems have been addressed only 5% of the time and other than that the research has been inclined towards algorithm development and comparison with benchmark instances.Figure 12
Distribution of benchmark problems attempted.


## 5.8. Software Tools Used

This survey shows that 25 software tools have been used for the competent solution of FJSSP. Table11 depicts that C++ has been the most popular language for programming the problem, with MATLAB being the second most popular.Table 11
Use of software tools for FJSSP solution.
Software tool
Times used
C++
32
MATLAB
28
JAVA
10
C#
7
Visual Basic
5
C
4
Visual C++
3


## 5.9. Special Cases of FJSSP

Although there are many different cases of FJSSP studied in literature, the following cases have received special attention as they have been studied more often than others.(i)
Dual-resource constrained FJSSP, for example, [52, 162]
(ii)
Sequence dependent setup times, for example, [88, 207]
(iii)
Distributed and flexible JSSP, for example, [79, 99]
(iv)
Just-In-Time dynamic scheduling, for example, [80, 83]
(v)
Overlapping in operations, for example, [73, 98]
(vi)
Random machine breakdowns, for example, [91, 184]
(vii)
Dynamic FJSSP, for example, [94, 96].


## 5.10. GA Parameters

It is evident from the literature review presented in Tables2, 3, and 4 that various GA parameters have been used to address the FJSSP. Table 12 presents the major types of mutation and their frequency of use. Similarly, Tables 13 and 14 present the frequency of crossover and selection operators.Table 12
Distribution of mutation schemes.
Mutation type
Times used
Swap mutation
60
Random
53
Inverse mutation
9
Assignment mutation
8
Insertion mutation
7
Precedence preserving shift mutation
7
Intelligent mutation
7
Allele mutation
5
Immigration mutation
4
Neighborhood mutation
4
Exchange mutation
3Table 13
Distribution of crossover schemes.
Crossover type
Times used
Two-point crossover
49
Precedence preserving order-based crossover
44
Uniform crossover
20
Single-point crossover
15
One-point crossover
13
Multipoint crossover
12
Assignment crossover
7
Modified crossover
7
Random
7
Generalized order crossover
5
Order crossover
5
Partially mapped crossover
5
Enhanced order crossover
4
Improved precedence preserving order-based crossover
5Table 14
Distribution of selection schemes.
Selection type
Times used
Tournament
50
Roulette wheel
33
Elitism
30
Fittest
9
Linear ranking
6
Random
6
Ranking selection
8


## 6. Conclusions

This paper has presented the review of GA based techniques for solution of FJSSP with the help of literature published in the conference and journal papers in the time frame of 2001–2017. The study presents a comprehensive insight into the research trends in this area.The contribution of this work is twofold. Firstly, it addresses the application of GA specifically to the FJSSP and provides a startup for researchers who want to excel in this area by providing recent research trends. Secondly, the parameters that have been used the most are also identified which can be mapped with references for advanced studies. Furthermore, the special cases of FJSSP have also been identified.The study has surveyed the implementation of GA for FJSSP in detail and the trends for use of GA parameters have also been presented, along with the benchmark studies conducted with each approach. It is obvious that GA is the most popular technique for the solution of FJSSP. The researchers have made no claim that any of the methods is the best, but the trend is to compare the solutions with the standard benchmarks. The study has pointed out the mostly used parameters of GA in the literature. It was also observed that hybrid GA is even more popular than the pure GA. Furthermore, due to the known phenomena of local minima trap in GA routine, local search techniques have mostly been integrated with the GA. Consequently, there is a need to explore options for integration of more advanced artificial intelligence based algorithms with GA.



---

*Source: 9270802-2018-02-28.xml*