# A Mathematical Model and Self-Adaptive NSGA-II for a Multiobjective IPPS Problem Subject to Delivery Time

Authors: Li Ba; Mingshun Yang; Xinqin Gao; Yong Liu; Zhoupeng Han; Erbao Xu; Yan Li
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

Process planning and scheduling are two important components of manufacturing systems. This paper deals with a multiobjective just-in-time integrated process planning and scheduling (MOJIT-IPPS) problem. Delivery time and machine workload are considered to make IPPS problem more suitable for manufacturing environments. The earliness/tardiness penalty, maximum machine workload, and total machine workload are objectives that are minimized. The decoding method is a crucial part that significantly influences the scheduling results. We develop a self-adaptive decoding method to obtain better results. A nondominated sorting genetic algorithm with self-adaptive decoding (SD-NSGA-II) is proposed for solving MOJIT-IPPS. Finally, the model and algorithm are proven through an example. Furthermore, different scale examples are tested to prove the good performance of the proposed method.


---

## Body

## 1. Introduction

Process planning and scheduling are two crucial parts in manufacturing industries. They are commonly performed independently in serial mode [1, 2]. In the product design stage, process planning is used to determine the raw materials, machine tools, and process routes. In the scheduling stage, machines are scheduled according to the results from process planning [3]. The independent and serial modes of the two subsystems may lead to unrealistic process routes, uneven resource utilization, and bottlenecks in scheduling [4].In recent years, IPPS problems have gradually become a research focus around the world. The integration of process planning and scheduling is an effective way to eliminate resource conflicts, decrease the flow time of workpieces, improve machine utilization, and reduce the production cycle [3].Currently, the basic IPPS problem, which considers makespan as an objective, has been a research focus in production scheduling. With the continuous attention of the whole society on energy conservation and waste elimination, just-in-time production has become the general consensus of modern manufacturing enterprises [5]. Delivery time is a key factor that has been considered in real production. Moreover, there are other important consideration factors in addition to the time factor. Therefore, it is difficult to meet actual production demand if optimization is based only on a single objective.In conclusion, to make IPPS problems more in line with real manufacturing situations, this paper focuses on a MOJIT-IPPS problem. The earliness/tardiness penalty, maximum machine workload, and total machine workload are regarded as objectives. A mathematical model of the MOJIT-IPPS problem is established. The decoding method is an important part that influences the JIT scheduling solution. Given the complexity of the problem, a SD-NSGA-II is proposed for the problem. Finally, the model and algorithm are proven through several examples.This paper initially provides a literature review related to IPPS problems inSection 2. A mathematical model of MOJIT-IPPS is established in Section 3. SD-NSGA-II is designed in Section 4. Computational results are analysed in Section 5. The paper ends with some conclusions in Section 6.


## 2. Literature Review

Researchers began studying the IPPS problem in the 1980s [6]. The basic IPPS problem can be defined as follows [7]: “given a set of n parts that are to be processed on m machines with operations including alternative manufacturing resources, select suitable manufacturing resources, and sequences of operations to determine a schedule in which the precedence constraints among operations can be satisfied and the corresponding objectives can be achieved.”Compared to the job shop scheduling problem (JSP) and flow shop scheduling problem (FSP), the IPPS problem has a larger solution space and is more complex because of flexibilities in process routes and machines. This problem has been identified as NP-hard [8]. Currently, an increasing number of studies have focused on the IPPS problem. Algorithm improvement is a research direction of IPPS. Many researchers have proposed advanced algorithms for improving the quality of solutions. In addition, more factors in real production have been considered in the basic IPPS problem to make it more realistic. Therefore, we summarized these studies in two aspects: algorithm improvement and problem improvement.


### 2.1. Improvement of Algorithms

Li et al. [1] proposed a novel hybrid algorithm based on particle swarm optimization (PSO) and a genetic algorithm (GA) for an IPPS problem with an uncertain processing time. Several different sizes of examples were involved to demonstrate the algorithm. Petrovic et al. [3] used an AND/OR graph to express flexible process plans. An algorithm based on a PSO and chaos theory was proposed to solve an IPPS problem. The advantage of the algorithm was proven by comparing it with a GA and a simulated annealing algorithm (SAA) through a set of examples. Seker et al. [8] proposed a hybrid heuristic algorithm based on a GA and artificial neural network (ANN) to solve an IPPS problem. A clustered chromosome structure was designed to improve the algorithm performance. Yin et al. [9] proposed an improved GA for solving a dynamic IPPS problem with consideration of machine breakdown and new job arrival. Zhang et al. [10] proposed an object-coding GA to solve an IPPS problem. An effective object-coding representation was designed, and experiments showed good performance of the algorithm. Jain et al. [11] proposed a simulation-based GA to solve an IPPS problem. A regeneration scheme was embedded in the algorithm to prevent premature convergence. Phanden et al. [12] established an IPPS model composed of a process route selection module, scheduling module, analysis module, and process route modification module. A GA was designed to solve the model. Li [13] proposed an active learning GA to solve an IPPS problem. The algorithm was proven to be a promising and effective method through experimental results. Lian et al. [14] proposed an imperialist competitive algorithm (ICA) to solve an IPPS problem. The performance of the ICA was evaluated on four sets of experiments. Özgüven et al. [15] proposed a mixed-integer linear programming model for an IPPS problem. Several examples were introduced and the results showed the superiority of the model. Zhou et al. [16] proposed a game-theoretic approach for generating optimal process plans for multiple jobs in networked manufacturing.


### 2.2. Improvement of Problems

Zhang et al. [2] studied an extended IPPS problem in a cloud manufacturing context, and they proposed three frameworks to cope with IPPS. Zhang [17] proposed an IPPS problem in a remanufacturing context and designed a simulation-based GA for the problem. Shokouhi [18] proposed and studied an IPPS problem considering precedence constraints, and a GA was designed for the problem. Xia et al. [19] proposed a dynamic IPPS problem with consideration of machine breakdown and new job arrival, and a model of the problem was established. A hybrid GA with variable neighbourhood search (VNS) was designed to solve the problem. Multiple objectives are considered in IPPS problem and studied by Manupati et al. [20, 21]. They proposed some novel algorithms for solving the problem.Currently, energy conservation and environmental protection have reached a consensus in many countries. Energy consumption has become a critical aspect in industries. Zhang et al. [22] established an IPPS model with total energy consumption as the objective. A GA-based approach was proposed to solve the problem. Dai et al. [23] created a mathematical model of an IPPS problem. Energy consumption and makespan were two objectives to be minimized. A modified GA was adopted to explore the optimal solution between the two objectives.In real production, all processes may not be able to be processed in the same workshop due to different process types. Transportation is another factor that must be considered in some real production environments. For this aspect, Manupati et al. [4, 24] considered transportation in IPPS and proposed algorithms to solve extended problems.Presently, on the one hand, the JIT production mode has become the general consensus of manufacturing enterprises. Each order should be completed on time. Many workshop scheduling problems consider delivery time, such as the JSP [25, 26], FSP [27, 28], parallel-machine scheduling problem (PMSP) [5, 29], and single-machine scheduling problem [30, 31]. On the other hand, machine workload is another key indicator in workshop scheduling.Based on the above literature, this paper considers delivery time in the IPPS problem to make it more in line with actual production. A mathematical model of the MOJIT-IPPS problem is established. The earliness/tardiness penalty, maximum machine workload, and total machine workload are objectives that are minimized.The decoding method is a critical module that influences the JIT scheduling solution. Due to the complexity of MOJIT-IPPS, this paper proposes a self-adaptive decoding method for MOJIT-IPPS. An NSGA-II with the self-adaptive decoding method is designed. The effectiveness of the proposed approach is demonstrated through a set of different scale examples by comparison with another decoding method.


## 2.1. Improvement of Algorithms

Li et al. [1] proposed a novel hybrid algorithm based on particle swarm optimization (PSO) and a genetic algorithm (GA) for an IPPS problem with an uncertain processing time. Several different sizes of examples were involved to demonstrate the algorithm. Petrovic et al. [3] used an AND/OR graph to express flexible process plans. An algorithm based on a PSO and chaos theory was proposed to solve an IPPS problem. The advantage of the algorithm was proven by comparing it with a GA and a simulated annealing algorithm (SAA) through a set of examples. Seker et al. [8] proposed a hybrid heuristic algorithm based on a GA and artificial neural network (ANN) to solve an IPPS problem. A clustered chromosome structure was designed to improve the algorithm performance. Yin et al. [9] proposed an improved GA for solving a dynamic IPPS problem with consideration of machine breakdown and new job arrival. Zhang et al. [10] proposed an object-coding GA to solve an IPPS problem. An effective object-coding representation was designed, and experiments showed good performance of the algorithm. Jain et al. [11] proposed a simulation-based GA to solve an IPPS problem. A regeneration scheme was embedded in the algorithm to prevent premature convergence. Phanden et al. [12] established an IPPS model composed of a process route selection module, scheduling module, analysis module, and process route modification module. A GA was designed to solve the model. Li [13] proposed an active learning GA to solve an IPPS problem. The algorithm was proven to be a promising and effective method through experimental results. Lian et al. [14] proposed an imperialist competitive algorithm (ICA) to solve an IPPS problem. The performance of the ICA was evaluated on four sets of experiments. Özgüven et al. [15] proposed a mixed-integer linear programming model for an IPPS problem. Several examples were introduced and the results showed the superiority of the model. Zhou et al. [16] proposed a game-theoretic approach for generating optimal process plans for multiple jobs in networked manufacturing.


## 2.2. Improvement of Problems

Zhang et al. [2] studied an extended IPPS problem in a cloud manufacturing context, and they proposed three frameworks to cope with IPPS. Zhang [17] proposed an IPPS problem in a remanufacturing context and designed a simulation-based GA for the problem. Shokouhi [18] proposed and studied an IPPS problem considering precedence constraints, and a GA was designed for the problem. Xia et al. [19] proposed a dynamic IPPS problem with consideration of machine breakdown and new job arrival, and a model of the problem was established. A hybrid GA with variable neighbourhood search (VNS) was designed to solve the problem. Multiple objectives are considered in IPPS problem and studied by Manupati et al. [20, 21]. They proposed some novel algorithms for solving the problem.Currently, energy conservation and environmental protection have reached a consensus in many countries. Energy consumption has become a critical aspect in industries. Zhang et al. [22] established an IPPS model with total energy consumption as the objective. A GA-based approach was proposed to solve the problem. Dai et al. [23] created a mathematical model of an IPPS problem. Energy consumption and makespan were two objectives to be minimized. A modified GA was adopted to explore the optimal solution between the two objectives.In real production, all processes may not be able to be processed in the same workshop due to different process types. Transportation is another factor that must be considered in some real production environments. For this aspect, Manupati et al. [4, 24] considered transportation in IPPS and proposed algorithms to solve extended problems.Presently, on the one hand, the JIT production mode has become the general consensus of manufacturing enterprises. Each order should be completed on time. Many workshop scheduling problems consider delivery time, such as the JSP [25, 26], FSP [27, 28], parallel-machine scheduling problem (PMSP) [5, 29], and single-machine scheduling problem [30, 31]. On the other hand, machine workload is another key indicator in workshop scheduling.Based on the above literature, this paper considers delivery time in the IPPS problem to make it more in line with actual production. A mathematical model of the MOJIT-IPPS problem is established. The earliness/tardiness penalty, maximum machine workload, and total machine workload are objectives that are minimized.The decoding method is a critical module that influences the JIT scheduling solution. Due to the complexity of MOJIT-IPPS, this paper proposes a self-adaptive decoding method for MOJIT-IPPS. An NSGA-II with the self-adaptive decoding method is designed. The effectiveness of the proposed approach is demonstrated through a set of different scale examples by comparison with another decoding method.


## 3. Mathematical Model of MOJIT-IPPS

There are different jobs that must be processed in a workshop. All jobs should be finished according to the delivery time. Each job can be processed through more than one process route, and each process can be processed by more than one machine. Under these conditions, the earliness/tardiness penalty, maximum machine workload, and total machine workload are regarded as the objectives. An optimal solution is obtained by choosing process routes, choosing machines, and sorting process sequences for each job.Based on the above description, a MOJIT-IPPS model is proposed. The following parameters are defined to establish the model for the problem:(i)
n: number of jobs.(ii)
m: number of machines.(iii)
p: number of process routes.(iv)
Rk: process route k, k∈1,p.(v)
psk: number of processes of Rk.(vi)
TMSj: available starting time of machine j, j∈1,m.(vii)
TSJikvj: Rk is chosen for job i, starting time on machine j of the vth process, i∈1,n, v∈1,psk.(viii)
TMJikvj: Rk is chosen for job i, process time on machine j of the vth process.(ix)
TFFJi: the final completion time of job i.(x)
TJDi: delivery time of job i.(xi)
WLMj: workload of machine j.(xii)
RJPik: Boolean variable representing the relationship between a job and process route. If Rk is chosen for job i, the variable is equal to 1; otherwise, it is 0.(xiii)
RPMkvj: Boolean variable representing the relationship between a process route and machine. If the vth process of Rk is processed on machine j, the variable is equal to 1; otherwise, it is 0.Based on the above parameters, the earliness/tardiness penalty, maximum machine workload, and total machine workload are considered the objectives. The objective functions are established as follows.The earliness/tardiness penalty is minimized:(1)Min∑i=1nTJDi−TFFJi.The maximum machine workload is minimized:(2)MinMaxWLMj.The total machine workload is minimized:(3)Min∑j=1mWLMj,where(4)WLMj=∑i=1n∑k=1p∑v=1pskRJPik⋅RPMkvj⋅TMJikvj,i∈1,n,j∈1,m,k∈1,pandv∈1,psk.The following constraints are considered in the model:


### 3.1. One Machine Can Only Perform One Process on a Job at a Time

If time starts att,(5)RJPik⋅RPMkv′j=1.Then, during time slott,t+TMJikv′j,(6)∑v=1pskRJPik⋅RPMkvj=1,where v′∈1,psk.


### 3.2. One Process Cannot Be Performed by More than One Machine

If time starts att,(7)RJPik⋅RPMkvj′=1.Then, during time slott,t+TMJikvj′,(8)∑j=1mRJPik⋅RPMkvj=1,where j′∈1,m.


### 3.3. The Job Is Processed Strictly according to the Process Sequence, and the Starting Time of Each Process Cannot Be Earlier than the Available Starting Time of the Machine That Is Chosen to Complete the Process

AssumingRJPik=1 and RJPik⋅RPMkv′j=1, RJPik⋅RPMkv′−1j′=1. Currently, the v′th process of job i will be performed; then,(9)TSJikv′j=TMSj,TMSj≥TFJikv′−1j,TFJikv′−1j′,TMSj<TFJikv′−1j,where v′∈2,psk.According to constraint (3), the related parameters are updated by the following equation.The completion time of thev′th process of job i is calculated as follows:(10)TFJikv′j=TSJikv′j+TMJikv′j.The available starting time of machinej is updated as follows:(11)TMSj=TFJikv′j.Ifv′=psk, TFFJi is updated as follows:(12)TFFJi=TFJikv′j.Equations (1)–(3) show the objectives that will be minimized. The workload of each machine is calculated by equation (4). The relationships between processes and machines are constrained through equations (5)–(8) to ensure the rationality of the manufacturing process. The starting time of each process is calculated by equation (9); the completion time of each process is calculated by equation (10); the available starting time of each machine is calculated by equation (11); and the final completion time of each job is calculated by equation (12).


## 3.1. One Machine Can Only Perform One Process on a Job at a Time

If time starts att,(5)RJPik⋅RPMkv′j=1.Then, during time slott,t+TMJikv′j,(6)∑v=1pskRJPik⋅RPMkvj=1,where v′∈1,psk.


## 3.2. One Process Cannot Be Performed by More than One Machine

If time starts att,(7)RJPik⋅RPMkvj′=1.Then, during time slott,t+TMJikvj′,(8)∑j=1mRJPik⋅RPMkvj=1,where j′∈1,m.


## 3.3. The Job Is Processed Strictly according to the Process Sequence, and the Starting Time of Each Process Cannot Be Earlier than the Available Starting Time of the Machine That Is Chosen to Complete the Process

AssumingRJPik=1 and RJPik⋅RPMkv′j=1, RJPik⋅RPMkv′−1j′=1. Currently, the v′th process of job i will be performed; then,(9)TSJikv′j=TMSj,TMSj≥TFJikv′−1j,TFJikv′−1j′,TMSj<TFJikv′−1j,where v′∈2,psk.According to constraint (3), the related parameters are updated by the following equation.The completion time of thev′th process of job i is calculated as follows:(10)TFJikv′j=TSJikv′j+TMJikv′j.The available starting time of machinej is updated as follows:(11)TMSj=TFJikv′j.Ifv′=psk, TFFJi is updated as follows:(12)TFFJi=TFJikv′j.Equations (1)–(3) show the objectives that will be minimized. The workload of each machine is calculated by equation (4). The relationships between processes and machines are constrained through equations (5)–(8) to ensure the rationality of the manufacturing process. The starting time of each process is calculated by equation (9); the completion time of each process is calculated by equation (10); the available starting time of each machine is calculated by equation (11); and the final completion time of each job is calculated by equation (12).


## 4. SD-NSGA-II for MOJIT-IPPS

Based on the description and modelling of the above problem, the MOJIT-IPPS problem is NP-hard. Deb et al. [32] proposed NSGA-II in 2002. To date, the algorithm has been applied to solve many multiobjective optimization problems. Considering the complexity and discreteness of the MOJIT-IPPS problem, this study proposes a SD-NSGA-II to solve the problem.


### 4.1. Encoding

A four-layer encoding structure is proposed to construct solutions. The structure consists of four layers: the workpiece, machine, process time, and process route. An example of the encoding structure of MOJIT-IPPS is provided in Table1.Table 1
Sample coding of MOJIT-IPPS
JiCode of the workpiece21212212MjCode of the machine42143112TMJikvjProcess time of the workpiece0.80.90.71.310.61.10.7RkCode of the process route32123123In Table1, for example, the codes in the first column mean that R3 is adopted for J2. Because the code “2” first appears in the workpiece layer, this code represents the first process of J2. M4 is chosen to complete this process. The process time is 0.8, and so on.


### 4.2. Decoding

Decoding is a key step that influences solutions. The semiactive decoding method is commonly used for many basic workshop scheduling problems where the makespan is the objective to be minimized, such as the basic JSP, FSP, and IPPS. However, this method is not suitable for MOJIT-IPPS because delivery time is taken into account. To improve the decoding performance, this paper proposes a self-adaptive decoding method for MOJIT-IPPS. We divide the method into three parts: active decoding, self-adaptive operation for solutions, and reverse active decoding.


#### 4.2.1. Part 1: Active Decoding

Compared with semiactive decoding, active decoding is more effective in compressing the completion time of each workpiece. A sample coding is shown in Table2. Two workpieces will be processed on two machines. Two processes will be performed for each workpiece. Sample coding is decoded from the first column to the end. A comparison between these two decoding methods is shown in Figure 1 (DT: delivery time).Table 2
Sample coding.
Ji2211Mi2112TMJikvj4322Figure 1
Comparison between semiactive decoding and active decoding. (a) Result by semiactive decoding. (b) Result by active decoding.If using semiactive decoding, processes will be performed according to start time of machines only. For example, the second process ofJ2 will be carried out by M1. When this process is finished on M1, the start time of M1 is updated to seven and the first process of J1 will be started at this time. However, M1 is idle from time zero to four. The first process of J1 can be performed during this time interval.Therefore, for reducing finished time of each workpiece, we adopt active decoding instead of semiactive decoding. Before introducing this decoding method, some parameters are defined as follows:(i)
SC: a sample coding that will be decoded(ii)
Lsc: the number of columns of SC(iii)
Jobk: the workpiece in the kth column of SC, k=1,2,…,Lsc(iv)
Machk: the machine in the kth column of SC(v)
Ts (Machk): the earliest start time of Machk;(vi)
Nop (Jobk): the number of processes of JobkSupposing that thekth column represents the vth process of Jobk, the steps of active decoding are as follows:(i)
Step 1: set countersk=1andf=0.(ii)
Step 2: check the idle time and work time of Machk from time zero to Ts (Machk); if exiting an idle time segment, f=f+1.(iii)
Step 3: iff > 0, go to Step 4; otherwise, go to Step 6.(iv)
Step 4: set a counterg=0. If the vth process of Jobk can be carried out in the gth idle time segment, then deal with this process in the idle time segment, and go to Step 7; otherwise, g=g+1, and go to Step 5.(v)
Step 5: ifg>f, go to Step 6; otherwise, go to Step 4.(vi)
Step 6: perform thevth process of Jobk at time Ts (Machk).(vii)
Step 7:k=k+1.(viii)
Step 8: ifk>Lsc, active decoding for SC is completed; otherwise, go to Step 2.


#### 4.2.2. Part 2: Self-Adaptive Operation for Solutions

The solution of all processes of workpieces must be adjusted to correct the location of each column. If not, the completion time will be extended, and workpieces may be finished late in reverse active decoding. A comparison is shown in Figure2.Figure 2
Comparison before and after self-adaptive operation.To present the flow of self-adaptive operation, “TScn” is defined as a set,TScn=TScn1,TScn2,…,TScnLsc. For example, “TScn1” denotes the start time of the process and is located in the first column of SC.The steps of self-adaptive operation are as follows:(i)
Step 1: make a copy of SC, named SCTem, and clear all columns of SCTem(ii)
Step 2: set a counteru = Lsc(iii)
Step 3: choose the maximum value in TScn, put the column that corresponds to this value into theuth column of SCTem, and clear this value in TScn(iv)
Step 4:u = u−1; if u is equal to zero, go to Step 5; otherwise, go to Step 3(v)
Step 5: replace SC with SCTem, and the self-adaptive operation for SC is completed


#### 4.2.3. Part 3: Reverse Active Decoding

In this part, solutions are decoded in reverse. The main decoding steps are same as those in part 1, but the start time of each workpiece is not equal to zero and each solution is decoded in reverse.The start time of workpieceh for reverse active decoding is denoted by “TSRevh.” The final completion time of workpiece h in part 1 is denoted by “TFFJh.” The delivery time of workpiece h is denoted by “TJDh.” TSRevh is calculated by the following equation:(13)TSRevh=MaxTFFJh,TJDh,h∈1,n.An example of reverse active decoding is shown in Figure3.Figure 3
An example of reverse active decoding.


### 4.3. Selection Operation

First, the Pareto dominance relationship is taken into consideration, each solution is ranked, and the rank of each solution is obtained. Second, the crowding distance of each solution is calculated. Finally, a crowded comparison operator is proposed. A tournament selection method is adopted to perform the selection operation.


#### 4.3.1. Ranking Operation

Before performing the ranking operation, the Pareto dominance relationship is defined as follows [33].Pareto dominance relationship: for a multiobjective minimization problem with N optimization objectives, assume a solution setP is composed of M individuals, P=x1,x2,…,xM. For any individual xi, the target value of the jth objective is fjxi. Then, if solution xu dominates solution xv, the following two conditions must be met:(1)
For any target valuesfk, fkxu≤fkxv(2)
∃k′,fk′xu<fk′xvwhere i,u,v∈1,M, j,k,k′∈1,N.The definition of the Pareto dominance relationship shows that if solutionxu dominates solution xv, solution xu is better than solution xv in the multiobjective minimization problem.Assuming that the population isP=x1,x2,…,xM, the rank set is Rank=rank1,rank2,…,rankM, and the number of individuals that dominate xii∈1,M is DN=dn1,dn2,…,dnM. Some variables are initialized as follows: rankh=−1, dnh=0, and h∈1,M. The ranking operation is shown in Figure 4.Figure 4
Flowchart of ranking operation.Figure4 shows that if solution xu dominates solution xv, the rank of xu is smaller than the rank of xv in the multiobjective minimization problem.


#### 4.3.2. Crowding Distance

In addition to rank, crowding distance is another important indicator. If the ranks of two individuals are equal, to maintain the diversity of the population, it is commonly believed that an individual with a larger crowding distance between the two individuals is a better individual [32].Assuming a multiobjective minimization problem, the number of optimization objectives isN, the population P is composed of M individuals, P=x1,x2,…,xM, and the crowding distance set is CD=cd1,cd2,…,cdM. The crowding distance of the jth target of xi is cdfij. The individual that is ranked one position before xi and the individual that is ranked one position behind xi are named xfront and xbehind, respectively. The individual with the maximum value of the jth target and the individual with the minimum value of the jth target are named xmax and xmin, respectively. Then, the crowding distance cdi of individual xi is calculated as the following two equations:(14)cdfij=fjxbehind−fjxfrontfjxmax−fjxmin,(15)cdi=∑j=1Ncdfij.


#### 4.3.3. Tournament Selection

Before tournament selection, a crowded comparison operator is defined as follows [32].Crowded comparison operator: for a multiobjective minimization problem with N optimization targets, assuming a solution setP is composed of M individuals, P=x1,x2,…,xM, the rank of solution xu is ranku, and the rank of solution xv is rankv. The crowding distances of solutions xu and xv are cdu and cdv, respectively. The notation of the crowded comparison operator is defined as “<”; then, xu<xv must meet the following condition (1) or (2):(1)
ranku<rankv(2)
ranku=rankv and cdu>cdvwhereu,v∈1,M.The crowded comparison operator shows that ifxu<xv, solution xu is better than xv.Based on the crowded comparison operator, tournament selection will be conducted for selecting individuals which will be crossed.


### 4.4. Crossover Operation

This paper adopts a precedence operation crossover (POX) operator [34] to crossover individuals. Assuming workpiece 2 will undergo crossover, an example of POX is shown in Figure 5.Figure 5
Crossover operation for MOJIT-IPPS.Because different process routes may be chosen for the same workpiece in different individuals, the same workpiece may have different numbers of operations in different individuals. Thus, the code length of generated individuals may be changed after crossover, as shown in Figure5.


### 4.5. Mutation Operation

Two kinds of mutation operators are adopted in SD-NSGA-II for the MOJIT-IPPS problem. First, swapping is performed on codes of two columns according to a swap probability. Two locations are generated randomly. The two columns of codes in the locations are exchanged. Second, single-point mutation is performed on the machine layer according to a single-point mutation probability.


### 4.6. Pareto Set

Assuming that the population size is equal toM, the number of iterations is equal to D. The following steps are adopted to construct a Pareto set:(i)
Step 1: initialize the Pareto set,PA=φ, and iteration counter e=0.(ii)
Step 2: the individuals of the first generationP are ranked, and the crowding distance of each individual is calculated.(iii)
Step 3: the selection, crossover, and mutation operations are performed on populationP, and then population P′ of the next generation is obtained.(iv)
Step 4: the temporary populationQ is established, Q=P∪P′.(v)
Step 5: the individuals of populationQ are ranked, and the crowding distance of each individual is calculated.(vi)
Step 6: each individual whose rank is equal to 1 in populationQ is compared with all individuals that belong to PA. If an individual is different from any individual in PA, it is added to PA.(vii)
Step 7:e++. If e<D, skip to Step 8; otherwise, skip to Step 9.(viii)
Step 8: the betterM individuals in population Q are chosen to form the new generation P; skip to Step 3.(ix)
Step 9:PA is ranked, and individuals whose ranks are larger than 1 are deleted. The Pareto set is formed.


### 4.7. Flowchart of SD-NSGA-II

To present the flowchart of SD-NSGA-II, some parameters are defined as follows:(i)
M: population size, controlling the number of individuals in the population.(ii)
CN: number of compared individuals, CN < M.(iii)
D: iterations, controlling the number of iterations of the algorithm.(iv)
Pc: crossover probability of the two selected individuals, decimals in (0, 1) interval.(v)
Pm: mutation probability of individuals, decimals in (0, 1) interval.(vi)
Pm1: probability that the swap operation is performed on codes of two columns of individuals, decimals in (0, 1) interval.(vii)
Pm2: probability that the single-point mutation is performed on the machine layer of the current individual, decimals in (0, 1) interval.A flowchart of SD-NSGA-II for the MOJIT-IPPS is shown in Figure6.Figure 6
Flowchart of SD-NSGA-II for MOJIT-IPPS.


## 4.1. Encoding

A four-layer encoding structure is proposed to construct solutions. The structure consists of four layers: the workpiece, machine, process time, and process route. An example of the encoding structure of MOJIT-IPPS is provided in Table1.Table 1
Sample coding of MOJIT-IPPS
JiCode of the workpiece21212212MjCode of the machine42143112TMJikvjProcess time of the workpiece0.80.90.71.310.61.10.7RkCode of the process route32123123In Table1, for example, the codes in the first column mean that R3 is adopted for J2. Because the code “2” first appears in the workpiece layer, this code represents the first process of J2. M4 is chosen to complete this process. The process time is 0.8, and so on.


## 4.2. Decoding

Decoding is a key step that influences solutions. The semiactive decoding method is commonly used for many basic workshop scheduling problems where the makespan is the objective to be minimized, such as the basic JSP, FSP, and IPPS. However, this method is not suitable for MOJIT-IPPS because delivery time is taken into account. To improve the decoding performance, this paper proposes a self-adaptive decoding method for MOJIT-IPPS. We divide the method into three parts: active decoding, self-adaptive operation for solutions, and reverse active decoding.


### 4.2.1. Part 1: Active Decoding

Compared with semiactive decoding, active decoding is more effective in compressing the completion time of each workpiece. A sample coding is shown in Table2. Two workpieces will be processed on two machines. Two processes will be performed for each workpiece. Sample coding is decoded from the first column to the end. A comparison between these two decoding methods is shown in Figure 1 (DT: delivery time).Table 2
Sample coding.
Ji2211Mi2112TMJikvj4322Figure 1
Comparison between semiactive decoding and active decoding. (a) Result by semiactive decoding. (b) Result by active decoding.If using semiactive decoding, processes will be performed according to start time of machines only. For example, the second process ofJ2 will be carried out by M1. When this process is finished on M1, the start time of M1 is updated to seven and the first process of J1 will be started at this time. However, M1 is idle from time zero to four. The first process of J1 can be performed during this time interval.Therefore, for reducing finished time of each workpiece, we adopt active decoding instead of semiactive decoding. Before introducing this decoding method, some parameters are defined as follows:(i)
SC: a sample coding that will be decoded(ii)
Lsc: the number of columns of SC(iii)
Jobk: the workpiece in the kth column of SC, k=1,2,…,Lsc(iv)
Machk: the machine in the kth column of SC(v)
Ts (Machk): the earliest start time of Machk;(vi)
Nop (Jobk): the number of processes of JobkSupposing that thekth column represents the vth process of Jobk, the steps of active decoding are as follows:(i)
Step 1: set countersk=1andf=0.(ii)
Step 2: check the idle time and work time of Machk from time zero to Ts (Machk); if exiting an idle time segment, f=f+1.(iii)
Step 3: iff > 0, go to Step 4; otherwise, go to Step 6.(iv)
Step 4: set a counterg=0. If the vth process of Jobk can be carried out in the gth idle time segment, then deal with this process in the idle time segment, and go to Step 7; otherwise, g=g+1, and go to Step 5.(v)
Step 5: ifg>f, go to Step 6; otherwise, go to Step 4.(vi)
Step 6: perform thevth process of Jobk at time Ts (Machk).(vii)
Step 7:k=k+1.(viii)
Step 8: ifk>Lsc, active decoding for SC is completed; otherwise, go to Step 2.


### 4.2.2. Part 2: Self-Adaptive Operation for Solutions

The solution of all processes of workpieces must be adjusted to correct the location of each column. If not, the completion time will be extended, and workpieces may be finished late in reverse active decoding. A comparison is shown in Figure2.Figure 2
Comparison before and after self-adaptive operation.To present the flow of self-adaptive operation, “TScn” is defined as a set,TScn=TScn1,TScn2,…,TScnLsc. For example, “TScn1” denotes the start time of the process and is located in the first column of SC.The steps of self-adaptive operation are as follows:(i)
Step 1: make a copy of SC, named SCTem, and clear all columns of SCTem(ii)
Step 2: set a counteru = Lsc(iii)
Step 3: choose the maximum value in TScn, put the column that corresponds to this value into theuth column of SCTem, and clear this value in TScn(iv)
Step 4:u = u−1; if u is equal to zero, go to Step 5; otherwise, go to Step 3(v)
Step 5: replace SC with SCTem, and the self-adaptive operation for SC is completed


### 4.2.3. Part 3: Reverse Active Decoding

In this part, solutions are decoded in reverse. The main decoding steps are same as those in part 1, but the start time of each workpiece is not equal to zero and each solution is decoded in reverse.The start time of workpieceh for reverse active decoding is denoted by “TSRevh.” The final completion time of workpiece h in part 1 is denoted by “TFFJh.” The delivery time of workpiece h is denoted by “TJDh.” TSRevh is calculated by the following equation:(13)TSRevh=MaxTFFJh,TJDh,h∈1,n.An example of reverse active decoding is shown in Figure3.Figure 3
An example of reverse active decoding.


## 4.2.1. Part 1: Active Decoding

Compared with semiactive decoding, active decoding is more effective in compressing the completion time of each workpiece. A sample coding is shown in Table2. Two workpieces will be processed on two machines. Two processes will be performed for each workpiece. Sample coding is decoded from the first column to the end. A comparison between these two decoding methods is shown in Figure 1 (DT: delivery time).Table 2
Sample coding.
Ji2211Mi2112TMJikvj4322Figure 1
Comparison between semiactive decoding and active decoding. (a) Result by semiactive decoding. (b) Result by active decoding.If using semiactive decoding, processes will be performed according to start time of machines only. For example, the second process ofJ2 will be carried out by M1. When this process is finished on M1, the start time of M1 is updated to seven and the first process of J1 will be started at this time. However, M1 is idle from time zero to four. The first process of J1 can be performed during this time interval.Therefore, for reducing finished time of each workpiece, we adopt active decoding instead of semiactive decoding. Before introducing this decoding method, some parameters are defined as follows:(i)
SC: a sample coding that will be decoded(ii)
Lsc: the number of columns of SC(iii)
Jobk: the workpiece in the kth column of SC, k=1,2,…,Lsc(iv)
Machk: the machine in the kth column of SC(v)
Ts (Machk): the earliest start time of Machk;(vi)
Nop (Jobk): the number of processes of JobkSupposing that thekth column represents the vth process of Jobk, the steps of active decoding are as follows:(i)
Step 1: set countersk=1andf=0.(ii)
Step 2: check the idle time and work time of Machk from time zero to Ts (Machk); if exiting an idle time segment, f=f+1.(iii)
Step 3: iff > 0, go to Step 4; otherwise, go to Step 6.(iv)
Step 4: set a counterg=0. If the vth process of Jobk can be carried out in the gth idle time segment, then deal with this process in the idle time segment, and go to Step 7; otherwise, g=g+1, and go to Step 5.(v)
Step 5: ifg>f, go to Step 6; otherwise, go to Step 4.(vi)
Step 6: perform thevth process of Jobk at time Ts (Machk).(vii)
Step 7:k=k+1.(viii)
Step 8: ifk>Lsc, active decoding for SC is completed; otherwise, go to Step 2.


## 4.2.2. Part 2: Self-Adaptive Operation for Solutions

The solution of all processes of workpieces must be adjusted to correct the location of each column. If not, the completion time will be extended, and workpieces may be finished late in reverse active decoding. A comparison is shown in Figure2.Figure 2
Comparison before and after self-adaptive operation.To present the flow of self-adaptive operation, “TScn” is defined as a set,TScn=TScn1,TScn2,…,TScnLsc. For example, “TScn1” denotes the start time of the process and is located in the first column of SC.The steps of self-adaptive operation are as follows:(i)
Step 1: make a copy of SC, named SCTem, and clear all columns of SCTem(ii)
Step 2: set a counteru = Lsc(iii)
Step 3: choose the maximum value in TScn, put the column that corresponds to this value into theuth column of SCTem, and clear this value in TScn(iv)
Step 4:u = u−1; if u is equal to zero, go to Step 5; otherwise, go to Step 3(v)
Step 5: replace SC with SCTem, and the self-adaptive operation for SC is completed


## 4.2.3. Part 3: Reverse Active Decoding

In this part, solutions are decoded in reverse. The main decoding steps are same as those in part 1, but the start time of each workpiece is not equal to zero and each solution is decoded in reverse.The start time of workpieceh for reverse active decoding is denoted by “TSRevh.” The final completion time of workpiece h in part 1 is denoted by “TFFJh.” The delivery time of workpiece h is denoted by “TJDh.” TSRevh is calculated by the following equation:(13)TSRevh=MaxTFFJh,TJDh,h∈1,n.An example of reverse active decoding is shown in Figure3.Figure 3
An example of reverse active decoding.


## 4.3. Selection Operation

First, the Pareto dominance relationship is taken into consideration, each solution is ranked, and the rank of each solution is obtained. Second, the crowding distance of each solution is calculated. Finally, a crowded comparison operator is proposed. A tournament selection method is adopted to perform the selection operation.


### 4.3.1. Ranking Operation

Before performing the ranking operation, the Pareto dominance relationship is defined as follows [33].Pareto dominance relationship: for a multiobjective minimization problem with N optimization objectives, assume a solution setP is composed of M individuals, P=x1,x2,…,xM. For any individual xi, the target value of the jth objective is fjxi. Then, if solution xu dominates solution xv, the following two conditions must be met:(1)
For any target valuesfk, fkxu≤fkxv(2)
∃k′,fk′xu<fk′xvwhere i,u,v∈1,M, j,k,k′∈1,N.The definition of the Pareto dominance relationship shows that if solutionxu dominates solution xv, solution xu is better than solution xv in the multiobjective minimization problem.Assuming that the population isP=x1,x2,…,xM, the rank set is Rank=rank1,rank2,…,rankM, and the number of individuals that dominate xii∈1,M is DN=dn1,dn2,…,dnM. Some variables are initialized as follows: rankh=−1, dnh=0, and h∈1,M. The ranking operation is shown in Figure 4.Figure 4
Flowchart of ranking operation.Figure4 shows that if solution xu dominates solution xv, the rank of xu is smaller than the rank of xv in the multiobjective minimization problem.


### 4.3.2. Crowding Distance

In addition to rank, crowding distance is another important indicator. If the ranks of two individuals are equal, to maintain the diversity of the population, it is commonly believed that an individual with a larger crowding distance between the two individuals is a better individual [32].Assuming a multiobjective minimization problem, the number of optimization objectives isN, the population P is composed of M individuals, P=x1,x2,…,xM, and the crowding distance set is CD=cd1,cd2,…,cdM. The crowding distance of the jth target of xi is cdfij. The individual that is ranked one position before xi and the individual that is ranked one position behind xi are named xfront and xbehind, respectively. The individual with the maximum value of the jth target and the individual with the minimum value of the jth target are named xmax and xmin, respectively. Then, the crowding distance cdi of individual xi is calculated as the following two equations:(14)cdfij=fjxbehind−fjxfrontfjxmax−fjxmin,(15)cdi=∑j=1Ncdfij.


### 4.3.3. Tournament Selection

Before tournament selection, a crowded comparison operator is defined as follows [32].Crowded comparison operator: for a multiobjective minimization problem with N optimization targets, assuming a solution setP is composed of M individuals, P=x1,x2,…,xM, the rank of solution xu is ranku, and the rank of solution xv is rankv. The crowding distances of solutions xu and xv are cdu and cdv, respectively. The notation of the crowded comparison operator is defined as “<”; then, xu<xv must meet the following condition (1) or (2):(1)
ranku<rankv(2)
ranku=rankv and cdu>cdvwhereu,v∈1,M.The crowded comparison operator shows that ifxu<xv, solution xu is better than xv.Based on the crowded comparison operator, tournament selection will be conducted for selecting individuals which will be crossed.


## 4.3.1. Ranking Operation

Before performing the ranking operation, the Pareto dominance relationship is defined as follows [33].Pareto dominance relationship: for a multiobjective minimization problem with N optimization objectives, assume a solution setP is composed of M individuals, P=x1,x2,…,xM. For any individual xi, the target value of the jth objective is fjxi. Then, if solution xu dominates solution xv, the following two conditions must be met:(1)
For any target valuesfk, fkxu≤fkxv(2)
∃k′,fk′xu<fk′xvwhere i,u,v∈1,M, j,k,k′∈1,N.The definition of the Pareto dominance relationship shows that if solutionxu dominates solution xv, solution xu is better than solution xv in the multiobjective minimization problem.Assuming that the population isP=x1,x2,…,xM, the rank set is Rank=rank1,rank2,…,rankM, and the number of individuals that dominate xii∈1,M is DN=dn1,dn2,…,dnM. Some variables are initialized as follows: rankh=−1, dnh=0, and h∈1,M. The ranking operation is shown in Figure 4.Figure 4
Flowchart of ranking operation.Figure4 shows that if solution xu dominates solution xv, the rank of xu is smaller than the rank of xv in the multiobjective minimization problem.


## 4.3.2. Crowding Distance

In addition to rank, crowding distance is another important indicator. If the ranks of two individuals are equal, to maintain the diversity of the population, it is commonly believed that an individual with a larger crowding distance between the two individuals is a better individual [32].Assuming a multiobjective minimization problem, the number of optimization objectives isN, the population P is composed of M individuals, P=x1,x2,…,xM, and the crowding distance set is CD=cd1,cd2,…,cdM. The crowding distance of the jth target of xi is cdfij. The individual that is ranked one position before xi and the individual that is ranked one position behind xi are named xfront and xbehind, respectively. The individual with the maximum value of the jth target and the individual with the minimum value of the jth target are named xmax and xmin, respectively. Then, the crowding distance cdi of individual xi is calculated as the following two equations:(14)cdfij=fjxbehind−fjxfrontfjxmax−fjxmin,(15)cdi=∑j=1Ncdfij.


## 4.3.3. Tournament Selection

Before tournament selection, a crowded comparison operator is defined as follows [32].Crowded comparison operator: for a multiobjective minimization problem with N optimization targets, assuming a solution setP is composed of M individuals, P=x1,x2,…,xM, the rank of solution xu is ranku, and the rank of solution xv is rankv. The crowding distances of solutions xu and xv are cdu and cdv, respectively. The notation of the crowded comparison operator is defined as “<”; then, xu<xv must meet the following condition (1) or (2):(1)
ranku<rankv(2)
ranku=rankv and cdu>cdvwhereu,v∈1,M.The crowded comparison operator shows that ifxu<xv, solution xu is better than xv.Based on the crowded comparison operator, tournament selection will be conducted for selecting individuals which will be crossed.


## 4.4. Crossover Operation

This paper adopts a precedence operation crossover (POX) operator [34] to crossover individuals. Assuming workpiece 2 will undergo crossover, an example of POX is shown in Figure 5.Figure 5
Crossover operation for MOJIT-IPPS.Because different process routes may be chosen for the same workpiece in different individuals, the same workpiece may have different numbers of operations in different individuals. Thus, the code length of generated individuals may be changed after crossover, as shown in Figure5.


## 4.5. Mutation Operation

Two kinds of mutation operators are adopted in SD-NSGA-II for the MOJIT-IPPS problem. First, swapping is performed on codes of two columns according to a swap probability. Two locations are generated randomly. The two columns of codes in the locations are exchanged. Second, single-point mutation is performed on the machine layer according to a single-point mutation probability.


## 4.6. Pareto Set

Assuming that the population size is equal toM, the number of iterations is equal to D. The following steps are adopted to construct a Pareto set:(i)
Step 1: initialize the Pareto set,PA=φ, and iteration counter e=0.(ii)
Step 2: the individuals of the first generationP are ranked, and the crowding distance of each individual is calculated.(iii)
Step 3: the selection, crossover, and mutation operations are performed on populationP, and then population P′ of the next generation is obtained.(iv)
Step 4: the temporary populationQ is established, Q=P∪P′.(v)
Step 5: the individuals of populationQ are ranked, and the crowding distance of each individual is calculated.(vi)
Step 6: each individual whose rank is equal to 1 in populationQ is compared with all individuals that belong to PA. If an individual is different from any individual in PA, it is added to PA.(vii)
Step 7:e++. If e<D, skip to Step 8; otherwise, skip to Step 9.(viii)
Step 8: the betterM individuals in population Q are chosen to form the new generation P; skip to Step 3.(ix)
Step 9:PA is ranked, and individuals whose ranks are larger than 1 are deleted. The Pareto set is formed.


## 4.7. Flowchart of SD-NSGA-II

To present the flowchart of SD-NSGA-II, some parameters are defined as follows:(i)
M: population size, controlling the number of individuals in the population.(ii)
CN: number of compared individuals, CN < M.(iii)
D: iterations, controlling the number of iterations of the algorithm.(iv)
Pc: crossover probability of the two selected individuals, decimals in (0, 1) interval.(v)
Pm: mutation probability of individuals, decimals in (0, 1) interval.(vi)
Pm1: probability that the swap operation is performed on codes of two columns of individuals, decimals in (0, 1) interval.(vii)
Pm2: probability that the single-point mutation is performed on the machine layer of the current individual, decimals in (0, 1) interval.A flowchart of SD-NSGA-II for the MOJIT-IPPS is shown in Figure6.Figure 6
Flowchart of SD-NSGA-II for MOJIT-IPPS.


## 5. Experimental Results and Analyses

### 5.1. Experiment 1: Multiobjective Optimization

There are seven types of shaft parts:J1−J7. The delivery time of each part is 30, 22, 21, 24, 27, 25, and 30, respectively. There are seven machines: M1−M7. There are six process methods: P1−P7. There are fourteen process routes: R1−R14. The earliness/tardiness penalty, maximum machine workload, and total machine workload are the objectives that will be minimized. The process routes of each workpiece are provided in Table 3.Table 3
Process routes.
JiRiDetails ofRi (machine code-process time)J1R1P3P2P4P6P13–3.2, 7–4.42–2, 6–2.41–4.6, 5–4.4, 6–6.66–5.2, 7–51–2.9, 3–5.4, 4–3.2R2P1P2P5P4—1–5.8, 3–2.1, 4–6.72–4.6, 6–32–4.1, 4–4.41–5.1, 5–5.3, 6–5.5—J2R3P7P1P3P6P54–3.2, 5–4.71–3.4, 3–6.3, 4–7.83–6.1, 7–4.46–2.4, 7–5.32–5.5, 4–4.3R4P7P1P2P5—4–2.9, 5–31–4.5, 3–7, 4–6.22–6.2, 6–22–3.9, 4–4.7—J3R5P3P6P7P4—3–2.1, 7–3.56–5.9, 7–5.14–7.3, 5–6.71–6.6, 5–5.8, 6–3—R6P6P1P4P2—6–3.4, 7–7.11–5.5, 3–5.4, 4–4.91–2.7, 5–7.8, 6–6.32–6.2, 6–3.6—J4R7P4P1P7——1–3, 5–5, 6–61–6.8, 3–5.2, 4–2.34–6.7, 5–7.7——R8P6P5P7P2—6–5.5, 7–3.32–6.1, 4–3.44–3.8, 5–72–2.1, 6–6.3—J5R9P2P4P1——2–2.2, 6–2.21–2.1, 5–7.9, 6–3.81–7, 3–7.9, 4–6——R10P1P2P7——1–6, 3–5, 4–2.12–5.1, 6–2.64–2.1, 5–4.7——J6R11P5P3P1P4P62–7.5, 4–7.63–3.7, 7–4.31–2, 3–2.3, 4–2.61–3.8, 5–5.8, 6–36–4.2, 7–3.2R12P1P4P7P5—1–6.8, 3–6.7, 4–41–5.9, 5–7.3, 6–3.24–7.3, 5–2.22–5.2, 4–5.3—J7R13P7P5P1——4–3.7, 5–72–4.3, 4–4.61–7, 3–4.2, 4–6.2——R14P2P7P6——2–4.8, 6–4.64–4.3, 5–2.16–2.7, 7–5.5——In this study, the parameters of the SD-NSGA-II are set asD = 500, M = 200, CN = 2, Pc=0.85, Pm = 0.1, Pm1 = 0.5, and Pm2 = 0.5. The C# programming language is used to create the algorithm. The results of the Pareto set are shown in Table 4. There are 32 solutions in the Pareto set.Table 4
Results of the Pareto set.
E/T penaltyMaximum machine workloadTotal machine workloadMaxMinAverageMaxMinAverageMaxMinAverage7.301.92515.218.996.685.289.4To express the results more directly, we select a solution in the Pareto set whose E/T penalty is equal to zero. A Gantt chart of the solution is shown in Figure7.Figure 7
Gantt chart of a solution in the Pareto set.The mathematical model and SD-NSGA-II for MOJIT-IPPS are proven through experiment 1. The earliness/tardiness penalty, maximum machine workload, and total machine workload are minimized simultaneously. Compared with optimizing only one objective, the scheduling solutions obtained by considering multiple objectives are more feasible for determining the real scheduling solution.


### 5.2. Experiment 2: Self-Adaptive Decoding Method

To evaluate the performance of the self-adaptive decoding method, a set of different scale examples is presented. As space is limited, several important parameters of the examples are provided in Table5.Table 5
Examples of experiment 2.
Parameters of example 1 (Ex1)nmpVRNVRTVRD (Ex1-1)VRD (Ex1-2)VRD (Ex1–3)3462–42.0–8.011–2021–3031–40Parameters of example 2 (Ex2)nmpVRNVRTVRD (Ex2-1)VRD (Ex2-2)VRD (Ex2-3)66123–42.0–8.011–2021–3031–40Parameters of example 3 (Ex3)nmpVRNVRTVRD (Ex3–1)VRD (Ex3-2)VRD (Ex3-3)98184–62.0–8.011–3021–4031–50Parameters of example 4 (Ex4)nmpVRNVRTVRD (Ex4–1)VRD (Ex4–2)VRD (Ex4-3)1210245–72.0–8.011–3021–4031–50In Table5, “VRN” represents the value range of the number of procedures of each process route, “VRT” represents the time range of each process, and “VRD” represents the delivery time range of each workpiece.The algorithm parameters for the four sets of examples are shown in Table6. Each set of examples is calculated 200 times by the two compared decoding methods. A comparison between the self-adaptive decoding method and a decoding method in [26] is shown in Table 7. For the twelve examples, the proposed self-adaptive decoding method provides better performance than the compared method [26] in Ex2-1, Ex2-2, Ex3-1, Ex3-2, Ex4-1, Ex4-2, and Ex4-3.Table 6
Algorithm parameters for the four sets of examples.
Algorithm parameters for Ex1MDPcPm1002000.90.1Algorithm parameters for Ex2MDPcPm3004000.90.1Algorithm parameters for Ex3MDPcPm4005000.90.1Algorithm parameters for Ex4MDPcPm5005000.90.1Table 7
Results for each example.
Example no.Self-adaptive decoding methodDecoding method in [26]E/T penaltyE/T penaltyMaxMinAverageMaxMinAverageEx1-1000000Ex1-2000000Ex1-3000000Ex2-1100.73.287512.94.37.306Ex2-21.800.0825200.316Ex2-3000000Ex3-152.59.828.76865.935.150.6725Ex3-25.200.209510.301.188Ex3-3000000Ex4-1108.933.173.2435153.1104.1125.904Ex4-232.35.416.546562.610.733.1735Ex4-32.200.0210.100.479


## 5.1. Experiment 1: Multiobjective Optimization

There are seven types of shaft parts:J1−J7. The delivery time of each part is 30, 22, 21, 24, 27, 25, and 30, respectively. There are seven machines: M1−M7. There are six process methods: P1−P7. There are fourteen process routes: R1−R14. The earliness/tardiness penalty, maximum machine workload, and total machine workload are the objectives that will be minimized. The process routes of each workpiece are provided in Table 3.Table 3
Process routes.
JiRiDetails ofRi (machine code-process time)J1R1P3P2P4P6P13–3.2, 7–4.42–2, 6–2.41–4.6, 5–4.4, 6–6.66–5.2, 7–51–2.9, 3–5.4, 4–3.2R2P1P2P5P4—1–5.8, 3–2.1, 4–6.72–4.6, 6–32–4.1, 4–4.41–5.1, 5–5.3, 6–5.5—J2R3P7P1P3P6P54–3.2, 5–4.71–3.4, 3–6.3, 4–7.83–6.1, 7–4.46–2.4, 7–5.32–5.5, 4–4.3R4P7P1P2P5—4–2.9, 5–31–4.5, 3–7, 4–6.22–6.2, 6–22–3.9, 4–4.7—J3R5P3P6P7P4—3–2.1, 7–3.56–5.9, 7–5.14–7.3, 5–6.71–6.6, 5–5.8, 6–3—R6P6P1P4P2—6–3.4, 7–7.11–5.5, 3–5.4, 4–4.91–2.7, 5–7.8, 6–6.32–6.2, 6–3.6—J4R7P4P1P7——1–3, 5–5, 6–61–6.8, 3–5.2, 4–2.34–6.7, 5–7.7——R8P6P5P7P2—6–5.5, 7–3.32–6.1, 4–3.44–3.8, 5–72–2.1, 6–6.3—J5R9P2P4P1——2–2.2, 6–2.21–2.1, 5–7.9, 6–3.81–7, 3–7.9, 4–6——R10P1P2P7——1–6, 3–5, 4–2.12–5.1, 6–2.64–2.1, 5–4.7——J6R11P5P3P1P4P62–7.5, 4–7.63–3.7, 7–4.31–2, 3–2.3, 4–2.61–3.8, 5–5.8, 6–36–4.2, 7–3.2R12P1P4P7P5—1–6.8, 3–6.7, 4–41–5.9, 5–7.3, 6–3.24–7.3, 5–2.22–5.2, 4–5.3—J7R13P7P5P1——4–3.7, 5–72–4.3, 4–4.61–7, 3–4.2, 4–6.2——R14P2P7P6——2–4.8, 6–4.64–4.3, 5–2.16–2.7, 7–5.5——In this study, the parameters of the SD-NSGA-II are set asD = 500, M = 200, CN = 2, Pc=0.85, Pm = 0.1, Pm1 = 0.5, and Pm2 = 0.5. The C# programming language is used to create the algorithm. The results of the Pareto set are shown in Table 4. There are 32 solutions in the Pareto set.Table 4
Results of the Pareto set.
E/T penaltyMaximum machine workloadTotal machine workloadMaxMinAverageMaxMinAverageMaxMinAverage7.301.92515.218.996.685.289.4To express the results more directly, we select a solution in the Pareto set whose E/T penalty is equal to zero. A Gantt chart of the solution is shown in Figure7.Figure 7
Gantt chart of a solution in the Pareto set.The mathematical model and SD-NSGA-II for MOJIT-IPPS are proven through experiment 1. The earliness/tardiness penalty, maximum machine workload, and total machine workload are minimized simultaneously. Compared with optimizing only one objective, the scheduling solutions obtained by considering multiple objectives are more feasible for determining the real scheduling solution.


## 5.2. Experiment 2: Self-Adaptive Decoding Method

To evaluate the performance of the self-adaptive decoding method, a set of different scale examples is presented. As space is limited, several important parameters of the examples are provided in Table5.Table 5
Examples of experiment 2.
Parameters of example 1 (Ex1)nmpVRNVRTVRD (Ex1-1)VRD (Ex1-2)VRD (Ex1–3)3462–42.0–8.011–2021–3031–40Parameters of example 2 (Ex2)nmpVRNVRTVRD (Ex2-1)VRD (Ex2-2)VRD (Ex2-3)66123–42.0–8.011–2021–3031–40Parameters of example 3 (Ex3)nmpVRNVRTVRD (Ex3–1)VRD (Ex3-2)VRD (Ex3-3)98184–62.0–8.011–3021–4031–50Parameters of example 4 (Ex4)nmpVRNVRTVRD (Ex4–1)VRD (Ex4–2)VRD (Ex4-3)1210245–72.0–8.011–3021–4031–50In Table5, “VRN” represents the value range of the number of procedures of each process route, “VRT” represents the time range of each process, and “VRD” represents the delivery time range of each workpiece.The algorithm parameters for the four sets of examples are shown in Table6. Each set of examples is calculated 200 times by the two compared decoding methods. A comparison between the self-adaptive decoding method and a decoding method in [26] is shown in Table 7. For the twelve examples, the proposed self-adaptive decoding method provides better performance than the compared method [26] in Ex2-1, Ex2-2, Ex3-1, Ex3-2, Ex4-1, Ex4-2, and Ex4-3.Table 6
Algorithm parameters for the four sets of examples.
Algorithm parameters for Ex1MDPcPm1002000.90.1Algorithm parameters for Ex2MDPcPm3004000.90.1Algorithm parameters for Ex3MDPcPm4005000.90.1Algorithm parameters for Ex4MDPcPm5005000.90.1Table 7
Results for each example.
Example no.Self-adaptive decoding methodDecoding method in [26]E/T penaltyE/T penaltyMaxMinAverageMaxMinAverageEx1-1000000Ex1-2000000Ex1-3000000Ex2-1100.73.287512.94.37.306Ex2-21.800.0825200.316Ex2-3000000Ex3-152.59.828.76865.935.150.6725Ex3-25.200.209510.301.188Ex3-3000000Ex4-1108.933.173.2435153.1104.1125.904Ex4-232.35.416.546562.610.733.1735Ex4-32.200.0210.100.479


## 6. Conclusions

The main works in this paper is summarized as follows:(1)
The earliness/tardiness penalty, maximum machine workload, and total machine workload are minimized simultaneously in the MOJIT-IPPS problem. A mathematical model of MOJIT-IPPS is established.(2)
Due to the complexity and particularity of the MOJIT-IPPS problem, a SD-NSGA-II is proposed to solve the problem. Each module of the algorithm is designed, and a flowchart of the algorithm is drawn.(3)
The above model and algorithm are validated experimentally. The Pareto set is obtained through the proposed SD-NSGA-II. The results indicate the good performance of the proposed method.Additionally, some future works will be carried out as follows:(1)
Algorithm improvement is a critical research direction for the IPPS problem. In this paper, a SD-NSGA-II is proposed for MOJIT-IPPS. We will continue research in this direction for the IPPS problem with delivery time. Specifically, more advanced algorithms will be developed to address different scale MOJIT-IPPS problems.(2)
The MOJIT-IPPS problem is a static scheduling problem in this paper. In future work, some dynamic factors will be considered in MOJIT-IPPS, such as inserting new workpieces, cancelling workpieces, and machine breakdown.



---

*Source: 6012737-2020-08-24.xml*