An effective hybrid algorithm for multi-objective flexible job-shop scheduling problem

Abstract

Genetic algorithm is one of primary algorithms extensively used to address the multi-objective flexible job-shop scheduling problem. However, genetic algorithm converges at a relatively slow speed. By hybridizing genetic algorithm with particle swarm optimization, this article proposes a teaching-and-learning-based hybrid genetic-particle swarm optimization algorithm to address multi-objective flexible job-shop scheduling problem. The proposed algorithm comprises three modules: genetic algorithm, bi-memory learning, and particle swarm optimization. A learning mechanism is incorporated into genetic algorithm, and therefore, during the process of evolution, the offspring in genetic algorithm can learn the characteristics of elite chromosomes from the bi-memory learning. For solving multi-objective flexible job-shop scheduling problem, this study proposes a discrete particle swarm optimization algorithm. The population is partitioned into two subpopulations for genetic algorithm module and particle swarm optimization module. These two algorithms simultaneously search for solutions in their own subpopulations and exchange the information between these two subpopulations, such that both algorithms can complement each other with advantages. The proposed algorithm is evaluated on some instances, and experimental results demonstrate that the proposed algorithm is an effective method for multi-objective flexible job-shop scheduling problem.

Keywords

Flexible job-shop scheduling problem hybrid algorithm genetic algorithm particle swarm optimization multi-objective optimization

Introduction

Flexible job-shop scheduling problem (FJSP) is an extension and generalization of the classical job-shop scheduling problem (JSP).^1–3 Generally, in a classical job-shop model, all jobs follow fixed routes, but not necessarily the same for each job, and every operation of all jobs is required to be processed on one predetermined machine.^4,5 JSP determines a sequence of operations on each machine to optimize one or multiple objectives. By contrast, if there exist two or more machines that can be allowed to process one operation, the model is called flexible job shop. The FJSP is required not only to determine the sequencing of operations on machines, but also to assign each operation to a machine.^1,2,6 It is well known that the JSP is non-deterministic polynomial (NP)-hard.⁷ As a generalization of the JSP, the FJSP is equally known to be NP-hard and is challenging due to the expanding machine flexibility.^1–3,8–11

The FJSP has important applications in many real industries such as semiconductor manufacturing, automobile assembly, and textile, where a group of machines is capable for each operation. Therefore, from both the theoretical and the practical viewpoint, FJSP is one of the most common scheduling models existing in modern industry environment. In addition, it is often necessary to optimize several conflict objectives simultaneously in the real world, and therefore, the multi-objective flexible job-shop scheduling problem (MOFJSP) has become a hot and important research topic.

Generally, the approaches applied to solve MOFJSP can be roughly divided into two categories, that is, priori method and posteriori method.^1,12 In the priori method, a MOFJSP is usually converted into a single-objective FJSP by combining multiple objectives into a single-objective function. According to the existing literature, the priori method got more concerns by researchers on earlier studies. For example, Brandimarte¹³ presented a hybrid tabu search (TS) with dispatching rules to solve MOFJSP. Specially, TS was used to solve the sub-problem of optimizing the operations sequencing and dispatching rules were applied to solve the sub-problem of operations assignment to machines. Kacem et al.¹⁴ embedded the local optimization algorithm within an evolution algorithm. Xia and Wu¹⁵ proposed a hybrid method to solve MOFJSP. They used particle swarm optimization (PSO) to assign operations and used simulated annealing (SA) algorithm to sequence operations on each machine. Gao et al.¹⁶ developed an adapted genetic algorithm (GA) hybridized with a shifting bottleneck strategy for MOFJSP. The posterior method has recently attracted many researchers to investigate multi-objective problems. For example, Kacem et al.¹⁷ presented a Pareto method based on the hybridization of fuzzy logic and evolutionary algorithms for MOFJSP. Li et al.¹⁸ developed a Pareto-based discrete artificial bee colony algorithm for MOFJSP. Ho et al.^10,19 proposed a hybrid evolutionary algorithm with local search and meanwhile introduced an elitism memory to store all non-dominated solutions that have been found. Yuan and Xu¹ elaborated a new memetic algorithms (MAs) by incorporating a local search algorithm into the adapted Non-dominated Sorting Genetic Algorithm II (NSGA) for MOFJSP. Wang et al.²⁰ developed a GA based on the immune and entropy principle to address MOFJSP. Wang et al.²¹ proposed an enhanced Pareto-based artificial bee colony algorithm for MOFJSP.

In general, there are two limitations about the priori methods mentioned above. One is that the priori methods require priori information, such as weighting factors of each objective, which are usually subjective. Another is that multiple runs are needed to get a set of satisfactory solutions. Unlike the priori method, the posterior method requires no priori information and therefore has more extensive applicability. Most of the posterior methods mentioned above have obtained better solutions by combining the explorative search of one algorithm and the exploitative search of another algorithm together. It is noticeable that these methods are Pareto-based and they can obtain a set of non-dominated solutions in a single run. Considering that GA and PSO are different in terms of optimization mechanism, information sharing scheme, and capabilities in explorative search and the exploitative search, and meanwhile, GA and PSO have achieved promising results by combining another algorithm,^10,15,19 it is meaningful to investigate the hybridization of GA and PSO to solve MOFJSP. In this context, considering the advantages and limitations of GA and PSO, this study aims to develop a novel hybrid GA with PSO to address MOFJSP, which hybridizes both algorithms to complement each other. External memory library stored with elite individuals is incorporated to improve the GA’s memory and learning capability for the elite individuals. Besides, based on the merits of the posteriori method, we adopt it to address MOFJSP in this study.

The contributions of this article are reflected in algorithm design. The novelties are stated as follows. First, because GA and PSO have their own advantages and disadvantages for MOFJSP, but they are also complementary. In this study, we combine GA with PSO to complement each other for solving MOFJSP; simultaneously, external memory library stored with elite individuals is also incorporated to improve the learning capability for GA. Second, to improve the crossover operation performance, GA is adapted by introducing a third parent to provide offspring, which has more opportunities to inherit good genes from parents. Third, the procedure of GA is redesigned by combining crossover and mutation operations to diversify population and retain good genes in population. In addition, a method is proposed to generate the initial population by considering the characteristics of MOFJSP. To our knowledge, this is the first time that the related algorithms and strategies have been used for MOFJSP.

The remainder of this article is organized as follows. We present the notations as well as the details of the mathematical formulation of MOFJSP in section “Problem statement and mathematical formulation.” The framework of the proposed approach is described in section “Teaching–learning-based hybrid genetic-particle swarm optimization algorithm for MOFJSP.” Section “Computational results” deals with a comparative study of the computational results. Finally, the last section discusses the conclusion and some directions for future research.

Problem statement and mathematical formulation

In FJSP environment, there are a set of independent jobs ${J_{1}, J_{2}, \dots, J_{n}}$ should be performed on a set of machines ${M_{1}, M_{2}, \dots, M_{m}}$ . Each job consists of one or more operations, and the jobs may follow different routes. An operation can be processed on more than one machine, and its processing time is machine dependent. The following assumptions outline the main structure of the problem in this article:

Jobs are independent of each other and are all available at the begin;

Jobs have equal priorities to begin processing;

Preemption is not allowed;

For each operation, there is a set of machines capable of performing it;

An operation is not allowed to process until its preceding operation is completed;

Each machine can perform at most one operation at any time.

This study aims to solve MOFJSP under all basic assumptions mentioned above. Terminologies and notations in this study are set up as below.

Sets and indices

m Total number of machines on the shop floor

M Set of machines

M_i ith machine (i = 1,…, m)

n Total number of jobs

J Set of jobs

J_j jth job (j = 1,…, n)

h_j Number of operations associated with the job J_j (j = 1,…, n)

O_jh hth operation associated with the job J_j (j = 1,…, n, and h = 1,…, h_j)

Ω_jh Subset of machines required for the operation O_jh

m_jh Number of machines required for the operation O_jh

Parameters

P_ijh Processing time of the operation O_jh by the machine M_i

S_jh Starting time of the operation O_jh (release time)

C_jh Completion time of the operation O_jh

d_j Due date of the job J_j

C_j Completion time of the job J_j

C_max Maximum completion time over all jobs(makespan)

H Large positive integer

T₀ Total number of all operations

Decision variables

$x_{ijh} = {1 \begin{matrix} = 1, if operation O_{jh} assigned to machine M_{i} \\ = 0, otherwise \end{matrix}$

$y_{ijhkl} = {\begin{matrix} = 1, if operation O_{jh} preceds O_{kl} on machine M_{i} \\ = 0, otherwise \end{matrix}$

Objective functions

The minimization of makespan (C_max), bottleneck machine workload (W_m), and total workload of machines (W_t) are the main objectives adopted by academic and industrial practice.^8,10,15,18 For the purpose of comparison with other methods, we also take them as criteria in this study. The expressions of objective functions are given by

C_{\max} = min (max_{1 ⩽ j ⩽ n} (C_{j}))

(1)

W_{m} = min (max_{1 ⩽ i ⩽ m} \sum_{j = 1}^{n} \sum_{h = 1}^{h_{j}} P_{ijh} x_{ijh})

(2)

W_{t} = min (\sum_{i = 1}^{m} \sum_{j = 1}^{n} \sum_{h = 1}^{h_{j}} P_{ijh} x_{ijh})

(3)

Constraints

The constraints of the mathematical model are defined as follows

c_{jh} - s_{jh} - \sum_{{i : O_{jh} \in Ω_{jh}}} (P_{ijh} x_{ijh}) = 0 \forall j, h = 1, \dots, h_{j}

(4)

\sum_{i = 1}^{m_{jh}} x_{ijh} = 1 j = 1, \dots, n; h = 1, \dots, h_{j}

(5)

c_{jh} ⩽ s_{j (h + 1)} j = 1, \dots, n; h = 1, \dots, h_{j} - 1

(6)

\begin{matrix} c_{jh} - c_{kl} + H y_{ijkhl} + H (1 - x_{ijh}) + H (1 - x_{ikl}) ⩾ P_{ijh} \\ \forall i, (j, h), (k, l) : O_{jh} \in Ω_{jh}, O_{kl} \in Ω_{kl} \end{matrix}

(7)

s_{jh} + x_{ijh} P_{ijh} ⩽ c_{jh} i = 1, \dots, m; j = 1, \dots, n; h = 1, \dots, h_{j}

(8)

c_{j h_{j}} ⩽ C_{\max} j = 1, \dots, n

(9)

s_{jh} ⩾ 0, c_{jh} ⩾ 0 j = 1, \dots, n; h = 1, \dots, h_{j}

(10)

Constraints (4) denote that the difference between completion time and starting time of operation O_jh on machine M_i equals to its processing time on machine M_i. It means that the operation must be completed without interruption once started, which guarantees assumption (3). Constraints (5) correspond to assumption (4), presenting the fact that an operation must be assigned to only one machine among the subset of alternative machines at a time. To guarantee assumption (5), constraints (6) and (7) handle respecting predefined sequence of operations associated with each job. Constraints (8) ensure assumption (6), that is, each machine can only perform at most one operation at a time. Constraints (9) describe that the completion time of each operation cannot be later than C_max. Constraints (10) define the domains of the decision variables.

Teaching–learning-based hybrid genetic-particle swarm optimization algorithm for MOFJSP

The structure of teaching–learning-based hybrid genetic-particle swarm optimization

GA is one of the algorithms used extensively to address MOFJSP. However, due to the problem of the slow convergence of GA, it cannot be directly applied to solve such a large-scale problem of MOFJSP. How to speed up the GA convergence while keeping its global search capability is a challenge. Many recent literatures adapted GA or/and incorporated other algorithms to speed up convergence.

GA and PSO are different from each other with respect to both the optimization mechanism and the information sharing scheme. In GA, the information is shared among chromosomes. Via the exploitation of the information shared among chromosomes and the operations of selection, crossover, and mutation on chromosomes, GA produces new generations of solutions. It means that GA can finely search solutions within the whole search space. However, GA lacks the adequate memory and learning capability for the elite individuals during the process of evolution, resulting in a relatively slow converging process. In addition, the performance of GA is easily affected by parameters and falls into a local optimum. In contrast with GA, PSO has memory and learning capability, and its information sharing scheme is one-way. In PSO, a particle obtains the information of the best particle in swarm and the best position in history of its own and updates its velocity and position only based on this information. As a result, PSO converges to satisfactory solutions at a high speed, but it also reduces the search accuracy. Therefore, PSO is suitable for coarse-grained searching in large-scale solution space. Overall, in solving MOFJSP, GA has strong global search capability but slow convergence while PSO has fast convergence but low accuracy convergence.

This study considers the combination of GA and PSO to address MOFJSP and proposes a novel approach, called teaching–learning-based hybrid genetic-particle swarm optimization (TL-HGAPSO). TL-HGAPSO consists of three modules, that is, GA module, bi-memory learning (BL) module, and PSO module. Figure 1 shows the structure of TL-HGAPSO and the relationship among the modules. GA is taken as the framework of TL-HGAPSO while PSO and an external memory library are incorporated in TL-HGAPSO. The purpose of introducing PSO is to improve the convergence speed of GA using the fast search capability of PSO, and on the other hand, to avoid GA falling into local optimum to some extent. In the meantime, the strong global search capability of GA is used to enhance the search accuracy of PSO in TL-HGAPSO. Through exchanging mutual information, GA module and PSO module improve the quality of their populations. In addition, since GA lacks the capability to learn from the elite individuals, in BL module, we implement an elitism strategy that stores elitist solutions in an external library and reintroduces them to GA population to improve learning capability of TL-HGAPSO. During the process of evolution, the individuals in GA module continuously learn from elitism individuals in BL module, and vice versa, inferior individuals in BL module are replaced with the elitism individuals in GA module simultaneously. In short, the purpose of TL-HGAPSO is to maintain the diversity within the population and to accelerate the process of convergence to optimal solutions.

Figure 1.

The structure of TL-HGAPSO.

GA module

We take the GA as the main framework of TL-HGAPSO. In GA module, to improve the performance of GA for MOFJSP, we modify the genetic operators and introduce an individual self-learning mode based on the adaptive crossover and mutation. The major elements of GA module are described as follows.

Coding and decoding

In the MOFJSP environment, operations should be assigned to machines before sequencing the operations on each machine. Therefore, the MOFJSP can be divided into two sub-problems: operations assignment and operations sorting.^{3,6,11,20,22,23} Specially, the former aims to allocate the machine for each operation, and the latter to sequence the operations on each machine. Accordingly, the coding scheme in TL-HGAPSO consists of two sections: machine allocation (i.e. assign operations to machines) and operations sorting. Tay and Wibowo²⁴ described four chromosome representations commonly used for coding GA-based solutions to the FJSP. Specially, the third chromosome representation, which is called “Simple Operation Order” by Tay et al., has been used in many research studies.^12,20,25 This article also uses this chromosome representation for coding solutions. The coding scheme used in this article is described as follows.

The length of two chromosomes are both equal to T₀. In the coding scheme of operation sorting, each gene represents an operation, and its value denotes the sequence of the job associated with this operation. The value of occurrence of job’s sequence indicates the operation of the job. For example, in Figure 2, “1 2 1 3 2 1 3 2 3” is the operation sorting code. The first occurrence of “3” denotes the first operation of J₃, that is, O₃₁, the second occurrence of “3” denotes O₃₂, and so on. Therefore, in this case, the sequence of the operation is O₁₁, O₂₁, O₁₂, O₃₁, O₂₂, O₁₃, O₃₂, O₂₃, O₃₃. In the coding scheme of machine allocation, gene’s position and value indicate a specific operation and the sequence of the machine on which the operation will be performed. For example, in Figure 2, the machine allocation code “1 3 5 3 2 3 1 4 3” indicates that assign O₁₁, O₁₂, O₁₃, O₂₁, O₂₂, O₂₃, O₃₁, O₃₂, and O₃₃ to machine M₁, M₃, M₅, M₃, M₂, M₃, M₁, M₄, and M₃, respectively. This coding scheme ensures that offspring generated from the crossover or mutation operation remain feasible and suitable for both P-FJSP and T-FJSP.

Figure 2.

Coding scheme in TL-HGAPSO.

Population initialization

Initial population is important for the exploration and exploitation of GA. Initializing the population randomly is a simple method and it is extensively used for FJSP. This method is suitable and reasonable for the problem without prior knowledge. However, it may generate many inferior chromosomes. Therefore, to make better convergence toward optimal solution, large number of iterations is usually used which takes more computational time. In the proposed TL-HGAPSO algorithm, a part of initial population is generated randomly while the other part of initial population is created based on the characteristics of MOFJSP to improve the quality of the initial population. Regarding MOFJSP in this study, it can be intuitively concluded that the closer the waiting time of the operations is, the more opportunities to obtain low workload and short makespan. Therefore, to produce the rest of population, we design a dispatch rule, called minimizing waiting time, which aims to equalize the waiting times of the operations (i.e. to minimizing the variance of the waiting time). The details are shown as follows:

Step 1: Create an array used to store jobs in random order (e.g. J₂J₃J₁).

Step 2: Assign the first operation (O₂₁, O₃₁, O₁₁) of each job in array (J₂J₃J₁) to machines (details of assignment see step 4). If the machine is idle, set the starting time of O_xl to zero. Otherwise, O_xl will be processed immediately once its precedent operation is completed.

Step 3: Select the machine M_s that will complete operation first, and the last operation O_jh on M_s. If more than one machine satisfies condition, one machine is randomly selected. Set t to the time when M_s is idle.

Step 4: For the subset of machines required for the operation O_j_(h + 1), that is, Ω_j ₍ _h + 1), calculate the waiting time of each $M_{k} \in Ω_{j (h + 1)}$ . If M_k is idle at time t, set waiting time to P_j_(h + 1)k. Otherwise, it indicates that M_k is processing an operation at time t, supposing it is O_zy. In this case, waiting time comprises three parts: the total processing time of all operations in the waiting queue of M_k, the remainder processing time of O_zy on M_k and P_j_(h + 1)k. Assign O_j_(h + 1) to the machine with shortest waiting time. If the selected machine is idle, it will perform O_j_(h + 1) immediately. Otherwise, put O_j_(h + 1) into the waiting queue of this machine.

Step 5: Go to step 3 until all operations have been assigned.

The randomized population helps maintain the diversity of population, while the population based on the characteristics of MOFJSP helps accelerate the process of convergence to optimal solutions. Therefore, the ratio of these two populations reflects the trade-off between population diversity and speed of convergence. In this study, when the ratio of these two populations is 1:1, better results can be achieved.

Crossover operation

The multi-parents precedence preserving order-based crossover (MPOX) is used to sequence operations. To improve crossover operation performance, we adapt GA algorithm by introducing a third parent to provide offspring more opportunities to inherit the good genes from parents. According to the fitness value of individuals, current population is partitioned into three sets, that is, Parent1, Parent2, and Parent3.

The detailed procedures of MPOX are given as follows:

Step 1: Put the individuals with fitness $f_{i} ⩾ 0.15 f$ into Parent1 and Parent2, the other better individuals into Parent3, where f_i denotes the fitness value of individual i, and f denotes the mean fitness value of all individuals.

Step 2: Partition the job set J ${J_{1}, J_{2}, \dots, J_{n}}$ into two non-empty subsets G1 and G2 randomly.

Step 3: Replicate the genes both belong to Parent1 and G2 into Children1, and the genes both belong to Parent2 and G1 into Children2; meanwhile, keep the position and sequence of genes unchanged.

Step 4: Replicate the genes both belong to Partent3 and G1 into Children1, and the genes both belongs to Parent3 and G2 into Children2; meanwhile, keep the sequence of genes unchanged.

An example of MPOX is shown in Figure 3.

Figure 3.

MPOX crossover operation.

The multiple point preservation crossover (MPX) is leveraged to assign operations to machines. The detailed procedures of MPX are as follows:

Step 1: Create an array of size T₀, named rand0_1, and initialize it with random binary numbers.

Step 2: From Parent1, replicate all genes with the same position as “1” in rand0_1 into Children2 and keep their position unchanged, and, in the same way, from Parent2, replicate the genes into Children1.

Step 3: Replicate the rest genes of Parent1 and Parent2 into Children1 and Children2, respectively.

An example of MPX is shown in Figure 4.

Figure 4.

MPX crossover operation.

Mutation operation

Mutation operation aims to maintain the diversity of the population. GA conducts the crossover operation and mutation operation in sequence. In this paper, the procedure of mutation operation is incorporated with crossover operation to increase its efficiency.

It will help diversify population when an individual with a higher degree of similarity to other individuals has more opportunities to conduct mutation operation. Therefore, in our TL-HGAPSO, if an individual has a high similarity value, mutation will be conducted before crossover; otherwise, mutation operation will be skipped. A similarity threshold is used to decide whether an individual needs to mutate or not. The procedures are as follows:

Step 1: Partition the population into three subsets: Parent1, Parent2, and Parent3 (refer to procedures of MPOX).

Step 2: Calculate Hamming similarity and threshold according to formulas (11) and (12)²⁶

h_{ij} = \frac{H_{ij}}{2 T_{0}}

(11)

S_{ij} = \frac{1}{\sqrt{\sum_{k = 1}^{2 T_{0}} {[Ch m_{i} (k) - Ch m_{j} (k)]}^{2}} + 1}

(12)

where H_ij is the Hamming distance between individual i and individual j, Chm_i(k) and Chm_j(k) represent the kth gene on chromosome i and chromosome j, respectively; h₁₃ and h₂₃ denote Hamming similarity of Parent3 with Parent1 and Parent2, respectively; s₁₃ and s₂₃ denote the corresponding similarity threshold. If h₁₃ > s₁₃ and h₂₃ > s₂₃, conduct crossover operation; otherwise, conduct mutation and crossover in sequence.

Step 3: Keep Parent3 into the offspring generation.

Meanwhile, the variation in the best fitness value of successive generations is used to measure the degree of population evolution. If the best fitness value has not been improved after several generations, it indicates that the population is evolving too slowly and needs to increase the mutation probability. In TL-HGAPSO, a convergence threshold is set to control the mutation probability. The procedures are as follows:

Step 1: Suppose the fitness value of the best individual in the initial population is f₁, the next generation is f₂, and so on; the nth generation’s best fitness is f_n;

Step 2: When f₁ = f₂, set convergence threshold Φ = 1; When f₁ = f₂ = f₃, set Φ = 2; When f₁ = f₂ = f₃ = …= f_n, set Φ = n –1; otherwise set Φ = 0;

Step 3: Update the mutation probability according to the convergence threshold

P_{m} = P_{0} + \frac{Φ}{100}

(13)

where P₀ denotes the initial mutation probability.

In addition, in TL-HGAPSO, we leverage the Pareto-based fitness assignment based on the fast and elitist non-dominated sorting in NSGA-II algorithm to calculate fitness assignment²⁷ and use the tournament selection as the selection operator.

BL module

The schemata theory implies that giving high priority of replication to the individuals with good genes is conducive to producing better offspring.¹⁹ Therefore, in BL module, two external memory libraries, that is, chromosome library and operation library, stored with good genes are introduced to direct the search into the promising areas.

The chromosome library stores the individuals with good genes to improve the offspring’s capability in learning good characteristics from parents. Thek-nearest neighbor (K-NN) classification algorithm is used to dynamically learn the elite schema in the chromosome library. More specifically, by comparing the best n individuals in the current population to the chromosome library, the most similar k individuals in the chromosome library are selected to replace the worst k individuals in current population.

Operation library is specially designed for MOFJSP. It is an integer array of size d, where d represents total number of operations, and each element is used to record the machine with shortest processing time for the corresponding operation. Note that if there exist two or more machines that have identical least processing time for an operation, one machine is selected by random. An example is presented here to illustrate operation library explicitly. Suppose that Table 1 gives processing time of the operations of a 3*5 FJSP. Figure 5 shows its operation library. As shown in Table 1, the processing time of O₁₁ on M₁, M₂, M₃, and M₄ is 2, 3, 4, and 3, respectively, and the least one is 2, which takes place on M₁. The sequence number of M₁ is “1,” that is, the first left element in operation library in Figure 5, which means that assigning O₁₁ to M₁ might provide more opportunities to obtain the optimum or an approximate optimum.

Table 1.

Processing time of 3*5 FJSP.

Job	Operation	Processing time for M_i
Job	Operation	M ₁	M ₂	M ₃	M ₄	M ₅
J ₁	O ₁₁	2	3	4	3	–
	O ₁₂	–	5	6	4	4
	O ₁₃	–	5	3	–	3
J ₂	O ₂₁	3	–	5	4	6
	O ₂₂	–	3	2	9	–
	O ₂₃	7	–	4	2	3
J ₃	O ₃₁	3	4	5	7	6
	O ₃₂	–	–	3	6	–
	O ₃₃	–	7	5	–	4

FJSP: flexible job-shop scheduling problem.

Figure 5.

An instance of operation library.

In addition, considering computation resources, we do not update the external library at each generation, but at every several generations using an elite selection strategy.

PSO module

The PSO has been introduced as an optimization technique in real-number spaces.¹⁵ However, MOFJSP under studied in this article is set in a discrete space. For taking advantages of PSO to solve MOFJSP, it is necessary to adapt the original PSO. Thus, we re-define the position updating equation of PSO for MOFJSP as formula (14)

X_{i}^{t + 1} = c_{2} \otimes f_{4} (c_{1} \otimes f_{3} (c_{1} \otimes f_{2} (w \otimes f_{1} (X_{i}^{t}), {pbest}_{i}^{t}), {pbest}_{i}^{t}), {gbest}_{i}^{t})

(14)

where X^t_i denotes particle position at the tth generation, w represents inertia weight, c₁ and c₂ are respectively self-awareness coefficient and society-awareness coefficient, pbest^t_i and gbest^t_i respectively indicate the best position of particle i at the tth generation and the best position of the particle in swarm at the tth generation. Note that $w, c_{1}, c_{2} \in [0, 1]$ are random numbers, generated uniformly in the range [0,1]. To state formula (14) explicitly, we decompose it into four formulas, that is, formulas (15)–(18)

A = w \otimes f_{1} (X_{i}^{t}) = {\begin{matrix} f_{1} (X_{i}^{t}), & r < w \\ X_{i}^{t}, & else \end{matrix}

(15)

where $f_{1} (X_{i}^{t})$ denotes the mutation operation and $r \in (0, 1)$ is a uniform random number. Formula (15) indicates that position of particle is affected by its historical state, and the mutation operation may have certain probability of conducting on it. Here, we use the mutation operation to implement the random search, which is helpful for particles to skip the local optima and diversify the population. In this article, the procedures of the mutation operation are as follows: in the section of operation sorting, an operation is selected randomly to be inserted into a random position; in the section of machine allocation, from the machine set $Ω_{jh}$ , one machine is selected by random for operation $O_{jh}$ to replace the original machine. An example is shown in Figure 6

B = c_{1} \otimes f_{2} (A, {pbest}_{i}^{t}) = {\begin{matrix} f_{2} (A, {pbest}_{i}^{t}), & r < c_{1} \\ A, & else \end{matrix}

(16)

C = c_{1} \otimes f_{3} (B, {pbest}_{i}^{t}) = {\begin{matrix} f_{3} (B, {pbest}_{i}^{t}), \begin{matrix} r < c_{1} \end{matrix} \\ B, & else \end{matrix}

(17)

where $f_{2} (A, {pbest}_{i}^{t})$ represents the POX crossover operation, and $f_{3} (B, {pbest}_{i}^{t})$ denotes the MPX crossover operation. Formulas (16) and (17) describe that particles adjust their positions twice according to their own optimal positions, which mean that particles can acquire knowledge from themselves

D = c_{2} \otimes f_{4} (C, {gbest}_{i}^{t}) = {\begin{matrix} f_{4} (C, {gbest}_{i}^{t}), & r < c_{2} \\ C, & else \end{matrix}

(18)

where $f_{4} (C, {gbest}_{i}^{t})$ denotes the MPX crossover operation. Formula (18) describes that particles adjust their position according to the best one particle in swarm, which means that particles can acquire knowledge from society.

Figure 6.

An instance of the operation of $f_{1} (X_{i}^{t})$ .

To summarize, in TL-HGAPSO, we adapt the particle position updating formula for MOFJSP. Crossover operation is used to exchange information between particles and historical experiences of their own as well as of the swarm. Mutation operation, a random search strategy of particles in this article, is used to improve the local search capability of particles. Here, self-awareness coefficient $c_{1}$ and society-awareness coefficient $c_{2}$ can be treated as crossover rate, and inertia weight w as the mutation rate. According to formula (14), the computational complexity of PSO is $O (3 n) + O (5 n) \approx O (8 n)$ .

TL-HGAPSO algorithm procedures

The flowchart illustrated in Figure 7 shows the main procedures of TL-HGAPSO, and main procedures are described as follows:

Step 1: Set parameters and initialize population R_t(t = 0) (referring to section “Population initialization”).

Step 2: Decode individuals of population R_t and calculate their fitness values; sort individuals according to NSGA-II; get Pareto solution set P_t_+ 1.

Step 3: If termination criterion is satisfied, that is, t = Gen, stop algorithm and output the results.

Step 4: If t < Gen, hybridize GA with PSO to generate the next generation R_t_+ 1. The detailed steps are as follows.

Step 4.1: Partition Pareto solution set P_t_+ 1 into GA subpopulation and PSO subpopulation.

Step 4.2: Search in GA subpopulation.

Step 4.2.1: If t = 0, use population P_t_+ 1 to initialize two external libraries in BL module.

Step 4.2.2: Conduct best individual selection and tournament selection operations.

Step 4.2.3: Update current GA subpopulation according to chromosome library (referring to section “BL module”)

Step 4.2.4: Partition GA subpopulation into three subpopulations: Parent1, Parent2, and Parent3 (referring to section “Crossover operation”); calculate Hamming distance and similarity threshold according to formulas (11) and (12), respectively.

Step 4.2.5: Calculate mutation according to formula (13) and conduct mutation operation (referring to section “Mutation operation”).

Step 4.2.6: Conduct MPOX and MPX crossover operation.

Step 4.2.7: Calculate fitness value of individuals; update the external libraries every q generations.

Step 4.3: Search in PSO subpopulation.

Step 4.3.1: Update the position of the particle according to formulas (14)–(18).

Step 4.3.2: Calculate the fitness value of the particle.

Step 4.3.3: Update pbest and gbest (referring to section “PSO module”).

Step 4.4: By exchanging information between GA subpopulation and PSO subpopulation, use the best individual in GA subpopulation to replace the worst individuals in PSO subpopulation, and vice versa; merge GA subpopulation and PSO subpopulation to get population Q_t_+ 1.

Step 4.5: Merge P_t₊₁ and Q_t₊₁ to get population R_t₊₁.

Step 5: Set t = t + 1, go to Step 2.

Figure 7.

Flow chart of TL-HGAPSO algorithm.

Computational results

TL-HGAPSO is programmed by MATLAB and running on a PC with 3.3G CPU and 8G RAM. We select three representative instances proposed by Kacem et al.^14,17 and 10 datasets designed by Brandimarte.¹³ Each instance runs 20 times. Because Kacem et al.,^14,17 Xia and Wu,¹⁵ and Xing et al.²⁸ provided relatively complete experiment results on the above representative instances in their studies, to illustrate the efficiency of our algorithm, we compare our results with theirs. Their algorithms are called Approach by Localization (AL), classic GA (CGA), PSO + SA and Search Method (SM) for short in this study, respectively.

The parameters are as follows: set the population size = 200, the maximum generation Gen = 200, the crossover rate $P_{c} = 0.7$ , the initial mutation rate $P_{0} = 0.1$ , the size of chromosome library h = 5, the inertia weights $w = 0.1$ , the self-awareness coefficient $c_{1} = 1.9$ , the society-awareness coefficient $c_{2} = 1.1$ , and the random numbers $r_{1}, r_{2} \in (0, 1)$ . The external memory library in BL module is updated every five generations.

Kacem’s instances

Table 2 shows the comparison of experiment results on Kacem’s instances.

Table 2.

Comparison of experiment results on Kacem’s instances.

Instance	Obj	AL + CGA		PSO + SA		SM				TL-HGAPSO
Instance	Obj	(1)	(2)	(1)	(2)	(1)	(2)	(3)	(4)	(1)	(2)	(3)
8*8P-FJSP	C_max	15	16	15	16	15	16	16	14	14	15	16
	W_M	N/A	N/A	12	13	12	11	13	12	12	12	13
	W_T	79	75	75	73	75	77	73	77	77	75	73
	Computational time(s)	N/A		N/A		73.148				10.37
10*10T-FJSP	C_max	7		7		8	7	8		7	8
	W_M	5		6		5	6	7		6	7
	W_T	45		44		42	42	41		42	41
	Computational time(s)	N/A		N/A		55.18				17.92
15*10T-FJSP	C_max	24		12		11				12
	W_M	11		11		11				11
	W_T	91		91		91				91
	Computational time(s)	N/A		N/A		195				98.6

FJSP: flexible job-shop scheduling problem; PSO: particle swarm optimization; SA: simulated annealing; TL-HGAPSO: teaching–learning-based hybrid genetic-particle swarm optimization; AL: Approach by Localization; CGA: classic GA; SM: Search Method.

Problem 8*8

In 8*8P-FJSP, there are eight jobs with 27 operations performed on eight machines. The obtained non-dominated solutions by the proposed algorithm are characterized by the following values:

Solution 1: C_max = 14; W_M = 12; W_T = 77.

Solution 2: C_max = 15; W_M = 12; W_T = 75.

Solution 3: C_max = 16; W_M = 13; W_T = 73.

Compared with AL + CGA, the proposed algorithm in this study finds better solutions in terms of C_max and W_T and provides the value of W_M. Compared with PSO + SA, in addition to two sets of solutions obtained by PSO + SA, the proposed algorithm also finds another set of non-dominated solutions. Compared with SM, although the proposed algorithm cannot find a set of solutions obtained by SM, it takes shorter computational time than SM. Figure 8 shows the Gantt chart and convergence curve of the makespan (C_max) of the first set of solutions obtained by the proposed algorithm. As shown in Figure 8, the value of makespan reduces dramatically at about 10th generation and the optimum of C_max is found, and the solution remains stable during the process of evolution. In other words, the convergence speed of TL-HGAPSO is very fast.

Figure 8.

The Gantt chart and the convergence curve of C_max of 8*8 problem (C_max = 14, W_M = 12, W_T = 77).

Problem 10*10

In 10*10T-FJSP, there are 10 jobs with 30 operations performed on 10 machines. The obtained non-dominated solutions by the proposed algorithm are characterized by the following values:

Solution 1: C_max = 7; W_M = 6; W_T = 42.

Solution 2: C_max = 8; W_M = 7; W_T = 41.

Compared with AL + CGA, the proposed algorithm reduces one objective W_T (42 instead of 45), increases one objective W_M (6 instead of 5) under the same value of C_max (7), it also finds another non-dominated solution set. Compared with PSO + SA, the proposed algorithm reduces W_T (42 instead of 44) under the same value of C_max(7) and W_M(6) and also obtains another set of non-dominated solutions. Compared with SM, the proposed algorithm cannot find a set of solutions obtained by SM, but it only takes about 1/3 computational time (17.92 instead of 55.18). Figure 9 shows the Gantt chart and convergence curve of the makespan of the first solution set achieved by the proposed algorithm. As shown in Figure 9, the value of makespan reduces dramatically at about fifth generation and the optimum of C_max is found, and the solution remains stable during the process of evolution. In addition, N Shahsavari-Pour and B Ghasemishabankareh⁸ evaluated their algorithm, called novel hybrid genetic algorithm and simulated annealing (NHGASA), on 10*10T-FJSP. Compared with NHGASA method, the proposed algorithm is also slightly faster than NHGASA (17.92 instead of 18.44). It means that the convergence speed of TL-HGAPSO is very fast.

Figure 9.

The Gantt chart and the convergence curve of C_max of 10*10 problem (C_max = 7, W_M = 6, W_T = 42).

Problem 15*10

In 15*10T-FJSP, there are 10 jobs with 56 operations performed on 15 machines. The obtained non-dominated solutions by the proposed algorithm are characterized by the following values

Solution 1: C_max = 12; W_M = 11; W_T = 91.

It is worth mentioning that there are two different schedules can get this set of solutions. Figure 10 shows these two schedules in the form of Gantt chart. Compared with AL + CGA, the proposed algorithm dramatically reduces C_max(12 instead of 24) under the same value of W_M(11) and W_T(91) and finds the same solutions as PSO + SA. Compared with SM method, the proposed algorithm cannot obtain the same solutions as SM, and its C_max is even worse than that of SM (12 instead of 11), but it only takes about one half of computational time (98.6 instead of 194.98). Figure 11 shows the convergence curve of the makespan (C_max) of the proposed algorithm. As shown in Figure 11, the value of makespan reduces dramatically at about fifth generation and the optimum of C_max is found, and the solution remains stable during the process of evolution. It means that the convergence speed of TL-HGAPSO is very fast.

Figure 10.

The Gantt chars of two different schedules of the solution (C_max = 12, W_M = 11, W_T = 91) on 15*10 problem.

Figure 11.

Convergence curve of C_max of 15*10 problem (C_max = 12, W_M = 11, W_T = 91).

Brandimarte dataset

We compare the proposed algorithm with SM on Mk01 to Mk10 instances in Brandimarte dataset. The comparison of experiment results is shown in Table 3. In all the 10 instances except Mk08, the proposed algorithm finds at least one Pareto solution that can dominate the solution obtained by SM. In Mk08 instance, the proposed algorithm finds the same solution as SM, and another three sets of non-dominated solutions. In addition, the computational time of the proposed algorithm is significantly less than that of SM.

Table 3.

Comparison of experiment results on Mk01 to Mk10.

Instance	Obj	SM	Time (min)	TL-HGAPSO						Time (min)
Instance	Obj	(1)	Time (min)	(1)	(2)	(3)	(4)	(5)	(6)	Time (min)
Mk01	C_max	42	4.78	40	42	42	43			1.78
	W_M	42		40	42	41	40
	W_T	162		162	162	158	156
Mk02	C_max	28	3.02	27	28	29	29	30		2.12
	W_M	28		27	27	27	29	30
	W_T	155		148	151	146	143	141
Mk03	C_max	204	26.14	204	204	212	213	214	220	4.75
	W_M	204		199	199	199	202	210	204
	W_T	852		850	855	850	853	849	847
Mk04	C_max	68	17.74	67	69	72	73	74	74	4.08
	W_M	67		67	68	55	54	54	55
	W_T	352		346	345	350	349	350	348
Mk05	C_max	177	8.26	175	177	179	181			4.34
	W_M	177		175	177	179	181
	W_T	702		682	697	679	677
Mk06	C_max	75	18.79	68	72	73	76	76	78	3.62
	W_M	67		66	60	60	74	60	62
	W_T	431		421	378	375	356	362	361
Mk07	C_max	150	5.68	144	148	151	154	157		5.06
	W_M	150		144	148	151	154	157
	W_T	717		673	670	669	663	662
Mk08	C_max	523	67.67	523	524	526	528			31.54
	W_M	532		532	524	524	524
	W_T	2524		2524	2519	2521	2507
Mk09	C_max	311	77.76	310	311	311	314			27.87
	W_M	299		299	299	303	299
	W_T	2374		2369	2295	2291	2283
Mk10	C_max	227	122.52	224	232	239	243	245	252	37.65
	W_M	221		220	216	217	223	205	227
	W_T	1989		1978	1919	1879	1923	1896	1902
Mk10	C_max	227	122.52	268	275	276	280
	W_M	221		164	255	256	269
	W_T	1989		1858	1866	1857	1862

TL-HGAPSO: teaching–learning-based hybrid genetic-particle swarm optimization; SM: Search Method.

To sum up, it can be concluded that the proposed algorithm generally outperforms the other approaches in most of the 13 instances with respect to the quality of solutions and the computational time. Regarding the quality of solutions, the proposed algorithm gets no worse solution than other algorithms, and in some instances, its solution is much better than that of other algorithms. For the computational time, the proposed algorithm shows advantage over other algorithms. The experiment results verify the efficiency of the proposed algorithm for solving MOFJSP.

Conclusion and future research directions

Since GA lacks adequate memory and learning capability for the elite individual, it converges at a relatively slow speed. PSO can effectively solve this deficiency of GA. We develop a novel hybrid GA approach with PSO to solve MOFJSP, which combines both algorithms to complement each other. In addition, we introduce external memory library to improve the learning capability of GA. Numerical experiments show that the proposed method is superior to other methods in terms of both solution quality and computational time in most of instances.

In this article, we consider three objectives FJSP, and our future research can be directed to extend the proposed approach by considering many objectives (more than three objectives). In addition, the model established in this article does not take uncertain factors into account. However, the uncertain events such as rush orders, machine failures, and raw material shortages usually exist in the realistic production environment. Therefore, a real-time scheduling problem is the topic of our ongoing research. Although the coding scheme used in this study can ensure that a chromosome (genotype) produced by the crossover and mutation operation on parent chromosomes will be a feasible solution, it may lead to different chromosomes corresponding to an identical solution. Therefore, it also would be interesting to study coding schemes.

Footnotes

Handling Editor: Xichun Luo

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This project is supported by National Science Foundation of China (no. 71620107002, 71601050) and Social Science Foundation of Fujian Province, China (no. FJ2016C049).

ORCID iD

Xiabao Huang

References

Yuan

Multiobjective flexible job shop scheduling using memetic algorithms. IEEE T Autom Sci Eng 2015; 12: 336–353.

Tay

NB.

Evolving dispatching rules using genetic programming for solving multi-objective flexible job-shop problems. Comput Ind Eng 2008; 54: 453–473.

El Khoukhi

Boukachour

El Hilali Alaoui

. The “Dual-Ants Colony”: a novel hybrid approach for the flexible job shop scheduling problem with preventive maintenance. Comput Ind Eng 2017; 106: 236–255.

Jain

Meeran

Deterministic job-shop scheduling: past, present and future. Eur J Oper Res 1999; 113: 390–434.

Jamili

Robust job shop scheduling problem: mathematical models, exact and heuristic algorithms. Expert Syst Appl 2016; 55: 341–350.

Gao

An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem. Int J Prod Econ 2016; 174: 93–110.

Garey

Johnson

Sethi

The complexity of flowshop and jobshop scheduling. Math Oper Res 1976; 1: 117–129.

Shahsavari-Pour

Ghasemishabankareh

A novel hybrid meta-heuristic algorithm for solving multi objective flexible job shop scheduling. J Manuf Syst 2013; 32: 771–780.

Sobeyko

Mönch

Heuristic approaches for scheduling jobs in large-scale flexible job shops. Comput Oper Res 2016; 68: 97–109.

10.

Tay

JC.

Solving multiple-objective flexible job shop problems by evolution and local search. IEEE T Syst Man Cy C 2008; 38: 674–685.

11.

Ishikawa

Kubota

Horio

Effective hierarchical optimization by a hierarchical multi-space competitive genetic algorithm for the flexible job-shop scheduling problem. Expert Syst Appl 2015; 42: 9434–9440.

12.

Gao

et al . An effective multi-objective discrete virus optimization algorithm for flexible job-shop scheduling problem with controllable processing times. Comput Ind Eng 2017; 104: 156–174.

13.

Brandimarte

Routing and scheduling in a flexible job shop by tabu search. Ann Oper Res 1993; 41: 157–183.

14.

Kacem

Hammadi

Borne

Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems. IEEE T Syst Man Cy C 2002; 32: 1–13.

15.

Xia

An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems. Comput Ind Eng 2005; 48: 409–425.

16.

Gao

Gen

Sun

et al . A hybrid of genetic algorithm and bottleneck shifting for multiobjective flexible job shop scheduling problems. Comput Ind Eng 2007; 53: 149–162.

17.

Kacem

Hammadi

Borne

Pareto-optimality approach for flexible job-shop scheduling problems: hybridization of evolutionary algorithms and fuzzy logic. Math Comput Simulat 2002; 60: 245–276.

18.

Pan

Gao

KZ.

Pareto-based discrete artificial bee colony algorithm for multi-objective flexible job shop scheduling problems. Int J Adv Manuf Technol 2011; 55: 1159–1169.

19.

Tay

Lai

MK.

An effective architecture for learning and evolving flexible job-shop schedules. Eur J Oper Res 2007; 179: 316–333.

20.

Wang

Gao

Zhang

et al . A multi-objective genetic algorithm based on immune and entropy principle for flexible job-shop scheduling problem. Int J Adv Manuf Technol 2010; 51: 757–767.

21.

Wang

Zhou

et al . An enhanced Pareto-based artificial bee colony algorithm for the multi-objective flexible job-shop scheduling. Int J Adv Manuf Technol 2012; 60: 1111–1123.

22.

Teekeng

Thammano

Modified genetic algorithm for flexible job-shop scheduling problems. Procedia Comput Sci 2012; 12: 122–128.

23.

Kundakcı

Kulak

Hybrid genetic algorithms for minimizing makespan in dynamic job shop scheduling problem. Comput Ind Eng 2016; 96: 31–51.

24.

Tay

Wibowo

. An effective chromosome representation for evolving flexible job shop schedules. In: Proceedings of Genetic and Evolutionary Computation Conference, Seattle, WA, 26–30 June 2004, pp. 210–221. Berlin, Heidelberg: Springer. https://www.springer.com/gp/book/9783540223436

25.

Zhang

Shao

et al . An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem. Comput Ind Eng 2009; 56: 1309–1318.

26.

Ming

Jia

Genetic algorithm controlled by two thresholds for Job Shop scheduling problem. Comput Integr Manuf 2007; 13: 329–332.

27.

Deb

Agrawal

Pratap

et al . A Fast Elitist Non-dominated Sorting Genetic Algorithm for Multi-objective Optimization: NSGA-II. In: Schoenauer

et al . (eds) Parallel Problem Solving from Nature PPSN VI. PPSN 2000. Lecture Notes in Computer Science, vol 1917 Paris, France, 18-20 September 2000, Berlin, Heidelberg: Springer.

28.

Xing

Chen

Yang

. An efficient search method for multi-objective flexible job shop scheduling problems. J Intell Manuf 2009; 20: 283–293.