Sage Journals: Discover world-class research

Abstract

In the practical production, the transportation of jobs is existed between different machines. These transportation operations directly affect the production cycle and the production efficiency. In this study, an improved memetic algorithm is proposed to solve the flexible job shop scheduling problem with transportation times, and the optimization objective is minimizing the makespan. In the improved memetic algorithm, an effective simulated annealing algorithm is adopted in the local search process, which combines the elite library and mutation operation. All the feasible solutions are divided into general solutions and local optimal solutions according to the elite library. The general solutions are executed by the simulated annealing algorithm to improve the quality, and the local optimal solutions are executed by the mutation operation to increase the diversity of the solution set. Comparison experiments with the improved genetic algorithm show that the improved memetic algorithm has better search performance and stability.

Keywords

Flexible job shop scheduling problem transportation times memetic algorithm simulated annealing algorithm

Introduction

The flexible job shop scheduling problem (FJSP) is an extension of the classic job shop scheduling problem (JSP), which is more in line with the characteristics of discrete manufacture environment. With the development of customization and product quality, the production process will be more flexible. The control of various time factors also needs to be more accurate. In actual production environments, the time factors include not only the processing time, but also the transportation time. These time factors affect the completion time and make the problem more complicated. If this part of the time is not taken into account, it may occur that the processing time is short but the transportation time is long during implementation, resulting in reduced scheduling efficiency. Therefore, a flexible job shop scheduling problem with transportation times (TT-FJSP) is studied in this paper.

The FJSP was first addressed by Brucker and Schile, they solved the problem by polynomial graphics algorithm.¹ Nevertheless, many experiments show that the exact algorithm is not very effective even in solving moderate-size FJSP instances.² Currently, the general method for solving the FJSP is to first establish a optimization model and then solve it by the intelligent optimization algorithm. The mixed integer model is one of the common used optimization model. Fattahi and colleagues^3,4 established a mixed integer linear programming model with location attributes for the FJSP with two or more jobs and the FJSP with some constraints between the operations. Nowadays, manufacturing has become refined and relies on intelligent solutions. Scheduling problem exists widely in actual production and manufacturing, and many solving methods are applicable to actual production to provide efficient and feasible solutions for production. With the development of problems, relevant optimization models and theories emerge in endlessly,⁵ and the value of practical application research is growing gradually.^6–8 The transportation time is an important factor of the actual schedule, which affects the final scheduling results. Naderi et al. studied the displacement flow workshop that takes into account the transportation time of semi-finished products, and they established different mixed integer programming models for multi-transporter and single-transporter shops.⁹ For the manufacturing system with resource flexibility, sequence-dependent setup, and transportation times, Rossi proposed a swarm intelligence approach to schedule.¹⁰ Karimi et al.¹¹ proposed an imperialist competitive algorithm to solve the TT-FJSP. Zhang and colleagues^12,13 successively used improved genetic algorithms (GA) solved the TT-FJSP and multi-objective FJSP with multiple time constraints.

According to the search scope, the intelligent optimization algorithms are mainly divided into two categories: global search and local search. The former has a large search range, such as GA,^14–16 particle swarm optimization algorithm,¹⁷ ant colony optimization algorithm,¹⁸ and artificial bee colony algorithm.¹⁹ The local search algorithm is the neighborhood search algorithm for solutions, such as the simulated annealing algorithm (SA)²⁰ and tabu search.²¹ Nonetheless, some experimental studies showed that the hybrid algorithms have better results.^22,23 The memetic algorithm (MA) is proposed by Moscato²⁴ to simulate the evolution of human culture. It is essentially a combination of the global population search and local search. Generally, the MA is similar to the GA, but the mutation part is replaced by a local search. Some scholars use the MA to solve the FJSP. Phu-ang and Thammano²⁵ presented a honeybee marriage-based MA to avoid falling into local optimal solutions. Gong et al.²⁶ used an MA for solving the multi-objective FJSP with worker flexibility.

In this paper, an improved memetic algorithm (IMA) is presented for solving the TT-FJSP. In the IMA, an effective SA with the elite library and mutation operation is adopted to form the local search method with parallel structure. To avoid repetitive searches and improve efficiency, the elite library is adopted to maintain outstanding solutions. Feasible solutions, according to the mutation probability, are divided into general solutions and local optimal solutions. General solutions are executed by the SA, and local optimal solutions are executed by the mutation operation. The proposed algorithm is evaluated and compared with the improved genetic algorithm (IGA),¹² and the comparison shows that the IMA is effective for the TT-FJSP.

The rest of this paper is organized as follows. The problem description and model are given in “Problem formulation” section. “The improved memetic algorithm” section formulates the IMA, and the experimental study results are given in “Experimental results and comparisons” section. The conclusions and some ideas for the future research are summarized in the final section.

Problem formulation

The FJSP can be described as follows: There are some jobs and machines. Every job has its own operation set, and the operations are processed under their process constraints. Each operation can be processed by multiple machines, and the processing time on different machines is different. The FJSP is generally divided into the fully flexible FJSP and partially flexible FJSP.²⁷ In the fully flexible FJSP, each operation can be processed on all machines. In the partially flexible FJSP, each operation can be processed on specific optional machines. A partially flexible FJSP instance is shown in Table 1.

Table 1.

An instance of the partially flexible FJSP.

Job	Operation	Processing time
		M ₁	M ₂	M ₃	M ₄	M ₅
J ₁	O _1,1		6	4	3	5
	O _1,2		5		4
J ₂	O _2,1	3		6		5
	O _2,2	4	6	5
	O _2,3		7		5	8

FJSP: flexible job shop scheduling problem.

The TT-FJSP has one more transportation times constraint: When one operation is completed, the finish time is not equal to the start time of the next operation, but it needs to determine whether the job needs to be transferred to another machine. If necessary, the transportation time of the job between the two machines should be considered, otherwise the transportation time is 0. The objective is the minimization of the makespan when the processing times and transportation times are considered simultaneously. In the TT-FJSP, several constraints and assumptions are made:

Jobs and machines are independent and available at time 0.

Job preemption is not allowed, and each machine can handle only 1 job at a time.

The operations belonging to the same job cannot be processed simultaneously.

Processing time of each operation corresponds to its processing machine, and all processing times are given.

Once the operation is completed, the job is transported to the machine of the next operation immediately, and the corresponding transportation time is spent.

Transportation time is related only to the selected processing machine and direction, and all transportation times are given.

Transportation resources are sufficient, which do not affect the transportation process.

Setup times are included in the processing times.

The mathematical model and related variables are defined as follows: job set J ={J₁, J₂, J₃, ..., J_i, ..., J_n} and J_i is the i-th job (i = 1, 2, 3, ..., n). Machine set M ={M₁, M₂, M₃, ..., M_k, ..., M_m}, M_k denotes the k-th machine (k = 1, 2, 3, ..., m). O_i,_h is the h-th operation of J_i (h = 1, 2, 3, ..., g_i) and O_i,_(h-1) represents the previous operation of O_i,_h, O_i’,_h’ is the operation that is processed just before O_i,_j on the same machine, and O_i*,_h* is the next operation of O_i,_h on the same machine. T_i,_h,k is the processing time required for operation O_i,_h on M_k. S_i,_h,k is the start time of O_i,_h on M_k. F_i,_h,k is the finish time of O_i,_h on M_k. MT_i,_j,k is the transportation time of J_i from M_j to M_k. C_i is the completion time of J_i, C_max is the makespan of all jobs. The objective of the TT-FJSP and its constraints are as follows:

$min C_{max}$ (1)

s.t.

$\begin{matrix} S_{i, h, k} = max (F_{i', h', k,} F_{i, (h - 1), j} + M T_{i, j, k}), \\ i = 1, \dots, n, h = 2, \dots, g_{i}, j, k = 1, \dots, m \end{matrix}$ (2)

$C_{max} \geq C_{i}, i = 1, \dots, n$ (3)

$C_{i} \geq F_{i, h, k}, i = 1, \dots, n, h = 1, \dots, g_{i}, k = 1, \dots, m$ (4)

$\begin{matrix} F_{i, h, k} = S_{i, h, k} + T_{i, h, k}, i = 1, \dots, n, \\ h = 1, \dots, g_{i}, k = 1, \dots, m \end{matrix}$ (5)

$S_{i, h, k} \geq 0, i = 1, \dots, n, h = 1, \dots, g_{i}, k = 1, \dots, m$ (6)

The objective is to minimize the makespan C_max. Equation (2) represents the processing sequence constraint of operations. Equation (3) expresses that the makespan is not less than the completion time of each job. Similarly, equation (4) means that the completion time of J_i is not less than the finish time of O_i,_h on M_k. Equation (5) indicates that the finish time equals the sum of the start time and processing time of the operation. Equation (6) denotes that the processing of jobs processing starts at time 0. For example, we used the data in Table 1 in our tests. The transportation times are given in Table 2, which shows the time taken to transport from the left corresponding machine to the next corresponding machine. The test result with transportation times is shown in Figure 1(a), and the test result without transportation times is shown in Figure 1(b). In Figure 1(a), the two light yellow rectangles represent the transportation times of J₁ and J₂, and it takes MT_2,1,4 to transport J₂ from machine M₁ to M₄, so S_2,3,4 is equal to F_2,2,1 plus MT_2,1,4. However, S_2,3,4 is equal to F_2,2,1 in Figure 1(b).

Table 2.

Transportation times of the instance.

Machine	M ₁	M ₂	M ₃	M ₄	M ₅
M ₁	0.0	2.2	4.4	2.5	3.0
M ₂	2.8	0.0	1.3	3.4	2.0
M ₃	3.9	2.1	0.0	1.3	2.8
M ₄	3.7	1.6	2.4	0.0	1.3
M ₅	1.8	2.9	1.9	4.0	0.0

Figure 1.

Gantt charts for two types of scheduling: (a) a scheduling scheme with transportation times; (b) a scheduling scheme without transportation times.

The improved memetic algorithm

The JSP has been proved to be an NP-hard problem,²⁸ while the TT-FJSP is an extension of the JSP and is also an NP-hard problem. This means that it may be difficult to get an optimal solution in finite time through exact solution methods. The MA is a meta-heuristic algorithm with both exploration and exploitation, which is suitable for this problem. The main processes of the IMA are as follows:

Step 1: Generate initial population according to encoding rules.

Step 2: Generate a new population for the next generation by the selection and crossover.

Step 3: Apply the local search and save the high-quality individuals.

Step 4: Check the termination criteria. If the criteria are not satisfied, then stop the algorithm and output the optimal individual in the population. Otherwise, go to Step 2.

The framework of the IMA is given in Algorithm 1. The encode and decode, initial population, selection, crossover, and local search are introduced in the following subsections.

Algorithm 1.

The framework of the IMA.

Input: parameters for the IMA and an TT-FJSP instanceOutput: the optimal individual S_opt 1 Iter = 0; 2 Set = generating initial population by the initialization method; 4 cal(Iter) = calculate the objective function value of the population in Set; 3 while Failure to satisfy the termination condition 5 Set = selection for individuals in Set according to cal(Iter); 6 Set = crossover for individuals in Set; 7 Set = local search for individuals in Set; 8 Iter = Iter + 1; 9 cal(Iter) = calculate the makespan of the individuals in Set;10 S(Iter) = select the optimal individual in Set according to cal(Iter);11 end12 S_opt = select the optimal individual in S;

Encode and decode

Encode is the first important step in the algorithm. Encode is the process of expressing the solutions of a problem in the form of chromosomes, or as individuals. Then the genetic operations, such as the selection and crossover, can be implemented.

The TT-FJSP contains two subproblems: machine selection and operation sequence. We use the two-section integer encode method to address these issues. The chromosome structure is divided into two sections: machine selection and operation sequencing. The machine selection determines the machines of all operations, and the operation sequencing determines the processing order. The lengths of these two sections are equal and equal to the total number of operations $\sum_{i = 1}^{n} o_{i}$ , o_i is the operation number of J_i.

Machine selection

In the machine selection, each gene position corresponds to each operation in sequence, and an integer is used to represent the sequence number of the optional processing machine of the operation, instead of the processing machine number. For example, according to Table 1, if the gene string is 4-1-2-3-3, the first gene position 4 indicates that the operation O_1,1 is processed on the fourth machine in the candidate set of O_1,1, that is M₅. The machine of O_1,2 is the first machine in the candidate set of O_1,2, that is M₂.

Operation sequencing

The operation sequencing is similar to the chromosomes in the JSP. The encode of this section is based on the processing order of the job. Each gene is the job number and the number of each operation in a job is indicated by the number of occurrences in the operation sequencing section. If the gene string is 2-1-1-2-2, then the corresponding operation sequencing is O_2,1-₁O,₁-₁O,₂-₂O,₂-₂O,₃.

Decode

There are three types of scheduling including active scheduling, semi-active scheduling and non-delay scheduling.²⁷ It has been proved that the optimal scheduling exists in the active scheduling set. That is, when chromosomes are decoded as actively scheduled, the result is closest to the optimal solution. Therefore, the plug-in decode method is used to decode chromosomes into the active scheduling. Each chromosome contains two sections, so it needs to be decoded separately.

Machine selection

The machine selection of the chromosome is decoded from left to right, and converted into machine matrix Jm and time matrix T . Machine matrix element Jm (i,h) is equal to the gene at the position $(\sum_{k = 1}^{i - 1} o_{k}) + h$ on the chromosome, denotes the selected processing machine number of O_i,_h. Time matrix element T (i,h) is the processing time of O_i,_h on the selected machine Jm (i,h). Jm (i,h) and T (i,h) have a 1-to-1 correspondence. According to the instance above, the first operation of J₁ is processed on M₅, the second operation of J₁ is processed on M₂ (as shown in equations (7) and (8)), and the processing time is 5.

$Jm = [\begin{matrix} 5 & 2 \\ 3 & 3 & 4 \end{matrix}]$ (7)

$T = [\begin{matrix} 5 & 5 \\ 6 & 5 & 8 \end{matrix}]$ (8)

Operation sequencing

This section gets the scheduling results according to the sequencing of the chromosome from left to right, and the processing and transportation times. To decode the chromosomes into the active schedule, we use an improved insertion method to sort the chromosomes and read the operation sequencing in turn until the algorithm reaches the end of the chromosomes. The specific process is as follows: If O_i,_h is both the first operation of J_i(h = 1) and the first operation on machine M_k, then the operation starts directly from 0 time. If O_i,_h is not the first operation of J_i(h ≠ 1), but the first operation on machine M_k, then the start time S_i,_h,k of O_i,_h is equal to the finish time F_i,_(h-1),j of its tightest preceding operation O_i,_(h-1) plus transportation time MT_i,_j,k. If O_i,_h is not the first operation on M_k, then all idle time periods (TS_k, TE_k) on machine M_k needs to be looked up. TS_k and TE_k represent the start time and the end time of the idle time period on machine M_k. Considering the transportation time, we can judge whether the idle time period can satisfy the insertion condition with equation (9). If it is satisfied, we can get the S_i,_h,k satisfying the processing sequence constraint (it can be obtained from equation (10). Otherwise, we can get the S_i,_h,k with equation (11). When there are several idle time periods on a machine, the insertion is attempted sequentially from the beginning to the end.

$T_{i, h, k} \leq {T E_{k} - max [(F_{i, (h - 1), j} + M T_{i, j, k}), T S_{k}]}$ (9)

$S_{i, h, k} = max [(F_{i, (h - 1), j} + M T_{i, j, k}), T S_{i}]$ (10)

$S_{i, h, k} = max [(F_{i, (h - 1), j} + M T_{i, j, k}), F_{i', h', j}]$ (11)

Population initialization method

The initial population can be obtained through a variety of methods. In general, the initial population method affects the convergence speed and the quality of the population. We use the random method to highlight the performance of other operations of the algorithm. The main steps are as follows:

Step 1: Randomly generate a chromosome to join the initial population: In the machine selection part, randomly select one from the optional machine at each gene position, and in the operation sequencing part, all operations are randomly arranged.

Step 2: Repeat Step 1 until the initial population is filled.

Selection operator

Selection is for good individuals to survive with a greater probability and avoid the disruption of good genes by operations such as the crossover and mutation. The tournament selection method was adopted as the selection method for the proposed algorithm. This method randomly selects some individuals from the population for comparison of fitness each time, then puts the highest fitness individual into the crossover pool and waits for the crossover, until the crossover pool is full.

Crossover operator

An excellent crossover can preserve the good genes in the paternal generation by exchanging information among the paternal individuals to produce good new individuals. It can also reduce a blind search and achieve a simple and efficient search. We propose a crossover method for chromosomes in the FJSP, which includes two different crossover modes.

Machine selection

A multi-point crossover is adopted to ensure that the chromosomes of solutions generated by crossover are still feasible. That is to say, the random selection of multiple intersection sites occurs, and then the exchange of genes on the same location of two parents occurs.

Operation sequencing

The multi-job crossover is adopted to avoid generating infeasible solutions. This method selects all the genes of several jobs in the parent chromosomes and crosses them in sequence. The pseudo-code of the multi-job crossover is given in Algorithm 2.

Algorithm 2.

The pseudo-code of the multi-job crossover.

Input: 2 parent individuals S ₁ and S ₂ Output: 2 offspring S₁’ and S₂’1 j = the number of jobs in S ₁ ;2 jc = a set of randomly selected jobs;3 S_c₁ = the operation sequencing of jc in S ₁ ;4 S_c₂ = the operation sequencing of jc in S ₂ ;5 S_r₁ = the remaining gene of S ₁ − S_c₁ in the original position of S ₁ , and the rest is 0;6 S_r₂ = the remaining gene of S ₂ – S_c₂ in the original position of S ₂ , and the rest is 0;7 S₁’ = replace 0 in S_r₁ with the value in S_c₂ in order;8 S₂’ = replace 0 in S_r₂ with the value in S_c₁ in order;

In fact, the crossover of the two parts is done simultaneously. When the crossover operator is executed, two individuals are first randomly selected from the population as parents. Then the machine selection and the operation sequencing of the offspring are generated by the multi-point crossover and the multi-job crossover, respectively. This process is repeated until the number of the offspring generated reaches the population size.

Local search

The IMA applies an independent local search (LS) to try to improve the quality of the solutions. The LS finds the local optimal solutions by searching the neighborhood solutions. The LS can be repeated to improve the overall quality of the whole population. In this research, an effective SA was adopted to form a new LS method by parallel structure, which adds the elite library and mutation operation of the GA. According to mutation probability P _m and the elite library, the feasible solutions are divided into local optimal solutions and general solutions. When a feasible solution is searched locally, it is judged whether it is in the elite library or not. If the solution is in the elite library or P _m > random(0,1), the solution is considered to be a non-potential solution, which is executed by the mutation operation. Otherwise, the solution is considered to be a potential solution, which is executed by the SA to avoid falling into the local optimum and searching for a better solution. The LS process is shown in Figure 2. The symbols in the Figure 2 are defined as follows: mutation probability P_m , initial temperature T ₀ , current temperature T, termination temperature T_f , temperature coefficient T_c , cooling factor α , maximum number of perturbation L_k . The probability exp(-△y/( T_c T)) is the acceptance probability of the worse solution. When △y is a small positive number and current temperature is high, the acceptance probability is close to 1, when current temperature is closer to the termination temperature, the acceptance probability is closer to 0.

Figure 2.

Flowchart of the local search.

Elite library

The elite library is introduced as a distribution strategy in the LS to avoid searching for the neighborhood solutions of the local optimal individual, which may lead to the output individual being the original individual itself or worse than the original individual. The elite library is a limited set and empty at first. Then the individual output by the SA is regarded as a local optimal individual and stored in the elite library as chromosome. When it is found that the individual already exists in the elite library, the mutation operation will be implemented instead of using the SA. The storage space of elite library (the number of local optimal individuals) is adjustable; if the space is too large, it will increase the time to check whether the individual exists in the library, on the contrary, if the space is too small, it will not play the role of avoiding repeated search.

Mutation operator

Common mutation operations include the interchange mutation, reverse sequence mutation, insertion mutation, and neighborhood-based search mutation. We use the random mutation for the machine selection of the chromosomes.

Step 1: Select several locations for the machine part of the mutated chromosome.

Step 2: Choose 1 machine to randomly replace the original machine.

Perturbation operator

The perturbation operator searches the neighborhood of the current individual. Since the maximum number of the perturbation is set to L_k, the L_k neighborhood solutions of solution S can be obtained and the optimal individuals can be output. The move strategy of operation proposed by Mastrolilli and Gambardella²⁹ is used to generate the neighborhood solution of the current individual.

Due to the additional transportation time constraint in this paper, some equations and definitions need to be modified. For each operation O_i,_h, the release time r_Oi,_h is shown in equation (12), the tail time t_Oi,_h is shown in equation (13). An operation O_i,_h is critical if and only if r_Oi,_h + T_i,_h,k + t_Oi,_h = C_max.

${r_{O}}_{i, h} = max (F_{i', h', k,} F_{i (h - 1), j} + M T_{i, j, k})$ (12)

$\begin{matrix} t_{O i, h} = & max ({T_{i}}_{*, h *, k} + t_{O_{i_{*}, h_{*}}}, M T_{i k, j} \\ + T_{i, (h + 1), j} + t_{i, (h + 1)}) \end{matrix}$ (13)

For a critical operation O_i_1,h1, it needs to be inserted to a suit place to minimize the makespan. Let Q_k be the sequence containing all the operations processed on machine k (except v if it processed on machine k). Then for the two subsequences of Q_k are shown in equations (14) and (15). It has been proved that the set obtained inserting O_i_1,h1 after all the operations of P_k-R_k and before all the operations of R_k-P_k contains at least an optimal insertion of O_i_1,h1 on k.²⁹ The perturbation operation jumps out the optimal individual from all neighborhood solutions of the current individual in each loop iteration, and then updates the optimal individual to the current individual.

$R_{k} = {O_{i, h} \in Q_{k} | r_{O_{i, h}} + T_{i, h, k} > r_{O_{i 1, (h 1 - 1)}} + T_{i 1, (h 1 - 1), j}}$ (14)

$P_{k} = {O_{i, h} \in Q_{k} | t_{O_{i_{,} h}} + T_{i, h, k} > t_{O_{i 1, (h 1 + 1)}} + T_{i 1, (h 1 + 1), j}}$ (15)

Termination condition

The termination condition of the IMA is that Iter equals the maximum number of iterations or that the generations of optimal individual unchanged equals n generations.

Experimental results and comparisons

All algorithms were performed in MATLAB R2017a on a PC with an Inter(R) Core(TM) i7-4785 T CPU at 2.2 GHz with 8 GB of RAM. The experiment tested the performance of the IMA for the TT-FJSP. The main parameters of the IMA, these parameter values are determined by extensive preliminary experiments, are shown in Table 3.

Table 3.

Main parameters of the IMA.

Parameters	Value
Population size	100
Maximum number of iterations	200
Maximum number of the optimal individual unchanged ( n )	30
Storage space of elite library	50
Crossover probability	0.8
Mutation probability ( P_m )	0.2
Initial temperature ( T ₀ )	90
Termination temperature ( T_f )	20
Temperature coefficient ( T_c )	0.001
Cooling factor ( α )	0.9
Maximum number of perturbation ( L_k )	10

IMA: improved memetic algorithm.

Experiment 1

To evaluate the effectiveness of IMA, we selected an instance (8 × 5) from Zhang et al.,¹² who proposed the IGA to solve the TT-FJSP. We compared the results of the IGA and IMA after we had run the 2 algorithms 10 times. The Gantt charts of the optimal individuals from the IGA are shown in Figures 3 and 4. The Gantt charts of the optimal individuals from the IMA are shown in Figures 5 and 6. The convergence curve of the solutions of the TT-FJSP from the IGA is shown in Figure 7. The convergence curve of the solutions of the TT-FJSP from the IMA is shown in Figure 8.

Figure 3.

Optimal scheduling scheme with transportation times from the IGA.

Figure 4.

Optimal scheduling scheme without transportation times from the IGA.

Figure 5.

Optimal scheduling scheme with transportation times from the IMA.

Figure 6.

Optimal scheduling scheme without transportation times from the IMA.

Figure 7.

Convergence curve of the IGA solutions.

Figure 8.

Convergence curve of the IMA solutions.

As shown in Figures 4 and 6, the makespan of the optimal individual from the IMA is 5 units faster than the makespan of the optimal individual from the IGA. In the Gantt chart of the optimal individual from the IMA in Figure 6, the operations are evenly distributed, and there are no large idle time periods on each machine. In contrast, in the Gantt chart of the optimal individual from the IGA in Figure 4, there are 2 idle time periods on M₂. By comparing Figures 5 and 7, we found that the makespan of the optimal individual from the IMA is 4 units faster than the makespan of the optimal individual from the IGA, and there is 3 idle time period on M₄ in Figure 5. By comparing Figures 8 and 9, we find that the value of the optimal individual from the IMA increases with the mean value of the population. The mean value of the population from the IGA does not increase, and the value of the optimal individual easily falls into the local optimum. Therefore, the IMA is more effective than the IGA.

Figure 9.

Comparison of the stability of the IMA and IGA.

Experiment 2

Because of the lack of experimental data on the TT-FJSP, we chose the IGA as the object of comparison. The experimental data sets were Brandimarte’s²¹ data sets, and the randomly generated transportation time are shown in Table 4. To obtain meaningful results, we ran our algorithm 10 times on the same instance. The results are shown in Table 5, the opt is the makespan of the optimal individual, the μ is the average value, the σ is the standard deviation, the Cv is the coefficient of variation. The coefficient of variation is defined as the ratio of the standard deviation to the average value and eliminates the influence of dimension, as shown in equation (16). It can express the stability of algorithm more accurately. MAPE is the mean absolute percentage error; it shows that the percentage of the IMA’s optimal individual is higher than that of the IGA’s optimal individual, as shown in equation (17).

Table 4.

Transportation time.

	M ₁	M ₂	M ₃	M ₄	M ₅	M ₆	M ₇	M ₈	M ₉	M ₁₀	M ₁₁	M ₁₂	M ₁₃	M ₁₄	M ₁₅
M ₁	0.0	2.2	4.4	2.5	3.0	1.9	4.1	2.2	3.9	1.9	0.5	0.7	2.5	3.9	0.5
M ₂	2.8	0.0	1.3	3.4	2.0	4.2	2.9	1.6	4.9	3.4	2.9	2.7	2.4	4.6	2.1
M ₃	3.9	2.1	0.0	1.3	2.8	2.6	1.9	2.2	1.6	1.7	4.9	4.1	4.1	1.4	1.6
M ₄	3.7	1.6	2.4	0.0	1.3	1.0	3.3	3.2	1.9	1.5	0.4	4.0	1.7	1.5	5.0
M ₅	1.8	2.9	1.9	4.0	0.0	1.5	4.0	3.4	1.7	3.7	3.7	4.5	4.0	4.9	2.8
M ₆	2.2	1.2	2.2	2.9	2.5	0.0	1.8	3.9	2.0	3.5	3.1	2.9	1.3	4.6	4.4
M ₇	4.8	3.3	3.7	2.2	2.1	3.0	0.0	4.1	2.1	2.1	3.2	3.2	4.9	2.8	3.3
M ₈	1.8	1.8	1.4	1.1	2.4	2.4	1.2	0.0	3.6	3.8	3.7	1.5	1.8	3.3	1.3
M ₉	2.3	1.7	3.4	3.2	3.9	1.5	1.3	3.0	0.0	1.3	1.9	4.7	2.3	4.6	0.6
M ₁₀	2.4	1.2	1.5	1.4	3.4	4.7	1.5	3.6	2.2	0.0	5.0	3.6	1.3	4.3	1.3
M ₁₁	1.9	4.7	0.6	4.4	2.0	2.4	4.9	2.0	3.6	4.9	0.0	2.2	2.8	4.3	4.8
M ₁₂	2.2	4.5	1.9	4.2	1.7	3.5	1.7	2.8	1.7	4.9	2.4	0.0	1.9	4.8	4.9
M ₁₃	2.6	4.7	2.1	3.4	4.2	1.6	0.2	2.7	3.7	4.9	0.3	2.8	0.0	2.2	3.5
M ₁₄	3.0	4.7	0.8	3.4	0.7	1.8	4.0	1.5	4.2	4.9	3.3	2.1	1.6	0.0	4.9
M ₁₅	0.2	2.9	4.6	1.8	2.6	4.9	4.3	2.3	0.9	4.9	4.7	1.2	4.9	3.9	0.0

Table 5.

Comparison of the IMA and IGA results.

Index	opt ^IMA	μ ^IMA	σ ^IMA	Cv ^IMA	opt ^IGA	μ ^IGA	σ ^IGA	Cv ^IGA	MAPE
Mk01	45.8	48.13	1.05	2.19%	52.7	59.4	2.11	3.57%	18.53%
Mk02	34.2	35.68	1.27	3.55%	50.3	53.4	2.87	5.37%	47.08%
Mk03	211	219.18	6.52	2.98%	262.9	275.4	5.03	1.83%	24.60%
Mk04	74.6	77.97	2.13	2.73%	87.9	91.9	2.51	2.73%	17.83%
Mk05	180	184.75	2.88	1.56%	206.1	211.1	3.24	1.53%	14.50%
Mk06	103.2	108.14	3.46	3.20%	148.4	153.9	3.80	2.47%	43.80%
Mk07	155.3	160.96	3.98	2.47%	215.2	228.7	6.87	3.00%	38.57%
Mk08	523	526.07	2.81	0.53%	560.4	573	6.15	1.07%	7.15%
Mk09	345.3	357.48	14.53	1.38%	417.1	450.3	14.73	3.27%	20.79%
Mk10	280	291.63	4.51	1.55%	374.8	390.5	6.89	1.76%	33.86%

IMA: improved memetic algorithm; IGA: improved genetic algorithm; MAPE: mean absolute percentage error.

$Cv = \frac{σ}{μ}$ (16)

$MAPE = \frac{100}{n} \sum_{t = 1}^{n} | \frac{IM A_{t} - IG A_{t}}{IM A_{t}} |$ (17)

Table 5 shows that the proposed IMA has a better performance than the IGA when solving the 10 problems of Mk01-Mk10 with the transportation time, including all the optimal and average values. The optimal individual from the IMA is 26.67% better than that from the IGA. The stability of the IMA and IGA is compared using the coefficient of variation shown in Figure 9. The average value of Cv^IMA is 2.21% and the average value of Cv^IGA is 2.66%. Therefore, the robustness of the IMA is better than that of the IGA.

Let us take the Mk01 problem as an example. The Gantt chart of the optimal individual from the IMA is shown in Figure 10. The Gantt chart of the optimal individual from the IMA is shown in Figure 11. As shown in Figures 10 and 11, the makespan of the optimal individual from the IMA is 6.9 units faster than the makespan of the optimal individual from the IGA. However, in both the Gantt charts, there are relatively large idle time periods on M₅, indicating that there is still a lot of room for improvement.

Figure 10.

Optimal scheduling scheme with transportation times from the IMA.

Figure 11.

Optimal scheduling scheme with transportation times from the IGA.

Conclusion and future research

In this paper, we studied the TT-FJSP and proposed an IMA. In this algorithm, feasible solutions are treated differently by the local search, general solutions are executed by the SA to improve the quality of the solutions, and the local optimal solutions are executed by the mutation operation to increase the diversity of the solutions. And the high-quality solutions are not lost as the population evolves because of the elite library. The IMA is evaluated and compared with an improved GA. The experimental results show that the optimal individual of each problem obtained from the IMA is better than that obtained from the IGA, and the convergence curve of the solutions is more reasonable with less uncertainty. Therefore, the IMA is effective for solving the TT-FJSP.

Our future work will address two main areas. First, we will further investigate the proposed algorithm. The SA has good search accuracy, but its search speed is not very fast, and it can be further improved. Therefore, the combination of multiple global search algorithms and local search algorithms is also worth trying. In addition, we will continue to explore the FJSP. The transportation constraints are not only the time constraints, we will also consider the limitations of routes and transportation resources.

Footnotes

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 research work is supported by the National Natural Science Foundation of China (U1904167,51705472,71871204,51905494),and Humanities and Social Sciences of Ministry of Education Planning Fund (18YJAZH125).

ORCID iD

Guohui Zhang

References

Brucker

Schile

. Job-shop scheduling with multi-purpose machines. Computing 1990; 45(4): 369–375.

Pezzella

Morganti

Ciaschetti

. A genetic algorithm for the flexible job-shop scheduling problem. Comput Oper Res 2008; 35(10): 3202–3212.

Fattahi

Mehrabad

Jolai

. Mathematical modeling and heuristic approaches to flexible job shop scheduling problems. J Intel Manuf 2007; 18(3): 331–342.

Fattahi

Jolai

Arkat

. Flexible job shop scheduling with overlapping in operations. Appl Math Model 2009; 33(7): 3076–3087.

Yin

Gao

, et al. A novel mathematical model and multi-objective method for the low-carbon flexible job shop scheduling problem, considering productivity, energy efficiency and noise reduction. Sustain Comput Inform Syst 2017; 13: 15–30.

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.

Gao

, et al. An effective multi-objective algorithm for energy efficient scheduling in a real-life welding shop. IEEE T Ind Inform 2018; 14(12): 5400–5409.

Gao

Pan

, et al. An effective hybrid genetic algorithm and variable neighborhood search for integrated process planning and scheduling in a packaging machine workshop. IEEE T Syst Man Cyb2019; 49(10): 1933–1944.

Naderi

Javid

Jolai

. Permutation flowshops with transportation times: mathematical models and solution methods. Int J Adv Manuf Tech 2010; 46: 631–647.

10.

Rossi

. Flexible job shop scheduling with sequence-dependent setup and transportation times by ant colony with reinforced pheromone relationships. Int J Prod Econ 2014; 153: 253–267.

11.

Karimi

Ardalan

Naderi

, et al. Scheduling flexible job-shops with transportation times: mathematical models and a hybrid imperialist competitive algorithm. Appl Math Model 2017; 41: 667–682.

12.

Zhang

Sun

Liu

, et al. Solving flexible job shop scheduling problems with transportation time based on improved genetic algorithm. Math Biosci Eng 2019; 16: 1334–1347.

13.

Zhang

Sun

, et al. An improved genetic algorithm for the flexible job shop scheduling problem with multiple time constraints. Swarm Evolut Comput 2020; 54: 100664.

14.

Zhang

Gao

Shi

. An effective genetic algorithm for the flexible job-shop scheduling problem. Expert Syst Appl 2011; 38: 3563–3573.

15.

Driss

Mouss

Laggoun

. A new genetic algorithm for flexible job-shop scheduling problems. J Mech Sci Technol 2015; 29: 1273–1281.

16.

Defersha

Bayat-Movahed

. Linear programming assisted (not embedded) genetic algorithm for flexible jobshop scheduling with lot streaming. Comput Ind Eng 2018; 117: 319–335.

17.

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.

18.

Chaouch

Driss

Ghedira

. A modified ant colony optimization algorithm for the distributed job shop scheduling problem. Proced Comput Sci 2017; 112: 296–305.

19.

Sharma

. Beer froth artificial bee colony algorithm for job-shop scheduling problem. Appl Soft Comput 2018; 68: 507–524.

20.

Xia

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

21.

Brandimarte

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

22.

Gao

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

23.

Zhang

Song

, et al. A variable neighborhood search based genetic algorithm for flexible job shop scheduling problem. Cluster Comput 2019; 22: 11561–11572.

24.

Moscato

. Memetic algorithms: a short introduction. In: Dorigo

Glover

Corne

(eds) New ideas in optimization. New York: McGraw Hill, 1999, pp. 219–234.

25.

Phu-ang

Thammano

. Memetic algorithm based on marriage in honey bees optimization for flexible job shop scheduling problem. Memetic Comput 2017; 9: 295–309.

26.

Gong

Deng

Gong

, et al. A memetic algorithm for multi-objective flexible job-shop problem with worker flexibility. Int J Prod Res 2018; 56(7-8): 2506–2522.

27.

Zhang

Guan

, et al. A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem. Comput Oper Res 2007; 34(11): 3229–3242.

28.

Garey

Johnson

Sethi

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

29.

Mastrolilli

Gambardella

. Effective neighbourhood functions for the flexible job shop problem. J Schedul 2000; 3(1): 3–20.

An improved memetic algorithm for the flexible job shop scheduling problem with transportation times

Abstract

Keywords

Introduction

Problem formulation

The improved memetic algorithm

Encode and decode

Machine selection

Operation sequencing

Decode

Machine selection

Operation sequencing

Population initialization method

Selection operator

Crossover operator

Machine selection

Operation sequencing

Local search

Elite library

Mutation operator

Perturbation operator

Termination condition

Experimental results and comparisons

Experiment 1

Experiment 2

Conclusion and future research

Footnotes

Declaration of conflicting interests

Funding

ORCID iD

References