# Hybrid Estimation of Distribution Algorithm for Solving Three-Stage Multiobjective Integrated Scheduling Problem

Authors: Chao Deng; Rong Hu; Bin Qian; Huai P. Jin
Journal: Complexity
 (2021)

---

## Abstract

Aiming at reducing the total energy consumption of three stages processing-transportation-assembly in the assembly manufacturing industry, a three-stage multiobjective integrated scheduling problem with job batch transportation considering the energy consumption (3sMISP_JBTEC) is proposed, and a comprehensive energy consumption model of multistage of 3sMISP_JBTEC with an improved turn off/on strategy in the processing stage and considering speed in the transportation stage is formulated. Then, a hybrid estimation of distribution algorithm with variable neighborhood search (HEDA_VNS) is developed to solve the scheduling problem. In the HEDA_VNS, the reasonable coding/decoding rules and speed scheduling scheme (SSS) are designed. Moreover, two local search strategies are designed to further enhance the performance of HEDA_VNS. Among them, three types of neighborhood search strategies are devised in Local Search I to improve the search efficiency while retaining the structure of the original high-quality solution. A variable neighborhood hybrid operation based on the speed scheduling set is designed in Local Search II to further improve the quality of the solution while balancing the optimization goals. Finally, simulations and comparisons show the efficiency of the proposed HEDA_VNS.


---

## Body

## 1. Introduction

As environmental pollution becomes a serious challenge for the world, the development of the manufacturing industry is gradually changing towards the green manufacturing. According to relevant surveys, the energy efficiency of the manufacturing industry is low and pollution emissions are high at moment. For instance, in China, the proportion of industrial GDP, 34.3%, is obtained by consuming 68% of the national energy in 2015 [1]. The production process plays an important role in the manufacturing industry. In recent years, in order to reduce energy consumption in the production process, many studies have been conducted on improving the energy efficiency [2–6]. However, among the methods, production scheduling is the most effective and prioritized way to improve the energy efficiency of the manufacturing industry [7].The assembly manufacturing industry is an important sector of manufacturing enterprises. The production process includes multiple stages of processing, transportation, and assembly. Energy consumption should not be ignored in the whole production process. The existing researches of assembly manufacturing industry have focused on the two-stage scheduling problem (2sSP) containing the processing-assembly and the three-stage scheduling problem (3sSP) containing the processing-transport-assembly. Compared with 2sSP, the transportation between the processing and assembly stages has a nonnegligible process in 3sSP. However, a large number of studies assumed that the transportation time of each job is constant in the transportation stage [8–11]; i.e., the number or load of transportation vehicles is unlimited, which is far from the actual problem. Therefore, Deng et al. [12] have integrated production and transportation, and the three-stage integration scheduling problem with job batch transportation (3sISP_JBT) of processing-transportation-assembly has been studied, which makes the problem model of the assembly manufacturing industry more realistic. However, the study only considers minimizing the makespan as the optimization goal. Although a close connection among the three stages has been established through the optimization, it leads to production process not compact enough in the single stage. Especially in the processing stage, a large idleness may be generated between two adjacent jobs on the same machine in the process of processing, which causes energy waste seriously. Furthermore, in the transportation stage, the energy consumption is affected by the load and speed of the vehicle closely. In terms of computational complexity, 2sSP has been proven to be NP-hard [13]. It is reduced to 3sSP. Also, 3sSP can be reduced to 3sISP_JBT. Therefore, the considered problem is also NP-hard. To sum up, the comprehensive energy consumption optimization for 3sISP_JBT needs to be further studied.For the energy-optimized multiobjective green scheduling problem of the production process, the existing research has largely focused on optimizing the machining process with methods of machine speed control, turn off/on machine strategy, etc. [14–18]. However, the transport of workpieces is ignored in the production process. Then, Lu et al. [19] investigated a permutation flow shop scheduling problem with sequence-dependent setup and controllable transportation time in the processing stage from a real-world manufacturing enterprise, where the objects include the makespan and energy consumption, and a hybrid multiobjective backtracking search algorithm (HMOBSA) has proposed to solve the problem. Dai et al. [20] studied a flexible job shop scheduling problem considering the transportation time in the processing stage, where the objects include makespan and the total energy consumption, and an improved genetic algorithm (GA) has been proposed to solve it. However, in the above literature, many scholars considered transportation in the energy optimization problem of workshop scheduling, but they mainly consider the impact of the transportation time on the entire makespan and do not study the energy consumption of transportation in the energy consumption index. After that, Tanimizu and Amano [21] studied the integrated scheduling problem of the processing-transportation stage, a processing-transportation comprehensive energy consumption model has been constructed to minimize the total delay time and the energy consumption, and a genetic algorithm (GA) based on heuristic rules has been adopted to solve this problem. Guo et al. [22] also studied the integrated scheduling problem of the processing-transportation stage, and a hybrid memetic algorithm has been proposed to minimize the total cost and energy consumption. Liu et al. [23] studied a novel integrated green scheduling problem of flexible job shop and crane transportation in the processing stage, a comprehensive energy consumption model has been built to optimize the comprehensive energy consumption and makespan, and an integrated algorithm of a genetic algorithm (GA) and glowworm swarm optimization (GSO) with green transport heuristic strategy has been proposed. It is noted that the above results have considered the transportation time and transportation process in the workshop scheduling optimization and have conducted energy consumption optimization research on this issue, while mainly considering the impact of load factors (constraints) of vehicles on the transportation stage and ignoring the impact of transportation speed on energy consumption. However, the impact of speed on energy consumption cannot be ignored in practice in the actual transportation process. A large number of existing studies have verified the impact of transportation speed on the energy consumption and scheduling schemes on the green transportation scheduling problems considering speed [24–26]. Hence, for 3sISP_JBT of the assembly manufacturing industry, in addition to designing effective energy-saving strategies for the two production stages of processing and assembly, it is necessary to further consider the impact of transportation speed on the energy consumption in the transportation stage to improve the entire production process energy optimization.At present, a large number of intelligent algorithms have emerged to solve scheduling problems [27–29]. The estimation of distribution algorithm (EDA) is an emerging evolutionary algorithm based on statistics. It learns high-quality individuals in the population in a statistical manner and constructs the probability model, and then the probability model is sampled to generate a new population. It guides the search direction of the algorithm and has a good global search capability. In recent years, EDA has been successfully applied to solve a variety of scheduling problems, including parallel machine scheduling problem [30], flow shop scheduling problem [31], job shop scheduling problem [32, 33], energy-saving job shop scheduling problem [34], vehicle transportation scheduling problem [35], and integrated scheduling problem [12]. Judging from the research status of EDA in scheduling optimization problems, EDA itself has the advantage of probabilistic model global search. In addition, it can be reasonably mixed with other effective algorithms and operations, which can greatly enrich the search ability and improve the algorithm performance.This paper aims to optimize the three-stage multiobjective integration scheduling problem with job batch transportation considering the energy consumption (3sMISP_JBTEC) in the assembly manufacturing industry. In the processing stage, the machining environment is a heterogeneous parallel machine of multiprocessing with release time. In the transportation stage, the transportation facilities are the same type vehicles. In the assembly stage, only one machine is used for assembly. The focus of this paper is to explore the interrelationship between the three stages processing-transportation-assembly and the key factors affecting energy consumption at each stage to further optimize the comprehensive energy consumption of the assembly manufacturing industry. The contributions of this paper are as follows:(1)
A mathematic model is formulated for the 3sMISP_JBTEC, in which the objective is to minimize the comprehensive energy consumption and makespan of the production task.(2)
In the proposed model, a comprehensive energy consumption model with an improved turn off/on strategy in the processing stage and speed factor in the transportation stage is built to optimize the comprehensive energy efficiency of the three stages, processing-transportation-assembly.(3)
A hybrid estimation of distribution algorithm with variable neighborhood search (HEDA_VNS) is presented to solve the proposed model.(4)
In HEDA_VNS, the reasonable coding/decoding rules and speed scheduling scheme are designed based on the specific characteristics. Then, two local search strategies are designed to further enhance the HEDA_VNS’s performance. Among them, three types of neighborhood search strategies are devised in Local Search I to improve the search efficiency while retaining the structure of the original high-quality solution. A variable neighborhood hybrid operation based on the speed set is designed in Local Search II to further improve the quality of the solution while balancing the optimization goals.The remainder of this paper is organized as follows. A mathematic model of the proposed 3sMISP_JBTEC is developed in Section2. HEDA_VNS algorithm is designed for solving 3sMISP_JBTEC in Section 3. Section 4 details the HEDA_VNS. Simulation experiment results and analysis is conducted in Section 5. Section 6 presents the conclusions.


## 2. Mathematical Formulation

In this section, the introduced 3sMISP_JBTEC is described in detail based on the assembly manufacturing environment. Then, a mathematical model is proposed to formulate the 3sMISP_JBTEC with the consideration of comprehensive energy consumption and makespan.


### 2.1. Problem Description and Assumptions

The 3sMISP_JBTEC problem is described as follows. According to the customer order (demand), we set the number of processed products asHP, the number of processing machines in the processing stage as m1, the number of transport vehicles in the transportation stage as HTR, and the number of assembled machines in the assembly stage as one. Each product is composed of multiple jobs, and each job needs to be processed in different procedures. The procedures of the jobs need to be processed in sequence on the machine that meets the processing constraints at the processing stage. After the jobs are processed, they are loaded by the same type vehicle in the transportation stage. Transport at a certain speed v to the assembly stage to wait for assembly. The jobs of each product are processed in three stages in the order of processing. Then, the model diagram is shown in Figure 1.Figure 1
The problem model of 3sMISP_JBTEC.Without loss of generality, the 3sMISP_JBTEC is investigated based on the following reasonable assumptions:(1)
Any processing machine in the processing stage can only process one job at the same time, and different jobs have release time; a process of job is immediately transferred to the next process after being processed, and the transfer time of job between the required machine is ignored; the preparation time of all processes of job is not related to the processing sequence and is included in the processing time of the process. Different processes of the same job cannot be processed at the same time; each process of each job cannot be interrupted once it starts processing.(2)
The assembly machine in the assembly stage can only assemble the same product at the same time, and the setup time between different products is set to zero; the initial state of the assembly machine is idle, and at zero time, any task is feasible.(3)
If the same raw material is processed through the same process in the processing stage, it is the same job, and one or more jobs that make up different products are not the same.


### 2.2. Notation

The main notations used in formulating the mathematical model of the 3sMISP_JBTEC problem are listed as follows:P: product set. z∈P, P=1,2,…,HP.Q: jobs set. j∈Q, Q=1,2,…,q.O: process set. i∈O, O=1,2,…,HO.T: vehicle set. t∈T, T=1,2,…,HTR.M: machine set in processing stage. k∈M,M=1,2,…,m1.Hk: the number of processes on the processing machine k.wt: the number of round trips of vehicle t. wt≥1.HT: the total number of transport vehicles. HT⊄∞.VT: the vehicle rated load (fixed value).DisP−A: the distance from the processing stage to the transportation stage.S: the vehicle speed set.WidleT: the unload weight of the vehicle.SVuse: the speed use set. SVuse=v1,…,vt,…,vHT.πK=π1K,π2K,…,πHoK: the permutation of the processes of all jobs in the processing stage. The jobs in the permutation are allocated to the corresponding machines for processing from left to right according to rules and parallel processing constraints.πk=π1k,π2k,…,πik,…,πHkk: the permutation of the process of the job on the processing machine k in the processing stage, where πik is the process of the job at the position i of πk.πTR=π1TR,π2TR,…,πjTR,…,πq1TR: the permutation of all the jobs in the transportation stage, where πjTRis the job at the position j of πTR.πTR−V=π1TR−V,π2TR−V,…,πtTR−V,…,πHTTR−V: the speed permutation of all vehicles in the transportation phase, where πtTR−V is the vehicle at the position t of πTR−V.πP=π1P,π2P,…,πzP,…,πHPP: the permutation of the products to be processed on the assembly machine in the assembly stage, where πzP is the product at the position z of πP.Pπik: the processing time of πik.Rπik: the release time when the job at the position i of πk first arrived at the processing machine k.PπzP: the assembly time of πzP.VπjTR: the weight of the job at position j of πTR.vπtTR−V: the speed at of the vehicle at position t of πTR−V.Ton: the time required to turn on a machine.Toff: the time required to turn off a machine.TkNum−off: the number of turning off the machine k.ekidle: the energy consumption of idle time of machine k.ekR: the energy consumption of release time of machine k.ekP: the average energy consumption of processing time of machine k.etvT: the energy consumption of vehicle t at a speed v.Eoff−on: the energy consumption requirement for turn off, then turn on the machine.ETidle: the energy consumption of vehicle t return one time without load.pre_mπik: the machine number of the previous processing operation of πik; the permutation of the previous process of πik with the machine number pre_mπik expressed as πipre_mπik. If the job πik is processed for the first time, then pre_mπik=0.pre_kπik: the process number of the previous processed job when πik processing on the machine k. The position of the process in the permutation is recorded as πpre_kπikk. If the machine k is processing the job for the first time, then pre_kπik=0.Cπik: the processing complete time of πik.Cst1πjTR: the processing completion time of the job j of πTR.SπjTR: the transportation starting time of the job j of πTR in vehicle t.CπjTRwt: the transportation completion time of the job j of πTR in wt trips of vehicle t.Cst2πjTR: the transportation completion time of the job j of πTR.SπzP: the assembly start time of πzP.Cst3πzP: the assembly completion time of πzP.


### 2.3. Comprehensive Energy Consumption Model

In the section, a comprehensive energy consumption model of 3sMISP_JBTEC is given in the three stages, respectively. In the processing stage, the energy consumption includes the release process, the processing process, and the idle process. Besides, an improved turn off/on strategy is proposed to better save energy and extend the life of the machine. In the transportation stage, the impact factor of speed and load is both considered to calculate energy consumption during transportation.


#### 2.3.1. Energy Consumption of the Processing Stage (ECst1)

The processing stage is a multiprocess heterogeneous parallel machine scheduling problem with release time. The processing workshop is a flexible workshop, and multiple processes of the jobs can be processed on different machines. It is flexible and versatile, but it is also one of the industrial workshops with the highest energy consumption [36]. Figure 2 is the energy consumption of the flexible machine k in the processing stage of the problem. It can be seen from Figure 2 that the energy consumption of this processing stage (ECst1) is composed of the energy consumption of the release process (ECRst1) when the jobs arrives at the machine for the first time, the energy consumption of the processing process (ECPst1) of the different jobs in machines, and the energy consumption of the idle process (ECidlest1). If the energy consumption caused by job transfermation between different machines is ignored, then the total energy consumption of the processing stage (ECst1) is calculated by using equation (1). In order to simplify the calculation, this paper simplified the unit energy consumption of each part to the average value:(1)ECst1=ECRst1+ECPst1+ECidlest1.Figure 2
Example of energy consumption of a processing machine.(1)Energy Consumption of Release Process (ECRst1). The energy consumption of the release process depends on the release time of jobs. Because there are differences between the jobs (i.e., size, shape, material, and weight) and machines, it directly affects ECRst1. Thus, the energy consumption of the machine’s release process is calculated by the following equation: (2)ECRst1=∑kekR⋅Rπik,i=1,…,Hk;k=1,…,m1.(2)Energy Consumption of the Processing Process (ECPst1). The energy consumption of the process depends on the processing time of the corresponding process of the job on the machine. The energy consumption of all machines in the processing process is calculated as (3)ECPst1=∑i∑kekP⋅Pπik,i=1,…,Hk;k=1,…,m1.(3)Energy Consumption of the Idle Process (ECidlest1) and an Improved Turn Off/On Strategy. The energy consumption of the process depends on the idle time of the machine. The idle time i on the machine k can be expressed as Pk,iidle=Sπi+1k−Cπik, where Pk,iidle>0. If the machine’s idle time is too long, it will cause a waste of energy. Therefore, the machine needs to be turned off to save energy at the appropriate time. The work in [37] gives the decision time period TB for whether or not to shut down the machine, where TB=maxEoff−on/ekidle,Ton+Toff. If Pkidle≥TB, the machine should be turned off. Although the power-off method can reduce energy consumption, it frequently may shorten the service life of the machine. Therefore, the work in [38] gives the maximum allowable number of machine turn off, where TNum−off. Then, in order to further save energy and prolong the life of the machine, an energy-saving strategy for turn on/off of machine was proposed in [19]. However, the closeness of adjacent idle in the same machine is not considered. If the adjacent idles are too close and Pkidle≥TB, turning the machine on and off frequently would still affect the life of the machine in the actual production process. Therefore, this paper designs an improved energy-saving strategy based on the above studies. The steps are as follows: Step 1: calculatePkidle of the machine k, then record the time Tk,idis between two adjacent idles, Tk,ndis=SPk,i+1idle−CPk,iidle, whereTk,idis>0.Step 2: compare withPk,iidle and TB in turn. If Pk,iidle≥TB and Tk,idis≤ε (where ε is a certain value), then put maxPk,iidle,Pk,i+1idle into set Ω and put minPk,iidle,Pk,i+1idle in the taboo table to avoid repeated comparisons, else put Pk,iidle (where Pk,iidle≥TB) into the set Ω directly.Step 3: sortPkidle which in the set Ω in nonascending order. Then, select the first number TNum−offof Pkidlein the sequence and put them in the set Ω′ which is recorded as PkStop_idle.From the above, the energy consumption of the idle process is calculated as(4)ECidlest1=∑i∑kekidle⋅Pk,iidle−∑i∑kekidle⋅Pk,iStop_idle+∑i∑kEoff−on⋅TNum−off=∑i∑kekidle⋅Sπi+1k−Cπik−∑i∑kekidle⋅Pk,iStop_idle+∑i∑kEoff−on⋅TNum−off,i=1,…,Hk−1;k=1,…m1;PkStop_idle∈Ω′.


#### 2.3.2. Energy Consumption of Transportation Stage (ECst2)

In the transportation stage, the jobs completed in the processing stage will be transported to the assembly place for assembly by multiple vehicles of the same type under certain constraints of load and speed. The constantDisP−A is the distance from the processing stage to the assembly stage. The vehicle can go back and forth multiple times, and thus, the vehicle is empty during the return process. The speed of each vehicle without load is a constant value vc, and the energy consumption is a constant value ETidle. It should be emphasized that once all vehicles begin to transport, the constant speed of vehicles should be maintained throughout the transportation process.In this line, some studies have been conducted on the energy consumption of vehicle transportation. Palmer [39] incorporated the energy consumption indicators into the vehicle transportation problem and proposed an energy consumption model that considers the total length or distance of the path. Kara et al. [40] proposed an energy consumption model considering the load of vehicle and distance. Kuo [24] further considered the vehicle speed and proposed a time-dependent speed and vehicle load energy consumption model. Demir et al. [25] developed a mathematical model of energy consumption of multiple parameters with speed, distance, and load. In the equation, Ptract (kilowatts) is the unit traction power of the vehicle, τ is the acceleration, M=w+f (w is the mass of the vehicle and f is the mass of the cargo carried by the vehicle), and the rest is the vehicle-related parameter. In this paper, the uniform speed of the vehicles is considered, where τ=0, but the influence of the gradient of the vehicle is not considered. Then, the per unit time of the vehicle t is shown in equation (6). Therefore, the energy consumption of the transportation stage can be given as shown in equation (7), where the unit of speed is m/s:(5)Ptract=Mτ+Mgsinθ+0.5CdρAv2+MgCrcosθv1000,(6)Pttract=0.5CdρAv2+MgCrv1000,(7)ECst2=∑tPttract⋅DisP−AvπtTR−V+∑t∑wETidle⋅wt=∑t0.5CdρA⋅vπtTR−V2+WidleT+∑jVπjTRgCr⋅DisP−A1000+∑t∑w0.5CdρAvc2+WidleTgCr⋅DisP−A⋅wt1000,j=1,…,q;t=1,…,HT;v∈S;w=1,2,….


#### 2.3.3. Energy Consumption of Assembly Stage (ECst3)

The assembly stage is a single machine scheduling problem. Since the assembly time of each product on the machine is unchanged, it will not affect the processing energy consumption so that the energy consumption is only related to the machine’s idle time. Therefore, energy consumption of the assembly process is calculated as(8)ECst3=∑zem2idle⋅Sπz+1P−CπzP,z=1,2,…,HP.In summary, the total energy consumption of 3sMISP_JBTEC is calculated as(9)ECtotal=ECst1+ECst2+ECst3.


### 2.4. Formulation of Multiobjective Model of 3sMISP_JBTEC

The 3sMISP_JBTEC is formulated as the following mathematical model, in which two objectives of makespan and total energy consumption are considered:(1)
The processing stage: it is a multiprocess heterogeneous parallel machine scheduling problem with release time in the processing stage. If the jobπik is processed for the first time, then pre_mπik=0; If the machine that processed job πik is the first time to process the job, then pre_kπik=0. The completion time Cπik of πik is calculated as follows:(10)Cπik=minPπik+Rπik,pre_mπik=0;pre_kπik=0,Cπik=minmaxCπpre_kπikk,Rπik+Pπik,pre_mπik=0;pre_kπik≠0,Cπik=minCπipre_mπik+Pπik,pre_mπik≠0;pre_kπik=0,Cπik=minmaxCπipre_mπik,Cπpre_kπikk+Pπik,pre_mπik≠0;pre_kπik≠0,Cst1πjt=Cπik,k=1,2,…,m1;j=1,2,…,q;i=1,2,…,Hk.(2)
The transportation stage: it is a multivehicle single-point delivery problem with the constraints of load and speed in the transportation stage. The total load of all jobs loaded in the vehiclet cannot exceed the vehicle rated load (VT). The transportation time of the vehicle t is determined by the speed vπtTR−V. The transportation completion time of the job j of πTR is calculated as follows:(11)SπjTRwt=maxCst1πjTRwt,wt=1,SπjTRwt=maxCst1πjTRwtt,SπjTRwt−1+Disp−tvπtTR−V+Disp−tvc,wt≠1,Cst2πjTRwt=SπjTRwt+Disp−tvπtTR−V,j=1,2,…,q;wt=1,2,…,l;t=1,2,…,HT.(3)
The assembly stage: it is a single-machine scheduling problem with arrival time or release time. The calculation formula for the assembly completion timeCst3πzP of the product πzP is shown as follows:(12)SπzP=maxCst2πjTR,Cst3πzP=maxCst3πz−1P,SπzP+PπzP,z=1,2,…,HP,j=1,2,…,q.(4)
The optimization goal: the optimization goal is to find an optimal sequenceπ∗=πK,πTR,πTR−V,πP in the set Π of the three-stage sequence from processing and transportation to assembly of the job which composed products so that the makespan Cmax and the total energy consumption Etotal of the three stages are minimized:(13)Cmaxπ∗=minπK,πTR,πTR−V,πP∈ΠCmaxπK,πTR,πTR−V,πP,Etotalπ∗=minπK,πTR,πTR−V,πP∈ΠEtotalπK,πTR,πTR−V,πP,π∗=argCmaxπK,πTR,πTR−V,πP,EtotalπK,πTR,πTR−V,πP⟶min,∀πK,πTR,πTR−V,πP∈Π.


## 2.1. Problem Description and Assumptions

The 3sMISP_JBTEC problem is described as follows. According to the customer order (demand), we set the number of processed products asHP, the number of processing machines in the processing stage as m1, the number of transport vehicles in the transportation stage as HTR, and the number of assembled machines in the assembly stage as one. Each product is composed of multiple jobs, and each job needs to be processed in different procedures. The procedures of the jobs need to be processed in sequence on the machine that meets the processing constraints at the processing stage. After the jobs are processed, they are loaded by the same type vehicle in the transportation stage. Transport at a certain speed v to the assembly stage to wait for assembly. The jobs of each product are processed in three stages in the order of processing. Then, the model diagram is shown in Figure 1.Figure 1
The problem model of 3sMISP_JBTEC.Without loss of generality, the 3sMISP_JBTEC is investigated based on the following reasonable assumptions:(1)
Any processing machine in the processing stage can only process one job at the same time, and different jobs have release time; a process of job is immediately transferred to the next process after being processed, and the transfer time of job between the required machine is ignored; the preparation time of all processes of job is not related to the processing sequence and is included in the processing time of the process. Different processes of the same job cannot be processed at the same time; each process of each job cannot be interrupted once it starts processing.(2)
The assembly machine in the assembly stage can only assemble the same product at the same time, and the setup time between different products is set to zero; the initial state of the assembly machine is idle, and at zero time, any task is feasible.(3)
If the same raw material is processed through the same process in the processing stage, it is the same job, and one or more jobs that make up different products are not the same.


## 2.2. Notation

The main notations used in formulating the mathematical model of the 3sMISP_JBTEC problem are listed as follows:P: product set. z∈P, P=1,2,…,HP.Q: jobs set. j∈Q, Q=1,2,…,q.O: process set. i∈O, O=1,2,…,HO.T: vehicle set. t∈T, T=1,2,…,HTR.M: machine set in processing stage. k∈M,M=1,2,…,m1.Hk: the number of processes on the processing machine k.wt: the number of round trips of vehicle t. wt≥1.HT: the total number of transport vehicles. HT⊄∞.VT: the vehicle rated load (fixed value).DisP−A: the distance from the processing stage to the transportation stage.S: the vehicle speed set.WidleT: the unload weight of the vehicle.SVuse: the speed use set. SVuse=v1,…,vt,…,vHT.πK=π1K,π2K,…,πHoK: the permutation of the processes of all jobs in the processing stage. The jobs in the permutation are allocated to the corresponding machines for processing from left to right according to rules and parallel processing constraints.πk=π1k,π2k,…,πik,…,πHkk: the permutation of the process of the job on the processing machine k in the processing stage, where πik is the process of the job at the position i of πk.πTR=π1TR,π2TR,…,πjTR,…,πq1TR: the permutation of all the jobs in the transportation stage, where πjTRis the job at the position j of πTR.πTR−V=π1TR−V,π2TR−V,…,πtTR−V,…,πHTTR−V: the speed permutation of all vehicles in the transportation phase, where πtTR−V is the vehicle at the position t of πTR−V.πP=π1P,π2P,…,πzP,…,πHPP: the permutation of the products to be processed on the assembly machine in the assembly stage, where πzP is the product at the position z of πP.Pπik: the processing time of πik.Rπik: the release time when the job at the position i of πk first arrived at the processing machine k.PπzP: the assembly time of πzP.VπjTR: the weight of the job at position j of πTR.vπtTR−V: the speed at of the vehicle at position t of πTR−V.Ton: the time required to turn on a machine.Toff: the time required to turn off a machine.TkNum−off: the number of turning off the machine k.ekidle: the energy consumption of idle time of machine k.ekR: the energy consumption of release time of machine k.ekP: the average energy consumption of processing time of machine k.etvT: the energy consumption of vehicle t at a speed v.Eoff−on: the energy consumption requirement for turn off, then turn on the machine.ETidle: the energy consumption of vehicle t return one time without load.pre_mπik: the machine number of the previous processing operation of πik; the permutation of the previous process of πik with the machine number pre_mπik expressed as πipre_mπik. If the job πik is processed for the first time, then pre_mπik=0.pre_kπik: the process number of the previous processed job when πik processing on the machine k. The position of the process in the permutation is recorded as πpre_kπikk. If the machine k is processing the job for the first time, then pre_kπik=0.Cπik: the processing complete time of πik.Cst1πjTR: the processing completion time of the job j of πTR.SπjTR: the transportation starting time of the job j of πTR in vehicle t.CπjTRwt: the transportation completion time of the job j of πTR in wt trips of vehicle t.Cst2πjTR: the transportation completion time of the job j of πTR.SπzP: the assembly start time of πzP.Cst3πzP: the assembly completion time of πzP.


## 2.3. Comprehensive Energy Consumption Model

In the section, a comprehensive energy consumption model of 3sMISP_JBTEC is given in the three stages, respectively. In the processing stage, the energy consumption includes the release process, the processing process, and the idle process. Besides, an improved turn off/on strategy is proposed to better save energy and extend the life of the machine. In the transportation stage, the impact factor of speed and load is both considered to calculate energy consumption during transportation.


### 2.3.1. Energy Consumption of the Processing Stage (ECst1)

The processing stage is a multiprocess heterogeneous parallel machine scheduling problem with release time. The processing workshop is a flexible workshop, and multiple processes of the jobs can be processed on different machines. It is flexible and versatile, but it is also one of the industrial workshops with the highest energy consumption [36]. Figure 2 is the energy consumption of the flexible machine k in the processing stage of the problem. It can be seen from Figure 2 that the energy consumption of this processing stage (ECst1) is composed of the energy consumption of the release process (ECRst1) when the jobs arrives at the machine for the first time, the energy consumption of the processing process (ECPst1) of the different jobs in machines, and the energy consumption of the idle process (ECidlest1). If the energy consumption caused by job transfermation between different machines is ignored, then the total energy consumption of the processing stage (ECst1) is calculated by using equation (1). In order to simplify the calculation, this paper simplified the unit energy consumption of each part to the average value:(1)ECst1=ECRst1+ECPst1+ECidlest1.Figure 2
Example of energy consumption of a processing machine.(1)Energy Consumption of Release Process (ECRst1). The energy consumption of the release process depends on the release time of jobs. Because there are differences between the jobs (i.e., size, shape, material, and weight) and machines, it directly affects ECRst1. Thus, the energy consumption of the machine’s release process is calculated by the following equation: (2)ECRst1=∑kekR⋅Rπik,i=1,…,Hk;k=1,…,m1.(2)Energy Consumption of the Processing Process (ECPst1). The energy consumption of the process depends on the processing time of the corresponding process of the job on the machine. The energy consumption of all machines in the processing process is calculated as (3)ECPst1=∑i∑kekP⋅Pπik,i=1,…,Hk;k=1,…,m1.(3)Energy Consumption of the Idle Process (ECidlest1) and an Improved Turn Off/On Strategy. The energy consumption of the process depends on the idle time of the machine. The idle time i on the machine k can be expressed as Pk,iidle=Sπi+1k−Cπik, where Pk,iidle>0. If the machine’s idle time is too long, it will cause a waste of energy. Therefore, the machine needs to be turned off to save energy at the appropriate time. The work in [37] gives the decision time period TB for whether or not to shut down the machine, where TB=maxEoff−on/ekidle,Ton+Toff. If Pkidle≥TB, the machine should be turned off. Although the power-off method can reduce energy consumption, it frequently may shorten the service life of the machine. Therefore, the work in [38] gives the maximum allowable number of machine turn off, where TNum−off. Then, in order to further save energy and prolong the life of the machine, an energy-saving strategy for turn on/off of machine was proposed in [19]. However, the closeness of adjacent idle in the same machine is not considered. If the adjacent idles are too close and Pkidle≥TB, turning the machine on and off frequently would still affect the life of the machine in the actual production process. Therefore, this paper designs an improved energy-saving strategy based on the above studies. The steps are as follows: Step 1: calculatePkidle of the machine k, then record the time Tk,idis between two adjacent idles, Tk,ndis=SPk,i+1idle−CPk,iidle, whereTk,idis>0.Step 2: compare withPk,iidle and TB in turn. If Pk,iidle≥TB and Tk,idis≤ε (where ε is a certain value), then put maxPk,iidle,Pk,i+1idle into set Ω and put minPk,iidle,Pk,i+1idle in the taboo table to avoid repeated comparisons, else put Pk,iidle (where Pk,iidle≥TB) into the set Ω directly.Step 3: sortPkidle which in the set Ω in nonascending order. Then, select the first number TNum−offof Pkidlein the sequence and put them in the set Ω′ which is recorded as PkStop_idle.From the above, the energy consumption of the idle process is calculated as(4)ECidlest1=∑i∑kekidle⋅Pk,iidle−∑i∑kekidle⋅Pk,iStop_idle+∑i∑kEoff−on⋅TNum−off=∑i∑kekidle⋅Sπi+1k−Cπik−∑i∑kekidle⋅Pk,iStop_idle+∑i∑kEoff−on⋅TNum−off,i=1,…,Hk−1;k=1,…m1;PkStop_idle∈Ω′.


### 2.3.2. Energy Consumption of Transportation Stage (ECst2)

In the transportation stage, the jobs completed in the processing stage will be transported to the assembly place for assembly by multiple vehicles of the same type under certain constraints of load and speed. The constantDisP−A is the distance from the processing stage to the assembly stage. The vehicle can go back and forth multiple times, and thus, the vehicle is empty during the return process. The speed of each vehicle without load is a constant value vc, and the energy consumption is a constant value ETidle. It should be emphasized that once all vehicles begin to transport, the constant speed of vehicles should be maintained throughout the transportation process.In this line, some studies have been conducted on the energy consumption of vehicle transportation. Palmer [39] incorporated the energy consumption indicators into the vehicle transportation problem and proposed an energy consumption model that considers the total length or distance of the path. Kara et al. [40] proposed an energy consumption model considering the load of vehicle and distance. Kuo [24] further considered the vehicle speed and proposed a time-dependent speed and vehicle load energy consumption model. Demir et al. [25] developed a mathematical model of energy consumption of multiple parameters with speed, distance, and load. In the equation, Ptract (kilowatts) is the unit traction power of the vehicle, τ is the acceleration, M=w+f (w is the mass of the vehicle and f is the mass of the cargo carried by the vehicle), and the rest is the vehicle-related parameter. In this paper, the uniform speed of the vehicles is considered, where τ=0, but the influence of the gradient of the vehicle is not considered. Then, the per unit time of the vehicle t is shown in equation (6). Therefore, the energy consumption of the transportation stage can be given as shown in equation (7), where the unit of speed is m/s:(5)Ptract=Mτ+Mgsinθ+0.5CdρAv2+MgCrcosθv1000,(6)Pttract=0.5CdρAv2+MgCrv1000,(7)ECst2=∑tPttract⋅DisP−AvπtTR−V+∑t∑wETidle⋅wt=∑t0.5CdρA⋅vπtTR−V2+WidleT+∑jVπjTRgCr⋅DisP−A1000+∑t∑w0.5CdρAvc2+WidleTgCr⋅DisP−A⋅wt1000,j=1,…,q;t=1,…,HT;v∈S;w=1,2,….


### 2.3.3. Energy Consumption of Assembly Stage (ECst3)

The assembly stage is a single machine scheduling problem. Since the assembly time of each product on the machine is unchanged, it will not affect the processing energy consumption so that the energy consumption is only related to the machine’s idle time. Therefore, energy consumption of the assembly process is calculated as(8)ECst3=∑zem2idle⋅Sπz+1P−CπzP,z=1,2,…,HP.In summary, the total energy consumption of 3sMISP_JBTEC is calculated as(9)ECtotal=ECst1+ECst2+ECst3.


## 2.3.1. Energy Consumption of the Processing Stage (ECst1)

The processing stage is a multiprocess heterogeneous parallel machine scheduling problem with release time. The processing workshop is a flexible workshop, and multiple processes of the jobs can be processed on different machines. It is flexible and versatile, but it is also one of the industrial workshops with the highest energy consumption [36]. Figure 2 is the energy consumption of the flexible machine k in the processing stage of the problem. It can be seen from Figure 2 that the energy consumption of this processing stage (ECst1) is composed of the energy consumption of the release process (ECRst1) when the jobs arrives at the machine for the first time, the energy consumption of the processing process (ECPst1) of the different jobs in machines, and the energy consumption of the idle process (ECidlest1). If the energy consumption caused by job transfermation between different machines is ignored, then the total energy consumption of the processing stage (ECst1) is calculated by using equation (1). In order to simplify the calculation, this paper simplified the unit energy consumption of each part to the average value:(1)ECst1=ECRst1+ECPst1+ECidlest1.Figure 2
Example of energy consumption of a processing machine.(1)Energy Consumption of Release Process (ECRst1). The energy consumption of the release process depends on the release time of jobs. Because there are differences between the jobs (i.e., size, shape, material, and weight) and machines, it directly affects ECRst1. Thus, the energy consumption of the machine’s release process is calculated by the following equation: (2)ECRst1=∑kekR⋅Rπik,i=1,…,Hk;k=1,…,m1.(2)Energy Consumption of the Processing Process (ECPst1). The energy consumption of the process depends on the processing time of the corresponding process of the job on the machine. The energy consumption of all machines in the processing process is calculated as (3)ECPst1=∑i∑kekP⋅Pπik,i=1,…,Hk;k=1,…,m1.(3)Energy Consumption of the Idle Process (ECidlest1) and an Improved Turn Off/On Strategy. The energy consumption of the process depends on the idle time of the machine. The idle time i on the machine k can be expressed as Pk,iidle=Sπi+1k−Cπik, where Pk,iidle>0. If the machine’s idle time is too long, it will cause a waste of energy. Therefore, the machine needs to be turned off to save energy at the appropriate time. The work in [37] gives the decision time period TB for whether or not to shut down the machine, where TB=maxEoff−on/ekidle,Ton+Toff. If Pkidle≥TB, the machine should be turned off. Although the power-off method can reduce energy consumption, it frequently may shorten the service life of the machine. Therefore, the work in [38] gives the maximum allowable number of machine turn off, where TNum−off. Then, in order to further save energy and prolong the life of the machine, an energy-saving strategy for turn on/off of machine was proposed in [19]. However, the closeness of adjacent idle in the same machine is not considered. If the adjacent idles are too close and Pkidle≥TB, turning the machine on and off frequently would still affect the life of the machine in the actual production process. Therefore, this paper designs an improved energy-saving strategy based on the above studies. The steps are as follows: Step 1: calculatePkidle of the machine k, then record the time Tk,idis between two adjacent idles, Tk,ndis=SPk,i+1idle−CPk,iidle, whereTk,idis>0.Step 2: compare withPk,iidle and TB in turn. If Pk,iidle≥TB and Tk,idis≤ε (where ε is a certain value), then put maxPk,iidle,Pk,i+1idle into set Ω and put minPk,iidle,Pk,i+1idle in the taboo table to avoid repeated comparisons, else put Pk,iidle (where Pk,iidle≥TB) into the set Ω directly.Step 3: sortPkidle which in the set Ω in nonascending order. Then, select the first number TNum−offof Pkidlein the sequence and put them in the set Ω′ which is recorded as PkStop_idle.From the above, the energy consumption of the idle process is calculated as(4)ECidlest1=∑i∑kekidle⋅Pk,iidle−∑i∑kekidle⋅Pk,iStop_idle+∑i∑kEoff−on⋅TNum−off=∑i∑kekidle⋅Sπi+1k−Cπik−∑i∑kekidle⋅Pk,iStop_idle+∑i∑kEoff−on⋅TNum−off,i=1,…,Hk−1;k=1,…m1;PkStop_idle∈Ω′.


## 2.3.2. Energy Consumption of Transportation Stage (ECst2)

In the transportation stage, the jobs completed in the processing stage will be transported to the assembly place for assembly by multiple vehicles of the same type under certain constraints of load and speed. The constantDisP−A is the distance from the processing stage to the assembly stage. The vehicle can go back and forth multiple times, and thus, the vehicle is empty during the return process. The speed of each vehicle without load is a constant value vc, and the energy consumption is a constant value ETidle. It should be emphasized that once all vehicles begin to transport, the constant speed of vehicles should be maintained throughout the transportation process.In this line, some studies have been conducted on the energy consumption of vehicle transportation. Palmer [39] incorporated the energy consumption indicators into the vehicle transportation problem and proposed an energy consumption model that considers the total length or distance of the path. Kara et al. [40] proposed an energy consumption model considering the load of vehicle and distance. Kuo [24] further considered the vehicle speed and proposed a time-dependent speed and vehicle load energy consumption model. Demir et al. [25] developed a mathematical model of energy consumption of multiple parameters with speed, distance, and load. In the equation, Ptract (kilowatts) is the unit traction power of the vehicle, τ is the acceleration, M=w+f (w is the mass of the vehicle and f is the mass of the cargo carried by the vehicle), and the rest is the vehicle-related parameter. In this paper, the uniform speed of the vehicles is considered, where τ=0, but the influence of the gradient of the vehicle is not considered. Then, the per unit time of the vehicle t is shown in equation (6). Therefore, the energy consumption of the transportation stage can be given as shown in equation (7), where the unit of speed is m/s:(5)Ptract=Mτ+Mgsinθ+0.5CdρAv2+MgCrcosθv1000,(6)Pttract=0.5CdρAv2+MgCrv1000,(7)ECst2=∑tPttract⋅DisP−AvπtTR−V+∑t∑wETidle⋅wt=∑t0.5CdρA⋅vπtTR−V2+WidleT+∑jVπjTRgCr⋅DisP−A1000+∑t∑w0.5CdρAvc2+WidleTgCr⋅DisP−A⋅wt1000,j=1,…,q;t=1,…,HT;v∈S;w=1,2,….


## 2.3.3. Energy Consumption of Assembly Stage (ECst3)

The assembly stage is a single machine scheduling problem. Since the assembly time of each product on the machine is unchanged, it will not affect the processing energy consumption so that the energy consumption is only related to the machine’s idle time. Therefore, energy consumption of the assembly process is calculated as(8)ECst3=∑zem2idle⋅Sπz+1P−CπzP,z=1,2,…,HP.In summary, the total energy consumption of 3sMISP_JBTEC is calculated as(9)ECtotal=ECst1+ECst2+ECst3.


## 2.4. Formulation of Multiobjective Model of 3sMISP_JBTEC

The 3sMISP_JBTEC is formulated as the following mathematical model, in which two objectives of makespan and total energy consumption are considered:(1)
The processing stage: it is a multiprocess heterogeneous parallel machine scheduling problem with release time in the processing stage. If the jobπik is processed for the first time, then pre_mπik=0; If the machine that processed job πik is the first time to process the job, then pre_kπik=0. The completion time Cπik of πik is calculated as follows:(10)Cπik=minPπik+Rπik,pre_mπik=0;pre_kπik=0,Cπik=minmaxCπpre_kπikk,Rπik+Pπik,pre_mπik=0;pre_kπik≠0,Cπik=minCπipre_mπik+Pπik,pre_mπik≠0;pre_kπik=0,Cπik=minmaxCπipre_mπik,Cπpre_kπikk+Pπik,pre_mπik≠0;pre_kπik≠0,Cst1πjt=Cπik,k=1,2,…,m1;j=1,2,…,q;i=1,2,…,Hk.(2)
The transportation stage: it is a multivehicle single-point delivery problem with the constraints of load and speed in the transportation stage. The total load of all jobs loaded in the vehiclet cannot exceed the vehicle rated load (VT). The transportation time of the vehicle t is determined by the speed vπtTR−V. The transportation completion time of the job j of πTR is calculated as follows:(11)SπjTRwt=maxCst1πjTRwt,wt=1,SπjTRwt=maxCst1πjTRwtt,SπjTRwt−1+Disp−tvπtTR−V+Disp−tvc,wt≠1,Cst2πjTRwt=SπjTRwt+Disp−tvπtTR−V,j=1,2,…,q;wt=1,2,…,l;t=1,2,…,HT.(3)
The assembly stage: it is a single-machine scheduling problem with arrival time or release time. The calculation formula for the assembly completion timeCst3πzP of the product πzP is shown as follows:(12)SπzP=maxCst2πjTR,Cst3πzP=maxCst3πz−1P,SπzP+PπzP,z=1,2,…,HP,j=1,2,…,q.(4)
The optimization goal: the optimization goal is to find an optimal sequenceπ∗=πK,πTR,πTR−V,πP in the set Π of the three-stage sequence from processing and transportation to assembly of the job which composed products so that the makespan Cmax and the total energy consumption Etotal of the three stages are minimized:(13)Cmaxπ∗=minπK,πTR,πTR−V,πP∈ΠCmaxπK,πTR,πTR−V,πP,Etotalπ∗=minπK,πTR,πTR−V,πP∈ΠEtotalπK,πTR,πTR−V,πP,π∗=argCmaxπK,πTR,πTR−V,πP,EtotalπK,πTR,πTR−V,πP⟶min,∀πK,πTR,πTR−V,πP∈Π.


## 3. HEDA_VNS for 3sMISP_JBTEC

### 3.1. Characteristics of 3sMISP_JBTEC

The characteristic of 3sMISP_JBTEC have the following three aspects:(1)
The problem is holistic and systematic. 3sMISP_JBTEC is a multistage integration problem. The scheduling result of the previous stage directly affects the latter stage. Therefore, the overall optimization should be considered when designing the solution algorithm.(2)
The connection between stages is close. Each stage of 3sMISP_JBTEC is not independent, and there are constraints between the process set, the job set, and the product set. Moreover, all the processes belonging to the same job must be processed before the job is transported, and the jobs belonging to the same product must be transported to the assembly place before assembly. Therefore, there is strong coupling between stages.(3)
The solution space of the problem is complicated. 3sMISP_JBTEC is a multistage and multiobjective scheduling problem, and its solution space is very complicated. In addition to the processing sequenceπK, the transportation job sequence πTR, and the product sequence πP, the problem also involves the speed-based vehicles sequence πTR−V. Therefore, it is necessary to analyze and use the characteristics of the problem to reasonably narrow the search space. Meanwhile, πTR−V in the transportation stage needs to be designed with reasonable operation in order to solve the problem better.Based on the above analysis, the following rules are proposed:Rule 1. Jobs belonging to the same product are assigned the same priority in the processing stage.Rule 2. Jobs belonging to the same product should be put into the same vehicle as far as possible under the vehicle loading constraints.Rule 3. Transport vehicles are filled first and transported first.Rule 4. All jobs belonging to the same product are assembled first when they arrive at the assembly place first in the assembly stage.


### 3.2. Design of HEDA_VNS Algorithm

In this section, the HEDA_VNS is designed to improve the efficiency for solving 3sMISP_JBTEC. Because the problem solution space is very complicated, HEDA_VNS only searches the solution space of the subproblems in the processing stage (πK). Then, πTR and πP are generated according to the characteristics of the problem and rules proposed in Section 3.1. Meanwhile, a reasonable speed scheduling scheme (SSS) is proposed for πTR−V in the transportation stage to further improve the quality of the nondominated solution of the problem.


#### 3.2.1. Encoding and Decoding

(i) Encoding and decoding of the processing stage. The encoding of the processing stage is the process-based permutation. Its length is determined by the product-job-process layer. Obviously, the job set Pz is determined by the product z, and the process set Qzj is determined by the job j, which is in the setPz, z∈P, j∈Q. The decoding adopts the method of earliest completion time (ECT) combined with insertion rule to determine the starting time of each process, while the machine allocation is completed. Then, the completion time of the job j in the processing stage and the energy consumption of the machine can be determined.(ii) Encoding and decoding of the transportation stage. In the transportation stage, the encoding and decoding of the job and the vehicle are involved. The job encoding of the transportation phase is based on the sorting of the jobs in the nondescending order of the completion time in the processing stage. The job decoding of the transport phase is based on Rule 2 in Section 3.1. Vt is the current load of the vehicle t, and set Vt=0 as the initial situation. The specific steps of decoding are given as follows: Step 1: select the jobsπjTR belonging to the product πzP from left to right in πTR.Step 2: put the selectedπjTR into the vehicle t in turn under the conditions VπjTR+Vt≤VT. If VπjTR+Vt>VT, put the job j into the vehicle t+1 and then update Vt and the set of jobs to be transported (πTR′).Step 3: check whether there is a jobπkTR in the set πTR′ that satisfies VπkTR+Vt≤VT. If VπkTR+Vt≤VT, put the job πjTR into the vehicle t until VπkTR+Vt>VT, update Vt and πTR′, t=t+1, z=z+1.Step 4: turn to step 1, untilπTR′ is empty.Following the above steps, the start transportation time of the job is determined by the job decoding in the transportation stage.The vehicle encoding is based on the sorting of vehicle speedπTR−V. The decoding of vehicle is based on Rule 3, and the vehicle speed can be obtained by the speed scheduling set. Then, the transportation completion time of the job and transportation energy consumption are determined.(iii) Encoding and decoding of the assembly stage. The assembly encoding is the product-based sorting in the assembly stage, and the product encoding πP is arrangement of nondescending order which is determined by the time when all the jobs belonging to the product arrive at the assembly workshop. The assembly decoding is based on Rule 4, and then, the product completion time and energy consumption are determined. Thus, the three-stage encoding of 3sMISP_JBTEC is shown in Figure 3.Figure 3
The coding method of scheduling solution.


#### 3.2.2. The Speed Scheduling Scheme

The speed interval set in the transportation stage of 3sMISP_JBTEC isv∈vmin,vmax. If the speed of vehicle is generated randomly, there is a large span in this interval. Then, it is not easy to find a more accurate nondominated solution to the problem in a short time. Therefore, in the section, a speed scheduling scheme (SSS) is designed to further refine the speed range, which can better solve the problem. The specific operations are as follows:(1)
The speed interval is divided into three speed subintervals: low, medium, and high speed. The low-speed interval isSVlow=vmin,va, the medium is SVmid=va,vb, and the high is SVhigh=vb,vmax, where vmin<va<vb<vmax.(2)
The speed scheduling setSVuse can be randomly generated from the following seven intervals. SVuse obtained by different modes can be traversed to the interval of different speeds while continuously updating the speed set to improve the quality of the solution:①
SVuse⊂SVlow, marked as SV1.②
SVuse⊂SVmid, marked as SV2.③
SVuse⊂SVhigh, marked as SV3.④
SVuse⊂SVlow∪SVmid, marked as SV4.⑤
SVuse⊂SVlow∪SVhigh, marked as SV5.⑥
SVuse⊂SVmid∪SVhigh, marked as SV6.⑦
SVuse⊂SVlow∪SVmid∪SVhigh, marked as SV7.


## 3.1. Characteristics of 3sMISP_JBTEC

The characteristic of 3sMISP_JBTEC have the following three aspects:(1)
The problem is holistic and systematic. 3sMISP_JBTEC is a multistage integration problem. The scheduling result of the previous stage directly affects the latter stage. Therefore, the overall optimization should be considered when designing the solution algorithm.(2)
The connection between stages is close. Each stage of 3sMISP_JBTEC is not independent, and there are constraints between the process set, the job set, and the product set. Moreover, all the processes belonging to the same job must be processed before the job is transported, and the jobs belonging to the same product must be transported to the assembly place before assembly. Therefore, there is strong coupling between stages.(3)
The solution space of the problem is complicated. 3sMISP_JBTEC is a multistage and multiobjective scheduling problem, and its solution space is very complicated. In addition to the processing sequenceπK, the transportation job sequence πTR, and the product sequence πP, the problem also involves the speed-based vehicles sequence πTR−V. Therefore, it is necessary to analyze and use the characteristics of the problem to reasonably narrow the search space. Meanwhile, πTR−V in the transportation stage needs to be designed with reasonable operation in order to solve the problem better.Based on the above analysis, the following rules are proposed:Rule 1. Jobs belonging to the same product are assigned the same priority in the processing stage.Rule 2. Jobs belonging to the same product should be put into the same vehicle as far as possible under the vehicle loading constraints.Rule 3. Transport vehicles are filled first and transported first.Rule 4. All jobs belonging to the same product are assembled first when they arrive at the assembly place first in the assembly stage.


## 3.2. Design of HEDA_VNS Algorithm

In this section, the HEDA_VNS is designed to improve the efficiency for solving 3sMISP_JBTEC. Because the problem solution space is very complicated, HEDA_VNS only searches the solution space of the subproblems in the processing stage (πK). Then, πTR and πP are generated according to the characteristics of the problem and rules proposed in Section 3.1. Meanwhile, a reasonable speed scheduling scheme (SSS) is proposed for πTR−V in the transportation stage to further improve the quality of the nondominated solution of the problem.


### 3.2.1. Encoding and Decoding

(i) Encoding and decoding of the processing stage. The encoding of the processing stage is the process-based permutation. Its length is determined by the product-job-process layer. Obviously, the job set Pz is determined by the product z, and the process set Qzj is determined by the job j, which is in the setPz, z∈P, j∈Q. The decoding adopts the method of earliest completion time (ECT) combined with insertion rule to determine the starting time of each process, while the machine allocation is completed. Then, the completion time of the job j in the processing stage and the energy consumption of the machine can be determined.(ii) Encoding and decoding of the transportation stage. In the transportation stage, the encoding and decoding of the job and the vehicle are involved. The job encoding of the transportation phase is based on the sorting of the jobs in the nondescending order of the completion time in the processing stage. The job decoding of the transport phase is based on Rule 2 in Section 3.1. Vt is the current load of the vehicle t, and set Vt=0 as the initial situation. The specific steps of decoding are given as follows: Step 1: select the jobsπjTR belonging to the product πzP from left to right in πTR.Step 2: put the selectedπjTR into the vehicle t in turn under the conditions VπjTR+Vt≤VT. If VπjTR+Vt>VT, put the job j into the vehicle t+1 and then update Vt and the set of jobs to be transported (πTR′).Step 3: check whether there is a jobπkTR in the set πTR′ that satisfies VπkTR+Vt≤VT. If VπkTR+Vt≤VT, put the job πjTR into the vehicle t until VπkTR+Vt>VT, update Vt and πTR′, t=t+1, z=z+1.Step 4: turn to step 1, untilπTR′ is empty.Following the above steps, the start transportation time of the job is determined by the job decoding in the transportation stage.The vehicle encoding is based on the sorting of vehicle speedπTR−V. The decoding of vehicle is based on Rule 3, and the vehicle speed can be obtained by the speed scheduling set. Then, the transportation completion time of the job and transportation energy consumption are determined.(iii) Encoding and decoding of the assembly stage. The assembly encoding is the product-based sorting in the assembly stage, and the product encoding πP is arrangement of nondescending order which is determined by the time when all the jobs belonging to the product arrive at the assembly workshop. The assembly decoding is based on Rule 4, and then, the product completion time and energy consumption are determined. Thus, the three-stage encoding of 3sMISP_JBTEC is shown in Figure 3.Figure 3
The coding method of scheduling solution.


### 3.2.2. The Speed Scheduling Scheme

The speed interval set in the transportation stage of 3sMISP_JBTEC isv∈vmin,vmax. If the speed of vehicle is generated randomly, there is a large span in this interval. Then, it is not easy to find a more accurate nondominated solution to the problem in a short time. Therefore, in the section, a speed scheduling scheme (SSS) is designed to further refine the speed range, which can better solve the problem. The specific operations are as follows:(1)
The speed interval is divided into three speed subintervals: low, medium, and high speed. The low-speed interval isSVlow=vmin,va, the medium is SVmid=va,vb, and the high is SVhigh=vb,vmax, where vmin<va<vb<vmax.(2)
The speed scheduling setSVuse can be randomly generated from the following seven intervals. SVuse obtained by different modes can be traversed to the interval of different speeds while continuously updating the speed set to improve the quality of the solution:①
SVuse⊂SVlow, marked as SV1.②
SVuse⊂SVmid, marked as SV2.③
SVuse⊂SVhigh, marked as SV3.④
SVuse⊂SVlow∪SVmid, marked as SV4.⑤
SVuse⊂SVlow∪SVhigh, marked as SV5.⑥
SVuse⊂SVmid∪SVhigh, marked as SV6.⑦
SVuse⊂SVlow∪SVmid∪SVhigh, marked as SV7.


## 3.2.1. Encoding and Decoding

(i) Encoding and decoding of the processing stage. The encoding of the processing stage is the process-based permutation. Its length is determined by the product-job-process layer. Obviously, the job set Pz is determined by the product z, and the process set Qzj is determined by the job j, which is in the setPz, z∈P, j∈Q. The decoding adopts the method of earliest completion time (ECT) combined with insertion rule to determine the starting time of each process, while the machine allocation is completed. Then, the completion time of the job j in the processing stage and the energy consumption of the machine can be determined.(ii) Encoding and decoding of the transportation stage. In the transportation stage, the encoding and decoding of the job and the vehicle are involved. The job encoding of the transportation phase is based on the sorting of the jobs in the nondescending order of the completion time in the processing stage. The job decoding of the transport phase is based on Rule 2 in Section 3.1. Vt is the current load of the vehicle t, and set Vt=0 as the initial situation. The specific steps of decoding are given as follows: Step 1: select the jobsπjTR belonging to the product πzP from left to right in πTR.Step 2: put the selectedπjTR into the vehicle t in turn under the conditions VπjTR+Vt≤VT. If VπjTR+Vt>VT, put the job j into the vehicle t+1 and then update Vt and the set of jobs to be transported (πTR′).Step 3: check whether there is a jobπkTR in the set πTR′ that satisfies VπkTR+Vt≤VT. If VπkTR+Vt≤VT, put the job πjTR into the vehicle t until VπkTR+Vt>VT, update Vt and πTR′, t=t+1, z=z+1.Step 4: turn to step 1, untilπTR′ is empty.Following the above steps, the start transportation time of the job is determined by the job decoding in the transportation stage.The vehicle encoding is based on the sorting of vehicle speedπTR−V. The decoding of vehicle is based on Rule 3, and the vehicle speed can be obtained by the speed scheduling set. Then, the transportation completion time of the job and transportation energy consumption are determined.(iii) Encoding and decoding of the assembly stage. The assembly encoding is the product-based sorting in the assembly stage, and the product encoding πP is arrangement of nondescending order which is determined by the time when all the jobs belonging to the product arrive at the assembly workshop. The assembly decoding is based on Rule 4, and then, the product completion time and energy consumption are determined. Thus, the three-stage encoding of 3sMISP_JBTEC is shown in Figure 3.Figure 3
The coding method of scheduling solution.


## 3.2.2. The Speed Scheduling Scheme

The speed interval set in the transportation stage of 3sMISP_JBTEC isv∈vmin,vmax. If the speed of vehicle is generated randomly, there is a large span in this interval. Then, it is not easy to find a more accurate nondominated solution to the problem in a short time. Therefore, in the section, a speed scheduling scheme (SSS) is designed to further refine the speed range, which can better solve the problem. The specific operations are as follows:(1)
The speed interval is divided into three speed subintervals: low, medium, and high speed. The low-speed interval isSVlow=vmin,va, the medium is SVmid=va,vb, and the high is SVhigh=vb,vmax, where vmin<va<vb<vmax.(2)
The speed scheduling setSVuse can be randomly generated from the following seven intervals. SVuse obtained by different modes can be traversed to the interval of different speeds while continuously updating the speed set to improve the quality of the solution:①
SVuse⊂SVlow, marked as SV1.②
SVuse⊂SVmid, marked as SV2.③
SVuse⊂SVhigh, marked as SV3.④
SVuse⊂SVlow∪SVmid, marked as SV4.⑤
SVuse⊂SVlow∪SVhigh, marked as SV5.⑥
SVuse⊂SVmid∪SVhigh, marked as SV6.⑦
SVuse⊂SVlow∪SVmid∪SVhigh, marked as SV7.


## 4. Methodology of HEDA_VNS

### 4.1. HEDA_VNS Global Search

#### 4.1.1. Initialization of Population, Probability Model, and Speed Scheduling Set

According to Rule 1, the product aggregation (PA) method is designed to generate the number ofη×popsize individuals in the processing stage, and the remaining individuals are generated randomly to initialize the population. The PA is a rule to generate an individual. The specific steps about PA are as follows (shown in Figure 4): first, a product sequence is randomly generated. Then, a job sequence that belongs to the same product is randomly generated. At last, a process sequence that is based on the same job is randomly generated. According to PA, the jobs that make up the same product can be more concentrated. After the jobs have been processed in the processing stage, they can be transported to the assembly stage faster and more concentrated.Figure 4
An example of the PA rule.According to the encoding method inSection 3.2.1, the process arrangement matrix ρ is used as the probability model. In order to ensure that the algorithm searches the solution space uniformly as much as possible, the probability model ρi,j adopts a uniform distribution, and ρi,j0=1/A. The initial speed scheduling set is SVuse⊂SV7 so that the transportation speed is generated randomly in vmin,vmax.


#### 4.1.2. Update Probability Matrix

For multiobjective optimization, the nondominated solution is selected in iteration to update the probability model.Ii,j is the number of times that the job j appeared at or before the position i of the process sequence vector. Ei,jg is the probability obtained through the nondominated solution statistics in the iteration g. This can be updated by ρi,jg, where γ∈0,1 is the learning rate:(14)Ii,j=1,jobjappears at or before positioni,0,else,Ei,jg=Ii,j∑i=1nIi,j,∀i,j,ρi,jg+1=1−γρi,jg+γEi,j.


#### 4.1.3. Sampling Method

In subsequent iteration of the algorithm, a new population is generated by sampling the probability matrix. The sampling method in this paper is designed for the problem model. The purpose is to make the jobs belong to the same product more likely to be aggregated together to produce higher-quality individuals, but each sampling uses roulette operation which guarantees the diversity of the population to a certain extent. Once a new individual is generated, it constitutes a new population for the next iteration. Specific steps are as follows:Step 1: wheni=1, the roulette method is used to sample the matrix to select the workpiece directly and judge whether j∈Pz. The probability that the job j appears in position i is ρi,jg. If the number of job j occurrences in the matrix ρ is equal to the total number of processes of jobj, set the column j of the matrix ρ to zero and normalize each row.Step 2: wheni≠1, add the probabilities of the job j belonging to Pz of the row i to get ∑j=mkρi,j, where j∈Pz:Step 2.1: if∑j=mkρi,j=0, the roulette method is used to sample directly.Step 2.2: if∑j=mkρi,j≠0, a random number ε,ε∈0.5,0.8 is generated and compared with ∑j=mkρi,j. If ∑j=mkρi,j≥ε, the roulette method is used to sample directly; if ∑j=mkρi,j<ε, then readjust the probability of job j on the current row i to obtain a new probability. Among them, the probability of job j belonging to the product Pz is calculated using formula (16) or otherwise using formula (17). Use roulette to sample after adjustment. If the number of job j in the matrix ρ is equal to the total number of processes of job j, set the column of the matrix to zero and normalize each row:(15)ρi,j∗=ρi,jz∑jz=mkρi,jz×ε,j∈Pz,(16)ρi,j∗=ρi,jz1−∑jz=mkρi,jz×1−ε,j∉Pz.Step 3: judge whether the jobj in the row i of sampling by Step 2 belongs to Pz; if job j∈Pz, then j=j+1 directly. If j∈Pz∗, then order Pz∗=Pz and j=j+1, until all the processes of the job j belonging to Pz are selected completely.


### 4.2. Local Search Strategy

#### 4.2.1. Local Search I

After new individuals of the population are sampled through the probability matrix, the probability matrix is updated with the individuals who have obtained nondominated solutions. A local search strategy is designed with Rule 1 in three situations to better guide the global search direction and beneficial to avoid some invalid search. Meanwhile, the original solution structure can be better retained.For the nondominant solutionπr obtained in the population (where r=1,2,…,m), two positions u,v (u≠v) in πr are selected randomly, and πru is the job encoding of the position u of πr.Situation 1.
Ifπru=πrv, it means that the two positions are the same job; the Swap operation will be invalid, then the Insert operation is performed at this time. If u<v, insert forward. Otherwise, insert back and to generate a new individual πr′. If f1πr>f1πr′andf2πr>f2πr′, let πr=πr′, then update the nondominated solution set.Situation 2.
Ifπru≠πrvand it does not belong to the same product, let x=maxu,v−minu,v and k=HO/HP−1 (where HO is the total number of processes of all products, i.e., the length of the individual πr in the processing stage and HP is the total number of products); if x≤k, the Swap operation is performed to generate a new individual. If f1πr>f1πr′andf2πr>f2πr′, let πr=πr′, update the nondominated solution set.Situation 3.
Ifπru≠πrv, it means that the two positions belong to different jobs. If they belong to the same product, then a hybrid operation based on the variable neighborhood local search of Insert and Swap is performed. Specific steps are given as follows (Algorithm 1).Algorithm 1:Local search insertSwap method.
Setloop=1;RepeatSetcount=0; max_count=2;RepeatIfcount=0, then the Insert operation is performed on πr to get πr′;Ifcount=1, then the Swap operation is performed on πr to get πr′;Iff1πr>f1πr′andf2πr>f2πr′, then count=0, πr=πr′, update nondominated solution set;Else, letcount=count+1;Untilcount=max_count;Untilloop=max_loop;End.


#### 4.2.2. Local Search II

In the transportation stage, the faster the vehicle transportation speed and the shorter the transportation time, and the jobs will be faster, reaching the assembly stage for assembly. Meanwhile, the makespan decreases, but the energy consumption increases. Hence, the two target values conflict. In order to balance the two goals and improve the quality of nondominated solutions, it is also necessary to search for the transportation speed and vehicle order. Combining the speed scheduling scheme given in Section3.2.2, a variable neighborhood search hybrid operation based on the speed set is designed in this section.For the nondominant solution setκ=π1,π2,π3,…,πm, πaTR−Vis the vehicle sequence corresponding to individual πa in the transportation stage. Two positions u,v (u≠v) are selected randomly in πaTR−V, and πoTR−Vu is the vehicle encoding of the position u of the individual πoTR−V. SVuse=v1,…,vHT is the current speed scheduling set, and SVx is the speed scheduling set x, where x=1,…,7. The specific operations are as follows (Algorithm 2).Algorithm 2:Local search speed mechanism.
Fora=1 to mForx=1 to 7SVuse=SVx;Setloop=1;RepeatSetcount=0; max_count=2;RepeatIfcount=0, then the Insert operation is performed on πaTR−V to get πaTR−V′;Ifcount=1, then the Swap operation is performed on πaTR−V to get πaTR−V′;Iff1πa,πaTR−V,SVuse>f1πa,πaTR−V′,SVuseandf2πa,πaTR−V,SVuse>f2πa,πaTR−V′,SVuse then set count=0, πaTR−V=πaTR−V′, update nondominated solution set;Else, setcount=count+1;Untilcount=max_count;Untilloop=max_loop;End;End.


### 4.3. Species Diversity Determination and Control Mechanism

With the continuous iteration of the algorithm, the diversity of the population will decrease, and the individuals in the population will become very similar, which will cause the algorithm to fall into a local optimum. In order to solve the problem, a population control mechanism of literature [41] is used in this paper to calculate the diversity value θdiv of contemporary populations. A diversity threshold δ is given; when θdiv≤δ, the current population is adjusted to retain noninferior individuals in the contemporary population, and φ×popsize/3 individuals are randomly generated by the PA rule, and the rest are randomly generated.


### 4.4. The Framework of HEDA_VNS

In HEDA_VNS, firstly, a probability model is adopted to learn high-quality solution information and guides the algorithm to search globally. Secondly, a Local Search I is designed by using the rules obtained from the analysis of the problem inSection 3.1. Then, in order to improve the quality of the solution, the Local Search II is combined with the speed scheduling set to realize an effective search in the velocity space. Finally, a population control mechanism is designed to maintain the diversity of the population. The framework of HEDA_VNS is shown in Figure 5.Figure 5
The framework of HEDA_VNS.


## 4.1. HEDA_VNS Global Search

### 4.1.1. Initialization of Population, Probability Model, and Speed Scheduling Set

According to Rule 1, the product aggregation (PA) method is designed to generate the number ofη×popsize individuals in the processing stage, and the remaining individuals are generated randomly to initialize the population. The PA is a rule to generate an individual. The specific steps about PA are as follows (shown in Figure 4): first, a product sequence is randomly generated. Then, a job sequence that belongs to the same product is randomly generated. At last, a process sequence that is based on the same job is randomly generated. According to PA, the jobs that make up the same product can be more concentrated. After the jobs have been processed in the processing stage, they can be transported to the assembly stage faster and more concentrated.Figure 4
An example of the PA rule.According to the encoding method inSection 3.2.1, the process arrangement matrix ρ is used as the probability model. In order to ensure that the algorithm searches the solution space uniformly as much as possible, the probability model ρi,j adopts a uniform distribution, and ρi,j0=1/A. The initial speed scheduling set is SVuse⊂SV7 so that the transportation speed is generated randomly in vmin,vmax.


### 4.1.2. Update Probability Matrix

For multiobjective optimization, the nondominated solution is selected in iteration to update the probability model.Ii,j is the number of times that the job j appeared at or before the position i of the process sequence vector. Ei,jg is the probability obtained through the nondominated solution statistics in the iteration g. This can be updated by ρi,jg, where γ∈0,1 is the learning rate:(14)Ii,j=1,jobjappears at or before positioni,0,else,Ei,jg=Ii,j∑i=1nIi,j,∀i,j,ρi,jg+1=1−γρi,jg+γEi,j.


### 4.1.3. Sampling Method

In subsequent iteration of the algorithm, a new population is generated by sampling the probability matrix. The sampling method in this paper is designed for the problem model. The purpose is to make the jobs belong to the same product more likely to be aggregated together to produce higher-quality individuals, but each sampling uses roulette operation which guarantees the diversity of the population to a certain extent. Once a new individual is generated, it constitutes a new population for the next iteration. Specific steps are as follows:Step 1: wheni=1, the roulette method is used to sample the matrix to select the workpiece directly and judge whether j∈Pz. The probability that the job j appears in position i is ρi,jg. If the number of job j occurrences in the matrix ρ is equal to the total number of processes of jobj, set the column j of the matrix ρ to zero and normalize each row.Step 2: wheni≠1, add the probabilities of the job j belonging to Pz of the row i to get ∑j=mkρi,j, where j∈Pz:Step 2.1: if∑j=mkρi,j=0, the roulette method is used to sample directly.Step 2.2: if∑j=mkρi,j≠0, a random number ε,ε∈0.5,0.8 is generated and compared with ∑j=mkρi,j. If ∑j=mkρi,j≥ε, the roulette method is used to sample directly; if ∑j=mkρi,j<ε, then readjust the probability of job j on the current row i to obtain a new probability. Among them, the probability of job j belonging to the product Pz is calculated using formula (16) or otherwise using formula (17). Use roulette to sample after adjustment. If the number of job j in the matrix ρ is equal to the total number of processes of job j, set the column of the matrix to zero and normalize each row:(15)ρi,j∗=ρi,jz∑jz=mkρi,jz×ε,j∈Pz,(16)ρi,j∗=ρi,jz1−∑jz=mkρi,jz×1−ε,j∉Pz.Step 3: judge whether the jobj in the row i of sampling by Step 2 belongs to Pz; if job j∈Pz, then j=j+1 directly. If j∈Pz∗, then order Pz∗=Pz and j=j+1, until all the processes of the job j belonging to Pz are selected completely.


## 4.1.1. Initialization of Population, Probability Model, and Speed Scheduling Set

According to Rule 1, the product aggregation (PA) method is designed to generate the number ofη×popsize individuals in the processing stage, and the remaining individuals are generated randomly to initialize the population. The PA is a rule to generate an individual. The specific steps about PA are as follows (shown in Figure 4): first, a product sequence is randomly generated. Then, a job sequence that belongs to the same product is randomly generated. At last, a process sequence that is based on the same job is randomly generated. According to PA, the jobs that make up the same product can be more concentrated. After the jobs have been processed in the processing stage, they can be transported to the assembly stage faster and more concentrated.Figure 4
An example of the PA rule.According to the encoding method inSection 3.2.1, the process arrangement matrix ρ is used as the probability model. In order to ensure that the algorithm searches the solution space uniformly as much as possible, the probability model ρi,j adopts a uniform distribution, and ρi,j0=1/A. The initial speed scheduling set is SVuse⊂SV7 so that the transportation speed is generated randomly in vmin,vmax.


## 4.1.2. Update Probability Matrix

For multiobjective optimization, the nondominated solution is selected in iteration to update the probability model.Ii,j is the number of times that the job j appeared at or before the position i of the process sequence vector. Ei,jg is the probability obtained through the nondominated solution statistics in the iteration g. This can be updated by ρi,jg, where γ∈0,1 is the learning rate:(14)Ii,j=1,jobjappears at or before positioni,0,else,Ei,jg=Ii,j∑i=1nIi,j,∀i,j,ρi,jg+1=1−γρi,jg+γEi,j.


## 4.1.3. Sampling Method

In subsequent iteration of the algorithm, a new population is generated by sampling the probability matrix. The sampling method in this paper is designed for the problem model. The purpose is to make the jobs belong to the same product more likely to be aggregated together to produce higher-quality individuals, but each sampling uses roulette operation which guarantees the diversity of the population to a certain extent. Once a new individual is generated, it constitutes a new population for the next iteration. Specific steps are as follows:Step 1: wheni=1, the roulette method is used to sample the matrix to select the workpiece directly and judge whether j∈Pz. The probability that the job j appears in position i is ρi,jg. If the number of job j occurrences in the matrix ρ is equal to the total number of processes of jobj, set the column j of the matrix ρ to zero and normalize each row.Step 2: wheni≠1, add the probabilities of the job j belonging to Pz of the row i to get ∑j=mkρi,j, where j∈Pz:Step 2.1: if∑j=mkρi,j=0, the roulette method is used to sample directly.Step 2.2: if∑j=mkρi,j≠0, a random number ε,ε∈0.5,0.8 is generated and compared with ∑j=mkρi,j. If ∑j=mkρi,j≥ε, the roulette method is used to sample directly; if ∑j=mkρi,j<ε, then readjust the probability of job j on the current row i to obtain a new probability. Among them, the probability of job j belonging to the product Pz is calculated using formula (16) or otherwise using formula (17). Use roulette to sample after adjustment. If the number of job j in the matrix ρ is equal to the total number of processes of job j, set the column of the matrix to zero and normalize each row:(15)ρi,j∗=ρi,jz∑jz=mkρi,jz×ε,j∈Pz,(16)ρi,j∗=ρi,jz1−∑jz=mkρi,jz×1−ε,j∉Pz.Step 3: judge whether the jobj in the row i of sampling by Step 2 belongs to Pz; if job j∈Pz, then j=j+1 directly. If j∈Pz∗, then order Pz∗=Pz and j=j+1, until all the processes of the job j belonging to Pz are selected completely.


## 4.2. Local Search Strategy

### 4.2.1. Local Search I

After new individuals of the population are sampled through the probability matrix, the probability matrix is updated with the individuals who have obtained nondominated solutions. A local search strategy is designed with Rule 1 in three situations to better guide the global search direction and beneficial to avoid some invalid search. Meanwhile, the original solution structure can be better retained.For the nondominant solutionπr obtained in the population (where r=1,2,…,m), two positions u,v (u≠v) in πr are selected randomly, and πru is the job encoding of the position u of πr.Situation 1.
Ifπru=πrv, it means that the two positions are the same job; the Swap operation will be invalid, then the Insert operation is performed at this time. If u<v, insert forward. Otherwise, insert back and to generate a new individual πr′. If f1πr>f1πr′andf2πr>f2πr′, let πr=πr′, then update the nondominated solution set.Situation 2.
Ifπru≠πrvand it does not belong to the same product, let x=maxu,v−minu,v and k=HO/HP−1 (where HO is the total number of processes of all products, i.e., the length of the individual πr in the processing stage and HP is the total number of products); if x≤k, the Swap operation is performed to generate a new individual. If f1πr>f1πr′andf2πr>f2πr′, let πr=πr′, update the nondominated solution set.Situation 3.
Ifπru≠πrv, it means that the two positions belong to different jobs. If they belong to the same product, then a hybrid operation based on the variable neighborhood local search of Insert and Swap is performed. Specific steps are given as follows (Algorithm 1).Algorithm 1:Local search insertSwap method.
Setloop=1;RepeatSetcount=0; max_count=2;RepeatIfcount=0, then the Insert operation is performed on πr to get πr′;Ifcount=1, then the Swap operation is performed on πr to get πr′;Iff1πr>f1πr′andf2πr>f2πr′, then count=0, πr=πr′, update nondominated solution set;Else, letcount=count+1;Untilcount=max_count;Untilloop=max_loop;End.


### 4.2.2. Local Search II

In the transportation stage, the faster the vehicle transportation speed and the shorter the transportation time, and the jobs will be faster, reaching the assembly stage for assembly. Meanwhile, the makespan decreases, but the energy consumption increases. Hence, the two target values conflict. In order to balance the two goals and improve the quality of nondominated solutions, it is also necessary to search for the transportation speed and vehicle order. Combining the speed scheduling scheme given in Section3.2.2, a variable neighborhood search hybrid operation based on the speed set is designed in this section.For the nondominant solution setκ=π1,π2,π3,…,πm, πaTR−Vis the vehicle sequence corresponding to individual πa in the transportation stage. Two positions u,v (u≠v) are selected randomly in πaTR−V, and πoTR−Vu is the vehicle encoding of the position u of the individual πoTR−V. SVuse=v1,…,vHT is the current speed scheduling set, and SVx is the speed scheduling set x, where x=1,…,7. The specific operations are as follows (Algorithm 2).Algorithm 2:Local search speed mechanism.
Fora=1 to mForx=1 to 7SVuse=SVx;Setloop=1;RepeatSetcount=0; max_count=2;RepeatIfcount=0, then the Insert operation is performed on πaTR−V to get πaTR−V′;Ifcount=1, then the Swap operation is performed on πaTR−V to get πaTR−V′;Iff1πa,πaTR−V,SVuse>f1πa,πaTR−V′,SVuseandf2πa,πaTR−V,SVuse>f2πa,πaTR−V′,SVuse then set count=0, πaTR−V=πaTR−V′, update nondominated solution set;Else, setcount=count+1;Untilcount=max_count;Untilloop=max_loop;End;End.


## 4.2.1. Local Search I

After new individuals of the population are sampled through the probability matrix, the probability matrix is updated with the individuals who have obtained nondominated solutions. A local search strategy is designed with Rule 1 in three situations to better guide the global search direction and beneficial to avoid some invalid search. Meanwhile, the original solution structure can be better retained.For the nondominant solutionπr obtained in the population (where r=1,2,…,m), two positions u,v (u≠v) in πr are selected randomly, and πru is the job encoding of the position u of πr.Situation 1.
Ifπru=πrv, it means that the two positions are the same job; the Swap operation will be invalid, then the Insert operation is performed at this time. If u<v, insert forward. Otherwise, insert back and to generate a new individual πr′. If f1πr>f1πr′andf2πr>f2πr′, let πr=πr′, then update the nondominated solution set.Situation 2.
Ifπru≠πrvand it does not belong to the same product, let x=maxu,v−minu,v and k=HO/HP−1 (where HO is the total number of processes of all products, i.e., the length of the individual πr in the processing stage and HP is the total number of products); if x≤k, the Swap operation is performed to generate a new individual. If f1πr>f1πr′andf2πr>f2πr′, let πr=πr′, update the nondominated solution set.Situation 3.
Ifπru≠πrv, it means that the two positions belong to different jobs. If they belong to the same product, then a hybrid operation based on the variable neighborhood local search of Insert and Swap is performed. Specific steps are given as follows (Algorithm 1).Algorithm 1:Local search insertSwap method.
Setloop=1;RepeatSetcount=0; max_count=2;RepeatIfcount=0, then the Insert operation is performed on πr to get πr′;Ifcount=1, then the Swap operation is performed on πr to get πr′;Iff1πr>f1πr′andf2πr>f2πr′, then count=0, πr=πr′, update nondominated solution set;Else, letcount=count+1;Untilcount=max_count;Untilloop=max_loop;End.


## 4.2.2. Local Search II

In the transportation stage, the faster the vehicle transportation speed and the shorter the transportation time, and the jobs will be faster, reaching the assembly stage for assembly. Meanwhile, the makespan decreases, but the energy consumption increases. Hence, the two target values conflict. In order to balance the two goals and improve the quality of nondominated solutions, it is also necessary to search for the transportation speed and vehicle order. Combining the speed scheduling scheme given in Section3.2.2, a variable neighborhood search hybrid operation based on the speed set is designed in this section.For the nondominant solution setκ=π1,π2,π3,…,πm, πaTR−Vis the vehicle sequence corresponding to individual πa in the transportation stage. Two positions u,v (u≠v) are selected randomly in πaTR−V, and πoTR−Vu is the vehicle encoding of the position u of the individual πoTR−V. SVuse=v1,…,vHT is the current speed scheduling set, and SVx is the speed scheduling set x, where x=1,…,7. The specific operations are as follows (Algorithm 2).Algorithm 2:Local search speed mechanism.
Fora=1 to mForx=1 to 7SVuse=SVx;Setloop=1;RepeatSetcount=0; max_count=2;RepeatIfcount=0, then the Insert operation is performed on πaTR−V to get πaTR−V′;Ifcount=1, then the Swap operation is performed on πaTR−V to get πaTR−V′;Iff1πa,πaTR−V,SVuse>f1πa,πaTR−V′,SVuseandf2πa,πaTR−V,SVuse>f2πa,πaTR−V′,SVuse then set count=0, πaTR−V=πaTR−V′, update nondominated solution set;Else, setcount=count+1;Untilcount=max_count;Untilloop=max_loop;End;End.


## 4.3. Species Diversity Determination and Control Mechanism

With the continuous iteration of the algorithm, the diversity of the population will decrease, and the individuals in the population will become very similar, which will cause the algorithm to fall into a local optimum. In order to solve the problem, a population control mechanism of literature [41] is used in this paper to calculate the diversity value θdiv of contemporary populations. A diversity threshold δ is given; when θdiv≤δ, the current population is adjusted to retain noninferior individuals in the contemporary population, and φ×popsize/3 individuals are randomly generated by the PA rule, and the rest are randomly generated.


## 4.4. The Framework of HEDA_VNS

In HEDA_VNS, firstly, a probability model is adopted to learn high-quality solution information and guides the algorithm to search globally. Secondly, a Local Search I is designed by using the rules obtained from the analysis of the problem inSection 3.1. Then, in order to improve the quality of the solution, the Local Search II is combined with the speed scheduling set to realize an effective search in the velocity space. Finally, a population control mechanism is designed to maintain the diversity of the population. The framework of HEDA_VNS is shown in Figure 5.Figure 5
The framework of HEDA_VNS.


## 5. Simulation Results and Discussion

### 5.1. Experimental Settings and Evaluation Index

#### 5.1.1. Experimental Settings

All test questions of 3sMISP_JBTEC are based on the structural of the three-stage integrated system. For test data, the number of jobs composed of each product and the number of procedures corresponding to the jobs are randomly generated in the interval of [2, 5] and [1, 3], respectively. The processing time of each job and the assembly time of each product are randomly generated in the interval of [20, 80] and [100, 200], respectively. The load of each job is randomly generated in the interval of [20, 50], and the unit energy consumption of the processing machine is randomly generated in the interval of [3, 5]. According to the literature [24], the parameters of vehicle-related are as follows: Cd=0.7, Cr=0.01, ρ=1.2041, A=3.912, and g=9.81. The distance of vehicle transportation is DisP−A=8000.In addition to the number of products and machines, the results of the test problems are also affected by the number of transport vehicles. Therefore, the test problems listed in this paper are expressed asP_M_T. All algorithms and test procedures are implemented by Delphi 2010 programming, and the operating system is WinXP.


#### 5.1.2. Evaluation Index

In the comparison, two indexes are used to evaluate the algorithm [42]. There are R_NSj and N_NSj. R_NSj is used to evaluate the quality of the nondominated solutions (shown in equation (17)). When R_NSj=0, the solutions in Sj are all dominated by other solutions. Also, when R_NSj=1, the solutions in Sj are all nondominated solutions in S. N_NSj is the number of solutions in Sj which are not dominated by other solutions (shown in equation (18)). The larger the value of N_NSj, the greater the number of nondominated solutions. Obviously, R_NSj is the dominant ratio, which evaluates the overall quality of the algorithm to obtain nondominated solutions, and N_NSj is the number of dominants, which evaluates the ability of the algorithm to obtain nondominated solutions. There is a positive correlation between these two indicators, and the correlation coefficient is 1/Sj:(17)R_NSj=Sj−x∈Sj∃y∈S:y≺x|Sj,(18)N_NSj=|Sj−x∈Sj∃y∈S:y≺x.


### 5.2. Key Parameter Setting and Influence of HEDA_VNS

In the section, the three key parameters of HEDA_VNS which are population size (popsize), iterative probability sampling parameters (η), and learning rate (γ) are analyzed by the Design of Experiment (DOE) method of medium-scale problems. On the basis of combining existing research, four levels of each parameter are determined (shown in Table 1); thereby, an orthogonal experimental table is established with a scale of L1643. The algorithm runs independently for each set of parameters for 10 medium-scale questions of 20 times, with 2×P×M×T seconds as the termination condition for each scale and the average value AVG of each scale under different parameter combinations of the algorithm as the evaluation index to determine the appropriate parameters combination. The results are shown in Table 2.Table 1
Parameter level.
ParameterLevel1234Popsize30405060η0.30.40.50.6γ0.10.20.30.4Table 2
Orthogonal table and average statistics.
Parameter combinationLevelAVG×10Popsizeηγ11110.50121220.44731330.39341440.29952120.37562230.49172340.38682410.29393130.607103240.583113310.412123420.286134140.456144210.486154320.363164430.368From the experimental results (shown in Table3 and Figure 6), it can be found that different parameter combinations have a greater impact on the performance of the algorithm. Based on the experimental analysis results, the best parameters popsize=50, η=0.4, and γ=0.3 are set in this paper, and further performance testing and comparison will be carried out based on this parameter setting.Table 3
The response value of parameters.
LevelPopsizeηγ10.4100.4850.42320.3860.5020.36830.4720.3890.46540.4190.3120.431Figure 6
The level trend of the influence of each parameter on the algorithm performance.
(a)(b)(c)


### 5.3. Analysis of the Results of Energy Consumption and Makespan under a Certain Problem Scale

In this section, HEDA_VNS is used to solve the 3sMISP_JBTEC with a problem scale of (3_3_2). The scale of the problem can be described as follows: 3 heterogeneous parallel machines in the processing stage, 2 vehicles with the same load in the transportation stage, and one machine in the assembly stage. 3 products are required to be processed and assembled during the three stages. The product composition is shown in Figure7. The 3 products are assembled from multiple jobs. Each job has multiple processes, and each process can be processed on multiple machines. The vehicle’s return to no-load speed is vc=40. The data of each stage of the product are shown in Table 4.Figure 7
The product composition of the problem scale of (3_3_2).Table 4
Data at each stage of the problem scale of (3_3_2).
P1P2P3J1J2J3J4J5J6J7J8J9Pijkm127—99———11691—1137554——87————8098—m225——39—7510111062———31112—59—————80m377107—59285756—3326101—5060——979783———Rjkm15593624110166398459m28875877010147803749m32555696064881147230Vj33482552636312533Az16112899Figure8 shows the noninferior solution set of the problem, and other scales are similar. It can be seen from Figure 8 that all the solutions are independent of each other due to conflicts and constraints between the makespan and total energy consumption (TEC). The conflicts and containments are embodied in both machine processing stage and vehicle transportation stage. The solution at point A in Figure 8 shows that it has a large span in the machine processing stage, but it has close connection between the stages, and all vehicles are transported at high speed. Meanwhile, the makespan is relatively smallest, but energy consumption is relatively highest. On the one hand, high-speed transportation can reduce the transportation time and the accumulation of intermediate inventory and effectively prevent delays in the manufacturing process. On the other hand, high-speed transportation may cause that jobs arrive early for assembly, which is prone to bottlenecks and a backlog of finished products. Therefore, it is not a blind pursuit of makespan, and it is necessary to limit the maximum speed level of transportation vehicles. The solution at point B in Figure 8 represents that the machining span is small, but the connection between the stages is not tight enough, and all vehicles are transported at low speed. Meanwhile, the makespan is relatively largest, but energy consumption is relatively lowest. In this case, although the processing stage is compact, the delivery delay time and the intermediate inventory level will be at the highest level, and the delivery of the finished product may be delayed. It can be seen that although it is the same problem, the noninferior solution will be affected due to different vehicle transportation speeds. Hence, enterprise managers need to make decisions based on the company itself and related policies, taking into account factors such as order time and demand; for example, the selected solution will be different if the same order is completed in a shorter planning period and the selected solution is completed in a longer planning period, but under normal circumstances, decision makers generally choose point C because the makespan and energy consumption are at a normal and acceptable level.Figure 8
The noninferior solution set of the problem scale of (3_3_2).


### 5.4. Comparison of Experimental Results of HEDA_VNS with Other Intelligent Algorithms

In order to further verify the effectiveness of HEDA_VNS compared with HMOBSA [19] and GA-GSO-GTHS [23], a large number of experiments can be carried out by means of the generated different types of problems. HMOBSA is an effective multiobjective backtracking algorithm. The performance of HMOBSA is superior to the well-known multiobjective algorithm (nondominated sorting genetic algorithm, NSGAII) and MOEA/D in solving energy consumption problems. The turn off/on strategy is also used when calculating energy consumption in the processing stage. GA-GSO-GTHS is a multiobjective hybrid optimization algorithm with strategy. The performance of GA-GSO-GTHS is better than most of the latest multiobjective optimization algorithms that are widely used in scheduling problems. It is effective in solving production energy consumption problems that consider transportation. In addition, the parameters of HMOBSA are set as follows: popsize=50, crossover probability pc=0.9, and mutation probability pm=0.1. The parameters of GA-GSO-GTHS are set as follows: popsize=100, pc=0.6, pm=0.05, step size s=5, maximum perceptual radius rs=20, volatility coefficient ρ=0.4, enhancement factor γ=0.6, perceptual radius scaling factor β=0.08, nt=5, and l0=5. The parameters selected by the three algorithms are all good parameters. Besides, HEDA_VNS runs for 200 generations, and other algorithms run the same time as HEDA_VNS. The comparative results of the three algorithms to solve 3sMISP_JBTEC under the randomly generated speed in vmin,vmax are listed in Table 5. Among them, R_N and N_N, respectively, represent the index values of the evaluation solutions corresponding to the three algorithms. The data in Table 5 are the average values of the algorithm after 20 runs.Table 5
Comparison of HEDA_VNS with HMOBSA and GA-GSO-GTHS.
No.P_M_THMOBSAGA-GSO-GTHSHEDA_VNSR_NN_NR_NN_NR_NN_N012_3_20.200.500.551.300.471.25023_2_20.050.100.500.970.521.30033_3_20.020.050.351.350.802.15044_4_20.050.300.751.550.601.50054_5_30.070.020.351.150.681.80065_3_30.030.010.270.450.811.60075_4_30.050.150.520.850.751.55085_5_30.150.350.130.650.801.95095_6_30.020.050.150.350.922.05106_4_30.000.000.130.350.952.20116_5_30.050.100.270.500.862.05126_6_30.020.050.220.650.902.20136_4_40.030.100.280.500.831.95146_5_40.020.050.320.850.781.90156_6_40.000.000.110.350.922.65167_5_40.000.000.160.300.952.80177_6_40.020.050.240.450.932.25187_7_40.030.050.120.350.932.05198_8_40.000.000.250.950.952.60209_9_40.000.000.100.250.951.85219_9_50.050.150.150.200.931.702210_10_50.020.050.080.150.922.052310_10_80.000.000.030.100.961.602415_15_50.000.000.020.050.951.952515_15_100.000.000.010.050.961.55It can be seen from Table5, for the 25 examples to be tested in this paper, the proposed HEDA_VNS finds more and better nondominated solutions for 23 instances of the 25 problem instances in terms of R_N and N_N. Moreover, as the problem size increases, HEDA_VNS is more effective. This is because HEDA_VNS is designed based on the characteristic of the problem, and the advantages of HEDA_VNS are mainly reflected in the following three aspects:(1)
The solution generated by the PA rule in the initialization phase can better improve the quality of the initial solution.(2)
A sampling mechanism based on the nature of the problem is designed so that the jobs belonging to the same product can be selected with a higher probability, which can more clearly guide the algorithm to search in the high-quality solution area.(3)
Two local search strategies are designed to improve the performance of the algorithm. Among them, three different search methods are designed in the Local Search I to perform a detailed search on the noninferior solution high-quality regions to improve the efficiency of the solution, which can effectively avoid some invalid searches and better retain the original high-quality solution structure. Then, a variable neighborhood hybrid operation based on the speed set is designed in Local Search II to search for transportation speed and vehicle order, which can balance the two optimization goals while further improving the quality of the solution.


## 5.1. Experimental Settings and Evaluation Index

### 5.1.1. Experimental Settings

All test questions of 3sMISP_JBTEC are based on the structural of the three-stage integrated system. For test data, the number of jobs composed of each product and the number of procedures corresponding to the jobs are randomly generated in the interval of [2, 5] and [1, 3], respectively. The processing time of each job and the assembly time of each product are randomly generated in the interval of [20, 80] and [100, 200], respectively. The load of each job is randomly generated in the interval of [20, 50], and the unit energy consumption of the processing machine is randomly generated in the interval of [3, 5]. According to the literature [24], the parameters of vehicle-related are as follows: Cd=0.7, Cr=0.01, ρ=1.2041, A=3.912, and g=9.81. The distance of vehicle transportation is DisP−A=8000.In addition to the number of products and machines, the results of the test problems are also affected by the number of transport vehicles. Therefore, the test problems listed in this paper are expressed asP_M_T. All algorithms and test procedures are implemented by Delphi 2010 programming, and the operating system is WinXP.


### 5.1.2. Evaluation Index

In the comparison, two indexes are used to evaluate the algorithm [42]. There are R_NSj and N_NSj. R_NSj is used to evaluate the quality of the nondominated solutions (shown in equation (17)). When R_NSj=0, the solutions in Sj are all dominated by other solutions. Also, when R_NSj=1, the solutions in Sj are all nondominated solutions in S. N_NSj is the number of solutions in Sj which are not dominated by other solutions (shown in equation (18)). The larger the value of N_NSj, the greater the number of nondominated solutions. Obviously, R_NSj is the dominant ratio, which evaluates the overall quality of the algorithm to obtain nondominated solutions, and N_NSj is the number of dominants, which evaluates the ability of the algorithm to obtain nondominated solutions. There is a positive correlation between these two indicators, and the correlation coefficient is 1/Sj:(17)R_NSj=Sj−x∈Sj∃y∈S:y≺x|Sj,(18)N_NSj=|Sj−x∈Sj∃y∈S:y≺x.


## 5.1.1. Experimental Settings

All test questions of 3sMISP_JBTEC are based on the structural of the three-stage integrated system. For test data, the number of jobs composed of each product and the number of procedures corresponding to the jobs are randomly generated in the interval of [2, 5] and [1, 3], respectively. The processing time of each job and the assembly time of each product are randomly generated in the interval of [20, 80] and [100, 200], respectively. The load of each job is randomly generated in the interval of [20, 50], and the unit energy consumption of the processing machine is randomly generated in the interval of [3, 5]. According to the literature [24], the parameters of vehicle-related are as follows: Cd=0.7, Cr=0.01, ρ=1.2041, A=3.912, and g=9.81. The distance of vehicle transportation is DisP−A=8000.In addition to the number of products and machines, the results of the test problems are also affected by the number of transport vehicles. Therefore, the test problems listed in this paper are expressed asP_M_T. All algorithms and test procedures are implemented by Delphi 2010 programming, and the operating system is WinXP.


## 5.1.2. Evaluation Index

In the comparison, two indexes are used to evaluate the algorithm [42]. There are R_NSj and N_NSj. R_NSj is used to evaluate the quality of the nondominated solutions (shown in equation (17)). When R_NSj=0, the solutions in Sj are all dominated by other solutions. Also, when R_NSj=1, the solutions in Sj are all nondominated solutions in S. N_NSj is the number of solutions in Sj which are not dominated by other solutions (shown in equation (18)). The larger the value of N_NSj, the greater the number of nondominated solutions. Obviously, R_NSj is the dominant ratio, which evaluates the overall quality of the algorithm to obtain nondominated solutions, and N_NSj is the number of dominants, which evaluates the ability of the algorithm to obtain nondominated solutions. There is a positive correlation between these two indicators, and the correlation coefficient is 1/Sj:(17)R_NSj=Sj−x∈Sj∃y∈S:y≺x|Sj,(18)N_NSj=|Sj−x∈Sj∃y∈S:y≺x.


## 5.2. Key Parameter Setting and Influence of HEDA_VNS

In the section, the three key parameters of HEDA_VNS which are population size (popsize), iterative probability sampling parameters (η), and learning rate (γ) are analyzed by the Design of Experiment (DOE) method of medium-scale problems. On the basis of combining existing research, four levels of each parameter are determined (shown in Table 1); thereby, an orthogonal experimental table is established with a scale of L1643. The algorithm runs independently for each set of parameters for 10 medium-scale questions of 20 times, with 2×P×M×T seconds as the termination condition for each scale and the average value AVG of each scale under different parameter combinations of the algorithm as the evaluation index to determine the appropriate parameters combination. The results are shown in Table 2.Table 1
Parameter level.
ParameterLevel1234Popsize30405060η0.30.40.50.6γ0.10.20.30.4Table 2
Orthogonal table and average statistics.
Parameter combinationLevelAVG×10Popsizeηγ11110.50121220.44731330.39341440.29952120.37562230.49172340.38682410.29393130.607103240.583113310.412123420.286134140.456144210.486154320.363164430.368From the experimental results (shown in Table3 and Figure 6), it can be found that different parameter combinations have a greater impact on the performance of the algorithm. Based on the experimental analysis results, the best parameters popsize=50, η=0.4, and γ=0.3 are set in this paper, and further performance testing and comparison will be carried out based on this parameter setting.Table 3
The response value of parameters.
LevelPopsizeηγ10.4100.4850.42320.3860.5020.36830.4720.3890.46540.4190.3120.431Figure 6
The level trend of the influence of each parameter on the algorithm performance.
(a)(b)(c)


## 5.3. Analysis of the Results of Energy Consumption and Makespan under a Certain Problem Scale

In this section, HEDA_VNS is used to solve the 3sMISP_JBTEC with a problem scale of (3_3_2). The scale of the problem can be described as follows: 3 heterogeneous parallel machines in the processing stage, 2 vehicles with the same load in the transportation stage, and one machine in the assembly stage. 3 products are required to be processed and assembled during the three stages. The product composition is shown in Figure7. The 3 products are assembled from multiple jobs. Each job has multiple processes, and each process can be processed on multiple machines. The vehicle’s return to no-load speed is vc=40. The data of each stage of the product are shown in Table 4.Figure 7
The product composition of the problem scale of (3_3_2).Table 4
Data at each stage of the problem scale of (3_3_2).
P1P2P3J1J2J3J4J5J6J7J8J9Pijkm127—99———11691—1137554——87————8098—m225——39—7510111062———31112—59—————80m377107—59285756—3326101—5060——979783———Rjkm15593624110166398459m28875877010147803749m32555696064881147230Vj33482552636312533Az16112899Figure8 shows the noninferior solution set of the problem, and other scales are similar. It can be seen from Figure 8 that all the solutions are independent of each other due to conflicts and constraints between the makespan and total energy consumption (TEC). The conflicts and containments are embodied in both machine processing stage and vehicle transportation stage. The solution at point A in Figure 8 shows that it has a large span in the machine processing stage, but it has close connection between the stages, and all vehicles are transported at high speed. Meanwhile, the makespan is relatively smallest, but energy consumption is relatively highest. On the one hand, high-speed transportation can reduce the transportation time and the accumulation of intermediate inventory and effectively prevent delays in the manufacturing process. On the other hand, high-speed transportation may cause that jobs arrive early for assembly, which is prone to bottlenecks and a backlog of finished products. Therefore, it is not a blind pursuit of makespan, and it is necessary to limit the maximum speed level of transportation vehicles. The solution at point B in Figure 8 represents that the machining span is small, but the connection between the stages is not tight enough, and all vehicles are transported at low speed. Meanwhile, the makespan is relatively largest, but energy consumption is relatively lowest. In this case, although the processing stage is compact, the delivery delay time and the intermediate inventory level will be at the highest level, and the delivery of the finished product may be delayed. It can be seen that although it is the same problem, the noninferior solution will be affected due to different vehicle transportation speeds. Hence, enterprise managers need to make decisions based on the company itself and related policies, taking into account factors such as order time and demand; for example, the selected solution will be different if the same order is completed in a shorter planning period and the selected solution is completed in a longer planning period, but under normal circumstances, decision makers generally choose point C because the makespan and energy consumption are at a normal and acceptable level.Figure 8
The noninferior solution set of the problem scale of (3_3_2).


## 5.4. Comparison of Experimental Results of HEDA_VNS with Other Intelligent Algorithms

In order to further verify the effectiveness of HEDA_VNS compared with HMOBSA [19] and GA-GSO-GTHS [23], a large number of experiments can be carried out by means of the generated different types of problems. HMOBSA is an effective multiobjective backtracking algorithm. The performance of HMOBSA is superior to the well-known multiobjective algorithm (nondominated sorting genetic algorithm, NSGAII) and MOEA/D in solving energy consumption problems. The turn off/on strategy is also used when calculating energy consumption in the processing stage. GA-GSO-GTHS is a multiobjective hybrid optimization algorithm with strategy. The performance of GA-GSO-GTHS is better than most of the latest multiobjective optimization algorithms that are widely used in scheduling problems. It is effective in solving production energy consumption problems that consider transportation. In addition, the parameters of HMOBSA are set as follows: popsize=50, crossover probability pc=0.9, and mutation probability pm=0.1. The parameters of GA-GSO-GTHS are set as follows: popsize=100, pc=0.6, pm=0.05, step size s=5, maximum perceptual radius rs=20, volatility coefficient ρ=0.4, enhancement factor γ=0.6, perceptual radius scaling factor β=0.08, nt=5, and l0=5. The parameters selected by the three algorithms are all good parameters. Besides, HEDA_VNS runs for 200 generations, and other algorithms run the same time as HEDA_VNS. The comparative results of the three algorithms to solve 3sMISP_JBTEC under the randomly generated speed in vmin,vmax are listed in Table 5. Among them, R_N and N_N, respectively, represent the index values of the evaluation solutions corresponding to the three algorithms. The data in Table 5 are the average values of the algorithm after 20 runs.Table 5
Comparison of HEDA_VNS with HMOBSA and GA-GSO-GTHS.
No.P_M_THMOBSAGA-GSO-GTHSHEDA_VNSR_NN_NR_NN_NR_NN_N012_3_20.200.500.551.300.471.25023_2_20.050.100.500.970.521.30033_3_20.020.050.351.350.802.15044_4_20.050.300.751.550.601.50054_5_30.070.020.351.150.681.80065_3_30.030.010.270.450.811.60075_4_30.050.150.520.850.751.55085_5_30.150.350.130.650.801.95095_6_30.020.050.150.350.922.05106_4_30.000.000.130.350.952.20116_5_30.050.100.270.500.862.05126_6_30.020.050.220.650.902.20136_4_40.030.100.280.500.831.95146_5_40.020.050.320.850.781.90156_6_40.000.000.110.350.922.65167_5_40.000.000.160.300.952.80177_6_40.020.050.240.450.932.25187_7_40.030.050.120.350.932.05198_8_40.000.000.250.950.952.60209_9_40.000.000.100.250.951.85219_9_50.050.150.150.200.931.702210_10_50.020.050.080.150.922.052310_10_80.000.000.030.100.961.602415_15_50.000.000.020.050.951.952515_15_100.000.000.010.050.961.55It can be seen from Table5, for the 25 examples to be tested in this paper, the proposed HEDA_VNS finds more and better nondominated solutions for 23 instances of the 25 problem instances in terms of R_N and N_N. Moreover, as the problem size increases, HEDA_VNS is more effective. This is because HEDA_VNS is designed based on the characteristic of the problem, and the advantages of HEDA_VNS are mainly reflected in the following three aspects:(1)
The solution generated by the PA rule in the initialization phase can better improve the quality of the initial solution.(2)
A sampling mechanism based on the nature of the problem is designed so that the jobs belonging to the same product can be selected with a higher probability, which can more clearly guide the algorithm to search in the high-quality solution area.(3)
Two local search strategies are designed to improve the performance of the algorithm. Among them, three different search methods are designed in the Local Search I to perform a detailed search on the noninferior solution high-quality regions to improve the efficiency of the solution, which can effectively avoid some invalid searches and better retain the original high-quality solution structure. Then, a variable neighborhood hybrid operation based on the speed set is designed in Local Search II to search for transportation speed and vehicle order, which can balance the two optimization goals while further improving the quality of the solution.


## 6. Conclusion

This paper aims at solving the three-stage multiobjective integrated scheduling problem considering the energy consumption (3sMISP_JBTEC) of processing-transport-assembly and studying the multiobjective problem modeling and solution algorithm with makespan and energy consumption. In terms of modeling, a mathematical model of multiobjective optimization problems is established. Then, the improved energy-saving strategy is adopted to save energy and extend the life of the machine in the processing and assembly stages. Meanwhile, the impact of speed on energy consumption is considered in the transportation stage. For solving the problem, the HEDA_VNS is designed to solve 3sMISP_JBTEC based on the characteristics of the problem. There is a conflict between the makespan and the energy consumption through the results of testing same-scale problems, and decision-makers need to make decisions based on different actual conditions. Moreover, HEDA_VNS is compared with other algorithms on large-scale problems, and comparative simulations show the efficiency of the proposed HEDA_VNS. This obtained result can provide a reference for the implementation of intelligent production in the assembly manufacturing industry.



---

*Source: 5558949-2021-06-01.xml*