# A Self-Adaptive Multiobjective Differential Evolution Algorithm for the Unrelated Parallel Batch Processing Machine Scheduling Problem

Authors: Cunli Song
Journal: Mathematical Problems in Engineering
 (2022)

---

## Abstract

In this paper, the unrelated parallel batch processing machine (UPBPM) scheduling problem is addressed to minimize the total energy consumption (TEC) and makespan. Firstly, a mixed-integer line programming model (MILP) of the UPBPM scheduling problem is presented. Secondly, a self-adaptive multiobjective differential evolution (AMODE) algorithm is put forward. Since the parameter value can affect the performance of the algorithm greatly, an adaptive parameter control method is proposed according to the convergence index of the individual and the evolution degree of the population to improve the exploitation and exploration ability of the algorithm. Meanwhile, an adaptive mutation strategy is proposed to improve the algorithm’s convergence and the solutions’ diversity. Finally, to verify the effectiveness of the algorithm, comparative experiments are carried out on 20 instances with 5 different scales. Numerical comparisons indicate that the proposed method can achieve high comprehensive performance.


---

## Body

## 1. Introduction

With the aggravation of environmental pollution and the depletion of energy, to ensure the sustainable development, many countries, enterprises, and individuals consciously take energy conservation and emission reduction as the goal of the production and life. As an enterprise, there are two main approaches to save energy. One is replacing the traditional machines with more energy-saving machines and the other is developing green production [1]. Compared with the former technology, the latter technology is always a feasible and sustainable technology. Therefore, research on energy aware scheduling has become a hot issue. For instance, Qu et al. [2], Wu et al. [3], and Lei et al. [4] addressed the energy aware job shop scheduling problem, respectively. Song [5], Kampa and Paprocka [6], and Qin et al. [7] addressed the energy-efficient hybrid flow shop scheduling problem, respectively. Zhou et al. [8] and Jia et al. [1] addressed the energy aware batch processing machine (BMP) scheduling problem. From the statistics data that Gao et al. [9] made about production scheduling before April 2019, there is less research on BMP scheduling problem considering energy conservation.Batch processing is a typical production system and has a wide range of application, such as heating process before rolling and heat treatment process in iron and steel enterprise, logistics freight, and electronics manufacturing. A BPM can process multijob at a same time, and the jobs processed on the same machine at the same time is called a batch. If a batch includes nonidentical jobs, then the processing time is decided by the job with the longest processing time. Therefore, the study of BPM scheduling problem is of great significance to improve production efficiency and energy conservation. In recent years, with the purchase of new energy-saving machine, the UPBPM scheduling problem becomes more complexity because it includes allocating jobs to machines, grouping, and scheduling at the same time. There have been some studies on this issue, such as Li [10] and Jia et al. [1] who addressed this problem to minimize the makespan. Kakkunuri et al. [11] addressed this problem to minimize the total weighted tardiness. Generally speaking, the research on this problem is still less. Therefore, we will address the UPBPM scheduling problem to minimize the total energy consumption (TEC) and makespan at the same. The main innovations of the study include the following:(1)
An adaptive multiobjective differential evolution (AMODE) algorithm is proposed to minimize the makespan and TEC of the scheduling problem of UPBPM. At the same time, processing, machine on/off, and daily operation energy-saving methods have been considered here.(2)
Considering that the parametersF and CR of differential evolution algorithm (DE) influence the performance of the algorithm, a parameter adaptive strategy is proposed to improve the ability of individual global search and local exploitation.(3)
To improve the convergence of the algorithm and the diversity of the solution, an adaptive mutation strategy is proposed, which can formulate the mutation strategy according to the individual’s distribution characteristics.In the rest of this paper, we will start the research work from five aspects: (1) The review of production scheduling; (2) describing and modeling the UPBPM scheduling problem; (3) the algorithm’s description; (4) experiments and analysis; (5) conclusion and prospect.


## 2. Literature Review

### 2.1. Energy Aware Production Scheduling

With the enhancement of energy conservation awareness of production enterprises, the energy aware scheduling problem has gradually become a hot issue. From the perspective of energy-saving methods, there are manly three ways: (1) Turning off the idle machine to save the standby energy consumption (SEC) of the machine: For the flow shop scheduling problem, Lu et al. [12] proposed a strategy of turning off the idle machine without affecting the service life of it to reduce the energy consumption; Cui and Lu [13] achieved this purpose by combining the maintenance position of the machine with its idle time; Song [5] proposed a strategy of moving job to reduce the machine’s standby time or improve the probability of meeting shutdown conditions to deduce the SEC, etc. For the job shop scheduling problem, Xu et al. [14] proposed a machine on/off strategy under the consideration of TOU price. Gong et al. [15] proposed three heuristics to insert the maintenance activities into the idle time of machines to reduce SEC, etc. (2) In real life, a machine often has different power at different operating speeds, such as vehicles in logistics transportation and electric machinery. Therefore, many researchers try to control the speed of a machine to save its energy consumption; for example, Li et al. [16] addressed a distributed flow shop scheduling problem; He et al. [17] addressed a scheduling problem of open shop; Vallejos-Cifuentes et al. [18] addressed the job shop scheduling; Zhou et al. [8] and Qian et al. [19] addressed the BPM scheduling, respectively, but they did not propose a specific speed control strategy, etc. (3) In the season of power shortage, some cities often implement TOU price. Therefore, enterprises begin to study the production scheduling problem under TOU price to deduce the total electricity fee and energy consumption; for example, Trevino-Martinez et al. [20], Ho et al. [21], and Qin et al. [7] addressed the flow shop scheduling problem, respectively; Xu et al. [14] and Kong et al. [22] addressed the job shop scheduling problem, respectively; Zhou et al. [8], Qian et al. [19], and Jia et al. [1] addressed BPM scheduling problem, respectively.From the above review, it can be concluded that the research on energy aware production scheduling problem mainly focuses on job shop and flow shop. At the same time, researchers begin to pay attention to energy aware BPM scheduling problem in recent years. Moreover, the research of energy aware BPM scheduling is just from the aspects of TOU electricity price or machine speed control; few literature pieces consider energy conservation from the perspective of reducing standby time and daily operation.


### 2.2. BPM Scheduling Problem

In recent years, the research on BPM scheduling problem is increasing and the heuristic algorithm and metaheuristic algorithm are the main methods. To minimize the makespan, Dupont and Ghazvini [23] proposed the heuristic best-fit-longest-processing-time (BFLPT) to the single BPM scheduling problem; Li et al. [24] proposed several heuristics based on BFLPT to the UPBPM scheduling problem. Damodaran and Velez-Gallego [25] extended the successive knapsack problem (SKP) heuristic proposed by Dupont and Ghazvini [23] to the IPBPM scheduling problem. To minimize the total weighted tardiness, Perez et al. [26] and Li et al. [27] proposed several heuristics to scheduling a single BPM problem. Heuristic algorithm has the advantage of fast running, especially for large-scale problems. However, the quality of its solution is often not high. At the same time, for multiobjective problems, heuristic rules often can not take care of each objective. More researchers adopt metaheuristics to schedule BPM problems. To minimize the makespan of a single BPM scheduling problem, Cheng et al. [28] and Li and Wang [29] adopted the ant colony optimization (ACO) algorithm; Melouk et al. [30] adopted simulated annealing (SA), Alizadeh et al. [31] adopted the particle swarm optimization (PSO), Molla-Alizadeh-Zavardehi et al. [32] adopted the imperialist competitive algorithm (ICP), Beldar et al. [33] proposed an effectual teaching learning based optimization (TLBO), Zhou et al. [34] adopted a differential evolution (DE) algorithm, and Damodaran et al. [35] proposed a genetic algorithm (GA). Damodaran et al. [36] proposed a greedy randomized adaptive search procedure (GRASP) to minimize the number of tardiness. To schedule the identical BPM problem, Majumder et al. [37] adopted a cuckoo search algorithm (CSA) to minimize the makespan. Guo et al. [38] adopted a CSA to minimize the total tardiness. Zhang et al.[39] adopted an artificial bee colony (ABC) to minimize the utilization rate of dyeing vats and the tardiness cost. Qian et al. [19] adopted an adaptive clustering-based evolutionary algorithm and Zhou et al. [8] adopted a multiobjective DE algorithm to minimize electricity cost and makespan, respectively. To schedule the UPBPM, Jia et al. [1] adopted a multiobjective ACO algorithm to minimize electricity cost and makespan. Hulett et al. [40] adopted a PSO to minimize the total weighted tardiness. Kakkunuri et al. [11] adopted a SA to minimize the total weighted tardiness. Zhou et al. [41] and Xu [42] adopted an improved genetic algorithm (GA) to minimize the makespan, respectively.From the above literature review, the research on BPM scheduling problem is more about metaheuristic algorithm but not the heuristic. In terms of the types of problems studied, more research focuses on the single BPM scheduling problem, the second is IPBPM, and the last is UPBPM. From the perspective of research objectives, there are more researches on makespan, followed by minimizing weighted tardiness, and then other objectives. The research on multiobjective BPM scheduling problem has gradually appeared in recent years and most considered energy-saving by saving electricity cost under the condition of TOU price and control machine’s speed. There is little research on energy-saving scheduling through shutdown. As a metaheuristic algorithm, DE algorithm has strong optimization ability and is easy to code. Therefore, it is necessary to study the multiobjective UPBPM scheduling problem by designing a new multiobjective DE.


## 2.1. Energy Aware Production Scheduling

With the enhancement of energy conservation awareness of production enterprises, the energy aware scheduling problem has gradually become a hot issue. From the perspective of energy-saving methods, there are manly three ways: (1) Turning off the idle machine to save the standby energy consumption (SEC) of the machine: For the flow shop scheduling problem, Lu et al. [12] proposed a strategy of turning off the idle machine without affecting the service life of it to reduce the energy consumption; Cui and Lu [13] achieved this purpose by combining the maintenance position of the machine with its idle time; Song [5] proposed a strategy of moving job to reduce the machine’s standby time or improve the probability of meeting shutdown conditions to deduce the SEC, etc. For the job shop scheduling problem, Xu et al. [14] proposed a machine on/off strategy under the consideration of TOU price. Gong et al. [15] proposed three heuristics to insert the maintenance activities into the idle time of machines to reduce SEC, etc. (2) In real life, a machine often has different power at different operating speeds, such as vehicles in logistics transportation and electric machinery. Therefore, many researchers try to control the speed of a machine to save its energy consumption; for example, Li et al. [16] addressed a distributed flow shop scheduling problem; He et al. [17] addressed a scheduling problem of open shop; Vallejos-Cifuentes et al. [18] addressed the job shop scheduling; Zhou et al. [8] and Qian et al. [19] addressed the BPM scheduling, respectively, but they did not propose a specific speed control strategy, etc. (3) In the season of power shortage, some cities often implement TOU price. Therefore, enterprises begin to study the production scheduling problem under TOU price to deduce the total electricity fee and energy consumption; for example, Trevino-Martinez et al. [20], Ho et al. [21], and Qin et al. [7] addressed the flow shop scheduling problem, respectively; Xu et al. [14] and Kong et al. [22] addressed the job shop scheduling problem, respectively; Zhou et al. [8], Qian et al. [19], and Jia et al. [1] addressed BPM scheduling problem, respectively.From the above review, it can be concluded that the research on energy aware production scheduling problem mainly focuses on job shop and flow shop. At the same time, researchers begin to pay attention to energy aware BPM scheduling problem in recent years. Moreover, the research of energy aware BPM scheduling is just from the aspects of TOU electricity price or machine speed control; few literature pieces consider energy conservation from the perspective of reducing standby time and daily operation.


## 2.2. BPM Scheduling Problem

In recent years, the research on BPM scheduling problem is increasing and the heuristic algorithm and metaheuristic algorithm are the main methods. To minimize the makespan, Dupont and Ghazvini [23] proposed the heuristic best-fit-longest-processing-time (BFLPT) to the single BPM scheduling problem; Li et al. [24] proposed several heuristics based on BFLPT to the UPBPM scheduling problem. Damodaran and Velez-Gallego [25] extended the successive knapsack problem (SKP) heuristic proposed by Dupont and Ghazvini [23] to the IPBPM scheduling problem. To minimize the total weighted tardiness, Perez et al. [26] and Li et al. [27] proposed several heuristics to scheduling a single BPM problem. Heuristic algorithm has the advantage of fast running, especially for large-scale problems. However, the quality of its solution is often not high. At the same time, for multiobjective problems, heuristic rules often can not take care of each objective. More researchers adopt metaheuristics to schedule BPM problems. To minimize the makespan of a single BPM scheduling problem, Cheng et al. [28] and Li and Wang [29] adopted the ant colony optimization (ACO) algorithm; Melouk et al. [30] adopted simulated annealing (SA), Alizadeh et al. [31] adopted the particle swarm optimization (PSO), Molla-Alizadeh-Zavardehi et al. [32] adopted the imperialist competitive algorithm (ICP), Beldar et al. [33] proposed an effectual teaching learning based optimization (TLBO), Zhou et al. [34] adopted a differential evolution (DE) algorithm, and Damodaran et al. [35] proposed a genetic algorithm (GA). Damodaran et al. [36] proposed a greedy randomized adaptive search procedure (GRASP) to minimize the number of tardiness. To schedule the identical BPM problem, Majumder et al. [37] adopted a cuckoo search algorithm (CSA) to minimize the makespan. Guo et al. [38] adopted a CSA to minimize the total tardiness. Zhang et al.[39] adopted an artificial bee colony (ABC) to minimize the utilization rate of dyeing vats and the tardiness cost. Qian et al. [19] adopted an adaptive clustering-based evolutionary algorithm and Zhou et al. [8] adopted a multiobjective DE algorithm to minimize electricity cost and makespan, respectively. To schedule the UPBPM, Jia et al. [1] adopted a multiobjective ACO algorithm to minimize electricity cost and makespan. Hulett et al. [40] adopted a PSO to minimize the total weighted tardiness. Kakkunuri et al. [11] adopted a SA to minimize the total weighted tardiness. Zhou et al. [41] and Xu [42] adopted an improved genetic algorithm (GA) to minimize the makespan, respectively.From the above literature review, the research on BPM scheduling problem is more about metaheuristic algorithm but not the heuristic. In terms of the types of problems studied, more research focuses on the single BPM scheduling problem, the second is IPBPM, and the last is UPBPM. From the perspective of research objectives, there are more researches on makespan, followed by minimizing weighted tardiness, and then other objectives. The research on multiobjective BPM scheduling problem has gradually appeared in recent years and most considered energy-saving by saving electricity cost under the condition of TOU price and control machine’s speed. There is little research on energy-saving scheduling through shutdown. As a metaheuristic algorithm, DE algorithm has strong optimization ability and is easy to code. Therefore, it is necessary to study the multiobjective UPBPM scheduling problem by designing a new multiobjective DE.


## 3. Problem Definition

### 3.1. Problem Description

JobsJ=J1,J2,⋯,Jn has to processed on UPBPMs such as M1,M1,⋯,Mm. The constraints about jobs are that they have nonidentical size, arrival time, and different processing time on each machine. The constraints about UPBPM are that they have nonidentical capacity and power. To process the n jobs on m machines to minimize the makespan and TEC, we must determine the processing machine for each job, group the jobs on the same machine into batches, and determine the processing order of each batch. The assumptions here are as follows:(1)
Machines are ready at zero.(2)
A machine can only process one task at a time and cannot be interrupted when processing.(3)
When a batch is processed, it is not allowed to add or delete jobs.(4)
Only jobs in the same family cluster are allowed to form a batch.


### 3.2. Symbols

For the convenience of mathematical modeling, symbols are defined as follows:j is job number and j=1,2,…,n.k is machine number and k=1,2,…,m.i is batch number and 0≤i≤n.n is number of jobs.m is number of machines.sj is dimension of job Jj.rj is arrival time of job Jj.pj,k is time that machine processes job Jj.ck is capacity of machine Mk.lk is power of machine Mk.spk is the standby power of machine per unit time.suk is the start-up energy consumption per time.sdk is the shutdown energy consumption per time.do is daily operation energy consumption of workshop per unit time.Bk,i is the i-th batch of machine Mk.Nk is number of batches on machine Mk.xj,k,i: if job Jj is on the i-th batch of machine Mk, then xj,k,i=1; otherwise, xj,k,i=0.BNk,i is number of jobs in batch Bk,i.STk,i is time that machine Mk begins to process batch Bk,i.CTk,i is time that machine Mk completes batch Bk,i.PTk,i is time that machine Mk processes batch Bk,i.WEk,i is energy wasted when machine Mk processes batch Bk,i.TEC is total energy consumption.Cmax is makespan.


### 3.3. Mathematical Modeling

Based on the symbols defined in Subsection3.2 and assumptions in Subsection 3.1, the MILP model of the UPBPM scheduling problem can be defined below:(1)minCmax,(2)minTEC.It is subject to(3)∑k=1m∑i=1Nkxj,k,i=1,(4)∑j=1nxj,k,i⋅sj≤ck,i=1,2,⋯,Nk,(5)PTk,i=maxxj,k,i⋅pj,k|i=1,2,⋯,Nk,(6)STk,i≥xj,k,i⋅rj,i=1,2,⋯,Nk,(7)STk,i+1≥CTk,i,∀i=1,2,⋯,Nk−1,(8)CTk,i=STk,i+PTk,i,i=1,2,⋯,Nk,(9)∑k=1M∑i=1NkBNk,i=n,(10)Cmax=maxk=1,2,⋯,m;i=1,2,⋯,NkCTk,i,(11)TEC=∑k=1m∑i=1NkPTk,i⋅lk+do⋅Cmax−mink=1,…,M,i=1,…,NkSTk,i+∑k=1Msuk+sdk,(12)WEk,i=lk⋅∑Jj∈Bk,iPk,i−pj⋅sj+Pk,i⋅ck−∑Jj∈Bk,isj,where (1) and (2) are the two objectives. Constraint (3) states that a job can only be allocated to one batch of one machine. Constraint (4) states that, for any machine, the sum of the size of the job in any batch processed on it should not exceed the capacity of it. Equation (5) is the formula to compute time that machine Mk processes batch Bk,i. Constraint (6) indicates that only when all jobs in a batch arrive can a batch have the conditions be processed. Constraint (7) indicates that, for the same machine, only the processing of the previous batch is completed; the next batch can be started. Equation (8) is the formula for calculating the completion time of batch Bk,i. Equation (9) shows that the cumulative number of jobs in all batches is exactly n. Equation (10) indicates that the batch with the latest completion time determines the maximum completion time. Equation (11) is the formula for calculating TEC which includes the processing energy consumption, standby energy consumption, daily operation energy consumption, and switching on and off energy consumption. Equation (12) is the formula for calculating WEk,i.


## 3.1. Problem Description

JobsJ=J1,J2,⋯,Jn has to processed on UPBPMs such as M1,M1,⋯,Mm. The constraints about jobs are that they have nonidentical size, arrival time, and different processing time on each machine. The constraints about UPBPM are that they have nonidentical capacity and power. To process the n jobs on m machines to minimize the makespan and TEC, we must determine the processing machine for each job, group the jobs on the same machine into batches, and determine the processing order of each batch. The assumptions here are as follows:(1)
Machines are ready at zero.(2)
A machine can only process one task at a time and cannot be interrupted when processing.(3)
When a batch is processed, it is not allowed to add or delete jobs.(4)
Only jobs in the same family cluster are allowed to form a batch.


## 3.2. Symbols

For the convenience of mathematical modeling, symbols are defined as follows:j is job number and j=1,2,…,n.k is machine number and k=1,2,…,m.i is batch number and 0≤i≤n.n is number of jobs.m is number of machines.sj is dimension of job Jj.rj is arrival time of job Jj.pj,k is time that machine processes job Jj.ck is capacity of machine Mk.lk is power of machine Mk.spk is the standby power of machine per unit time.suk is the start-up energy consumption per time.sdk is the shutdown energy consumption per time.do is daily operation energy consumption of workshop per unit time.Bk,i is the i-th batch of machine Mk.Nk is number of batches on machine Mk.xj,k,i: if job Jj is on the i-th batch of machine Mk, then xj,k,i=1; otherwise, xj,k,i=0.BNk,i is number of jobs in batch Bk,i.STk,i is time that machine Mk begins to process batch Bk,i.CTk,i is time that machine Mk completes batch Bk,i.PTk,i is time that machine Mk processes batch Bk,i.WEk,i is energy wasted when machine Mk processes batch Bk,i.TEC is total energy consumption.Cmax is makespan.


## 3.3. Mathematical Modeling

Based on the symbols defined in Subsection3.2 and assumptions in Subsection 3.1, the MILP model of the UPBPM scheduling problem can be defined below:(1)minCmax,(2)minTEC.It is subject to(3)∑k=1m∑i=1Nkxj,k,i=1,(4)∑j=1nxj,k,i⋅sj≤ck,i=1,2,⋯,Nk,(5)PTk,i=maxxj,k,i⋅pj,k|i=1,2,⋯,Nk,(6)STk,i≥xj,k,i⋅rj,i=1,2,⋯,Nk,(7)STk,i+1≥CTk,i,∀i=1,2,⋯,Nk−1,(8)CTk,i=STk,i+PTk,i,i=1,2,⋯,Nk,(9)∑k=1M∑i=1NkBNk,i=n,(10)Cmax=maxk=1,2,⋯,m;i=1,2,⋯,NkCTk,i,(11)TEC=∑k=1m∑i=1NkPTk,i⋅lk+do⋅Cmax−mink=1,…,M,i=1,…,NkSTk,i+∑k=1Msuk+sdk,(12)WEk,i=lk⋅∑Jj∈Bk,iPk,i−pj⋅sj+Pk,i⋅ck−∑Jj∈Bk,isj,where (1) and (2) are the two objectives. Constraint (3) states that a job can only be allocated to one batch of one machine. Constraint (4) states that, for any machine, the sum of the size of the job in any batch processed on it should not exceed the capacity of it. Equation (5) is the formula to compute time that machine Mk processes batch Bk,i. Constraint (6) indicates that only when all jobs in a batch arrive can a batch have the conditions be processed. Constraint (7) indicates that, for the same machine, only the processing of the previous batch is completed; the next batch can be started. Equation (8) is the formula for calculating the completion time of batch Bk,i. Equation (9) shows that the cumulative number of jobs in all batches is exactly n. Equation (10) indicates that the batch with the latest completion time determines the maximum completion time. Equation (11) is the formula for calculating TEC which includes the processing energy consumption, standby energy consumption, daily operation energy consumption, and switching on and off energy consumption. Equation (12) is the formula for calculating WEk,i.


## 4. The Proposed Algorithm AMODE

### 4.1. The Framework of AMODE

The framework of the algorithm AMODE is shown in Figure1 and the details are described in the follow subsection of Section 4.Figure 1
Framework of the algorithm AMODE.


### 4.2. Code and Initialization

The solution of the scheduling problem of UPBPM should include the machine which processes a job, the batch that the job is included in, and the processing order of each batch. It is difficult to express this information in a code and even if you can that will make the solution space increase exponentially. Therefore, we code a solution withn real data. Given X is a solution, then, X=x1,…xi,…,xn, where, xi∈1,M+1, xi is the code information of job ji, xi is the machine number which processes job ji, and xi−xi expresses the priority that ji be grouped on that machine. The grouping rules and process sequence of jobs are determined according to the decoding algorithm in Section 4.3. Take 7 jobs processed on 2 machines as an example; the detailed processing data and solution code are shown in Table 1. According to the integer part of each job’s code in the last line in Table 1, we can ascertain that machine M1 processes jobs J1, J4, J5, and J7 and machine M2 processes jobs J2, J3, and J6; then, according to the fractional part of each job’s code, we can ascertain that the grouping priority of jobs on machine M1 is J7,J1,J4,J5 and M2 is J6,J3,J2. The scheduling results can be determined by the decoding rules in Section 4.3. Note that the initial solution Xi0i=1,2,⋯n is generated by the following equation:(13)xi,j0=xl+Rj×xu−xl,j=1,2,…,n,where xl=1 and xu=M+1, respectively, and Rj is a random number from 0 to 1.Table 1
An UPBMP instance and a solution of the problem.
j1234567pi12233421171320sj1112201315816aj11227643xj1.232.612.151.571.622.021.01


### 4.3. Decoding and Energy-Saving Strategy

According to the code in Section4.2, in order to obtain a specific scheduling result, it is necessary to determine the rule of grouping and the processing sequence of each batch. The four bias decoding rules proposed by Song [43] can make better use of the problem knowledge to get better scheduling results. In view of this, this paper will adopt the four bias heuristic rules to decode the solution. Since the four heuristic rules are bias, it is necessary to set an appropriate proportion of each rule to ensure the diversity of solutions. We will determine their proportion relationship through experiments in Section 5. For more details about the heuristic rule please see the literature.Two strategies are proposed here to reduce the energy consumption. (1) For all machines, move each batch back as far as possible under the condition that the machine’s completion time remains unchanged. Thus, the SEC can be saved by compressing the machine’s idle time. That means delaying the start of the machine. (2) On the basis of not affecting the maximum completion time, the start-up of all machines shall be delayed as far as possible to eliminate the total working hours. That means shortening the operation time. Take the instance in Table1 for example. According to the heuristic Rule1, the batches on machine M1 and the processing order are B1,1j7,j1 and B1,2j4,j5, the batch on machine M2 is B2,1j6,j2,j3, and the Gantt chart is shown in Figure 2(a). To reduce the SEC of machines, move the batches on machine M1 back and the Gantt chart is shown in Figure 2(b). To save the operation energy consumption, move the batch on machine M2 and the Gantt chart is shown in Figure 2(c).Figure 2
The scheduling result of the instance. (a) The initial scheduling result. (b) Move the batches on each machine backward without increasing the makespan to eliminate the standby time. (c) Move the batch on each machine backward as a whole without increasing the makespan to eliminate the overall working hours.
(a)(b)(c)


### 4.4. An Adaptive Mutation Strategy (AMS)

The mutation operator affects the algorithm’s convergence speed and the solutions’ distributivity. Since the mutation strategyDEbest1|bin has good convergence, this strategy is applied to create variants. The mutation formula is shown as (14):(14)Vit=Xgbest+F⋅Xp1t−Xp2t,(15)vi,jt=M,vi,jtmodM=0vi,jtmodM,otherwise.Vit is the variant, Xgbest comes from Pareto archives (PA) of the algorithm AMODE, t indicates the generation of the population, F is the scaling parameter, and Xp1t and Xp2t are two solutions randomly chosen from the t-th population. To ensure the legitimacy of each gene, (15) is used to revise the genes.The convergence and crowding degree of each solution in PA is different. Therefore, to effectively guide the solution’s mutation operation and balance the convergence speed and the population diversity simultaneously, an adaptive mutation operator is proposed here. The strategy will adaptively adjust the exploration and exploitation strategy according to the algorithm environment. The steps are as follows.Step 1.
Calculate each individual’s convergence index (CI) with (16) and rank them in nonascending manner according to their CI.(16)CIXit=1∑j=1∧j≠iN∑q=1QmaxfqXit−fqXjt,0,where Q means the number of multiple objectives, N means the population size, and fqXit expresses the value of individual Xit on objective q. To avoid the influence of different dimensions objective on the statistics of CI, all targets are counted by the normalized values. Obviously, CIXit indicates the superiority of individual Xit and the greater the CIXit is, the better the convergence is.
Then, the individuals are divided into three different zones by (17) according to their ranking value RCIXit, where a and b are two parameters and satisfy 0<a<b<1. Figure 3 shows the partition result diagram. In Section 5.3, the appropriate values of a and b will be determined through experimental analysis.(17)regionXit=IRCIXit<a×NIIa×N≤RCIXit<b×NIIIb×N≤RCIXit.Figure 3
An instance of the population division.Step 2.
Calculate the crowding distance (CD) and CI of the individual inPA with (18) and (16) , respectively. Obviously, the greater the CD value is, the greater the sparsity of the individual is. The greater the CI value is, the better the convergence of the individual is, where np is the individuals’ number in PA.(18)DidsXi=∑q=1QfqXi+1−fqXi−12,i≠1,i≠np∑q=1QfqX2−fqX12,i=1∑q=1QfqXnp−fqXnp−12,i=np,Step 3.
SelectXgbest. Different strategies were proposed to select Xgbest for individuals in different zone.(1)
For the individual of zone I, select an individual fromPA as Xgbest by using the roulette strategy and the probability of the individual Xi in PA is determined by (19). That means the Pareto(19)pXi=DisXi∑r=1npDisXr.(2)
For the individual of zone III, select an individual fromPA as Xgbest by using the roulette strategy, but the probability of the individual Xi in PA is determined by (20). That means the Pareto frontier solution with larger CI value is more likely to be chosen to improve the exploitation ability of the algorithm.(20)pXi=CIXi∑r=1npCIXr.(3)
For the individual of zone II, at the early phase of the algorithm, the strategy of zone III is adopted to selectXgbest to improve the exploration ability. At the later phase of the algorithm, the strategy of zone I is used to select Xgbest to improve the diversity of solutions.


### 4.5. Other Operators

The cross operation can create new individual with (21), parameter CR is the crossover probability, and 0<CR<1.(21)ui,jt=vi,jt,rand<CRxi,jt,otherwise.In order to determine which individual of the trialUit and the current Xit−1 enters to the next generation population, the greedy selection strategy proposed by Zhou et al. [8] is adopted here; for more details, please see the literature.


### 4.6. An Adaptive Parameter Control Strategy (APCS)

In DE algorithm,F and CR are two important parameters. When the values of F and CR are large, the disturbance of the algorithm is large, which is conducive to the global search of the algorithm, but not conducive to the convergence. Otherwise, it is conducive to the local search of the algorithm, but easy to precocious. Therefore, an adaptive parameter adjustment strategy based on the attenuation of evolution times and the convergence index the population is proposed and shown in (23).(22)Pi=Pl+Pu−Plλ⋅α+1−λβi,0<λ<1,(23)α=Iter−tIter,(24)βi=maxj=1,2,…npCIXj−CIXimaxj=1,2,…npCIXj−minj=1,2,…npCIXj.In (22)–(24), Pi is the parameter F or CR of the individual Xit. [Pu, PL] is the value range of parameter of F or CR. α and Iter are the attenuation coefficient and the maximum evolution times of the algorithm, respectively. λ and 1 − λ are the weight factor of α and βi, respectively, and here λ=0.5. Therefore, βi is the relative CI of the individual Xit. βi∈0,1; the smaller the βi is, the better the convergence of the individual Xit is, and vice versa.For a metaheuristic algorithm, we hope it has a better exploration ability in the early time and a stronger exploitation ability in the latter.α in (23) can attenuate F and CR with the increase of algorithm iteration and achieve this purpose. From the relative convergence index βi of individual Xit, when the convergence of Xit is better, the value of βi will be smaller; then, F and CR will be smaller, so the better genes of individual Xit will have a higher possibility to enter into the next generation. On the contrary, F and CR will have a greater value; thus, the search range can be expanded and the population’s diversity can be increased.


### 4.7. The Pseudocode of AMODE

Integrate the above operators; the pseudocode of AMODE is shown in Algorithm 1.Algorithm 1: Pseudocode of the AMODE.
Input: process data and jobsOutput: the Pareto frontier solutions (PA)function AMODE ( ){ //step 1: initializationInitialize the size of populationN;Initialize variable Fu and Fd; //[Fu, Fd] is the value range of parameterFInitialize variable Cru and Crd; //[Cru, Crd] is the value range of parameter CRInitialize variable a andb;Set Iter = 800;SetPA=ϕ;for(i = 1 to N){ Generate solutionXi randomly;EvaluateXi;}Statistic the Pareto solutions inX11,X21,…,XN1 and put them in PA;}//step2: AMODE algorithmt = 1;whilet ≤ Iter{ computerα according (23);fori = 1 to N{ ComputerCIXit according to Eq (16);Computerβi according to Eq (24);ComputerFit and CRit according to (22);}Sort all individuals according their CI value;Determine the zone of each individual according to (17) and label them;fori to N//Execute the evolution operation on each solution{ SelectXgbest from PA according the zone’s strategy of Xit;Randomly select two individuals from populationX1t,X2t,…,XNt;Execute mutation operation according Eq (14) and create variant Vit;CrossVit and Xit and create Uit;Execute greedy select operation and select one ofXit and Uit enter into next generation;Update PA using the strategy of Section4.6;}t = t + 1;}Output PA; //step3: output;}


## 4.1. The Framework of AMODE

The framework of the algorithm AMODE is shown in Figure1 and the details are described in the follow subsection of Section 4.Figure 1
Framework of the algorithm AMODE.


## 4.2. Code and Initialization

The solution of the scheduling problem of UPBPM should include the machine which processes a job, the batch that the job is included in, and the processing order of each batch. It is difficult to express this information in a code and even if you can that will make the solution space increase exponentially. Therefore, we code a solution withn real data. Given X is a solution, then, X=x1,…xi,…,xn, where, xi∈1,M+1, xi is the code information of job ji, xi is the machine number which processes job ji, and xi−xi expresses the priority that ji be grouped on that machine. The grouping rules and process sequence of jobs are determined according to the decoding algorithm in Section 4.3. Take 7 jobs processed on 2 machines as an example; the detailed processing data and solution code are shown in Table 1. According to the integer part of each job’s code in the last line in Table 1, we can ascertain that machine M1 processes jobs J1, J4, J5, and J7 and machine M2 processes jobs J2, J3, and J6; then, according to the fractional part of each job’s code, we can ascertain that the grouping priority of jobs on machine M1 is J7,J1,J4,J5 and M2 is J6,J3,J2. The scheduling results can be determined by the decoding rules in Section 4.3. Note that the initial solution Xi0i=1,2,⋯n is generated by the following equation:(13)xi,j0=xl+Rj×xu−xl,j=1,2,…,n,where xl=1 and xu=M+1, respectively, and Rj is a random number from 0 to 1.Table 1
An UPBMP instance and a solution of the problem.
j1234567pi12233421171320sj1112201315816aj11227643xj1.232.612.151.571.622.021.01


## 4.3. Decoding and Energy-Saving Strategy

According to the code in Section4.2, in order to obtain a specific scheduling result, it is necessary to determine the rule of grouping and the processing sequence of each batch. The four bias decoding rules proposed by Song [43] can make better use of the problem knowledge to get better scheduling results. In view of this, this paper will adopt the four bias heuristic rules to decode the solution. Since the four heuristic rules are bias, it is necessary to set an appropriate proportion of each rule to ensure the diversity of solutions. We will determine their proportion relationship through experiments in Section 5. For more details about the heuristic rule please see the literature.Two strategies are proposed here to reduce the energy consumption. (1) For all machines, move each batch back as far as possible under the condition that the machine’s completion time remains unchanged. Thus, the SEC can be saved by compressing the machine’s idle time. That means delaying the start of the machine. (2) On the basis of not affecting the maximum completion time, the start-up of all machines shall be delayed as far as possible to eliminate the total working hours. That means shortening the operation time. Take the instance in Table1 for example. According to the heuristic Rule1, the batches on machine M1 and the processing order are B1,1j7,j1 and B1,2j4,j5, the batch on machine M2 is B2,1j6,j2,j3, and the Gantt chart is shown in Figure 2(a). To reduce the SEC of machines, move the batches on machine M1 back and the Gantt chart is shown in Figure 2(b). To save the operation energy consumption, move the batch on machine M2 and the Gantt chart is shown in Figure 2(c).Figure 2
The scheduling result of the instance. (a) The initial scheduling result. (b) Move the batches on each machine backward without increasing the makespan to eliminate the standby time. (c) Move the batch on each machine backward as a whole without increasing the makespan to eliminate the overall working hours.
(a)(b)(c)


## 4.4. An Adaptive Mutation Strategy (AMS)

The mutation operator affects the algorithm’s convergence speed and the solutions’ distributivity. Since the mutation strategyDEbest1|bin has good convergence, this strategy is applied to create variants. The mutation formula is shown as (14):(14)Vit=Xgbest+F⋅Xp1t−Xp2t,(15)vi,jt=M,vi,jtmodM=0vi,jtmodM,otherwise.Vit is the variant, Xgbest comes from Pareto archives (PA) of the algorithm AMODE, t indicates the generation of the population, F is the scaling parameter, and Xp1t and Xp2t are two solutions randomly chosen from the t-th population. To ensure the legitimacy of each gene, (15) is used to revise the genes.The convergence and crowding degree of each solution in PA is different. Therefore, to effectively guide the solution’s mutation operation and balance the convergence speed and the population diversity simultaneously, an adaptive mutation operator is proposed here. The strategy will adaptively adjust the exploration and exploitation strategy according to the algorithm environment. The steps are as follows.Step 1.
Calculate each individual’s convergence index (CI) with (16) and rank them in nonascending manner according to their CI.(16)CIXit=1∑j=1∧j≠iN∑q=1QmaxfqXit−fqXjt,0,where Q means the number of multiple objectives, N means the population size, and fqXit expresses the value of individual Xit on objective q. To avoid the influence of different dimensions objective on the statistics of CI, all targets are counted by the normalized values. Obviously, CIXit indicates the superiority of individual Xit and the greater the CIXit is, the better the convergence is.
Then, the individuals are divided into three different zones by (17) according to their ranking value RCIXit, where a and b are two parameters and satisfy 0<a<b<1. Figure 3 shows the partition result diagram. In Section 5.3, the appropriate values of a and b will be determined through experimental analysis.(17)regionXit=IRCIXit<a×NIIa×N≤RCIXit<b×NIIIb×N≤RCIXit.Figure 3
An instance of the population division.Step 2.
Calculate the crowding distance (CD) and CI of the individual inPA with (18) and (16) , respectively. Obviously, the greater the CD value is, the greater the sparsity of the individual is. The greater the CI value is, the better the convergence of the individual is, where np is the individuals’ number in PA.(18)DidsXi=∑q=1QfqXi+1−fqXi−12,i≠1,i≠np∑q=1QfqX2−fqX12,i=1∑q=1QfqXnp−fqXnp−12,i=np,Step 3.
SelectXgbest. Different strategies were proposed to select Xgbest for individuals in different zone.(1)
For the individual of zone I, select an individual fromPA as Xgbest by using the roulette strategy and the probability of the individual Xi in PA is determined by (19). That means the Pareto(19)pXi=DisXi∑r=1npDisXr.(2)
For the individual of zone III, select an individual fromPA as Xgbest by using the roulette strategy, but the probability of the individual Xi in PA is determined by (20). That means the Pareto frontier solution with larger CI value is more likely to be chosen to improve the exploitation ability of the algorithm.(20)pXi=CIXi∑r=1npCIXr.(3)
For the individual of zone II, at the early phase of the algorithm, the strategy of zone III is adopted to selectXgbest to improve the exploration ability. At the later phase of the algorithm, the strategy of zone I is used to select Xgbest to improve the diversity of solutions.


## 4.5. Other Operators

The cross operation can create new individual with (21), parameter CR is the crossover probability, and 0<CR<1.(21)ui,jt=vi,jt,rand<CRxi,jt,otherwise.In order to determine which individual of the trialUit and the current Xit−1 enters to the next generation population, the greedy selection strategy proposed by Zhou et al. [8] is adopted here; for more details, please see the literature.


## 4.6. An Adaptive Parameter Control Strategy (APCS)

In DE algorithm,F and CR are two important parameters. When the values of F and CR are large, the disturbance of the algorithm is large, which is conducive to the global search of the algorithm, but not conducive to the convergence. Otherwise, it is conducive to the local search of the algorithm, but easy to precocious. Therefore, an adaptive parameter adjustment strategy based on the attenuation of evolution times and the convergence index the population is proposed and shown in (23).(22)Pi=Pl+Pu−Plλ⋅α+1−λβi,0<λ<1,(23)α=Iter−tIter,(24)βi=maxj=1,2,…npCIXj−CIXimaxj=1,2,…npCIXj−minj=1,2,…npCIXj.In (22)–(24), Pi is the parameter F or CR of the individual Xit. [Pu, PL] is the value range of parameter of F or CR. α and Iter are the attenuation coefficient and the maximum evolution times of the algorithm, respectively. λ and 1 − λ are the weight factor of α and βi, respectively, and here λ=0.5. Therefore, βi is the relative CI of the individual Xit. βi∈0,1; the smaller the βi is, the better the convergence of the individual Xit is, and vice versa.For a metaheuristic algorithm, we hope it has a better exploration ability in the early time and a stronger exploitation ability in the latter.α in (23) can attenuate F and CR with the increase of algorithm iteration and achieve this purpose. From the relative convergence index βi of individual Xit, when the convergence of Xit is better, the value of βi will be smaller; then, F and CR will be smaller, so the better genes of individual Xit will have a higher possibility to enter into the next generation. On the contrary, F and CR will have a greater value; thus, the search range can be expanded and the population’s diversity can be increased.


## 4.7. The Pseudocode of AMODE

Integrate the above operators; the pseudocode of AMODE is shown in Algorithm 1.Algorithm 1: Pseudocode of the AMODE.
Input: process data and jobsOutput: the Pareto frontier solutions (PA)function AMODE ( ){ //step 1: initializationInitialize the size of populationN;Initialize variable Fu and Fd; //[Fu, Fd] is the value range of parameterFInitialize variable Cru and Crd; //[Cru, Crd] is the value range of parameter CRInitialize variable a andb;Set Iter = 800;SetPA=ϕ;for(i = 1 to N){ Generate solutionXi randomly;EvaluateXi;}Statistic the Pareto solutions inX11,X21,…,XN1 and put them in PA;}//step2: AMODE algorithmt = 1;whilet ≤ Iter{ computerα according (23);fori = 1 to N{ ComputerCIXit according to Eq (16);Computerβi according to Eq (24);ComputerFit and CRit according to (22);}Sort all individuals according their CI value;Determine the zone of each individual according to (17) and label them;fori to N//Execute the evolution operation on each solution{ SelectXgbest from PA according the zone’s strategy of Xit;Randomly select two individuals from populationX1t,X2t,…,XNt;Execute mutation operation according Eq (14) and create variant Vit;CrossVit and Xit and create Uit;Execute greedy select operation and select one ofXit and Uit enter into next generation;Update PA using the strategy of Section4.6;}t = t + 1;}Output PA; //step3: output;}


## 5. Experiment and Analysis

To do the comparison experiments, we code the algorithm with C++ on a PC with an intel(R) core™ i7-1165G7, CPU 2.80 GHz, and 16 GB memory. Three kinds of experiments have been done. The parameters’ appropriate value of AMODE is determined in the first experiment, the effectiveness of the adaptive strategy is verified in the second experiment, and the comparison and analysis with other algorithms are carried out in the third experiment. Unless otherwise specified, each algorithm runs 10 times on each instance for each experiment.


### 5.1. Test Instance

In this paper, 20 different scale instances are considered, where the job’s scale is 100, 150, 200, 250, and 300, respectively, and the number of the unrelated parallel machine is 3 and 5, respectively. The job’s processing time is taken evenly between 4 and 48. According to the number of processing machines, the size of jobs is also set to 3 and 5 levels, respectively. Job’s arrival time is divided into three grades and the three time nodesR1, R2, and R3 are computed by (25)–(28). More details are shown in Table 2. Note that the SEC of a machine per unit time and the primary switching energy consumption of the machine are set to 0.3 times and 1 time of the processing energy consumption of the machine per unit time, respectively. The name of instance is like j∗c∗a∗, where ∗ is an integer number, the first ∗ indicates the scale of the job, the second ∗ indicates the number of the machine, and the third ∗ represents instance number.(25)R=0.05⋅∑j=1n∑k=1mpj,km,(26)R1=rand⋅R,(27)R2=R+rand⋅R,(28)R3=2⋅R∗rand⋅2⋅R.Table 2
Setting of experimental data.
FactorsNoteValueScale of jobsnn∈50,100,150,200,250,300Scale of machinesmm=3,5Machine capacityckc1=30,c2=40,c3=50, c4=60,c5=70Machine powerlklk=5⋅rnd⋅k+1+k−1Rang of the job’s processing timepj,kU8,48Range of the job’s arrival timerj0,R1,R1,R2,R2,R3Job’ proportion in each periodNone{50%, 25%, 25%}Job’s sizesjU11,30,U230,40,U3[40,50], U4 [50,60], U5 [60,70]Job’s proportion from small size to large sizeppj70%,20%,10%,0,0,where,m=370%,10%,10%,5%,5%,where,m=5Proportion of job with special family cluster requirementsps10%


### 5.2. Performance Metrics

To compare the performance of the multiobjective algorithms, four different indexes are selected:(1)
The number of Pareto solutions (NPS) metric: The greater the NPS is the more choices the enterpriser has.(2)
C metric: C(A, B) represents the proportion of solutions in B set dominated by solutions in A set and it can be calculated as (29). Generally speaking, A and B are two Pareto solution sets obtained by two different algorithms on the same problem.(29)CA,B=f∈B|∃e∈A:e≻ff.(3)
Hypervolume metric (HV): HV is a comprehensive index, which measures the area enclosed by the obtained Pareto frontier solutions and reference point in the target space. The larger the HV, the better the comprehensive performance of the algorithm.(4)
Inverted Generational Distance (IGD). It evaluates the convergence and distribution of the algorithm by calculating the sum of the minimum distance between each real Pareto frontier solution and the nondominated solution obtained by the algorithm. The smaller the value, the better the convergence and distribution performance of the algorithm.


### 5.3. Experiment Tests

#### 5.3.1. Parameter Setting

In AMODE, there are four parameters such as population sizeN, the iteration time iter=n×θ (where n means the number of jobs and parameter θ should be determined), parameter (a, b) that determines the size of the different population zone, and the proportion of each decoding rule (Rule1, Rule2, Ruel3, and Rule4). To determine the value of the four key parameters, the Tagui method of experiment is adopted here and a medium-sized instance j150c3a1 is utilized to do the experiment. Table 3 shows the four factor levels of each parameter. In Table 4, 16 different combinations of the orthogonal array L1644 are shown. For each combination, AMODE runs 10 times independently and the mean HV is recorded in the column of AHV in Table 4. Figure 4 shows the factor-level trend of the four parameters.Table 3
Parameters and their levels.
ParametersFactor level1234N708090100Iter2345(a, b)(0.1, 0.9)(0.2, 0.8)(0.3, 0.7)(0.4, 0.6)(Rule1, Rule2, Rule3, Rule4)(0.25, 0.25, 0.25, 0.25)(0.3, 0.3, 0.2, 0.2)(0.4, 0.4, 0.1, 0.1)(0.45, 0.45, 0.05, 0.05)Table 4
Orthogonal arrayL1644 for N, iter, (a, b), (Rule1, Rule2, Rule3, Rule4) and AHV values.
Experiments numberFactor levelsAHVNIter(a, b)(Rule1, Rule2, Rule3, Rule4)121320.6417242120.6678343330.785424130.7322531140.6852612340.6213713110.71834310.6042911430.62381032230.68161133420.6451214220.66201341210.60381422410.56741523240.681644440.6665Figure 4
Factor-level trend for the four key parameters.From the AHV values in Table4 and the factor trends in Figure 4, it can be seen that AMODE produces the corresponding best AHV when the four levels of parameters N,θ, (a, b), and (Rule1, Rule2, Rule3, Rule4) are (4, 3, 1, 3), respectively. That is, the proposed algorithm has better performance when the four key parameters are set to N = 100, θ = 4, (a, b) = (0.1, 0.9), and (Rule1, Rule2, Rule3, Rule4) = (0.4, 0.4, 0.1, 0.1).


#### 5.3.2. Experiment and Analysis of the Improved Strategy

To show the effectiveness of the improved strategies, three variants of AMODE, i.e., AMODE-I, AMODE-II, and AMODE-III, are generated. In detail, AMODE adopts all strategies in Section4. The difference between AMODE-I and AMODE is that AMODE-I just adopts the decoding rules Rule1 and Rule2 and the proportion of each rule is 50%, respectively. The difference between AMODE-I and AMODE is that AMODE-II does not adopt the AMP; the difference between AMODE-II and AMODE is that AMODE-III does not adopt APCS. More details of the four algorithms are shown in Table 5. 20 instances with 5 different scales are selected to test the performance of the four algorithms and each algorithm runs on each instance 10 times. The mean values of HV, NPFS, and IGD are recorded in Table 6 and the mean value of C is recorded in Table 7. In addition, Tables 8 and 9 are the Wilcoxon rank test results based on the terms of HV and NPFS in Table 6 and the better results are marked with boldface.Table 5
The parameters setting of the four algorithms.
AlgorithmDecodingAPCSAMSPopulation sizeIterationAMODE-I(0.5, 0.5, 0, 0)YesYes1003 ×nAMODE-II(0.4, 0.4, 0.1, 0.1)YesNo1003 ×nAMODE-III(0.4, 0.4, 0.1, 0.1)F = 0.5, CR = 0.3Yes1003 ×nAMODE(0.4, 0.4, 0.1, 0.1)YesYes1003 ×nTable 6
Comparative experimental results of four algorithms on evaluation indexes HV, NPFS, and IGD on 20 instances.
InstancesAMODE-IAMODE-IIAMODE-IIIAMODEHVNPFSIGDHVNPFSIGDHVNPFSIGDHVNPFSIGDj100c3a10.92087.83.38E − 40.82562.99.47E − 30.78153.66.44E − 30.86213.26.81E − 3j100c3a20.9456.38.67E − 40.72362.41.96E − 20.87974.83.95E − 30.881213.72.78E − 3j100c5a10.54233.18.36E − 20.7994.74.73E − 20.81115.31.56E − 20.931817.19.07E − 3j100c5a20.63294.49.48E − 20.63454.75.04E − 20.83436.21.77E − 30.85148.37.09E − 4j150c3a10.618812.54.14E − 30.596321.22.10E − 30.6065201.32E − 30.743227.55.32E − 4j150c3a20.73714.35.63E − 30.748215.24.11E − 30.812214.89.77E − 40.754416.41.37E − 4j150c5a10.618810.41.83E − 20.5963123.05E − 30.606513.19.42E − 40.743213.31.02E − 3j150c5a20.69311.31.92E − 20.711816.72.71E − 30.83718.48.34E − 40.842119.51.45E − 4j200c3a10.574517.72.69E − 20.683720.13.09E − 30.691924.71.96E − 40.722825.72.88E − 4j200c3a20.515511.51.69E − 10.645323.37.87E − 30.645324.64.39E − 30.700233.31.67E − 4j200c5a10.65399.12.14E − 20.608511.86.33E − 30.840612.39.07E − 40.891313.94.01E − 4j200c5a20.66488.21.75E − 10.667611.38.67E − 30.764710.49.04E − 30.802112.63.68E − 3j250c3a10.494712.33.44E − 10.609624.52.38E − 20.641305.62E − 30.671736.29.33E − 4j250c3a20.423615.78.76E − 10.595630.73.65E − 20.622935.36.33E − 30.641850.84.08E − 4J250c5a10.18611.52.67E − 10.201319.2.1.83E − 10.267719.83.67E − 20.290220.37.22E − 2J250c5a20.754813.63.34E − 30.7218.22.13E − 30.749917.92.98E − 30.748418.12.71E − 3j300c3a10.4189814.72.46E − 20.473216.82.53E − 30.54417.36.06E − 40.551619.44.37E − 4j300c3a20.5289810.14.35E − 10.604514.27.01E − 20.661116.83.85E − 20.6815249.07E − 4j300c5a10.1549.31.89E − 10.136110.21.04E − 10.217314.75.88E − 20.229713.94.09E − 2j300c5a20.5568.31.89E − 10.571611.64.08E − 20.7213.63.56E − 30.754220.65.73E − 4Table 7
Comparison experiments of AMODE, AMODE-I, AMODE-II, and AMODE-III in terms of C on 20 instances.
InstancesC(AMODE-I, AMODE)C(AMODE, AMODE-I)C(AMODE-II, AMODE)C(AMODE, AMODE-II)C(AMODE-III, AMODE)C(AMODE, AMODE-III)j100c3a10.250.458300.50.33330.4722j100c3a20.53070.20.360.51230.26150.4j100c5a10.1750.74580.116770.57220.27360.5278j100c5a20.03340.807900.72220.24240.4603j150c3a10.04910.7050.14820.58420.14030.5695j150c3a20.17730.43450.19690.6160.25130.5035j150c5a10.21080.46670.24530.47350.16610.5594j150c5a20.10620.39880.06200.8160.17140.5759j200c3a10.14410.5520.195200.56150.3250.4871j200c3a20.01280.88040.15650.54260.18910.6395j200c5a10.12760.52530.12990.75820.43080.4055j200c5a20.05240.64110.05240.69520.22380.3417j250c3a10.1430.51820.30540.41630.35370.4233j250c3a20.10230.50150.22160.47480.23120.4348j250c5a10.08640.91110.12080.74260.35310.3522j250c5a20.33240.37650.27190.30860.3660.4022j300c3a10.02860.79440.03750.80060.30520.5792j300c3a20.10990.45450.1960.66340.27150.5046j300c5a10.02780.8210.06480.79630.13750.581j300c5a20.03030.63360.01820.86850.29130.6573The bold values show the better C value between the two comparison algorithms.Table 8
Wilcoxon’s test of AMODE with AMODE-I, AMODE-II, and AMODE-III in HV metric for asymptotic significance (two tailed).
AMODE vs.+R−RZp valueα = 0.05AMODE-I2028−3.622p ≤ 0.01YesAMODE-II2000−3.920p ≤ 0.01YesAMODE-III19416−3.323p ≤ 0.01YesTable 9
Wilcoxon’s test of AMODE with AMODE-I, AMODE-II, and AMODE-III in NPFS metric for asymptotic significance (two tailed).
AMODE vs+R−RZp-valueα = 0.05AMODE-I2037−3.659p ≤ 0.01YesAMODE-II2044−3.697p ≤ 0.01YesAMODE-III2100−3.920p ≤ 0.01YesIn Table6, firstly, to verify the performance of the decoding rules, let us compare the results between AMODE and AMODE-I. In terms of NPFS and IGD, AMODE is worse than AMODE-I on two small scale instances j100c3a1 and j100c3a2 but better on the other instances. In terms of HV, AMODE is worse than AMODE-I on three instances j100c3a1, j100c3a2, and j200c5a2, 17 out of 20 instances that AMODE are better than AMODE-I. These indicate that the solutions of AMODE have better convergence and diversity than that of AMODE-I. In addition, in Table 7, AMODE beats AMODE-I on 19 instances besides j100c3a2 in terms of C and this shows that the performance of the algorithm is greatly impacted by the decoding rules. Secondly, to verify the performance of the adaptive mutation strategy, let us compare the results between AMODE and AMODE-II. In terms of NPFS and IGD, AMODE is only worse than MODE-II on one instance j250c5a2 while better than AMODE-II in terms of HV on all instances. In Table 7, the mean C value of AMODE also is better than AMODE-II on all instances. These indicate that AMODE has stronger exploitation and exploration capabilities and the effectiveness of the AMS. Thirdly, to verify the performance of the adaptive parameter control strategy, let us compare the results got by AMODE and AMODE-III. In terms of NPFS, AMODE is better than AMODE-III on all instances while just on instances j150c3a2 and j250c5a2 it is worse than MODE-III in terms of HV. In terms of IGD, AMODE got smaller IGD mean value on 18 than MODE-III and this shows that the solutions of AMODE have better diversity and distribution than AMODE-III. In Table 7, the mean C value of AMODE is worse than MODE-III on only two instances j200c5a1 and j250c5a1 and these show the effectiveness of the APS. In Table 8, the P-values of AMODE versus AMODE-I, AMODE versus AMODE-II, and AMODE versus AMODE-III are all less than 0.001; these show the performance of AMODE has a significant difference with AMODE-I, AMODE-II, and AMODE-III. The same conclusion can also be drawn from Table 9.


#### 5.3.3. Comparison Experiment

To assess the performance of AMODE, three algorithms, NSGAII [44], MODDE [8], a multiobjective DE algorithm, and ACBEA [19], a multiobjective evolutionary algorithm based on adaptive clustering, are adopted for the comparison experiments. The job permutation-based representation in [8, 19] is adopted in the three comparative algorithms as the solution representation, the decoding strategy in [8] is adapted, and the other aspects of the compared algorithm are implemented according to the literature. To be fair, the population size and the iteration time of the three comparison algorithms are set as the same as AMODE; each algorithm will run 10 times on each instance. The mean value of C is shown in Table 10 and the mean values of HV, NPFS and IGD are shown in Table 11. Moreover, the better value is marked in boldface. Figure 5 is a scatter diagram of the Pareto solutions obtained by the four comparison algorithms on 8 cases, respectively, Figure 6 shows the 95% confidence interval plot of HV, and Figure 7 shows the mean CPU running time of the four algorithms on each scale instance in the form of histogram.Table 10
The comparison experiment of AMODE, NSGAII, MODDE, and ACBEA in the metric ofC.
InstanceC(AMODE, NSGAII)C(NSGAII, AMODE)C(AMODE, MODDE)C(MODDE, AMODE)C(AMODE, ACBEA)C(ACBEA, AMODE)j100c3a10.87440.1135100.23640.5067j100c3a20.92300.92030.07690.46330.605j100c5a10.947300.97210.01620.58640.2207j100c5a20.73130.1667100.20150.5j150c3a1100.96670.02330.63330.2471j150c3a20.95650.0434100.66670.1132j150c5a1100.88740.10530.26310.483j150c5a2100.93330.12350.66670.136j200c3a1100.970.05640.80130.0476j200c3a2100.89250.10360.72220.0952j200c5a110100.58920.1217j200c5a2100.947400.570.225j250c3a110100.47240.3083j250c3a210100.38780.2419j250c5a1100.90910.01170.46920.3567j250c5a210100.6750.2631j300c3a110100.54120.1722j300c3a210100.50.2467j300c5a110100.76920.2389j300c5a2100.88280.03230.66670.3725Table 11
The comparison experiment in terms of metric HV, NPFS, and IGD of the four comparison algorithms.
InstanceAMODENSGAIIMODDEACBEAHVNPFSIGDHVNPFSIGDHVNPFSIGDHVNPFSIGDj100c3a10.88675.91.01E − 20.79534.39.43E-20.81682.60.1740.90133.22.05E−2j100c3a20.84194.71.83E − 20.74562.10.1130.82762.79.71E−20.96253.64.45E−2j100c5a10.94287.83.12E − 30.58215.58.14E−20.802741.73E−20.86217.84.72E−3j100c5a20.89598.44.43E − 30.64544.69.73E−20.67045.93.61E−20.88058.06.27E−3j150c3a10.719427.57.16E−40.57613.45.88E−20.6041193.92E−30.670727.96.09E − 4j150c3a20.711116.42.13E − 40.480110.81.18E−20.540915.74.73E−30.647214.31.82E−3j150c5a10.762513.38.52E − 40.5395.78.74E−20.63388.22.91E−20.68579.81.67E−3j150c5a20.885819.51.79E − 40.54511.33.54E−20.432618.68.09E−20.837316.42.83E−4j200c3a10.672625.74.68E − 40.5218102.09E−20.572116.31.93E−30.601519.68.19E−4j200c3a20.710433.31.47E − 40.6031191.03E−20.634620.41.64E−30.6868258.65E−4j200c5a10.884413.95.54E − 40.65211.82.17E−20.76049.37.45E−30.844511.71.69E−3j200c5a20.802712.66.92E−40.706.76.31E−30.714891.17E−30.775313.23.24E − 4j250c3a10.688236.21.14E − 40.548317.51.33E−20.588823.23.63E−20.619225.61.97E−3j250c3a20.666750.81.09E − 40.629319.21.68E−20.632327.55.76E−30.648438.32.38E−4j250c5a10.30220.34.81E − 30.253811.18.74E−20.266513.62.07E−20.282315.79.37E−3j250c5a20.773318.11.83E − 40.6569.61.94E−30.66399.91.65E−30.75513.24.23E−4j300c3a10.56619.42.46E−40.386416.21.78E−20.425915.86.21E−30.539722.92.27E − 4j300c3a20.6569242.73E−40.422220.14.07E−30.392519.41.83E−20.634320.52.03E − 4j300c5a10.247313.91.76E − 30.15697.89.08E−20.28911.32.91E−20.338411.74.61E−3j300c5a20.752320.62.07E − 40.360813.27.03E−20.3361173.66E−20.5515.62.09E−3The bold values in Table 11 show the better value obtained on the corresponding indicators.Figure 5
The Pareto frontier solutions got by the four comparison algorithms on 8 different instances.Figure 6
The 95% confidence interval plot of HV that the four comparison algorithms get on 20 instances, where 1 = NSGAII, 2 = MODDE, 3 = ACBEA, and 4 = AMODE.Figure 7
The mean CPU running time of different algorithms in different scale instances.In Table10, see from the mean C value that we can draw the conclusion that the Pareto frontier solutions obtained by NSGAII and MODDE are almost dominated by the solutions obtained by AMODE; in particular for the instances with 200 or more jobs, the Pareto frontier solutions obtained by NSGAII and MODDE are completely dominated by the solutions of AMODE. Therefore, from point the C indicator, AMODE outperforms NSGAII and MODDE.Compared to the valuesCACBEA,AMODE and CACBEA,AMODE, it can be seen that there are 3 out of 20 instances, such as instances j100c3a2, j100c5a2, and j150c5a1, where the CACBEA,AMODE is greater than CACBEA,AMODE. These denote the Pareto frontier solutions got by ACBEA are better than AMODE. But for the other 17 instances, the CACBEA,AMODE are greater than CACBEA,AMODE and these denote the Pareto frontier solutions got by AMODE dominate the solutions got by ACBEA on most instances. Therefore, from the indicator C, AMODE outperforms the other three algorithms.In Table11, in terms of HV, AMODE got higher value on 18 instances, ACBEA got higher value on 2 small scale instances, and NSGAII and MODDE got none. This shows that AMODE has better convergence than the other three algorithms. In terms of IGD, AMODE got smaller value on 16 instances while ACBEA got smaller value on the other 4 instances. These denote that the distribution and diversity of the solutions that AMODE got are better than the other three comparison algorithms. In terms of NPFS, AMODE obtained more dominated solutions on 17 instances, ACBEA obtained more dominated solutions on the remaining instances, and the number of dominated solutions that NSGAII and MODDE obtained is less compared with AMODE and ACBEA. Therefore, in terms of NPFS, AMODE outperforms the other three algorithms. These indicate that AMODE can provide more option for the operator. The experimental results in Table 11 are just consistent with the experimental conclusion in Table 11, which shows that the AMODE has great advantages in dealing with the multiobjective scheduling problem of UPBMP.To compare the quality of the solution obtained by the four comparison algorithms, the spread of the solutions on 8 different instances with scale are shown in Figure5, where the x-axis shows the makespan and the y-axis denotes the TEC, respectively. It is obvious that the Pareto solution obtained by AMODE is better than that of the other three compared algorithms in terms of quality and distribution. Figure 6 is the 95% confidence interval plot of HV of the four comparison algorithms obtained on 20 instances. It can seen that the line of 95% confidence interval of AMODE on most instances is shorter and this indicates that AMODE has better robustness than the other three comparison algorithms. From the value of the 95% confidence interval, AMODE is greater than the other comparison three algorithms on 18 instances; this indicates that AMODE outperforms the other comparison three algorithms, especially medium- and large-scale problems. ACBEA comes the second, MODDE is the third, and NSGAII is the last. As it can be seen from Figure 7, for the problem of the same scale, the algorithm AMODE is not as fast as the algorithms NSGAII and MODDE but faster than the algorithm ACBEA. It shows that, to obtain a better Pareto fronter solution, it is necessary to sacrifice the CPU running time, but as can be seen from Figure 7, the overall running time of the algorithm AMODE is within an acceptable range. When the scale of the problem is 300, the algorithm in this paper needs to run about 8 minutes on average.


## 5.1. Test Instance

In this paper, 20 different scale instances are considered, where the job’s scale is 100, 150, 200, 250, and 300, respectively, and the number of the unrelated parallel machine is 3 and 5, respectively. The job’s processing time is taken evenly between 4 and 48. According to the number of processing machines, the size of jobs is also set to 3 and 5 levels, respectively. Job’s arrival time is divided into three grades and the three time nodesR1, R2, and R3 are computed by (25)–(28). More details are shown in Table 2. Note that the SEC of a machine per unit time and the primary switching energy consumption of the machine are set to 0.3 times and 1 time of the processing energy consumption of the machine per unit time, respectively. The name of instance is like j∗c∗a∗, where ∗ is an integer number, the first ∗ indicates the scale of the job, the second ∗ indicates the number of the machine, and the third ∗ represents instance number.(25)R=0.05⋅∑j=1n∑k=1mpj,km,(26)R1=rand⋅R,(27)R2=R+rand⋅R,(28)R3=2⋅R∗rand⋅2⋅R.Table 2
Setting of experimental data.
FactorsNoteValueScale of jobsnn∈50,100,150,200,250,300Scale of machinesmm=3,5Machine capacityckc1=30,c2=40,c3=50, c4=60,c5=70Machine powerlklk=5⋅rnd⋅k+1+k−1Rang of the job’s processing timepj,kU8,48Range of the job’s arrival timerj0,R1,R1,R2,R2,R3Job’ proportion in each periodNone{50%, 25%, 25%}Job’s sizesjU11,30,U230,40,U3[40,50], U4 [50,60], U5 [60,70]Job’s proportion from small size to large sizeppj70%,20%,10%,0,0,where,m=370%,10%,10%,5%,5%,where,m=5Proportion of job with special family cluster requirementsps10%


## 5.2. Performance Metrics

To compare the performance of the multiobjective algorithms, four different indexes are selected:(1)
The number of Pareto solutions (NPS) metric: The greater the NPS is the more choices the enterpriser has.(2)
C metric: C(A, B) represents the proportion of solutions in B set dominated by solutions in A set and it can be calculated as (29). Generally speaking, A and B are two Pareto solution sets obtained by two different algorithms on the same problem.(29)CA,B=f∈B|∃e∈A:e≻ff.(3)
Hypervolume metric (HV): HV is a comprehensive index, which measures the area enclosed by the obtained Pareto frontier solutions and reference point in the target space. The larger the HV, the better the comprehensive performance of the algorithm.(4)
Inverted Generational Distance (IGD). It evaluates the convergence and distribution of the algorithm by calculating the sum of the minimum distance between each real Pareto frontier solution and the nondominated solution obtained by the algorithm. The smaller the value, the better the convergence and distribution performance of the algorithm.


## 5.3. Experiment Tests

### 5.3.1. Parameter Setting

In AMODE, there are four parameters such as population sizeN, the iteration time iter=n×θ (where n means the number of jobs and parameter θ should be determined), parameter (a, b) that determines the size of the different population zone, and the proportion of each decoding rule (Rule1, Rule2, Ruel3, and Rule4). To determine the value of the four key parameters, the Tagui method of experiment is adopted here and a medium-sized instance j150c3a1 is utilized to do the experiment. Table 3 shows the four factor levels of each parameter. In Table 4, 16 different combinations of the orthogonal array L1644 are shown. For each combination, AMODE runs 10 times independently and the mean HV is recorded in the column of AHV in Table 4. Figure 4 shows the factor-level trend of the four parameters.Table 3
Parameters and their levels.
ParametersFactor level1234N708090100Iter2345(a, b)(0.1, 0.9)(0.2, 0.8)(0.3, 0.7)(0.4, 0.6)(Rule1, Rule2, Rule3, Rule4)(0.25, 0.25, 0.25, 0.25)(0.3, 0.3, 0.2, 0.2)(0.4, 0.4, 0.1, 0.1)(0.45, 0.45, 0.05, 0.05)Table 4
Orthogonal arrayL1644 for N, iter, (a, b), (Rule1, Rule2, Rule3, Rule4) and AHV values.
Experiments numberFactor levelsAHVNIter(a, b)(Rule1, Rule2, Rule3, Rule4)121320.6417242120.6678343330.785424130.7322531140.6852612340.6213713110.71834310.6042911430.62381032230.68161133420.6451214220.66201341210.60381422410.56741523240.681644440.6665Figure 4
Factor-level trend for the four key parameters.From the AHV values in Table4 and the factor trends in Figure 4, it can be seen that AMODE produces the corresponding best AHV when the four levels of parameters N,θ, (a, b), and (Rule1, Rule2, Rule3, Rule4) are (4, 3, 1, 3), respectively. That is, the proposed algorithm has better performance when the four key parameters are set to N = 100, θ = 4, (a, b) = (0.1, 0.9), and (Rule1, Rule2, Rule3, Rule4) = (0.4, 0.4, 0.1, 0.1).


### 5.3.2. Experiment and Analysis of the Improved Strategy

To show the effectiveness of the improved strategies, three variants of AMODE, i.e., AMODE-I, AMODE-II, and AMODE-III, are generated. In detail, AMODE adopts all strategies in Section4. The difference between AMODE-I and AMODE is that AMODE-I just adopts the decoding rules Rule1 and Rule2 and the proportion of each rule is 50%, respectively. The difference between AMODE-I and AMODE is that AMODE-II does not adopt the AMP; the difference between AMODE-II and AMODE is that AMODE-III does not adopt APCS. More details of the four algorithms are shown in Table 5. 20 instances with 5 different scales are selected to test the performance of the four algorithms and each algorithm runs on each instance 10 times. The mean values of HV, NPFS, and IGD are recorded in Table 6 and the mean value of C is recorded in Table 7. In addition, Tables 8 and 9 are the Wilcoxon rank test results based on the terms of HV and NPFS in Table 6 and the better results are marked with boldface.Table 5
The parameters setting of the four algorithms.
AlgorithmDecodingAPCSAMSPopulation sizeIterationAMODE-I(0.5, 0.5, 0, 0)YesYes1003 ×nAMODE-II(0.4, 0.4, 0.1, 0.1)YesNo1003 ×nAMODE-III(0.4, 0.4, 0.1, 0.1)F = 0.5, CR = 0.3Yes1003 ×nAMODE(0.4, 0.4, 0.1, 0.1)YesYes1003 ×nTable 6
Comparative experimental results of four algorithms on evaluation indexes HV, NPFS, and IGD on 20 instances.
InstancesAMODE-IAMODE-IIAMODE-IIIAMODEHVNPFSIGDHVNPFSIGDHVNPFSIGDHVNPFSIGDj100c3a10.92087.83.38E − 40.82562.99.47E − 30.78153.66.44E − 30.86213.26.81E − 3j100c3a20.9456.38.67E − 40.72362.41.96E − 20.87974.83.95E − 30.881213.72.78E − 3j100c5a10.54233.18.36E − 20.7994.74.73E − 20.81115.31.56E − 20.931817.19.07E − 3j100c5a20.63294.49.48E − 20.63454.75.04E − 20.83436.21.77E − 30.85148.37.09E − 4j150c3a10.618812.54.14E − 30.596321.22.10E − 30.6065201.32E − 30.743227.55.32E − 4j150c3a20.73714.35.63E − 30.748215.24.11E − 30.812214.89.77E − 40.754416.41.37E − 4j150c5a10.618810.41.83E − 20.5963123.05E − 30.606513.19.42E − 40.743213.31.02E − 3j150c5a20.69311.31.92E − 20.711816.72.71E − 30.83718.48.34E − 40.842119.51.45E − 4j200c3a10.574517.72.69E − 20.683720.13.09E − 30.691924.71.96E − 40.722825.72.88E − 4j200c3a20.515511.51.69E − 10.645323.37.87E − 30.645324.64.39E − 30.700233.31.67E − 4j200c5a10.65399.12.14E − 20.608511.86.33E − 30.840612.39.07E − 40.891313.94.01E − 4j200c5a20.66488.21.75E − 10.667611.38.67E − 30.764710.49.04E − 30.802112.63.68E − 3j250c3a10.494712.33.44E − 10.609624.52.38E − 20.641305.62E − 30.671736.29.33E − 4j250c3a20.423615.78.76E − 10.595630.73.65E − 20.622935.36.33E − 30.641850.84.08E − 4J250c5a10.18611.52.67E − 10.201319.2.1.83E − 10.267719.83.67E − 20.290220.37.22E − 2J250c5a20.754813.63.34E − 30.7218.22.13E − 30.749917.92.98E − 30.748418.12.71E − 3j300c3a10.4189814.72.46E − 20.473216.82.53E − 30.54417.36.06E − 40.551619.44.37E − 4j300c3a20.5289810.14.35E − 10.604514.27.01E − 20.661116.83.85E − 20.6815249.07E − 4j300c5a10.1549.31.89E − 10.136110.21.04E − 10.217314.75.88E − 20.229713.94.09E − 2j300c5a20.5568.31.89E − 10.571611.64.08E − 20.7213.63.56E − 30.754220.65.73E − 4Table 7
Comparison experiments of AMODE, AMODE-I, AMODE-II, and AMODE-III in terms of C on 20 instances.
InstancesC(AMODE-I, AMODE)C(AMODE, AMODE-I)C(AMODE-II, AMODE)C(AMODE, AMODE-II)C(AMODE-III, AMODE)C(AMODE, AMODE-III)j100c3a10.250.458300.50.33330.4722j100c3a20.53070.20.360.51230.26150.4j100c5a10.1750.74580.116770.57220.27360.5278j100c5a20.03340.807900.72220.24240.4603j150c3a10.04910.7050.14820.58420.14030.5695j150c3a20.17730.43450.19690.6160.25130.5035j150c5a10.21080.46670.24530.47350.16610.5594j150c5a20.10620.39880.06200.8160.17140.5759j200c3a10.14410.5520.195200.56150.3250.4871j200c3a20.01280.88040.15650.54260.18910.6395j200c5a10.12760.52530.12990.75820.43080.4055j200c5a20.05240.64110.05240.69520.22380.3417j250c3a10.1430.51820.30540.41630.35370.4233j250c3a20.10230.50150.22160.47480.23120.4348j250c5a10.08640.91110.12080.74260.35310.3522j250c5a20.33240.37650.27190.30860.3660.4022j300c3a10.02860.79440.03750.80060.30520.5792j300c3a20.10990.45450.1960.66340.27150.5046j300c5a10.02780.8210.06480.79630.13750.581j300c5a20.03030.63360.01820.86850.29130.6573The bold values show the better C value between the two comparison algorithms.Table 8
Wilcoxon’s test of AMODE with AMODE-I, AMODE-II, and AMODE-III in HV metric for asymptotic significance (two tailed).
AMODE vs.+R−RZp valueα = 0.05AMODE-I2028−3.622p ≤ 0.01YesAMODE-II2000−3.920p ≤ 0.01YesAMODE-III19416−3.323p ≤ 0.01YesTable 9
Wilcoxon’s test of AMODE with AMODE-I, AMODE-II, and AMODE-III in NPFS metric for asymptotic significance (two tailed).
AMODE vs+R−RZp-valueα = 0.05AMODE-I2037−3.659p ≤ 0.01YesAMODE-II2044−3.697p ≤ 0.01YesAMODE-III2100−3.920p ≤ 0.01YesIn Table6, firstly, to verify the performance of the decoding rules, let us compare the results between AMODE and AMODE-I. In terms of NPFS and IGD, AMODE is worse than AMODE-I on two small scale instances j100c3a1 and j100c3a2 but better on the other instances. In terms of HV, AMODE is worse than AMODE-I on three instances j100c3a1, j100c3a2, and j200c5a2, 17 out of 20 instances that AMODE are better than AMODE-I. These indicate that the solutions of AMODE have better convergence and diversity than that of AMODE-I. In addition, in Table 7, AMODE beats AMODE-I on 19 instances besides j100c3a2 in terms of C and this shows that the performance of the algorithm is greatly impacted by the decoding rules. Secondly, to verify the performance of the adaptive mutation strategy, let us compare the results between AMODE and AMODE-II. In terms of NPFS and IGD, AMODE is only worse than MODE-II on one instance j250c5a2 while better than AMODE-II in terms of HV on all instances. In Table 7, the mean C value of AMODE also is better than AMODE-II on all instances. These indicate that AMODE has stronger exploitation and exploration capabilities and the effectiveness of the AMS. Thirdly, to verify the performance of the adaptive parameter control strategy, let us compare the results got by AMODE and AMODE-III. In terms of NPFS, AMODE is better than AMODE-III on all instances while just on instances j150c3a2 and j250c5a2 it is worse than MODE-III in terms of HV. In terms of IGD, AMODE got smaller IGD mean value on 18 than MODE-III and this shows that the solutions of AMODE have better diversity and distribution than AMODE-III. In Table 7, the mean C value of AMODE is worse than MODE-III on only two instances j200c5a1 and j250c5a1 and these show the effectiveness of the APS. In Table 8, the P-values of AMODE versus AMODE-I, AMODE versus AMODE-II, and AMODE versus AMODE-III are all less than 0.001; these show the performance of AMODE has a significant difference with AMODE-I, AMODE-II, and AMODE-III. The same conclusion can also be drawn from Table 9.


### 5.3.3. Comparison Experiment

To assess the performance of AMODE, three algorithms, NSGAII [44], MODDE [8], a multiobjective DE algorithm, and ACBEA [19], a multiobjective evolutionary algorithm based on adaptive clustering, are adopted for the comparison experiments. The job permutation-based representation in [8, 19] is adopted in the three comparative algorithms as the solution representation, the decoding strategy in [8] is adapted, and the other aspects of the compared algorithm are implemented according to the literature. To be fair, the population size and the iteration time of the three comparison algorithms are set as the same as AMODE; each algorithm will run 10 times on each instance. The mean value of C is shown in Table 10 and the mean values of HV, NPFS and IGD are shown in Table 11. Moreover, the better value is marked in boldface. Figure 5 is a scatter diagram of the Pareto solutions obtained by the four comparison algorithms on 8 cases, respectively, Figure 6 shows the 95% confidence interval plot of HV, and Figure 7 shows the mean CPU running time of the four algorithms on each scale instance in the form of histogram.Table 10
The comparison experiment of AMODE, NSGAII, MODDE, and ACBEA in the metric ofC.
InstanceC(AMODE, NSGAII)C(NSGAII, AMODE)C(AMODE, MODDE)C(MODDE, AMODE)C(AMODE, ACBEA)C(ACBEA, AMODE)j100c3a10.87440.1135100.23640.5067j100c3a20.92300.92030.07690.46330.605j100c5a10.947300.97210.01620.58640.2207j100c5a20.73130.1667100.20150.5j150c3a1100.96670.02330.63330.2471j150c3a20.95650.0434100.66670.1132j150c5a1100.88740.10530.26310.483j150c5a2100.93330.12350.66670.136j200c3a1100.970.05640.80130.0476j200c3a2100.89250.10360.72220.0952j200c5a110100.58920.1217j200c5a2100.947400.570.225j250c3a110100.47240.3083j250c3a210100.38780.2419j250c5a1100.90910.01170.46920.3567j250c5a210100.6750.2631j300c3a110100.54120.1722j300c3a210100.50.2467j300c5a110100.76920.2389j300c5a2100.88280.03230.66670.3725Table 11
The comparison experiment in terms of metric HV, NPFS, and IGD of the four comparison algorithms.
InstanceAMODENSGAIIMODDEACBEAHVNPFSIGDHVNPFSIGDHVNPFSIGDHVNPFSIGDj100c3a10.88675.91.01E − 20.79534.39.43E-20.81682.60.1740.90133.22.05E−2j100c3a20.84194.71.83E − 20.74562.10.1130.82762.79.71E−20.96253.64.45E−2j100c5a10.94287.83.12E − 30.58215.58.14E−20.802741.73E−20.86217.84.72E−3j100c5a20.89598.44.43E − 30.64544.69.73E−20.67045.93.61E−20.88058.06.27E−3j150c3a10.719427.57.16E−40.57613.45.88E−20.6041193.92E−30.670727.96.09E − 4j150c3a20.711116.42.13E − 40.480110.81.18E−20.540915.74.73E−30.647214.31.82E−3j150c5a10.762513.38.52E − 40.5395.78.74E−20.63388.22.91E−20.68579.81.67E−3j150c5a20.885819.51.79E − 40.54511.33.54E−20.432618.68.09E−20.837316.42.83E−4j200c3a10.672625.74.68E − 40.5218102.09E−20.572116.31.93E−30.601519.68.19E−4j200c3a20.710433.31.47E − 40.6031191.03E−20.634620.41.64E−30.6868258.65E−4j200c5a10.884413.95.54E − 40.65211.82.17E−20.76049.37.45E−30.844511.71.69E−3j200c5a20.802712.66.92E−40.706.76.31E−30.714891.17E−30.775313.23.24E − 4j250c3a10.688236.21.14E − 40.548317.51.33E−20.588823.23.63E−20.619225.61.97E−3j250c3a20.666750.81.09E − 40.629319.21.68E−20.632327.55.76E−30.648438.32.38E−4j250c5a10.30220.34.81E − 30.253811.18.74E−20.266513.62.07E−20.282315.79.37E−3j250c5a20.773318.11.83E − 40.6569.61.94E−30.66399.91.65E−30.75513.24.23E−4j300c3a10.56619.42.46E−40.386416.21.78E−20.425915.86.21E−30.539722.92.27E − 4j300c3a20.6569242.73E−40.422220.14.07E−30.392519.41.83E−20.634320.52.03E − 4j300c5a10.247313.91.76E − 30.15697.89.08E−20.28911.32.91E−20.338411.74.61E−3j300c5a20.752320.62.07E − 40.360813.27.03E−20.3361173.66E−20.5515.62.09E−3The bold values in Table 11 show the better value obtained on the corresponding indicators.Figure 5
The Pareto frontier solutions got by the four comparison algorithms on 8 different instances.Figure 6
The 95% confidence interval plot of HV that the four comparison algorithms get on 20 instances, where 1 = NSGAII, 2 = MODDE, 3 = ACBEA, and 4 = AMODE.Figure 7
The mean CPU running time of different algorithms in different scale instances.In Table10, see from the mean C value that we can draw the conclusion that the Pareto frontier solutions obtained by NSGAII and MODDE are almost dominated by the solutions obtained by AMODE; in particular for the instances with 200 or more jobs, the Pareto frontier solutions obtained by NSGAII and MODDE are completely dominated by the solutions of AMODE. Therefore, from point the C indicator, AMODE outperforms NSGAII and MODDE.Compared to the valuesCACBEA,AMODE and CACBEA,AMODE, it can be seen that there are 3 out of 20 instances, such as instances j100c3a2, j100c5a2, and j150c5a1, where the CACBEA,AMODE is greater than CACBEA,AMODE. These denote the Pareto frontier solutions got by ACBEA are better than AMODE. But for the other 17 instances, the CACBEA,AMODE are greater than CACBEA,AMODE and these denote the Pareto frontier solutions got by AMODE dominate the solutions got by ACBEA on most instances. Therefore, from the indicator C, AMODE outperforms the other three algorithms.In Table11, in terms of HV, AMODE got higher value on 18 instances, ACBEA got higher value on 2 small scale instances, and NSGAII and MODDE got none. This shows that AMODE has better convergence than the other three algorithms. In terms of IGD, AMODE got smaller value on 16 instances while ACBEA got smaller value on the other 4 instances. These denote that the distribution and diversity of the solutions that AMODE got are better than the other three comparison algorithms. In terms of NPFS, AMODE obtained more dominated solutions on 17 instances, ACBEA obtained more dominated solutions on the remaining instances, and the number of dominated solutions that NSGAII and MODDE obtained is less compared with AMODE and ACBEA. Therefore, in terms of NPFS, AMODE outperforms the other three algorithms. These indicate that AMODE can provide more option for the operator. The experimental results in Table 11 are just consistent with the experimental conclusion in Table 11, which shows that the AMODE has great advantages in dealing with the multiobjective scheduling problem of UPBMP.To compare the quality of the solution obtained by the four comparison algorithms, the spread of the solutions on 8 different instances with scale are shown in Figure5, where the x-axis shows the makespan and the y-axis denotes the TEC, respectively. It is obvious that the Pareto solution obtained by AMODE is better than that of the other three compared algorithms in terms of quality and distribution. Figure 6 is the 95% confidence interval plot of HV of the four comparison algorithms obtained on 20 instances. It can seen that the line of 95% confidence interval of AMODE on most instances is shorter and this indicates that AMODE has better robustness than the other three comparison algorithms. From the value of the 95% confidence interval, AMODE is greater than the other comparison three algorithms on 18 instances; this indicates that AMODE outperforms the other comparison three algorithms, especially medium- and large-scale problems. ACBEA comes the second, MODDE is the third, and NSGAII is the last. As it can be seen from Figure 7, for the problem of the same scale, the algorithm AMODE is not as fast as the algorithms NSGAII and MODDE but faster than the algorithm ACBEA. It shows that, to obtain a better Pareto fronter solution, it is necessary to sacrifice the CPU running time, but as can be seen from Figure 7, the overall running time of the algorithm AMODE is within an acceptable range. When the scale of the problem is 300, the algorithm in this paper needs to run about 8 minutes on average.


## 5.3.1. Parameter Setting

In AMODE, there are four parameters such as population sizeN, the iteration time iter=n×θ (where n means the number of jobs and parameter θ should be determined), parameter (a, b) that determines the size of the different population zone, and the proportion of each decoding rule (Rule1, Rule2, Ruel3, and Rule4). To determine the value of the four key parameters, the Tagui method of experiment is adopted here and a medium-sized instance j150c3a1 is utilized to do the experiment. Table 3 shows the four factor levels of each parameter. In Table 4, 16 different combinations of the orthogonal array L1644 are shown. For each combination, AMODE runs 10 times independently and the mean HV is recorded in the column of AHV in Table 4. Figure 4 shows the factor-level trend of the four parameters.Table 3
Parameters and their levels.
ParametersFactor level1234N708090100Iter2345(a, b)(0.1, 0.9)(0.2, 0.8)(0.3, 0.7)(0.4, 0.6)(Rule1, Rule2, Rule3, Rule4)(0.25, 0.25, 0.25, 0.25)(0.3, 0.3, 0.2, 0.2)(0.4, 0.4, 0.1, 0.1)(0.45, 0.45, 0.05, 0.05)Table 4
Orthogonal arrayL1644 for N, iter, (a, b), (Rule1, Rule2, Rule3, Rule4) and AHV values.
Experiments numberFactor levelsAHVNIter(a, b)(Rule1, Rule2, Rule3, Rule4)121320.6417242120.6678343330.785424130.7322531140.6852612340.6213713110.71834310.6042911430.62381032230.68161133420.6451214220.66201341210.60381422410.56741523240.681644440.6665Figure 4
Factor-level trend for the four key parameters.From the AHV values in Table4 and the factor trends in Figure 4, it can be seen that AMODE produces the corresponding best AHV when the four levels of parameters N,θ, (a, b), and (Rule1, Rule2, Rule3, Rule4) are (4, 3, 1, 3), respectively. That is, the proposed algorithm has better performance when the four key parameters are set to N = 100, θ = 4, (a, b) = (0.1, 0.9), and (Rule1, Rule2, Rule3, Rule4) = (0.4, 0.4, 0.1, 0.1).


## 5.3.2. Experiment and Analysis of the Improved Strategy

To show the effectiveness of the improved strategies, three variants of AMODE, i.e., AMODE-I, AMODE-II, and AMODE-III, are generated. In detail, AMODE adopts all strategies in Section4. The difference between AMODE-I and AMODE is that AMODE-I just adopts the decoding rules Rule1 and Rule2 and the proportion of each rule is 50%, respectively. The difference between AMODE-I and AMODE is that AMODE-II does not adopt the AMP; the difference between AMODE-II and AMODE is that AMODE-III does not adopt APCS. More details of the four algorithms are shown in Table 5. 20 instances with 5 different scales are selected to test the performance of the four algorithms and each algorithm runs on each instance 10 times. The mean values of HV, NPFS, and IGD are recorded in Table 6 and the mean value of C is recorded in Table 7. In addition, Tables 8 and 9 are the Wilcoxon rank test results based on the terms of HV and NPFS in Table 6 and the better results are marked with boldface.Table 5
The parameters setting of the four algorithms.
AlgorithmDecodingAPCSAMSPopulation sizeIterationAMODE-I(0.5, 0.5, 0, 0)YesYes1003 ×nAMODE-II(0.4, 0.4, 0.1, 0.1)YesNo1003 ×nAMODE-III(0.4, 0.4, 0.1, 0.1)F = 0.5, CR = 0.3Yes1003 ×nAMODE(0.4, 0.4, 0.1, 0.1)YesYes1003 ×nTable 6
Comparative experimental results of four algorithms on evaluation indexes HV, NPFS, and IGD on 20 instances.
InstancesAMODE-IAMODE-IIAMODE-IIIAMODEHVNPFSIGDHVNPFSIGDHVNPFSIGDHVNPFSIGDj100c3a10.92087.83.38E − 40.82562.99.47E − 30.78153.66.44E − 30.86213.26.81E − 3j100c3a20.9456.38.67E − 40.72362.41.96E − 20.87974.83.95E − 30.881213.72.78E − 3j100c5a10.54233.18.36E − 20.7994.74.73E − 20.81115.31.56E − 20.931817.19.07E − 3j100c5a20.63294.49.48E − 20.63454.75.04E − 20.83436.21.77E − 30.85148.37.09E − 4j150c3a10.618812.54.14E − 30.596321.22.10E − 30.6065201.32E − 30.743227.55.32E − 4j150c3a20.73714.35.63E − 30.748215.24.11E − 30.812214.89.77E − 40.754416.41.37E − 4j150c5a10.618810.41.83E − 20.5963123.05E − 30.606513.19.42E − 40.743213.31.02E − 3j150c5a20.69311.31.92E − 20.711816.72.71E − 30.83718.48.34E − 40.842119.51.45E − 4j200c3a10.574517.72.69E − 20.683720.13.09E − 30.691924.71.96E − 40.722825.72.88E − 4j200c3a20.515511.51.69E − 10.645323.37.87E − 30.645324.64.39E − 30.700233.31.67E − 4j200c5a10.65399.12.14E − 20.608511.86.33E − 30.840612.39.07E − 40.891313.94.01E − 4j200c5a20.66488.21.75E − 10.667611.38.67E − 30.764710.49.04E − 30.802112.63.68E − 3j250c3a10.494712.33.44E − 10.609624.52.38E − 20.641305.62E − 30.671736.29.33E − 4j250c3a20.423615.78.76E − 10.595630.73.65E − 20.622935.36.33E − 30.641850.84.08E − 4J250c5a10.18611.52.67E − 10.201319.2.1.83E − 10.267719.83.67E − 20.290220.37.22E − 2J250c5a20.754813.63.34E − 30.7218.22.13E − 30.749917.92.98E − 30.748418.12.71E − 3j300c3a10.4189814.72.46E − 20.473216.82.53E − 30.54417.36.06E − 40.551619.44.37E − 4j300c3a20.5289810.14.35E − 10.604514.27.01E − 20.661116.83.85E − 20.6815249.07E − 4j300c5a10.1549.31.89E − 10.136110.21.04E − 10.217314.75.88E − 20.229713.94.09E − 2j300c5a20.5568.31.89E − 10.571611.64.08E − 20.7213.63.56E − 30.754220.65.73E − 4Table 7
Comparison experiments of AMODE, AMODE-I, AMODE-II, and AMODE-III in terms of C on 20 instances.
InstancesC(AMODE-I, AMODE)C(AMODE, AMODE-I)C(AMODE-II, AMODE)C(AMODE, AMODE-II)C(AMODE-III, AMODE)C(AMODE, AMODE-III)j100c3a10.250.458300.50.33330.4722j100c3a20.53070.20.360.51230.26150.4j100c5a10.1750.74580.116770.57220.27360.5278j100c5a20.03340.807900.72220.24240.4603j150c3a10.04910.7050.14820.58420.14030.5695j150c3a20.17730.43450.19690.6160.25130.5035j150c5a10.21080.46670.24530.47350.16610.5594j150c5a20.10620.39880.06200.8160.17140.5759j200c3a10.14410.5520.195200.56150.3250.4871j200c3a20.01280.88040.15650.54260.18910.6395j200c5a10.12760.52530.12990.75820.43080.4055j200c5a20.05240.64110.05240.69520.22380.3417j250c3a10.1430.51820.30540.41630.35370.4233j250c3a20.10230.50150.22160.47480.23120.4348j250c5a10.08640.91110.12080.74260.35310.3522j250c5a20.33240.37650.27190.30860.3660.4022j300c3a10.02860.79440.03750.80060.30520.5792j300c3a20.10990.45450.1960.66340.27150.5046j300c5a10.02780.8210.06480.79630.13750.581j300c5a20.03030.63360.01820.86850.29130.6573The bold values show the better C value between the two comparison algorithms.Table 8
Wilcoxon’s test of AMODE with AMODE-I, AMODE-II, and AMODE-III in HV metric for asymptotic significance (two tailed).
AMODE vs.+R−RZp valueα = 0.05AMODE-I2028−3.622p ≤ 0.01YesAMODE-II2000−3.920p ≤ 0.01YesAMODE-III19416−3.323p ≤ 0.01YesTable 9
Wilcoxon’s test of AMODE with AMODE-I, AMODE-II, and AMODE-III in NPFS metric for asymptotic significance (two tailed).
AMODE vs+R−RZp-valueα = 0.05AMODE-I2037−3.659p ≤ 0.01YesAMODE-II2044−3.697p ≤ 0.01YesAMODE-III2100−3.920p ≤ 0.01YesIn Table6, firstly, to verify the performance of the decoding rules, let us compare the results between AMODE and AMODE-I. In terms of NPFS and IGD, AMODE is worse than AMODE-I on two small scale instances j100c3a1 and j100c3a2 but better on the other instances. In terms of HV, AMODE is worse than AMODE-I on three instances j100c3a1, j100c3a2, and j200c5a2, 17 out of 20 instances that AMODE are better than AMODE-I. These indicate that the solutions of AMODE have better convergence and diversity than that of AMODE-I. In addition, in Table 7, AMODE beats AMODE-I on 19 instances besides j100c3a2 in terms of C and this shows that the performance of the algorithm is greatly impacted by the decoding rules. Secondly, to verify the performance of the adaptive mutation strategy, let us compare the results between AMODE and AMODE-II. In terms of NPFS and IGD, AMODE is only worse than MODE-II on one instance j250c5a2 while better than AMODE-II in terms of HV on all instances. In Table 7, the mean C value of AMODE also is better than AMODE-II on all instances. These indicate that AMODE has stronger exploitation and exploration capabilities and the effectiveness of the AMS. Thirdly, to verify the performance of the adaptive parameter control strategy, let us compare the results got by AMODE and AMODE-III. In terms of NPFS, AMODE is better than AMODE-III on all instances while just on instances j150c3a2 and j250c5a2 it is worse than MODE-III in terms of HV. In terms of IGD, AMODE got smaller IGD mean value on 18 than MODE-III and this shows that the solutions of AMODE have better diversity and distribution than AMODE-III. In Table 7, the mean C value of AMODE is worse than MODE-III on only two instances j200c5a1 and j250c5a1 and these show the effectiveness of the APS. In Table 8, the P-values of AMODE versus AMODE-I, AMODE versus AMODE-II, and AMODE versus AMODE-III are all less than 0.001; these show the performance of AMODE has a significant difference with AMODE-I, AMODE-II, and AMODE-III. The same conclusion can also be drawn from Table 9.


## 5.3.3. Comparison Experiment

To assess the performance of AMODE, three algorithms, NSGAII [44], MODDE [8], a multiobjective DE algorithm, and ACBEA [19], a multiobjective evolutionary algorithm based on adaptive clustering, are adopted for the comparison experiments. The job permutation-based representation in [8, 19] is adopted in the three comparative algorithms as the solution representation, the decoding strategy in [8] is adapted, and the other aspects of the compared algorithm are implemented according to the literature. To be fair, the population size and the iteration time of the three comparison algorithms are set as the same as AMODE; each algorithm will run 10 times on each instance. The mean value of C is shown in Table 10 and the mean values of HV, NPFS and IGD are shown in Table 11. Moreover, the better value is marked in boldface. Figure 5 is a scatter diagram of the Pareto solutions obtained by the four comparison algorithms on 8 cases, respectively, Figure 6 shows the 95% confidence interval plot of HV, and Figure 7 shows the mean CPU running time of the four algorithms on each scale instance in the form of histogram.Table 10
The comparison experiment of AMODE, NSGAII, MODDE, and ACBEA in the metric ofC.
InstanceC(AMODE, NSGAII)C(NSGAII, AMODE)C(AMODE, MODDE)C(MODDE, AMODE)C(AMODE, ACBEA)C(ACBEA, AMODE)j100c3a10.87440.1135100.23640.5067j100c3a20.92300.92030.07690.46330.605j100c5a10.947300.97210.01620.58640.2207j100c5a20.73130.1667100.20150.5j150c3a1100.96670.02330.63330.2471j150c3a20.95650.0434100.66670.1132j150c5a1100.88740.10530.26310.483j150c5a2100.93330.12350.66670.136j200c3a1100.970.05640.80130.0476j200c3a2100.89250.10360.72220.0952j200c5a110100.58920.1217j200c5a2100.947400.570.225j250c3a110100.47240.3083j250c3a210100.38780.2419j250c5a1100.90910.01170.46920.3567j250c5a210100.6750.2631j300c3a110100.54120.1722j300c3a210100.50.2467j300c5a110100.76920.2389j300c5a2100.88280.03230.66670.3725Table 11
The comparison experiment in terms of metric HV, NPFS, and IGD of the four comparison algorithms.
InstanceAMODENSGAIIMODDEACBEAHVNPFSIGDHVNPFSIGDHVNPFSIGDHVNPFSIGDj100c3a10.88675.91.01E − 20.79534.39.43E-20.81682.60.1740.90133.22.05E−2j100c3a20.84194.71.83E − 20.74562.10.1130.82762.79.71E−20.96253.64.45E−2j100c5a10.94287.83.12E − 30.58215.58.14E−20.802741.73E−20.86217.84.72E−3j100c5a20.89598.44.43E − 30.64544.69.73E−20.67045.93.61E−20.88058.06.27E−3j150c3a10.719427.57.16E−40.57613.45.88E−20.6041193.92E−30.670727.96.09E − 4j150c3a20.711116.42.13E − 40.480110.81.18E−20.540915.74.73E−30.647214.31.82E−3j150c5a10.762513.38.52E − 40.5395.78.74E−20.63388.22.91E−20.68579.81.67E−3j150c5a20.885819.51.79E − 40.54511.33.54E−20.432618.68.09E−20.837316.42.83E−4j200c3a10.672625.74.68E − 40.5218102.09E−20.572116.31.93E−30.601519.68.19E−4j200c3a20.710433.31.47E − 40.6031191.03E−20.634620.41.64E−30.6868258.65E−4j200c5a10.884413.95.54E − 40.65211.82.17E−20.76049.37.45E−30.844511.71.69E−3j200c5a20.802712.66.92E−40.706.76.31E−30.714891.17E−30.775313.23.24E − 4j250c3a10.688236.21.14E − 40.548317.51.33E−20.588823.23.63E−20.619225.61.97E−3j250c3a20.666750.81.09E − 40.629319.21.68E−20.632327.55.76E−30.648438.32.38E−4j250c5a10.30220.34.81E − 30.253811.18.74E−20.266513.62.07E−20.282315.79.37E−3j250c5a20.773318.11.83E − 40.6569.61.94E−30.66399.91.65E−30.75513.24.23E−4j300c3a10.56619.42.46E−40.386416.21.78E−20.425915.86.21E−30.539722.92.27E − 4j300c3a20.6569242.73E−40.422220.14.07E−30.392519.41.83E−20.634320.52.03E − 4j300c5a10.247313.91.76E − 30.15697.89.08E−20.28911.32.91E−20.338411.74.61E−3j300c5a20.752320.62.07E − 40.360813.27.03E−20.3361173.66E−20.5515.62.09E−3The bold values in Table 11 show the better value obtained on the corresponding indicators.Figure 5
The Pareto frontier solutions got by the four comparison algorithms on 8 different instances.Figure 6
The 95% confidence interval plot of HV that the four comparison algorithms get on 20 instances, where 1 = NSGAII, 2 = MODDE, 3 = ACBEA, and 4 = AMODE.Figure 7
The mean CPU running time of different algorithms in different scale instances.In Table10, see from the mean C value that we can draw the conclusion that the Pareto frontier solutions obtained by NSGAII and MODDE are almost dominated by the solutions obtained by AMODE; in particular for the instances with 200 or more jobs, the Pareto frontier solutions obtained by NSGAII and MODDE are completely dominated by the solutions of AMODE. Therefore, from point the C indicator, AMODE outperforms NSGAII and MODDE.Compared to the valuesCACBEA,AMODE and CACBEA,AMODE, it can be seen that there are 3 out of 20 instances, such as instances j100c3a2, j100c5a2, and j150c5a1, where the CACBEA,AMODE is greater than CACBEA,AMODE. These denote the Pareto frontier solutions got by ACBEA are better than AMODE. But for the other 17 instances, the CACBEA,AMODE are greater than CACBEA,AMODE and these denote the Pareto frontier solutions got by AMODE dominate the solutions got by ACBEA on most instances. Therefore, from the indicator C, AMODE outperforms the other three algorithms.In Table11, in terms of HV, AMODE got higher value on 18 instances, ACBEA got higher value on 2 small scale instances, and NSGAII and MODDE got none. This shows that AMODE has better convergence than the other three algorithms. In terms of IGD, AMODE got smaller value on 16 instances while ACBEA got smaller value on the other 4 instances. These denote that the distribution and diversity of the solutions that AMODE got are better than the other three comparison algorithms. In terms of NPFS, AMODE obtained more dominated solutions on 17 instances, ACBEA obtained more dominated solutions on the remaining instances, and the number of dominated solutions that NSGAII and MODDE obtained is less compared with AMODE and ACBEA. Therefore, in terms of NPFS, AMODE outperforms the other three algorithms. These indicate that AMODE can provide more option for the operator. The experimental results in Table 11 are just consistent with the experimental conclusion in Table 11, which shows that the AMODE has great advantages in dealing with the multiobjective scheduling problem of UPBMP.To compare the quality of the solution obtained by the four comparison algorithms, the spread of the solutions on 8 different instances with scale are shown in Figure5, where the x-axis shows the makespan and the y-axis denotes the TEC, respectively. It is obvious that the Pareto solution obtained by AMODE is better than that of the other three compared algorithms in terms of quality and distribution. Figure 6 is the 95% confidence interval plot of HV of the four comparison algorithms obtained on 20 instances. It can seen that the line of 95% confidence interval of AMODE on most instances is shorter and this indicates that AMODE has better robustness than the other three comparison algorithms. From the value of the 95% confidence interval, AMODE is greater than the other comparison three algorithms on 18 instances; this indicates that AMODE outperforms the other comparison three algorithms, especially medium- and large-scale problems. ACBEA comes the second, MODDE is the third, and NSGAII is the last. As it can be seen from Figure 7, for the problem of the same scale, the algorithm AMODE is not as fast as the algorithms NSGAII and MODDE but faster than the algorithm ACBEA. It shows that, to obtain a better Pareto fronter solution, it is necessary to sacrifice the CPU running time, but as can be seen from Figure 7, the overall running time of the algorithm AMODE is within an acceptable range. When the scale of the problem is 300, the algorithm in this paper needs to run about 8 minutes on average.


## 6. Conclusion

In this paper, the energy aware UPBPM scheduling problem with more constraints is addressed and an adaptive multiobjective differential evolution algorithm (AMODE) is proposed. First, in view of the great influence of parameters on the global search and local search ability of the DE algorithm, an adaptive parameter control strategy is proposed, which can adjust the parameters according to the current individual’s convergence index and evolution times. Second, to effectively guide the algorithm’s search and balance the convergence and diversity of the solution, an adaptive mutation strategy is proposed. The strategy divides the whole population into three levels according to the individual’s convergence index ranking, and the individuals of different levels adopt different mutation strategies. Third, a greedy selection operator in other literature is adapted to ensure that excellent nondominated solutions have more opportunities to enter the next generation, so as to speed the AMODE’s convergence. Finally, through experiments on 20 instances with different scales, the setting of various parameters of the algorithm and the effectiveness of the improvement measures of the algorithm are analyzed. Through the comparative experiments with the well-known algorithms, we can draw the conclusion that AMODE outperforms NSGAII, MODDE, and ABCEA.In the future, the research work can focus on the following:(1)
The combinatorial optimization algorithm based on learning mechanism.(2)
The multiobjective algorithm that combines multiobjective optimization with integrated decision making as in [45, 46].(3)
The multiobjective algorithm that selects individuals based on indicator and crowding distance at the same time as in [47].(4)
The distributed BPM scheduling problem, etc.



---

*Source: 5056356-2022-09-15.xml*