Many-Objective Flexible Job Shop Scheduling Problem with Green Consideration

Abstract

With the increasingly customized product requirements of customers, the manufactured products have the characteristics of multi-variety and small-batch production. A high-quality production scheduling scheme can reduce energy consumption, improve production capacity and processing quality of the enterprise. The high-dimensional many-objective green flexible job shop scheduling problem (Ma-OFJSSP) urgently needs to be solved. However, the existing optimization method are difficult to effectively optimize the Ma-OFJSSP. This study proposes a many-objective flexible job shop scheduling model. An optimization method SV-MA is designed to effectively optimize the Ma-OFJSSP model. The SV-MA memetic algorithm combines an improved strength Pareto evolution method (SPEA2) and the variable neighborhood search method. To effectively distinguish the better solutions and increase the selection pressure of the non-dominated solutions, the fitness calculation method based on the shift-based density estimation strategy is adopted. The SV-MA algorithm designs the variable neighborhood strategy which combines with scheduling knowledge. Finally, in the workshop scheduling benchmarks and the machining workshop engineering case, the feasibility and effectiveness of the proposed model and SV-MA algorithm are verified by comparison with other methods. The production scheduling scheme obtained by the proposed model and SV-MA optimization algorithm can improve production efficiency and reduce energy consumption in the production process.

1. Introduction

With the transformation and upgrading of manufacturing industry, production scheduling is becoming more and more important in manufacturing enterprises. Workshop production scheduling problem is the important decision content of intelligent factory production management [1]. The production scheduling scheme will directly affect the energy consumption, production capacity, cost, manufacturing quality of the enterprise. Therefore, production scheduling is very important for workshop production, and it is also an important research direction for intelligent manufacturing and green manufacturing.

With the increasingly customized product requirements of customers, the manufactured products have the characteristics of multi-variety and small-batch production. Each product has many and complicated processes, and each operation can be processed on one or more equipment. This type of production is typical flexible job shop scheduling problem (FJSSP). FJSSP is more in line with the current actual production status of manufacturing enterprises. However, it has the characteristics of complex modeling, complex calculation and multiple constraints [2,3]. A high-quality flexible job shop scheduling scheme can reduce energy consumption and improve the production operation capacity and processing quality of the enterprise [4].

To achieve the high efficiency, consumption reduction, high-quality, and low cost in the production process of the flexible workshop, many scheduling objectives need to be optimized in the production scheduling process. Therefore, FJSSP has transformed into a high-dimensional many-objective optimization problem. However, the existing optimization method are difficult to effectively optimize the many-objective green flexible job shop scheduling problem (Ma-OFJSSP). Therefore, optimization algorithm of the Ma-OFJSSP need to be studied.

In mathematics, a job shop scheduling problem with completion time is an NP-hard problem, so high-dimensional Ma-OFJSSP is NP-hard [5]. In engineering, realizing the scheduling optimization of the Ma-OFJSSP can increase production capacity, improve the production operation capacity and manufacturing quality, and save energy and reduce consumption. Its research has important application value.

For FJSSP research, most of the research focuses on the optimization of production indicators, such as completion time and processing cost. With the introduction of energy-saving concepts, the status of energy consumption in production management has gradually increased. To solve the resource-constrained FJSSP, Wei et al. [6] proposed an optimization algorithm that mixes the multi-objective genetic algorithm (MOGA) with the whale optimization algorithm (WOA) to improve the adaptive ability of genetic operators. Li et al. [7] established an energy-saving FJSSP model considering transportation, and designed an imperialist competitive algorithm with feedback (FICA) to optimize the FJSSP scheduling model. This method has better optimization performance demonstrated by the experimental results. For the variable batch FJSSP, Wu et al. [8] established the variable batches scheduling model, and proposed a batch optimization algorithm with inverse scheduling. Meanwhile, the neighborhood update method and population update methods are designed. Kong et al. [9] designed an improved shuffled frog-leaping algorithm to optimize the FJSSP model. By comparing optimization methods such as tabu search and ant colony optimization, this method has better search capabilities.

Most of the above research for FJSSP are low-dimensional multi-objective FJSSP. The number of optimization objectives is usually two or three. However, with the development of lean manufacturing and green manufacturing, the optimization objectives of production scheduling are gradually increase, usually no less than four. Therefore, the high-dimensional many-objective FJSSP has gradually been formed. The research on the high-dimensional Ma-OFJSSP is consistent with the real demand of the current engineering.

Evolutionary algorithm is a type of random search algorithm. Evolutionary algorithm simulates natural selection and natural evolution of living beings. It can obtain a set of non-dominant solutions after one run. Evolutionary algorithm is very suitable to optimize many-objective optimization problems. Genetic algorithm is the most commonly used evolutionary algorithm. However, as the number of objectives increases, the proportion of non-dominated solutions in the population increases rapidly. It is difficult to distinguish better solutions by the dominance relationship. Meanwhile, the selection pressure for non-dominated solutions gradually decreases.

In the study of the Ma-OFJSSP, there is less research relating to the flexible job shop. The existing optimization method is difficult to effectively distinguish the better solutions in the optimization process. The selection pressure for the non-dominated solutions is gradually reduced. Meanwhile, the global search and local search of the optimization method cannot be effectively balanced.

Therefore, to efficiently solve the high-dimensional Ma-OFJSSP, a high-dimensional many-objective FJSSP model with five optimization objectives is established. A new memetic algorithm is designed to solve the high-dimensional Ma-OFJSSP. The memetic algorithm combines an improved strength Pareto evolution method (SPEA2) and the variable neighborhood search method. A memetic algorithm that effectively balances the global search ability and local search ability is proposed. The variable neighborhood search structure which combines scheduling knowledge and critical operations is designed. In the high-dimensional many-objective scheduling optimization algorithm, it is necessary to design a suitable chromosome encoding and decoding method. Meanwhile, the corresponding genetic operator for this chromosome encoding method need to be designed. Finally, benchmark examples and engineering cases verify the competitiveness of the designed SV-MA method in optimizing high-dimensional Ma-OFJSSP.

The main contributions of this paper are as follows: To effectively distinguish the better solutions and increase the selection pressure of the non-dominated solutions, the fitness calculation method based on the shift-based density estimation strategy is adopted. To effectively solve the high-dimensional Ma-OFJSSP, a new memetic algorithm SV-MA method is proposed to optimize the Ma-OFJSSP. The memetic algorithm combines the improved SPEA2 and the variable neighborhood search method. Meanwhile, the global search and local search of this optimization method can be effectively balanced. The feasibility and effectiveness of this method are demonstrated in solving practical engineering problems. The production scheduling scheme obtained by the proposed model and the SV-MA optimization algorithm can improve production efficiency and reduce energy consumption in the production process.

The remaining sections of this paper are arranged as follows. Section 2 introduces related works. Section 3 introduces the high-dimensional many-objective FJSSP and model. Section 4 introduces the SV-MA memetic algorithm. Section 5 describes the experiment results and discussion. Section 6 describes conclusion and the future research.

2. Related Work

For FJSSP research, Caldeira et al. [10] proposed a flexible job shop scheduling model with the objectives of attaining the maximum completion time, energy consumption, and instability, and designed an improved backtracking search method to optimize the scheduling model. The search performance of the optimization algorithm is enhanced. For the dual-resource FJSSP, Wu et al. [11] designed a similarity-based set-up time reduction scheduling algorithm and an improved non-dominated sorting genetic algorithm to solve the scheduling model. It can effectively improve production efficiency. For a low-carbon FJSSP, Zhu et al. [12] designed a swarm-based intelligent method which is called discrete African buffalo optimization (DABO). The effectiveness of the optimization method is verified by computational experiments. Tan et al. [13] designed an improved micro genetic method to optimize the integrated scheduling model. In order to obtain a good scheduling scheme for flexible workshops, Choudhary et al. [14] designed a modified particle swarm optimization method to optimize the production scheduling model. The improved optimization method incorporates mutation operations and has better solution performance. Gong et al. [15] proposed the nonlinear integer programming scheduling model considering green production, and designed a new non-dominated evolutionary algorithm NEFRL. This method uses an overall fitness ranking method that can increase the search performance of the optimization method.

For the Ma-OFJSSP, Sun et al. [16] proposed an optimization method that mixes the Tabu search method and the non-dominated sorting selection method. When solving the scheduling model, it can maintain the diversity and convergence of the population. Li et al. [17] studied the high-dimensional many-objective job shop scheduling problem under worker resource constraints, and proposed two genetic algorithms based on reference points which integrate a fitness evaluation mechanism based on fuzzy correlation entropy (FCE). Zhu et al. [18] studied the high-dimensional many-objective permutation flow shop scheduling problem and proposed an effective optimal foraging algorithm. In this optimization method, the fuzzy relative entropy is used as the fitness function. The feasibility of this method is verified by calculation experiments. Masood et al. [19] studied a job shop scheduling model containing four optimization objectives, and proposed a many-objective optimization method which combines genetic programming and NSGA-III. This optimization method innovatively designed a reference point update method. To maintain the balance between convergence and diversity in the solution process of many-objective optimization method, Zhang et al. [20] studied a many-objective evolution method based on the point of determinacy. In order to optimize the high-dimensional many-objective FJSSP, Li et al. [21] designed a new imperialist competition algorithm, which added a variable neighborhood search algorithm. The feasibility of this algorithm is proved by calculation experiments. Xu et al. [22] designed a fuzzy set-based many-objective evolutionary algorithm to solve the high-dimensional Ma-OFJSSP. The new evolutionary algorithm which guides the search of the algorithm used similarity as the fitness of the genetic algorithm. For the lack of selection pressure on non-dominated solutions in the process of many-objective optimization, Zhang et al. [23] studied a new ranking method, and incorporated the new ranking method into the many-objective differential evolution algorithm. The feasibility of the algorithm is verified by calculation experiments. Xiang et al. [24] studied the many-objective evolutionary algorithm based on vector angles, designed new genetic operators and individual retention strategies. The optimization method improved the tolerance for infeasible solutions. Bi et al. [25] studied the high-dimensional many-objective evolutionary algorithm based on hyperplane projection, and proposed the crowding density of population individuals on the hyperplane, which improved the uniform distribution of non-dominated solutions on the Pareto Front. Meanwhile, supply chain management requires the coordination of various parts including raw material suppliers, product manufacturers, sellers, etc. In the globalized economic environment, market competition is more intense. The production scheduling and inventory management of an enterprise should not only consider the internal business process of an enterprise, but also carry out comprehensive optimization control from the overall supply chain [26,27,28,29]. To solve the many-objective optimization problem, He et al. [30] proposed an evolutionary algorithm based on objective space to improve the selection pressure. A mating selection based on FC is proposed to improve algorithm performance [31,32]. Liu et al. [33] designed a co-evolutionary particle swarm algorithm to improve convergence. Liu et al. [34] designed a many-objective multi-population genetic algorithm.

3. Problem and Model Description

The basic introduction of the FJSSP can be described as: under the constraints of limited production resources, manufacturing tasks are allocated to available equipment by the scheduling rules. The scheduling of production tasks needs to meet one or more production indicators. There are no less than four scheduling optimization objectives for the high-dimensional Ma-OFJSSP. The goal of high-dimensional Ma-OFJSSP is to arrange when each operation is processed on which equipment, and finally realize the optimization of many scheduling objectives.

Based on the following conditions and assumptions:

(1)

Each equipment can only process one workpiece at a time;

(2)

All equipments are usable at zero time;

(3)

The machining operation cannot be interrupted;

(4)

The manufacturing process of the workpieces is determined, and the priority of all the workpieces is the same;

(5)

There are sequential constraints between the operations of the same workpiece, and operation $j$ can be started after operation $i$ is completed.

This paper establishes many-objective FJSSP model with five objectives. It can be expressed as the following formula.

$$\min F={\left(f_1,f_2,f_3,f_4,f_5\right)}^T$$

(1)

(1)

Makespan $f_1$. Shortening the production time of the workpiece can ensure that the manufacturing enterprise can deliver on time. Makespan is the most fundamental optimization objective in production scheduling research.

$$f_1=\max \left(C_i\left|i=1,2,3\cdots n\right.\right)$$

(2)

were $C_i$ is the mskespan of the last operation for the $i$-th workpiece.

(2)

Total equipment load $f_2$.

$$f_2={\displaystyle \sum _{k=1}^m{\displaystyle \sum _{i=1}^n{\displaystyle \sum _{j=1}^{q_i}{a}_{ij}^k\times t_{ij}^k}}}$$

(3)

where $a_{ij}^k$ represents whether the operation $O_{ij}^k$ is processed on equipment $M_k$, and $t_{ij}^k$ represents the manufacturing time of operation $O_{ij}^k$ on machine $M_k$.

(3)

Energy consumption $f_3$. Reducing energy consumption is conducive to reduce costs and protect the environment. The energy consumption of the workshop includes operating energy consumption and no-load energy consumption of equipment.

$$f_3={\displaystyle \sum _{k=1}^m{E}_k}={\displaystyle \sum (E_k^J+E_k^K)}$$

(4)

Operating energy consumption is calculated as follows:

$$E_k^J={\displaystyle \sum _{i=1}^n{\displaystyle \sum _{j=1}^{q_i}\left(a_{ij}^k\times t_{ij}^k\right)}}\times P^k$$

(5)

No-load energy consumption is calculated as follows:

$$E_k^K=\left(C_k-S_k-{\displaystyle \sum _{i=1}^n{\displaystyle \sum _{j=1}^{q_i}\left(a_{ij}^k\times t_{ij}^k\right)}}\right)\times P{D}^k$$

(6)

Among them, $E_k^J$ represents the operating energy consumption of the equipment $M_k$, $E_k^K$ represents the no-load energy consumption of the equipment $M_k$, $P^k$ represents the operating power of the equipment $M_k$, $P{D}^k$ represents the no-load power of the equipment $M_k$, $S_{kz,j}$ represents the start time of the $j$-th operation on the equipment $M_k$, and $O_{kz,j}$ represents the equipment $M_k$ end time of the $j$-th operation.

(4)

Delay time $f_4$.

$$f_4={\displaystyle \sum {}_{i=1}^n}\max \left(C_i-D{D}_i,0\right)$$

(7)

where $D{D}_i$ is the delivery date of workpiece $i$.

(5)

Processing quality $f_5$. The processing quality of an operation on a machine can be reflected by the failure rate of operation. The higher the rate of defective products, the more unstable the processing quality of the process.

$$f_5={\displaystyle \sum _{i=1}^n{\displaystyle \sum _{j=1}^{q_i}{O}_{ij}^k{L}_{ijk}}}$$

(8)

4. The Proposed SV-MA Memetic Algorithm

4.1. Overview of SV-MA Method

Firstly, SV-MA optimization method need to initialize the parent population $P_t$ with size $N$. The fitness of individuals in the population need to be obtained. SV-MA method performs genetic selection operator, and then use crossover and mutation genetic operators to obtain offspring population $Q_t$ with size N. If the generated random probability value is greater than the setting neighborhood search probability, the neighborhood search is performed for the individuals of offspring population. The combined population $U_t$ with size 2N is consist of the parent population $P_t$ and the offspring population $Q_t$. Meanwhile, the fitness of the combined population is calculated.

To select N individuals from the population $U_t$, the environment selection operation is required. Firstly, If the fitness of the individual is less than 1, the individual is put into the set $X_t$. If the total number of individuals in the $X_t$ is less than N, the individuals with the smaller fitness value in the combined population enter the next generation population. If the total number of individuals in the $X_t$ is greater than N, individuals need to be selected in turn from the $X_t$ according to the pruning rule. This calculation process continues to repeat until the maximum number of iterations is met. Finally, the scheduling scheme solution sets are obtained. A suitable scheduling scheme is selected from the scheduling scheme solution set by the fuzzy decision method. The flowchart of the SV-MA method is shown in Figure 1.

4.2. Encoding Method

The SV-MA optimization method uses an encoding method of two-layer chromosome, as shown in Figure 2. The first layer is the operation chromosome and the second layer is the equipment chromosome. The total number of genes in two-layer chromosome is equal to the total number of operations.

The workpiece number can represent the gene of the operation chromosome. The operation number of the workpiece is determined according to the number of occurrences of the workpiece in the operation chromosome. By altering the position of each gene in the operation chromosome, the processing order which is defined by the operation chromosome can be changed.

The equipment chromosome is arranged from left to right according to the length of the operation chromosome. The genes of each operation are arranged to constitute a chromosome. The processing machine of each operation can be changed by changing the equipment number in the optional equipment set.

4.3. Fitness

To avoid that the individuals dominated by the external members have the same fitness value in SPEA2, the solution dominated by each individual and the solution dominating it are taken into account.

To indicate the number of solutions dominated by individual $I$, the intensity value is taken as the eigenvalue of individual $I$.

$$S\left(i\right)=\left|\left\{\left.j\left|\right.j\in P+Q\wedge i\succ j\right\}\right.\right|$$

(9)

where $P$ represents population in the evolution process, $Q$ represents archive set, $i$ and $j$ represent individual in the population, $S\left(i\right)$ represents the intensity value of individual $i$, the |.| function represents number of individuals.

On the basis of $S(i)$, the original fitness value of individual $I$ is equal to the sum of the intensity values of all individuals dominating the individual $I$.

$$R\left(i\right)={\displaystyle \sum _{j\in Pop}S\left(j\right)}$$

(10)

In the calculation process of individual fitness, in order to distinguish individuals with the same original fitness value, the individual density value is introduced.

$$D\left(i\right)=\frac{1}{{\sigma }_i^k+2}$$

(11)

where ${\sigma }_i^k$ is the distance between individual $i$ and its $k$-th neighbor.

In order to make the traditional MOEA based on Pareto domination suitable for solving high-dimensional optimization problems, Li et al. [35] designed a shift-based density estimation strategy (SDE). Different from other density estimation strategies, SDE contains individual distribution information and convergence information. The moving distance of two individuals is calculated by SDE method. Then, the distance between individuals and other individuals in the population is calculated and arranged in increasing order.

The individual fitness calculation method based on SDE is denoted by Equation (12).

$$F\left(i\right)=R\left(i\right)+D\left(i\right)$$

(12)

4.4. The Crossover and Mutation Method

The crossover and mutation operation of SV-MA optimization method is consist of operation chromosome and equipment chromosome. Firstly, the mapping relationship for the two encoding chromosomes is determined.

In the first part, all workpiece numbers are arranged in order according to the number of operations. For example, chromosome P1 indicates that workpiece 1 has three operations, workpiece 2 has two operations. Then, the position information of the above sequence is extracted to form a mapping rule.

P1 = [1 1 1 2 2 3 3 3 3]

P2 = [1 2 3 4 5 6 7 8 9]

The composition of P1 is changed by changing the arrangement order of P2 sequence, so as to realize different operation chromosome.

The second part is the equipment chromosome, and the mapping relationship is defined as follows:

P3 = [1 1 1 2 2 3 3 3 3]

$$\mathrm{P}4=[m_{11} m_{12} m_{13} m_{21} m_{22} m_{31} m_{32} m_{33} m_{34}]$$

$m_{ij}$ denotes the equipment number of operation $O_{ij}$ in the optional equipment set.

The crossover method of operation chromosomes is as follows: the crossover operation generates the number that was picked between 1 and 0, and compares it with the setting crossover probability value. If it is less than the crossover probability value, it is determined that two individuals need to complete the crossover operation. P1 and P2 are two operation chromosomes. Firstly, two unequal intersections are discretionarily selected, and the genes between the intersections are exchanged to generate new operation chromosomes. Then, the repeated genes in the new sequence are deleted and the lacking genes are supplemented. Finally, two qualified new individuals are generated, such as:

P1 = [1 2 |5 4 3 9| 7 6 8]

P2 = [4 3 |9 7 8 1| 2 5 6]

P1′ and P2′ can be obtained by exchanging the gene positions between the crossover points.

P1′ = [1 2 |9 7 8 3| 4 6 5]

P2′ = [7 8 |5 4 3 9| 2 1 6]

For the equipment chromosomes P1_1 and P2_1, the following equations directly used for crossover.

P3′ = round (a × P1_1 + (1 − a) × P2_1)

(13)

P4′ = round (a × P2_1 + (1 − a) × P1_1)

(14)

In the above formula, round is the rounding operation, and the boundary of the rounded chromosome is checked to ensure that the new chromosome meets the conditions.

Mutation is conducive to enhance the diversity of the population, prevent the algorithm from falling into prematurity, and enhance the local search ability of decision-making optimization methods. Adaptive mutation method based on blood relationship is used. The two-points inversion method is adopted for the mutation of operation chromosome. Two genes of operation chromosome are randomly selected to exchange in order to generate a new chromosome, as shown in Figure 3.

The mutation operation of the equipment chromosome is performed by the following Equation (15).

P1_1′ = Hlimts − P1_1 + Llimits

(15)

Hlimts and Llimits denote the maximum and minimum equipment numbers of the workpiece process, respectively. P1_1 is the current row number of the operation in the optional equipment set.

4.5. Variable Neighborhood Search

A neighborhood is an important concept in the field of optimization. It defines the search direction and range based on the current solution or solution set. For general continuous optimization problems, the neighborhood can be regarded as a spherical region centered on a point. Combinatorial optimization problem is no longer applicable to the traditional concept of distance, and a new neighborhood structure needs to be defined. A variable neighborhood search (VNS) is a heuristic method based on local search algorithm. Many combinatorial optimization problems were optimized by variable neighborhood search method. In the process of population evolution, if the generated random probability value is greater than the setting neighborhood search probability, the SV-MA method looks for the neighborhood of the individuals. The design of a neighborhood structure is the key to the VNS algorithm. This paper adopts the following two neighborhood structures:

NN1: The critical operation neighborhood search based on key block.

In the scheduling Gantt chart of FJSSP, the longest path without time interval between operations is known as critical path. It corresponds to the longest path from the start node 0 to the end node # in the disjunctive graph model [36]. L (U, V) represents the length of the longest path from the node of operation U to the node of operation V in the disjunctive graph. The operations that compose the critical path are known as critical operations; otherwise, they are non-critical operations.

We adopt a new neighborhood structure based on critical operation. Firstly, we find the key block in the critical operation, and then insert the operation in the block and the operation at the end of the block into the first operation position of the key block. Other operations move backward without changing the processing sequence of different operations for the same workpiece.

NN2: the double-layer neighborhood search based on critical operations.

Firstly, NN2 adjusts the critical operations and uses the two-point exchange strategy. Two exchange positions are discretionarily selected in the critical operation, and the genes at the two positions are exchanged. For example, the gene code of the operation chromosome is “12584376”, and two operations 2 and 8 are randomly selected from the critical operations to exchange positions 2 and 8. The chromosome obtained by exchanging the genes is “16584372”.

The equipment chromosome neighborhood also needs to be adjusted. Operations are arranged on different processing equipment, which will produce different scheduling schemes. If the corresponding machine selected by the operation is altered, the NN2 method can obtain neighborhood of the machine chromosome. When selecting the processing equipment of the operation in the alternative machine set, we use the dominance relationship to judge the advantages and disadvantages of the selecting machine. The processing time, energy consumption, and processing quality of each machine are recorded separately in the alternative machine set. If the objective values can dominate the three objective values generated by the current machine, the other processing machine will be selected to process the current operation.

4.6. The Environment Selection Method

The combined population $U_t$ with size 2N was obtained by mixing the parent population $P_t$ and the offspring population $Q_t$. The fitness of the combined population was calculated.

In order to select N individuals from the population $U_t$, the environment selection operation is required. Firstly, if the fitness of the individual is less than 1, the individual is put into the set $X_t$. If the total number of individuals in the $X_t$ is less than N, the individuals with the smaller fitness value in the combined population enter the next generation population. If the total number of individuals in the $X_t$ is greater than N, individuals need to be selected in turn from t in the $X_t$ according to the pruning rule.

Firstly, the distance between the individual and other individuals in the population is calculated, and the nearest individual is selected in turn for deletion. When multiple individuals have the same distance from their previous $L$ adjacent individuals and different distances from their k-th adjacent individuals, an individual with the minimum distance is selected to delete.

5. Experiment Results and Discussion

5.1. FJSSP Benchmarks and Parameter Setting

There are no standard test benchmarks for the Ma-OFJSSP. To verify the effectiveness and feasibility of the designed SV-MA method in optimizing the high-dimensional Ma-OFJSSP, we uses 10 BRdata test problems (MK01∼MK10) [37] as basic benchmark in this paper. Ten new test benchmarks (FMK01∼FMK10) are generated for the Ma-OFJSSP, as shown in

Table 1. Composition of the instances.

Instances	Size (n × m)	Source
FMK01	10 × 6	MK01
FMK02	10 × 6	MK02
FMK03	15 × 8	MK03
FMK04	15 × 8	MK04
FMK05	15 × 4	MK05
FMK06	10 × 15	MK06
FMK07	20 × 5	MK07
FMK08	20 × 10	MK08
FMK09	20 × 10	MK09
FMK10	20 × 15	MK10

.

To more accurately evaluate the performance of each optimization method in solving different benchmark examples, each optimization method is calculated 30 times, and the 30 performance metric values are evaluated by the Wilcoxon rank sum test. The level of significance is 0.05. The parameter settings of the SV-MA decision-making method in solving the Ma-OFJSSP are shown in

Table 2. Parameters setting.

Parameters	Value
Population size	126
Number of iterations	50
Crossover probability	0.8
Initial mutation probability	0.5

.

5.2. Comparison with Other Algorithms

To demonstrate the effectiveness and feasibility of the SV-MA algorithm in solving high-dimensional Ma-OFJSSP, we choose PICEAG, SPEA2, NSGA-Ⅱ, and NSGA-Ⅲ as comparison algorithms [38,39,40,41].

To guarantee the fair comparison, the time iteration stop condition is applied in each algorithm. Firstly, we run NSGA-Ⅱindependently 10 times for all instances. With 50 iterations as the stop criterion, the computation time of each instance is saved. The average computation time of each instance is shown in

Table 3. The average calculation time of each benchmark.

Instances	Average Time (s)
FMK01	9.5149
FMK02	10.0694
FMK03	17.9803
FMK04	12.3134
FMK05	13.6289
FMK06	18.6108
FMK07	13.7169
FMK08	24.9126
FMK09	26.7579
FMK10	26.8914

. This average time is used as the iteration stop condition of each optimization method on the instance.

Table 4. Statistical values of IGD.

Problems	NSGA-Ⅱ		NSGA-Ⅲ		PICEAg		SPEA2		SV-MA
	Mean	p-Value	Mean	p-Value	Mean	p-Value	Mean	p-Value	Mean
FMk01	26.6696	5.4940 × 10−11	16.3373	4.4591 × 10−4	28.4832	9.9186 × 10−11	44.6132	3.0198 × 10−11	12.0134
FMk02	19.1202	4.5043 × 10−11	10.4509	5.8737 × 10−4	20.7576	1.3288 × 10−10	38.6129	3.0198 × 10−11	8.4422
FMk03	1.5565 × 102	1.8567 × 10−9	96.1612	0.0251	1.7602 × 102	3.4741 × 10−10	2.0854 × 102	7.3890 × 10−11	87.8403
FMk04	28.4973	5.5726 × 10−10	20.8074	0.0251	44.1646	3.0198 × 10−11	74.4926	3.0198 × 10−11	17.9809
FMk05	76.1421	8.9934 × 10−11	39.9149	3.0058 × 10−4	1.0007 × 102	4.0771 × 10−11	1.2460 × 102	4.5043 × 10−11	27.6451
FMk06	84.3526	9.9186 × 10−11	30.3240	0.0035	54.7412	9.9186 × 10−11	81.3184	3.6897 × 10−11	25.1816
FMk07	1.8901 × 102	3.0198 × 10−11	47.9071	0.1761	1.0161 × 102	1.7769 × 10−10	2.3583 × 102	3.0198 × 10−11	43.0390
FMk08	2.7167 × 102	1.5465 × 10−9	1.4601 × 102	4.7444 × 10−6	3.0356 × 102	9.9186 × 10−11	5.2723 × 102	3.0198 × 10−11	95.9897
FMk09	3.9634 × 102	1.1737 × 10−9	2.3064 × 102	0.0030	4.6503 × 102	4.6159 × 10−10	7.4004 × 102	3.0198 × 10−11	1.5095 × 102
FMk10	2.8435 × 102	2.3714 × 10−10	1.4794 × 102	0.0033	3.5743 × 102	9.9186 × 10−11	4.1620 × 102	3.0198 × 10−11	1.1393 × 102

and

Table 5. Statistical values of HV.

Problems	NSGA-Ⅱ		NSGA-Ⅲ		PICEAg		SPEA2		SV-MA
	Mean	p-Value	Mean	p-Value	Mean	p-Value	Mean	p-Value	Mean
FMk01	0.0029	4.5043 × 10−11	0.0046	3.9881 × 10−4	0.0032	2.0152 × 10−8	0.0015	3.0198 × 10−11	0.0059
FMk02	0.0020	3.6897 × 10−11	0.0041	0.0339	0.0022	1.5580 × 10−8	6.6089× 10−4	3.0198 × 10−11	0.0047
FMk03	0.0030	4.9751 × 10−11	0.0042	1.1057 × 10−4	0.0033	1.5465 × 10−9	0.0023	3.0198 × 10−11	0.0049
FMk04	0.0025	5.4940 × 10−11	0.0033	0.0099	0.0022	1.3288 × 10−10	0.0012	3.0198 × 10−11	0.0038
FMk05	4.2994 × 10−4	3.6897 × 10−11	6.6402 × 10−4	0.1413	4.3955 × 10-4	2.8715 × 10−10	2.71944 × 10−4	3.0198 × 10−11	6.9968×10−4
FMk06	0.0022	4.5043 × 10−11	0.0066	0.5106	0.0033	1.7769 × 10−10	0.0020	3.0198 × 10−11	0.0069
FMk07	4.1903 × 10−4	3.0198 × 10−11	0.0014	0.0103	7.2393 × 10-4	9.9186 × 10−11	2.3731 × 10−4	3.0198 × 10−11	0.0017
FMk08	3.6886 × 10−4	3.3383 × 10−11	5.4561 × 10−4	0.0023	3.7335 × 10-4	4.9751 × 10−11	2.2745 × 10−4	3.0198 × 10−11	6.2285×10−4
FMk09	4.6042 × 10−4	3.0198 × 10−11	6.8530 × 10−4	0.0032	4.1952 × 10-4	5.4940 × 10−11	2.3996 × 10−4	3.0198 × 10−11	8.0475×10−4
FMk10	6.9971 × 10−4	7.3890 × 10−11	0.0010	8.5641 × 10−4	6.3220 × 10-4	1.3288 × 10−10	4.5766 × 10−4	3.0198 × 10−11	0.0012

, respectively show the mean value of IGD metric and HV metric, and the p value of the rank sum test obtained by running each method 30 times on FJSSP benchmark instances. In Table 4 and Table 5, values that are significantly better than other methods are showed in bold.

$$IGD\left(P^{*},P\right)=\frac{{\displaystyle {\sum }_{x\in P^{*}}\min dis\left(x,P\right)}}{\left|P^{*}\right|}$$

(16)

$$HV=\delta \left({\cup }_{i=1}^{\left|S\right|}{v}_i\right)$$

(17)

The proposed memetic algorithm SV-MA combines the improved strength Pareto evolution method and the variable neighborhood search method. In order to effectively distinguish the better solutions and increase the selection pressure of non-dominated solutions, the SV-MA optimization method adopts the new fitness calculation method that is different from the concept of dominance. Fitness of individual $I$ can be expressed as the proportion of the total number of other individuals which were dominated by individual $I$. It can realize the effective differentiation of population individuals.

Meanwhile, SV-MA algorithm integrates the fitness calculation method based on the shift-based density estimation strategy, so that the individual fitness can reflect individual distribution information and convergence information. The balance of convergence and diversity are maintained in the process of population evolution. To effectively prevent the optimization process from falling into local convergence, the neighborhood search is performed for the individuals of offspring population according to the local search probability. This paper adopts the following two neighborhood structures: the critical operation neighborhood search based on a key block and double-layer neighborhood search, based on critical operation. These two neighborhood structures combine the scheduling domain knowledge, and make the neighborhood search more targeted and efficient. The proposed neighborhood search method can avoid the blind search of an individual neighborhood, and improve the convergence and diversity of population.

However, with the increase in the number of objectives, the proportion of non-dominated solutions in the population increases rapidly. NSGA-Ⅲ and NSGA-Ⅱ methods use dominance relationship to select non-dominated solutions. For solving the high-dimensional Ma-OFJSSP, it cannot effectively distinguish the better individuals. Therefore, the proposed SV-MA optimization method can effectively solve the high-dimensional Ma-OFJSSP.

In order to further study the computational performance of SV-MA method in the process of population optimization, FMK02 instances are randomly chosen. Each algorithm, respectively, solves the benchmark instances.

For FMK02 benchmark, the feasibility of high-dimensional Ma-OFJSSP model and SV-MA optimization method are analyzed in detail.

The five optimization decision-making methods separately solve the FMK02 benchmark examples once. After the optimization of each algorithm, a group of non-dominated solution sets will be obtained. We count the mean and min values of each scheduling optimization objective in the non-dominated solution sets, as shown in

Table 6. Statistical values of non-dominated solution set.

Algorithms	Objectives	Min Value	Mean Value
PICEAg	makespan	47	53.0396
	delay time	41.4000	85.2507
	equipment load	204	212.6190
	energy consumption	57.2198	60.4310
	manufacturing quality	6.2480	6.6280
NSGA-Ⅱ	makespan	47	52.4444
	delay time	53.4	84.0888
	equipment load	198	201
	energy consumption	55.0101	57.4869
	manufacturing quality	6.0276	6.5410
NSGA-Ⅲ	makespan	46	58.8650
	delay time	33	125.0476
	equipment load	187	208.7857
	energy consumption	52.9481	62.1223
	manufacturing quality	5.9057	6.6268
SPEA2	makespan	53	62.4285
	delay time	71	145.1714
	equipment load	200	211
	energy consumption	57.4716	62.9731
	manufacturing quality	6.5655	6.6878
SV-MA	makespan	46	56.5555
	delay time	34.8000	106.6397
	equipment load	186	213.3175
	energy consumption	51.9160	60.8999
	manufacturing quality	5.8034	6.4938

.

After solving FMK02 benchmark by SV-MA optimization method, a set of non-dominated solution sets will be obtained. The best compromise solution will be obtained by fuzzy decision method, as shown in

Table 7. The best compromise solution.

Algorithm	Makespan	Delay Time	Equipment Load	Energy Consumption	Processing Quality
SV-MA	46	38.6000	195	51.9160	6.7702
PICEAg	47	41.4000	211	57.2198	6.8144
SPEA2	55	136	202	57.4716	6.6606
NSGA-Ⅲ	47	53.4000	194	53.4980	6.8788
NSGA-Ⅱ	47	53.4000	201	55.0101	6.5967

. The best compromise solution is the production scheduling scheme of FMK02 benchmark.

For FMK02 benchmark, Figure 4 shows the production scheduling scheme optimized by the SV-MA method.

5.3. Engineering Case—The Component Production Factory

The component manufacturing workshop of an enterprise belongs to a typical flexible job shop [42]. The manufacturing workshop has eight sets of equipment. At present, there are eight workpieces to be processed. The processing time and unqualified rate of each operation on different equipment are shown in

Table 8. The component information.

Workpiece	Operation	Processing Time (min)/Processing Quality								Date of Delivery/Min
		M1	M2	M3	M4	M5	M6	M7	M8
1	$O_{11}$	4/0.05	9/0.12	-	8/0.06	5/0.15	-	10/0.1	-	40
	$O_{12}$	-	4/0.18	3/0.07	-	-	5/0.11	-	2/0.15
	$O_{13}$	-	3/0.07	-	5/0.08	-	8/0.11	4/0.09	-
	$O_{14}$	6/0.13	-	5/0.08	-	7/0.07	-	8/0.09	-
2	$O_{21}$	9/0.08	7/0.11	-	2/0.13	-	10/0.16	-	5/0.09	35
	$O_{22}$	-	4/0.06	-	3/0.08	8/0.14	-	9/0.14	-
	$O_{23}$	3/0.07	-	7/0.09	-	-	9/0.13	-	-
	$O_{24}$	-	10/0.17	-	-	5/0.07	-	7/0.14	-
3	$O_{31}$	8/0.09	8/0.07	-	-	-	12/0.14	-	11/0.06	35
	$O_{32}$	1/0.17	-	8/0.07	-	4/0.13	-	11/0.09	-
	$O_{33}$	-	6/0.14	-	5/0.08	-	11/0.09	-	-
	$O_{34}$	-	4/0.12	-	7/0.13	-	-	12/0.07	-
4	$O_{41}$	-	2/0.07	4/0.05	-	7/0.14	-	-	9/0.09	40
	$O_{42}$	4/0.11	-	7/0.07	-	-	9/0.13	-	-
	$O_{43}$	5/0.14	-	-	8/0.09	-	-	3/0.16	-
	$O_{44}$	-	3/0.07	-	-	8/0.09	-	5/0.11	-
5	$O_{51}$	7/0.07	-	9/0.11	-	-	8/0.13	-	-	50
	$O_{52}$	-	4/0.11	-	7/0.13	-	5/0.09	-	9/0.12
	$O_{53}$	4/0.05	6/0.07	-	-	9/0.11	-	10/0.06	-
	$O_{54}$	-	-	5/0.12	4/0.11	-	-	-	-
6	$O_{61}$	6/0.09	7/0.07	-	-	11/0.09	-	8/0.11	-	30
	$O_{62}$	-	-	3/0.08	-	-	8/0.13	-	7/0.14
	$O_{63}$	-	3/0.09	-	8/0.11	-	-	7/0.07	-
	$O_{64}$	10/0.13	-	2/0.07	-	9/0.06	-	-	-
7	$O_{71}$	-	5/0.07	-	-	7/0.12	7/0.13	-	-	36
	$O_{72}$	4/0.09	3/0.07	-	7/0.15	-	-	2/0.11	-
	$O_{73}$	2/0.08	-	-	1/0.05	3/0.06	-	-	6/0.11
	$O_{74}$	-	-	8/0.08	-	4/0.11	3/0.17	-	-
8	$O_{81}$	8/0.06	-	4/0.11	-	-	-	10/0.05	-	40
	$O_{82}$	10/0.06	4/0.07	-	3/0.13	-	11/0.04	-	-
	$O_{83}$	-	-	2/0.18	-	5/0.14	-	11/0.10	4/0.08
	$O_{84}$	-	7/0.06	-	8/0.11	-	9/0.13	-	6/0.11

.

The operating power of each item of equipment is modified in the manufacturing workshop. The operating and no-load power of each machine are shown in

Table 9. The equipment information.

Equipment Number	Operating/No-Load Power (kW)
M1	0.37/1.278
M2	0.35/1.024
M3	0.43/0.967
M4	0.32/1.120
M5	0.41/0.935
M6	0.33/1.356
M7	0.34/1.212
M8	0.39/1.048

. The fixed power of the workshop is 10 kW. The unqualified rate of different operations is randomly set.

The production scheduling scheme of the component manufacturing workshop is obtained by the proposed many-objective scheduling model and SV-MA optimization decision method.

Table 10. The best compromise solution of the engineering case.

Optimization Objective	Makespan	Energy Consumption	Equipment Load	Delay Time	Manufacturing Quality
Value	34	8.70	143	0	3.09

shows the best compromise solution.

Through engineering production examples, the competitiveness and feasibility of the designed model and SV-MA method are demonstrated. The Ma-OFJSSP is effectively solved. Figure 5 shows the production scheduling scheme optimized by the SV-MA method.

6. Conclusions

To reduce energy consumption, improve the production operation capacity and processing quality of the enterprise, the high-dimensional Ma-OFJSSP is studied. However, the existing optimization method are difficult to effectively optimize the Ma-OFJSSP. Firstly, the many-objective production scheduling model is established, and the SV-MA optimization method is proposed. The memetic algorithm combines an improved strength Pareto evolution method and the variable neighborhood search method. In the comparison experiment of optimization algorithms, the feasibility and effectiveness of the proposed SV-MA algorithm are demonstrated. The SV-MA optimization method designs the variable neighborhood strategy which combines with scheduling knowledge. The critical operation neighborhood search based on key block and the double-layer neighborhood search based on critical operation are de-signed to effectively avoid the optimization process from falling into local convergence. To effectively distinguish the better solutions, the new fitness calculation method is adopted. Meanwhile, the shift-based density estimation (SDE) strategy is introduced into the fitness calculation method. Individual fitness can reflect individual distribution information and convergence information.

Finally, in the machining workshop engineering case, the SV-MA method can ensure that the flexible job shop can obtain a high-quality many-objective production scheduling scheme which can improve production efficiency and reduce energy consumption in the production process. The proposed model and SV-MA optimization algorithm are conducive to achieve intelligent manufacturing and green manufacturing.

For future research, we will consider material transportation and equipment failures in the FJSSP model. By optimizing the integrated scheduling model, the production scheduling scheme is more in line with actual production.