# Bi-Objective Re-Entrant Hybrid Flow Shop Scheduling considering Energy Consumption Cost under Time-of-Use Electricity Tariffs

Authors: Kaifeng Geng; Chunming Ye; Zhen hua Dai; Li Liu
Journal: Complexity
 (2020)

---

## Abstract

Re-entrant hybrid flow shop scheduling problem (RHFSP) is widely used in industries. However, little attention is paid to energy consumption cost with the raise of green manufacturing concept. This paper proposes an improved multiobjective ant lion optimization (IMOALO) algorithm to solve the RHFSP with the objectives of minimizing the makespan and energy consumption cost under Time-of-Use (TOU) electricity tariffs. A right-shift operation is then used to adjust the starting time of operations by avoiding the period of high electricity price to reduce the energy consumption cost as far as possible. The experimental results show that IMOALO algorithm is superior to multiobjective ant lion optimization (MOALO) algorithm, NSGA-II, and MOPSO in terms of the convergence, dominance, and diversity of nondominated solutions. The proposed model can make enterprises avoid high price period reasonably, transfer power load, and reduce the energy consumption cost effectively. Meanwhile, parameter analysis indicates that the period of TOU electricity tariffs and energy efficiency of machines have great impact on the scheduling results.


---

## Body

## 1. Introduction

Re-entrant hybrid flow shop scheduling problem (RHFSP) is a combination of classic hybrid flow shop scheduling problem and re-entrant scheduling problem. It means that all jobs have the same processing path among the stages and go back and forth in the same order many times. It is widely used in some special industries, such as thin-film transistor-liquid crystal display (TFT-LCD) panel manufacturing, printed circuit board (PCB), and semiconductor wafer manufacturing. With the rising energy prices and the increasingly serious environmental problems, the issue of reducing energy consumption cost has become a focus for many factory managers. Recently, many power energy suppliers have begun to implement a so-called Time-of-Use (TOU) electricity tariffs, such pricing mechanism represents a huge opportunity to reduce costs for consumers by shifting electricity usage from on-peak period to other period. RHFSP is a typical NP-hard problem [1], which is difficult to solve with exact algorithms, so it will be of academic significance and engineering application value to develop efficient intelligent optimization algorithms for the RHFSP under TOU electricity tariffs.Since Graves et al. [2] first proposed reentrant scheduling problem (RSP) in 1983, many scholars have studied this field. Bertel and Billaut [3] applied a genetic algorithm for the RHFSP aiming at minimizing the weighted number of delayed jobs. Chen et al. [4] proposed a hybrid tabu search algorithm for the RHFSP with the objective of minimizing the makespan. Choi and Kim [5] proposed several heuristic algorithms for RHFSP, such as improved Nawaz Enscore and Ham (NEH) algorithm, aiming at minimizing the makespan. Kim and Lee [6] studied the RHFSP considering unrelated parallel machines with the objective of minimizing the makespan and total tardiness. In practice, the total tardiness objective is treated as constraints, so the problem is converted into single objective. El-Khouly et al. [7] used Lagrange decomposition to optimize the RSP aiming at minimizing the total tardiness. Wu et al. [8] studied RSP with learning effects, aiming at minimizing the makespan. Cho et al. [9] proposed a genetic algorithm for the RHFSP in order to minimise the makespan and total tardiness. Ying et al. [10] used an iterative Pareto greedy algorithm for the bi-objective RHFSP based on the research in [9]. Shen et al. [11, 12] applied an improved teaching and learning optimization algorithm and a Pareto-based discrete harmony search algorithm to solve the bi-objective RHFSP. Cheng and Lei [13] studied an improved imperialist competition algorithm for the RSP in order to minimise the makespan and total tardiness. In conclusion, production decision makers assume that electricity prices are constant in the production cycle, so they are only interested in time-related objectives, such as maximum tardiness, total tardiness, and makespan.With the rising international energy costs and the increasingly serious environmental problems in recent years, it is particularly important to achieve green and sustainable development in the manufacturing sector. Energy consumption in the industrial sector is approximately 50% of the total energy consumption [14]. In Germany, the manufacturing enterprises consume around more than 47% of the total energy consumption. In China, the manufacturing industries are responsible for 50% of the national electricity energy each year [15]. Therefore, the increasing energy price and the current sustainable development trend bring new pressure to manufacturing enterprises. It must be noted, however, that either adopting advanced production technology or purchasing new equipment needs a lot of investment. Under TOU electricity tariffs, without investing a large amount of money in equipment and technology, it can reduce the energy costs just by adjusting production tasks reasonably, and the benefits could be enjoyed easily by majority of SMEs. Zhang et al. [16] proposed an integer programming model to solve the flow shop scheduling problem under TOU electricity tariffs without affecting the production efficiency in order to minimise the carbon dioxide emissions and electricity cost. Luo et al. [17] addressed the multiobjective ant colony optimization algorithm to solve the hybrid flow shop scheduling problem with unrelated parallel machines under TOU electricity tariffs aiming at minimizing the makespan and energy consumption cost. Wang and Li [18] studied the manufacturing model considering both energy consumption and demand under TOU electricity tariffs. Fang et al. [19] used a mixed integer programming method for the flow shop scheduling problem with peak power constraints. Moon and Park [20] proposed two discrete-time mathematical models for the flexible job shop scheduling problem under TOU electricity tariffs with the objective of weighted sum of maximum completion time and power cost. Che et al. [21] proposed the mixed integer programming model for the single machine scheduling problem with the objective of minimizing the electricity cost under TOU electricity tariffs. Mikhaylidi et al. [22] studied the production and operation scheduling problem of rechargeable batteries under TOU electricity tariffs using a dynamic programming algorithm, aiming at minimizing total power consumption and delaying penalty cost. Shrouf et al. [23] proposed a discrete-time integer programming model and genetic algorithm to solve the single machine scheduling problem with power outage mechanism under TOU electricity tariffs. The objective is to minimise the total power cost. Gong et al. [24] modeled the same problem with arbitrary job processing sequence and demonstrated how to reduce power cost under real-time price, TOU electricity price, and critical peak price schemes through a practical case of a surface grinder. In addition, other scholars have also studied the scheduling problems under TOU electricity tariffs in different fields (e.g., Tan et al. [25]; Castro et al. [26]; Sharma et al. [27]; Tan and Liu [28]). Although some achievements have been made in this field, the research on green job shop scheduling under TOU electricity tariffs is still immature, and the study on RHFSP with unrelated parallel machines considering energy consumption cost is even less. This paper proposes the improved multiobjective ant lion optimization (IMOALO) algorithm with right-shift operation to approximate the Pareto optimal solutions for RHFSP under TOU electricity tariffs with the objective of minimizing the makespan and energy consumption cost. On the premise of not affecting the production efficiency, according to the characteristics of TOU electricity tariffs, the operations are arranged in the period with low electricity price as far as possible. Through this method, enterprises can reduce a large number of energy consumption cost and improve the competitiveness of enterprises, so as to realize the green and sustainable development of economy.The rest of the paper is organized as follows: the RHFSP is described and the mathematical model is established in Section2. In Section 3, the proposed IMOALO algorithm is introduced in detail. In Section 4, the performance comparisons with other three algorithms are shown. The parameter analysis of the period of TOU electricity tariffs and energy efficiency of machines are studied in Section 5. Finally, some conclusions and future work are given in Section 6.


## 2. Problem Statement and Mathematical Model

### 2.1. Problem Statement

In this paper, the RHFSP with unrelated parallel machine is studied, which can be described as follows:n jobs need to be processed in s serial stages. There is at least one stage, in which the number of unrelated parallel machines is more than one. Each job can be processed on any machine at the corresponding stage, and part of jobs may visit some stages more than once, as shown in Figure 1. The objective is to allocate all jobs to the machines and fix the starting and ending time for each operation.Figure 1
Diagram of RHFSP with unrelated parallel machines.Additionally, the following assumptions are made: All machines and jobs are ready at zero time. At any time, each machine can process at most one job, and each job can only be processed by one machine. The number of jobs and the processing time of all operations are given in advance. The number of stages and the number of unrelated parallel machines at each stage are known in advance. The power and speed of each machine are given in advance. All operations of each job have sequence constraints, and all jobs have no influence on each other. The power and speed of unrelated parallel machines at each stage are different. The total energy consumption of each job is independent of the machine chosen. Preemption is not allowed, and once the job is processed, it cannot be interrupted. The buffer capacity between any two continuous stages is infinite, regardless of machine failure and adjustment time.


### 2.2. Mathematical Model

The symbols involved in the model and their implications are as follows:n: number of jobsj: index for jobs, j=1,2,…,ns: number of stagesi: index for stages, i=1,2,…,smi: number of unrelated parallel machines at the stage il: index for machines at the stage i, l=1,2,…,miMtotal: number of machines at all stages, Mtotal=m1+m2+⋯+msq: index for machinesNj: number of operations for job jk: index of operations for job j, k=1,2,…,NjOjk: the k−th operation of job jPjk: standard processing time of OjkUi: set of operations processed at the stage iSjk: starting time of OjkEjk: ending time of OjkCj: completion time of job jM: a large numberMil: the l−th machine at the stage iVil: speed of Mil, if Ojk is arranged on the Mil, the actual processing time is Pjk/VilPWq: power of machine qSWq: idle power of machine qft: electricity price functionyqt=1,if the machineqis working at timet,0,otherwise,∀qrijkl=1,ifOjkis processed on theMil,0,otherwise,∀i,j,k,lZjkj′k′=1,ifOjkprocedesOj′k′,0,otherwise,∀j<j′,k,k′On the basis of literature studies [10, 29], a bi-objective RHFSP mathematical model is proposed in this paper. Formulas (1) and (2) represent the two objective functions. Constraint (3) implies that the starting time of the operation Ojk+1 is not earlier than the ending time of Ojk. Constraint (4) ensures that each operation can only be processed on one machine at the corresponding stage. Constraints (5)–(7) ensure that each machine processes at most one operation simultaneously. Constraints (8) and (9) specify the starting and ending time of Ojk. Constraints (10) and (11) describe the maximum completion time.The first objective of this paper is to minimise the makespan (maximum completion time), as shown in the following formula:(1)f1=Cmax=maxCj.Here,Cmax denotes the makespan.The second objective of this paper is to minimize the total energy consumption cost, which mainly includes the energy consumption cost in machine processing state and in idle state, as shown in the following formula:(2)f2=TECmin=∑t=0Cmax∑q=1MtotalPWqyqt+SWq1−yqtft.Here,TECmin denotes the total energy consumption cost.The two objectives are subject to(3)∑l=1mirijklSjk+PjkVil≤∑l=1mi′ri′jk+1lSjk+1,∀i,i′,j,k,(4)∑l=1mirijkl=1,∀i,j,Ojk∈Ui,(5)M2−rijkl−rij′k′l+M1−Zjkj′k′+Sj′k′−Sjk≥PjkVil,∀i,j<j′,l,Ojk∈Ui,Oj′k′∈Ui,(6)M2−rijkl−rij′k′l+MZjkj′k′+Sjk−Sj′k′≥Pj′k′Vi′l′,∀i,j<j′,l,Ojk∈Ui,Oj′k′∈Ui,(7)M2−rijkl−rijk′l+Sjk′−Sjk≥PjkVil,∀i,k<k′,l,Ojk∈Ui,Ojk′∈Ui,(8)Sjk≥0,∀j,k,(9)Ejk=Sjk+PjkVil,∀j,k,(10)Cj=∑i=1s∑l=1mirijNjlSjNj+PjNjVil,∀j,(11)Cj≤Cmax,∀j.


## 2.1. Problem Statement

In this paper, the RHFSP with unrelated parallel machine is studied, which can be described as follows:n jobs need to be processed in s serial stages. There is at least one stage, in which the number of unrelated parallel machines is more than one. Each job can be processed on any machine at the corresponding stage, and part of jobs may visit some stages more than once, as shown in Figure 1. The objective is to allocate all jobs to the machines and fix the starting and ending time for each operation.Figure 1
Diagram of RHFSP with unrelated parallel machines.Additionally, the following assumptions are made: All machines and jobs are ready at zero time. At any time, each machine can process at most one job, and each job can only be processed by one machine. The number of jobs and the processing time of all operations are given in advance. The number of stages and the number of unrelated parallel machines at each stage are known in advance. The power and speed of each machine are given in advance. All operations of each job have sequence constraints, and all jobs have no influence on each other. The power and speed of unrelated parallel machines at each stage are different. The total energy consumption of each job is independent of the machine chosen. Preemption is not allowed, and once the job is processed, it cannot be interrupted. The buffer capacity between any two continuous stages is infinite, regardless of machine failure and adjustment time.


## 2.2. Mathematical Model

The symbols involved in the model and their implications are as follows:n: number of jobsj: index for jobs, j=1,2,…,ns: number of stagesi: index for stages, i=1,2,…,smi: number of unrelated parallel machines at the stage il: index for machines at the stage i, l=1,2,…,miMtotal: number of machines at all stages, Mtotal=m1+m2+⋯+msq: index for machinesNj: number of operations for job jk: index of operations for job j, k=1,2,…,NjOjk: the k−th operation of job jPjk: standard processing time of OjkUi: set of operations processed at the stage iSjk: starting time of OjkEjk: ending time of OjkCj: completion time of job jM: a large numberMil: the l−th machine at the stage iVil: speed of Mil, if Ojk is arranged on the Mil, the actual processing time is Pjk/VilPWq: power of machine qSWq: idle power of machine qft: electricity price functionyqt=1,if the machineqis working at timet,0,otherwise,∀qrijkl=1,ifOjkis processed on theMil,0,otherwise,∀i,j,k,lZjkj′k′=1,ifOjkprocedesOj′k′,0,otherwise,∀j<j′,k,k′On the basis of literature studies [10, 29], a bi-objective RHFSP mathematical model is proposed in this paper. Formulas (1) and (2) represent the two objective functions. Constraint (3) implies that the starting time of the operation Ojk+1 is not earlier than the ending time of Ojk. Constraint (4) ensures that each operation can only be processed on one machine at the corresponding stage. Constraints (5)–(7) ensure that each machine processes at most one operation simultaneously. Constraints (8) and (9) specify the starting and ending time of Ojk. Constraints (10) and (11) describe the maximum completion time.The first objective of this paper is to minimise the makespan (maximum completion time), as shown in the following formula:(1)f1=Cmax=maxCj.Here,Cmax denotes the makespan.The second objective of this paper is to minimize the total energy consumption cost, which mainly includes the energy consumption cost in machine processing state and in idle state, as shown in the following formula:(2)f2=TECmin=∑t=0Cmax∑q=1MtotalPWqyqt+SWq1−yqtft.Here,TECmin denotes the total energy consumption cost.The two objectives are subject to(3)∑l=1mirijklSjk+PjkVil≤∑l=1mi′ri′jk+1lSjk+1,∀i,i′,j,k,(4)∑l=1mirijkl=1,∀i,j,Ojk∈Ui,(5)M2−rijkl−rij′k′l+M1−Zjkj′k′+Sj′k′−Sjk≥PjkVil,∀i,j<j′,l,Ojk∈Ui,Oj′k′∈Ui,(6)M2−rijkl−rij′k′l+MZjkj′k′+Sjk−Sj′k′≥Pj′k′Vi′l′,∀i,j<j′,l,Ojk∈Ui,Oj′k′∈Ui,(7)M2−rijkl−rijk′l+Sjk′−Sjk≥PjkVil,∀i,k<k′,l,Ojk∈Ui,Ojk′∈Ui,(8)Sjk≥0,∀j,k,(9)Ejk=Sjk+PjkVil,∀j,k,(10)Cj=∑i=1s∑l=1mirijNjlSjNj+PjNjVil,∀j,(11)Cj≤Cmax,∀j.


## 3. The Proposed Improved Multiobjective Ant Lion Optimization Algorithm

“No Free Lunch Theorem” [30] points out that there is no algorithm that can solve all optimization problems. In this paper, we use the ant lion optimization (ALO) algorithm to solve the RHFSP. The ALO algorithm is a new metaheuristic algorithm proposed by Australian scholars Mirjalili et al. in 2014 inspired by ant lion hunting behavior in nature [31]. The locations of ants and ant lions represent the solutions of the optimization problem. Ants obtain the global optimal solution by random walking around the ant lions and learning from the elite ant lions. In 2016, Mirjalili et al. proposed a multiobjective ant lion optimization (MOALO) algorithm [32], of which the search mechanism is very similar to ALO. At present, the ALO algorithm has been widely used in power grid and power optimization [33–35], optimal power flow optimization [36], link state routing protocol optimization [37], feature selection [38], and integrated process planning and scheduling [39]. To get better optimization results, the MOALO algorithm is improved from three aspects: (1) If the initial population is generated by a completely random method, its solutions may be concentrated in a local range, which is not conducive to convergence to the global optimal solution. This paper adopted the Latin hypercube sampling technology to initialize the population. (2) The adaptive elite ant lion updating strategy is used to improve the exploring ability in the early stage and the exploiting ability in the later stage of MOALO. (3) The local search ability of MOALO is improved by two neighbourhood structures. The flowchart for the proposed algorithm is shown in Figure 2.Figure 2
The flowchart for the proposed IMOALO algorithm.


### 3.1. Encoding and Decoding

ALO algorithm is mainly used to solve continuous optimization problems, but rarely to deal with combination optimization problems. Random key ascending sequence coding is used in this paper to construct the mapping from individual position to job sequencing and then using the decoding method in [9, 10] to decode it. Finally, scheduling schemes are generated according to various constraints. The mathematical model contains a large number of 0-1 variables. If the minimum time unit is too small, it will seriously affect the calculation speed of the model. If the minimum time unit is too large, the error will be relatively large. In this paper, the minimum time unit is set to one tenth of an hour. The decoding process is detailed as follows:Step 1: select the first genei (i.e., job i) from the chromosome, arrange all the operations of job i on the machine that can finish it as early as possible, and record the starting time and ending time of each operationStep 2: select the next genei′ and arrange machines for it and obtain the available machine set MS for operation Oi′jStep 3: select machineq from MS, obtain all idle time periods MStart,MEnd of machine q, and traverse all idle time periods of machine q, and the earliest starting time ti′j of operation Oi′j is shown in the following formula:(12)tij=maxCi′j−1,MStart.Step 4: find a suitable insertion point forOi′j according to formula (13). If no idle time period satisfying the conditions is found, set the starting time of operation Oi′j to ti′j=LMq, where LMq represents the ending time of the last operation of machine q:(13)ti′j+Pi′j≤MEnd.Step 5: traverse all machines inMS, repeat step 3 and step 4 to select the minimum ti′j:Step 6: calculate the ending time of operationOi′j, as shown in the following formula:(14)Ci′j=ti′j+Pi′j.Step 7: repeat step 2–step 6 until all genes in the chromosome have been processed.Taking an example, in which there are 3 stages and 4 jobs. The number of unrelated identical parallel machines is 3, 2, and 2 at each stage, respectively. The standard processing time of each operation on the corresponding stage is shown in Table1. In addition, the power and speed of machines at each stage are different, as shown in Table 2. For example, at stage 1, the processing speed and power of M1,1, M2,1, M3,1 are 1, 2, and 3 and 10, 20, and 30, respectively. The idle power of all machines is 2.Table 1
Processing times of the four-job and three-stage example (hour).
Processing timesPjk
First pass
re-entrant 1
re-entrant 2
Stage 1
Stage 2
Stage 3
Stage 1
Stage 2
Stage 3
Stage 1
Stage 2
Stage 3
Job 1
2
2
1
0
2
1
0
1
2
Job 2
1
3
0
0
2
1
0
2
1
Job 3
3
1
2
2
1
0
0
0
0
Job 4
2
1
1
2
0
0
3
1
0Table 2
Speed and power settings of all machines.
Stage
Machine
Power
Speed
Idle powerSW
Stage 1
M
1,1
10
1
2
M
2,1
20
2
M
3,1
30
3
Stage 2
M
1,2
10
1
M
2,2
20
2
Stage 3
M
1,3
10
1
M
2,3
20
2In this paper, according to [14], TOU electricity tariffs function (yuan/Kwh) is as follows:(15)ft=1.15,15≤t<20,0.75,7≤t<15,20≤t<22,0.42,0≤t<7,22≤t<24.If the processing timePjk=0, it means that the job is not processed in a certain pass. Using random key coding, the permutation of all jobs represents each individual, and each element in the individual is selected in [0, 1] arbitrarily. The corresponding permutation can be obtained by ascending the ranking of each element. To get a feasible schedule, the decoding method is used to determine the processing order of all jobs at each stage and a suitable machine is assigned for each operation. Then, the starting and ending time of each operation can be obtained. At last, the objective function values can be calculated. Taking the individual [0.8147, 0.1270, 0.9058, 0.9134] as an example, the corresponding permutation is 2-1-3-4 according to the ascending order. The detailed process of decoding is as follows. Firstly, all the operations of job 2 are arranged on the machine that can finish it at the earliest time. Then, each operation of job 1 will be arranged on the machine that can finish it as early as possible. If the ending time of a certain operation of the job 2 is smaller than the starting time of the arranged operation of job 4 on a certain machine, the operation of the job 2 will be arranged before it, otherwise, it will be arranged behind it. By analogy, all operations of job 3 and 4 are arranged on the right machines, the Gantt charts are shown in Figure 3. Then, Cmax = 7.8333 hour and TECmin = 184.1634 yuan are obtained.Figure 3
Gantt charts. (a) Scheduling job 2. (b) Scheduling job 1. (c) Scheduling job 3. (d) Scheduling job 4.
(a)
(b)
(c)
(d)


### 3.2. Population Initialization

Generally, the region of the optimal solution is difficult to predict, and the solution space characteristics of the initial population can represent the information of all individuals to a certain extent, so the distribution performance of the initial population directly affects the convergence of the algorithm. In this paper, Latin hypercube sampling technique is used to initialize the population.Assuming thatm samples need to be extracted in n-dimensional vector space, the specific steps of Latin hypercube sampling are as follows:(1)
Each dimension vector is divided intom intervals and they do not overlap with each other(2)
The point is randomly selected in all intervals of each dimension(3)
The selected points in (2) are randomly extracted from each dimension to form a new vector


### 3.3. Adaptive Elite Ant Lion Updating Strategy

According to the elite strategy, the ALO algorithm updates the ant position according to the following formula:(16)Antjt=12RAt+REt.Among them,Antjt is the current position of ant and RAt and REt are ants selected by the roulette wheel selection and ants around the elite ant lion in generation t, respectively. However, in general, the initial stage of the algorithm should have a strong exploring ability, the update step is larger, and the later stage of the algorithm should have a strong exploiting ability, the update step is smaller, so the adaptive elite ant lion update strategy is introduced to update the ant position in this paper, as shown in the following formula:(17)Antjt=ftRAt+1−ftREt,where ft=1−t/T2 is the adaptive coefficient and T and t represent the maximum number and current number of iterations. At the beginning of iterations, ft is about 1 and the value of Antjt is mainly determined by RAt, which can ensure that the algorithm has strong exploratory ability and global search ability in the early stage. As the number of iterations increases, ft gets smaller and smaller. At the later stage of iterations, the value of Antjt is mainly determined by REt, and ants mainly walk around elite ant lions, which ensures that the algorithm has strong exploiting ability in the later stage. In summary, ants can choose different walking modes adaptively, which help to improve the exploring and exploiting ability of the algorithm.


### 3.4. Neighbourhood Structure

In this paper, insertion neighbourhood and exchange neighbourhood are used to improve the local search ability of MOALO. Each individual has a 50% probability to perform insertion or exchange operations, respectively.Insertion neighbourhood: first of all, a new sequenceπ with n−1 jobs is obtained by deleting one job from the individual randomly. Then, the job j is inserted into n−1 intervals of sequence π, and the objective function values fitnessi of n−1 new individuals are calculated, i∈1,n−1. The corresponding objective function values of the original sequence is fitnessn. Then, the dominance is judged and the optimal solution best is assumed to fitness1. If fitnessi≺best, then best=fitnessi, and so on; the individual corresponding to best is taken as the optimal insertion sequence, as shown in Figure 4(a).Figure 4
(a) Example of insertion neighbourhood. (b) Example of exchange neighbourhood.
(a)
(b)Exchange neighbourhood: firstly, a jobj is randomly selected from the individual, and the job j is exchanged with the remaining n−1 jobs, respectively. Then, the objective function values fitnessi of the individual after exchange is calculated, i∈1,n−1, and the corresponding objective function values of the original sequence is fitnessn. Finally, the dominance is judged and the optimal solution best is assumed to fitness1. If fitnessi≺best, then best=fitnessi, and so on; the individual corresponding to best is taken as the optimal exchange sequence, as shown in Figure 4(b).


### 3.5. Right-Shift Operation Based on TOU Electricity Tariffs

Under TOU electricity tariffs, the RHFSP considering energy consumption cost should not only select the appropriate machines for all jobs but also determine the starting time and ending time for each operation reasonably. Due to the complexity of RHFSP, it is inevitable that there will be waiting time for machines and jobs, especially in the case of large number of jobs, so the waiting time can be fully utilized to adjust the processing time of each operation. A right-shift operation is then added in the decoding process, and the time to minimise the energy consumption cost of the operation is selected from the possible starting time as the appropriate starting time. If there are more than one qualified starting time, the maximum value is chosen as the starting time to ensure that there is enough right-shift space. The right-shift operation does not change the makespan and job sequence but helps to reduce the energy consumption cost. Due to the limitation of the decoding method, each operation is decoded according to the earliest ending time, so there is no space to move left. It can be seen that the adjustment of the latter operation will affect the adjustment of the former one, so the right-shift operation should follow the rules from back to front in turn. Firstly, all operations are arranged in a nonincremental order according to the ending time, and then the right-shift operation is carried out in this order. Taking the operationOjk as an example, the detailed adjustment process is as follows.Assuming that the operationOjk is processed on machine Mil, the index of machine Mil is q and the adjustment range of Sjk is t∈tmin,tmax. So without affecting the production efficiency, the job j can choose any time in this range as the starting time.(1)
Suppose thatOjk is the last operation on machine Mil and k=Nj. If Ejk = Cmax, then the operation does not need to move right. If Ejk<Cmax, then tmin=Sjk, tmax=Cmax−Pjk/Vil, and a new idle period will be added in this case; the adjustment range is shown in Figure 5. Therefore, the additional idle energy consumption cost should be considered. The starting time of operation Ojk after adjustment is(18)Sjk′=argmintmin≤t<tmax∑x=tx+Pjk/VilPWqfx+∑x=Sjkx=tSWqfx.(2)
Suppose thatOjk is the last operation of job jk=Nj, but not the last operation of machine Mil. If the next operation on machine Mil is Oj′k′, then tmin=Sjk and tmax=Sj′k′−Pjk/Vil; the adjustment range is shown in Figure 6. The starting time of operation Ojk after adjustment is(19)Sjk′=argmintmin≤t<tmax∑x=tx+Pjk/VilPWqfx.(3)
Suppose thatOjk is the last operation on machine Mil, job j has the next operation Ojk+1 and Ojk+1 is processed on machine Mi′l′. The adjustment range is shown in Figure 7; meanwhile, tmin=Sjk and tmax=Sjk+1−Pjk/Vil. The starting time of operation Ojk after adjustment is(20)Sjk′=argmintmin≤t<tmax∑x=tx+Pjk/VilPWqfx.(4)
In other cases,tmin=Sjk and tmax=minSj′k′,Sjk+1−Pjk/Vil. If Sj′k′≤Sjk+1, the adjustment range is shown in Figure 8. If Sj′k′>Sjk+1, the adjustment range is shown in Figure 9. Adjustment of starting time of process Ojk can be divided into two situations:(a)
IfOjk is the first operation on Mil, part of idle time will be removed, so the removal idle energy consumption cost should be considered, then(21)Sjk′=argmintmin≤t<tmax∑x=tx+Pjk/VilPWqfx−∑x=Sjkx=tSWqfx.(b)
Otherwise,(22)Sjk′=argmintmin≤t<tmax∑x=tx+Pjk/VilPWqfx.Figure 5
Adjustment diagram whenOjk is the last operation on machine Mil and k=Nj.Figure 6
Adjustment diagram whenOjk is not the last operation on machine Mil and k=Nj.Figure 7
Adjustment diagram whenOjk is not the last operation on machine Mil and k≠Nj.Figure 8
Adjustment diagram whenSj′k′≤Sjk+1.Figure 9
Adjustment diagram whenSj′k′>Sjk+1.


## 3.1. Encoding and Decoding

ALO algorithm is mainly used to solve continuous optimization problems, but rarely to deal with combination optimization problems. Random key ascending sequence coding is used in this paper to construct the mapping from individual position to job sequencing and then using the decoding method in [9, 10] to decode it. Finally, scheduling schemes are generated according to various constraints. The mathematical model contains a large number of 0-1 variables. If the minimum time unit is too small, it will seriously affect the calculation speed of the model. If the minimum time unit is too large, the error will be relatively large. In this paper, the minimum time unit is set to one tenth of an hour. The decoding process is detailed as follows:Step 1: select the first genei (i.e., job i) from the chromosome, arrange all the operations of job i on the machine that can finish it as early as possible, and record the starting time and ending time of each operationStep 2: select the next genei′ and arrange machines for it and obtain the available machine set MS for operation Oi′jStep 3: select machineq from MS, obtain all idle time periods MStart,MEnd of machine q, and traverse all idle time periods of machine q, and the earliest starting time ti′j of operation Oi′j is shown in the following formula:(12)tij=maxCi′j−1,MStart.Step 4: find a suitable insertion point forOi′j according to formula (13). If no idle time period satisfying the conditions is found, set the starting time of operation Oi′j to ti′j=LMq, where LMq represents the ending time of the last operation of machine q:(13)ti′j+Pi′j≤MEnd.Step 5: traverse all machines inMS, repeat step 3 and step 4 to select the minimum ti′j:Step 6: calculate the ending time of operationOi′j, as shown in the following formula:(14)Ci′j=ti′j+Pi′j.Step 7: repeat step 2–step 6 until all genes in the chromosome have been processed.Taking an example, in which there are 3 stages and 4 jobs. The number of unrelated identical parallel machines is 3, 2, and 2 at each stage, respectively. The standard processing time of each operation on the corresponding stage is shown in Table1. In addition, the power and speed of machines at each stage are different, as shown in Table 2. For example, at stage 1, the processing speed and power of M1,1, M2,1, M3,1 are 1, 2, and 3 and 10, 20, and 30, respectively. The idle power of all machines is 2.Table 1
Processing times of the four-job and three-stage example (hour).
Processing timesPjk
First pass
re-entrant 1
re-entrant 2
Stage 1
Stage 2
Stage 3
Stage 1
Stage 2
Stage 3
Stage 1
Stage 2
Stage 3
Job 1
2
2
1
0
2
1
0
1
2
Job 2
1
3
0
0
2
1
0
2
1
Job 3
3
1
2
2
1
0
0
0
0
Job 4
2
1
1
2
0
0
3
1
0Table 2
Speed and power settings of all machines.
Stage
Machine
Power
Speed
Idle powerSW
Stage 1
M
1,1
10
1
2
M
2,1
20
2
M
3,1
30
3
Stage 2
M
1,2
10
1
M
2,2
20
2
Stage 3
M
1,3
10
1
M
2,3
20
2In this paper, according to [14], TOU electricity tariffs function (yuan/Kwh) is as follows:(15)ft=1.15,15≤t<20,0.75,7≤t<15,20≤t<22,0.42,0≤t<7,22≤t<24.If the processing timePjk=0, it means that the job is not processed in a certain pass. Using random key coding, the permutation of all jobs represents each individual, and each element in the individual is selected in [0, 1] arbitrarily. The corresponding permutation can be obtained by ascending the ranking of each element. To get a feasible schedule, the decoding method is used to determine the processing order of all jobs at each stage and a suitable machine is assigned for each operation. Then, the starting and ending time of each operation can be obtained. At last, the objective function values can be calculated. Taking the individual [0.8147, 0.1270, 0.9058, 0.9134] as an example, the corresponding permutation is 2-1-3-4 according to the ascending order. The detailed process of decoding is as follows. Firstly, all the operations of job 2 are arranged on the machine that can finish it at the earliest time. Then, each operation of job 1 will be arranged on the machine that can finish it as early as possible. If the ending time of a certain operation of the job 2 is smaller than the starting time of the arranged operation of job 4 on a certain machine, the operation of the job 2 will be arranged before it, otherwise, it will be arranged behind it. By analogy, all operations of job 3 and 4 are arranged on the right machines, the Gantt charts are shown in Figure 3. Then, Cmax = 7.8333 hour and TECmin = 184.1634 yuan are obtained.Figure 3
Gantt charts. (a) Scheduling job 2. (b) Scheduling job 1. (c) Scheduling job 3. (d) Scheduling job 4.
(a)
(b)
(c)
(d)


## 3.2. Population Initialization

Generally, the region of the optimal solution is difficult to predict, and the solution space characteristics of the initial population can represent the information of all individuals to a certain extent, so the distribution performance of the initial population directly affects the convergence of the algorithm. In this paper, Latin hypercube sampling technique is used to initialize the population.Assuming thatm samples need to be extracted in n-dimensional vector space, the specific steps of Latin hypercube sampling are as follows:(1)
Each dimension vector is divided intom intervals and they do not overlap with each other(2)
The point is randomly selected in all intervals of each dimension(3)
The selected points in (2) are randomly extracted from each dimension to form a new vector


## 3.3. Adaptive Elite Ant Lion Updating Strategy

According to the elite strategy, the ALO algorithm updates the ant position according to the following formula:(16)Antjt=12RAt+REt.Among them,Antjt is the current position of ant and RAt and REt are ants selected by the roulette wheel selection and ants around the elite ant lion in generation t, respectively. However, in general, the initial stage of the algorithm should have a strong exploring ability, the update step is larger, and the later stage of the algorithm should have a strong exploiting ability, the update step is smaller, so the adaptive elite ant lion update strategy is introduced to update the ant position in this paper, as shown in the following formula:(17)Antjt=ftRAt+1−ftREt,where ft=1−t/T2 is the adaptive coefficient and T and t represent the maximum number and current number of iterations. At the beginning of iterations, ft is about 1 and the value of Antjt is mainly determined by RAt, which can ensure that the algorithm has strong exploratory ability and global search ability in the early stage. As the number of iterations increases, ft gets smaller and smaller. At the later stage of iterations, the value of Antjt is mainly determined by REt, and ants mainly walk around elite ant lions, which ensures that the algorithm has strong exploiting ability in the later stage. In summary, ants can choose different walking modes adaptively, which help to improve the exploring and exploiting ability of the algorithm.


## 3.4. Neighbourhood Structure

In this paper, insertion neighbourhood and exchange neighbourhood are used to improve the local search ability of MOALO. Each individual has a 50% probability to perform insertion or exchange operations, respectively.Insertion neighbourhood: first of all, a new sequenceπ with n−1 jobs is obtained by deleting one job from the individual randomly. Then, the job j is inserted into n−1 intervals of sequence π, and the objective function values fitnessi of n−1 new individuals are calculated, i∈1,n−1. The corresponding objective function values of the original sequence is fitnessn. Then, the dominance is judged and the optimal solution best is assumed to fitness1. If fitnessi≺best, then best=fitnessi, and so on; the individual corresponding to best is taken as the optimal insertion sequence, as shown in Figure 4(a).Figure 4
(a) Example of insertion neighbourhood. (b) Example of exchange neighbourhood.
(a)
(b)Exchange neighbourhood: firstly, a jobj is randomly selected from the individual, and the job j is exchanged with the remaining n−1 jobs, respectively. Then, the objective function values fitnessi of the individual after exchange is calculated, i∈1,n−1, and the corresponding objective function values of the original sequence is fitnessn. Finally, the dominance is judged and the optimal solution best is assumed to fitness1. If fitnessi≺best, then best=fitnessi, and so on; the individual corresponding to best is taken as the optimal exchange sequence, as shown in Figure 4(b).


## 3.5. Right-Shift Operation Based on TOU Electricity Tariffs

Under TOU electricity tariffs, the RHFSP considering energy consumption cost should not only select the appropriate machines for all jobs but also determine the starting time and ending time for each operation reasonably. Due to the complexity of RHFSP, it is inevitable that there will be waiting time for machines and jobs, especially in the case of large number of jobs, so the waiting time can be fully utilized to adjust the processing time of each operation. A right-shift operation is then added in the decoding process, and the time to minimise the energy consumption cost of the operation is selected from the possible starting time as the appropriate starting time. If there are more than one qualified starting time, the maximum value is chosen as the starting time to ensure that there is enough right-shift space. The right-shift operation does not change the makespan and job sequence but helps to reduce the energy consumption cost. Due to the limitation of the decoding method, each operation is decoded according to the earliest ending time, so there is no space to move left. It can be seen that the adjustment of the latter operation will affect the adjustment of the former one, so the right-shift operation should follow the rules from back to front in turn. Firstly, all operations are arranged in a nonincremental order according to the ending time, and then the right-shift operation is carried out in this order. Taking the operationOjk as an example, the detailed adjustment process is as follows.Assuming that the operationOjk is processed on machine Mil, the index of machine Mil is q and the adjustment range of Sjk is t∈tmin,tmax. So without affecting the production efficiency, the job j can choose any time in this range as the starting time.(1)
Suppose thatOjk is the last operation on machine Mil and k=Nj. If Ejk = Cmax, then the operation does not need to move right. If Ejk<Cmax, then tmin=Sjk, tmax=Cmax−Pjk/Vil, and a new idle period will be added in this case; the adjustment range is shown in Figure 5. Therefore, the additional idle energy consumption cost should be considered. The starting time of operation Ojk after adjustment is(18)Sjk′=argmintmin≤t<tmax∑x=tx+Pjk/VilPWqfx+∑x=Sjkx=tSWqfx.(2)
Suppose thatOjk is the last operation of job jk=Nj, but not the last operation of machine Mil. If the next operation on machine Mil is Oj′k′, then tmin=Sjk and tmax=Sj′k′−Pjk/Vil; the adjustment range is shown in Figure 6. The starting time of operation Ojk after adjustment is(19)Sjk′=argmintmin≤t<tmax∑x=tx+Pjk/VilPWqfx.(3)
Suppose thatOjk is the last operation on machine Mil, job j has the next operation Ojk+1 and Ojk+1 is processed on machine Mi′l′. The adjustment range is shown in Figure 7; meanwhile, tmin=Sjk and tmax=Sjk+1−Pjk/Vil. The starting time of operation Ojk after adjustment is(20)Sjk′=argmintmin≤t<tmax∑x=tx+Pjk/VilPWqfx.(4)
In other cases,tmin=Sjk and tmax=minSj′k′,Sjk+1−Pjk/Vil. If Sj′k′≤Sjk+1, the adjustment range is shown in Figure 8. If Sj′k′>Sjk+1, the adjustment range is shown in Figure 9. Adjustment of starting time of process Ojk can be divided into two situations:(a)
IfOjk is the first operation on Mil, part of idle time will be removed, so the removal idle energy consumption cost should be considered, then(21)Sjk′=argmintmin≤t<tmax∑x=tx+Pjk/VilPWqfx−∑x=Sjkx=tSWqfx.(b)
Otherwise,(22)Sjk′=argmintmin≤t<tmax∑x=tx+Pjk/VilPWqfx.Figure 5
Adjustment diagram whenOjk is the last operation on machine Mil and k=Nj.Figure 6
Adjustment diagram whenOjk is not the last operation on machine Mil and k=Nj.Figure 7
Adjustment diagram whenOjk is not the last operation on machine Mil and k≠Nj.Figure 8
Adjustment diagram whenSj′k′≤Sjk+1.Figure 9
Adjustment diagram whenSj′k′>Sjk+1.


## 4. Computational Results

In order to evaluate the effectiveness of the designed IMOALO algorithm in solving RHFSP, three other multiobjective optimization algorithms, MOALO, MOPSO, and NSGA-II, are selected for comparative study. The experimental environment is Windows 8, Intel Core i7-7700 CPU@3.60 GHz, 8G memory, and the computer simulation program is written with Matlab R2017a. In addition, to objectively compare the performance of the algorithms, the common parameters of various algorithms are taken the same value.


### 4.1. Description of Test Data

This paper chooses the small-sized test problems by Cho et al. [9] as benchmark instances to verify the performance of the proposed IMOALO algorithm for solving bi-objective RHFSP. Since there are no parameters about the speed and power of machines in the instances, it is assumed that the faster the machine processing speed is, the more the power will be. In addition, the energy consumption of the same job is fixed and independent of the selected machine. This paper selects six small-sized test problems randomly for testing, and Table 3 shows the range of parameter values. For example, there are two unrelated parallel machines at a stage, numbered 1 and 2, corresponding speed is 1 and 2, and corresponding power is 10 and 20, respectively.Table 3
Parameter settings.
Parameters
Range
Remarks
Number of jobs
[10, 20]
Discrete integer values in [10, 20]
Number of stages
[5, 10]
Discrete integer values in [5, 10]
Number of machines at each stage
[1, 2]
1 or 2
Number of reentrance
[1, 2]
1 or 2
Processing time of each operation
[1, 10]
Discrete integer values in [1, 10]
Speed of machine
[1, 2]
1 or 2
Power of machine
[10, 20]
10 or 20
Idle power of machine
2
ConstantIn this paper, a three-period TOU electricity tariffs function with a total period of 24 hours is used. The expression of the function is shown in formula (23), and the graph of the piecewise function is shown in Figure 10. As can be seen from the figure, the on-peak price (1.15 yuan/kwh) is nearly three times as high as that of off-peak (0.42 yuan/kwh). Such a large price gap means that there is a huge potential to save energy consumption cost for the manufacturing industry.Figure 10
Electricity price over 24-hour time period.


### 4.2. Performance Measures

Three performance measures [40] are used for performance comparison, including convergence measure IGD, dominance measure Ω, and diversity measure Δ. In addition, because the real optimal Pareto fronts of the tested problem are unknown, this paper approximates the union set of nondominant solutions of the four algorithms as the optimal Pareto solutions.IGD evaluates the convergence of the algorithm and the distribution of nondominated solutions by calculating the minimum distance between each point on the optimal Pareto front and the Pareto front obtained by using a certain algorithm. It is a comprehensive performance measure. Because the units of two optimization objectives are different, it is necessary to normalize the objective values before participating in the calculation of IGD. The calculation formula is shown in (23), where N∗ is the number of nondominated solutions on the Pareto optimal front and N is the set of nondominated solutions obtained by using a certain algorithm. Obviously, the smaller the IGD, the better the convergence and distribution quality:(23)IGD=∑x∈N∗distx,NN∗.The measureΩ denotes the percentage of nondominated solutions obtained by a certain algorithm in the optimal Pareto set, which is given by(24)Ωk=P∪iHi\P∪i≠kHiP∪iHi,where PS is the number of nondominated solutions in the Pareto set S and Hk is the set of nondominated solutions obtained by the k−th algorithm. The larger the value of Ω, the better the dominance performance of the algorithm. If the optimal Pareto set is obtained by using a certain algorithm Hk, then Ωk = 100%.The measureΔ represents the diversity of the nondominated solutions, and it can be calculated by(25)Δ=df+dl+∑i=1N−1di−d¯df+dl+N−1d¯,where N is the number of nondominated solutions in the obtained Pareto set. df and dl are the Euclidean distances between two boundary solutions in the nondominated Pareto set and two extreme solutions on the optimal Pareto front. di is the Euclidean distance between i and i+1 consecutive solutions in the Pareto set. d¯ is the mean Euclidean distance of all nondominated solutions. The smaller the value of Δ, the better the diversity performance.


### 4.3. Results and Discussion

For each instance, each of the four algorithms runs 20 times independently, and each run gets a set of [IGD, Ω, Δ]. The minimum (Min), average (Avg), and maximum (Max) of each performance measure after 20 runs for the four algorithms are reported in the Table 4. The bold font represents the optimal results of each performance measure.Table 4
Comparisons of four algorithms for six test problems.
Test problems
Performance measures
IMOALO
MOALO
MOPSO
NSGA-II
Sproblem-01-02
IGD
Min
0.0133
0.0913
0.1282
0.0879
Avg
0.0724
0.1409
0.1733
0.1896
Max
0.1213
0.2033
0.2680
0.3088
Ω
Min
0.4182
0.1361
0.1353
0.1261
Avg
0.5539
0.2709
0.1755
0.2354
Max
0.6611
0.3336
0.2764
0.3044
Δ
Min
0.0622
0.0936
0.1462
0.0709
Avg
0.0906
0.1379
0.1803
0.1614
Max
0.1356
0.2254
0.2447
2415
Sproblem-02-02
IGD
Min
0.0441
0.0850
0.0649
0.0837
Avg
0.0718
0.1284
0.1313
0.1510
Max
0.1022
0.1588
0.1768
0.1801
Ω
Min
0.4776
0.2104
0.1368
0.1236
Avg
0.6116
0.2688
0.3026
0.2218
Max
0.7605
0.3348
0.4039
0.3016
Δ
Min
0.1177
0.1501
0.1549
0.1320
Avg
0.1330
0.1719
0.2113
0.1967
Max
0.1742
0.2297
0.2605
0.2937
Sproblem-03-02
IGD
Min
0.0037
0.0451
0.0818
0.1913
Avg
0.0690
0.0953
0.1016
0.1246
Max
0.1174
0.1545
0.1217
0.1771
Ω
Min
0.4952
0.2239
0.1568
0.1047
Avg
0.6002
0.2686
0.2531
0.2064
Max
0.7176
0.3389
0.3965
0.3439
Δ
Min
0.0714
0.0819
0.1260
0.1274
Avg
0.1180
0.1358
0.1621
0.1766
Max
0.1795
0.1717
0.2213
0.2326
Sproblem-04-02
IGD
Min
0.0359
0.0875
0.1230
0.1063
Avg
0.0676
0.1281
0.1494
0.1633
Max
0.0849
0.1936
0.2088
0.2155
Ω
Min
0.4427
0.1688
0.0903
0.1209
Avg
0.5645
0.3179
0.2060
0.2678
Max
0.6992
0.4287
0.3799
0.3596
Δ
Min
0.0714
0.0819
0.0961
0.1274
Avg
0.1011
0.1358
0.1621
0.1766
Max
0.1721
0.1617
0.2213
0.2326
Sproblem-05-02
IGD
Min
0.0031
0.0361
0.0485
0.0749
Avg
0.0496
0.0896
0.1051
0.0912
Max
0.0946
0.1339
0.1578
0.1193
Ω
Min
0.4894
0.1839
0.1134
0.1214
Avg
0.6634
0.2975
0.1727
0.2304
Max
0.7518
0.3814
0.2956
0.3167
Δ
Min
0.0659
0.0845
0.1332
0.1016
Avg
0.1199
0.1495
0.1731
0.1642
Max
0.1734
0.2009
0.2087
0.2034
Sproblem-06-02
IGD
Min
0.0370
0.1598
0.1252
0.1359
Avg
0.0738
0.2015
0.1717
0.1893
Max
0.1061
0.2427
0.2069
0.2272
Ω
Min
0.5693
0.0629
0.0904
0.1441
Avg
0.7411
0.1092
0.1469
0.1897
Max
0.8779
0.1721
0.1984
0.2366
Δ
Min
0.0530
0.1177
0.0620
0.1199
Avg
0.0922
0.1518
0.1372
0.1672
Max
0.1681
0.2024
0.1597
0.2371Minimum value, mean value, and maximum value can only show the solution effect of each algorithm from the macro level. Table5 lists the statistical difference between the IMOALO and other algorithms based on the T-test. The bold font represents that it is significantly different at the significant level 0.05. It can be seen that IGD, Δ, and Ω measures of IMOALO have significant differences on almost all the problems with other three algorithms from Tables 4 and 5. Therefore, at 95% confidence level, the proposed IMOALO algorithm has significant advantages over other algorithms. The box charts of three performance measures are shown in Figure 11. It can be seen from the figure that Ω measures of IMOALO are greater than in other algorithms; meanwhile, Δ and Ω measures of IMOALO are smaller than in other algorithms significantly, which further verifies the conclusion.Table 5
T-test of IMOALO vs. MOALO, MOPSO, and NSGA-II.
Test problems
Performance measures
p value of IMOALO vs.
MOALO
MOPSO
NSGA-II
Sproblem-01-02
IGD
0.0114
0.0003
0
Ω
0
0
0
Δ
0.1191
0.0045
0.0222
Sproblem-02-02
IGD
0.0043
0.0028
0.0001
Ω
0
0
0
Δ
0.0240
0
0.0004
Sproblem-03-02
IGD
0.0374
0.0110
0
Ω
0
0
0
Δ
0.2739
0.0091
0.0007
Sproblem-04-02
IGD
0.0001
0
0
Ω
0
0
0
Δ
0.0239
0.0001
0
Sproblem-05-02
IGD
0.0025
0
0.0018
Ω
0
0
0
Δ
0.0608
0.0013
0.0064
Sproblem-06-02
IGD
0
0
0
Ω
0
0
0
Δ
0.0007
0.008
0Figure 11
Box charts of three performance measures.Take Sproblem-04-02 as an example to analyse the effectiveness of adding right-shift operation on the scheduling results. There are 16 jobs, 8 machines, 1 reentrance, and 6 stages in the problem. Besides, the number of unrelated parallel machines at each stage is 1, 2, 1, 2, 1, and 1, respectively. Taking a nondominated solution 2-8-13-12-5-11-9-6-1-4-10-7-16-15-14-3 of IMOALO as an example, its objective function valuesCmax = 151.5 hour and TECmin = 4991 yuan. In Figure 12, the Gantt charts with right-shift operation under TOU electricity tariffs are illustrated, and Figure 13 shows the Gantt charts (Cmax = 151.5 hour and TECmin = 5133 yuan) without right-shift operation under TOU electricity tariffs. Comparisons show that the processing times of some operations have been shifted without affecting the production efficiency, and energy consumption cost is reduced by 2.76% to 142 yuan. In the processing cycle, the trend charts of total energy consumption of all machines are shown in Figure 14. It can be seen from Figure 14 that the electric load shifts obviously in some period. For example, in the vicinity where 45 hours and 75 hours are the periods with low electricity price, the total energy consumption of all machines increases after the right-shift procedure; on the contrary, in the vicinity where 55 hours and 115 hours are the periods with high electricity price, the total energy consumption of all machines decreases after the right-shift procedure. Obviously, the energy consumption cost can be saved by avoiding the periods with high electric price. To further prove the effectiveness of the right-shift operation, the above six small-scale problems run 20 times independently without considering right-shift operation under TOU electricity tariffs. Figure 15 shows the relative change of the average Cmax and TECmin of each problem (Sproblem is abbreviated as S), and the negative sign denotes relative decrease. From Figure 15, we can see that the energy consumption cost of each case has decreased. Although the makespan of most instances has increased slightly, it is acceptable that sacrificing a small amount of production efficiency for a large reduction in production cost. In summary, the RHFSP model considering energy consumption cost under the TOU electricity tariffs can reduce the energy consumption cost and enhance the competitiveness of enterprises; meanwhile, there is no significant impact on the makespan.Figure 12
Gantt charts with right-shift operation under TOU electricity tariffs.Figure 13
Gantt charts without right-shift operation under TOU electricity tariffs.Figure 14
Trend charts of real-time total energy consumption of all machines.Figure 15
Relative change of makespan and total energy consumption cost.


## 4.1. Description of Test Data

This paper chooses the small-sized test problems by Cho et al. [9] as benchmark instances to verify the performance of the proposed IMOALO algorithm for solving bi-objective RHFSP. Since there are no parameters about the speed and power of machines in the instances, it is assumed that the faster the machine processing speed is, the more the power will be. In addition, the energy consumption of the same job is fixed and independent of the selected machine. This paper selects six small-sized test problems randomly for testing, and Table 3 shows the range of parameter values. For example, there are two unrelated parallel machines at a stage, numbered 1 and 2, corresponding speed is 1 and 2, and corresponding power is 10 and 20, respectively.Table 3
Parameter settings.
Parameters
Range
Remarks
Number of jobs
[10, 20]
Discrete integer values in [10, 20]
Number of stages
[5, 10]
Discrete integer values in [5, 10]
Number of machines at each stage
[1, 2]
1 or 2
Number of reentrance
[1, 2]
1 or 2
Processing time of each operation
[1, 10]
Discrete integer values in [1, 10]
Speed of machine
[1, 2]
1 or 2
Power of machine
[10, 20]
10 or 20
Idle power of machine
2
ConstantIn this paper, a three-period TOU electricity tariffs function with a total period of 24 hours is used. The expression of the function is shown in formula (23), and the graph of the piecewise function is shown in Figure 10. As can be seen from the figure, the on-peak price (1.15 yuan/kwh) is nearly three times as high as that of off-peak (0.42 yuan/kwh). Such a large price gap means that there is a huge potential to save energy consumption cost for the manufacturing industry.Figure 10
Electricity price over 24-hour time period.


## 4.2. Performance Measures

Three performance measures [40] are used for performance comparison, including convergence measure IGD, dominance measure Ω, and diversity measure Δ. In addition, because the real optimal Pareto fronts of the tested problem are unknown, this paper approximates the union set of nondominant solutions of the four algorithms as the optimal Pareto solutions.IGD evaluates the convergence of the algorithm and the distribution of nondominated solutions by calculating the minimum distance between each point on the optimal Pareto front and the Pareto front obtained by using a certain algorithm. It is a comprehensive performance measure. Because the units of two optimization objectives are different, it is necessary to normalize the objective values before participating in the calculation of IGD. The calculation formula is shown in (23), where N∗ is the number of nondominated solutions on the Pareto optimal front and N is the set of nondominated solutions obtained by using a certain algorithm. Obviously, the smaller the IGD, the better the convergence and distribution quality:(23)IGD=∑x∈N∗distx,NN∗.The measureΩ denotes the percentage of nondominated solutions obtained by a certain algorithm in the optimal Pareto set, which is given by(24)Ωk=P∪iHi\P∪i≠kHiP∪iHi,where PS is the number of nondominated solutions in the Pareto set S and Hk is the set of nondominated solutions obtained by the k−th algorithm. The larger the value of Ω, the better the dominance performance of the algorithm. If the optimal Pareto set is obtained by using a certain algorithm Hk, then Ωk = 100%.The measureΔ represents the diversity of the nondominated solutions, and it can be calculated by(25)Δ=df+dl+∑i=1N−1di−d¯df+dl+N−1d¯,where N is the number of nondominated solutions in the obtained Pareto set. df and dl are the Euclidean distances between two boundary solutions in the nondominated Pareto set and two extreme solutions on the optimal Pareto front. di is the Euclidean distance between i and i+1 consecutive solutions in the Pareto set. d¯ is the mean Euclidean distance of all nondominated solutions. The smaller the value of Δ, the better the diversity performance.


## 4.3. Results and Discussion

For each instance, each of the four algorithms runs 20 times independently, and each run gets a set of [IGD, Ω, Δ]. The minimum (Min), average (Avg), and maximum (Max) of each performance measure after 20 runs for the four algorithms are reported in the Table 4. The bold font represents the optimal results of each performance measure.Table 4
Comparisons of four algorithms for six test problems.
Test problems
Performance measures
IMOALO
MOALO
MOPSO
NSGA-II
Sproblem-01-02
IGD
Min
0.0133
0.0913
0.1282
0.0879
Avg
0.0724
0.1409
0.1733
0.1896
Max
0.1213
0.2033
0.2680
0.3088
Ω
Min
0.4182
0.1361
0.1353
0.1261
Avg
0.5539
0.2709
0.1755
0.2354
Max
0.6611
0.3336
0.2764
0.3044
Δ
Min
0.0622
0.0936
0.1462
0.0709
Avg
0.0906
0.1379
0.1803
0.1614
Max
0.1356
0.2254
0.2447
2415
Sproblem-02-02
IGD
Min
0.0441
0.0850
0.0649
0.0837
Avg
0.0718
0.1284
0.1313
0.1510
Max
0.1022
0.1588
0.1768
0.1801
Ω
Min
0.4776
0.2104
0.1368
0.1236
Avg
0.6116
0.2688
0.3026
0.2218
Max
0.7605
0.3348
0.4039
0.3016
Δ
Min
0.1177
0.1501
0.1549
0.1320
Avg
0.1330
0.1719
0.2113
0.1967
Max
0.1742
0.2297
0.2605
0.2937
Sproblem-03-02
IGD
Min
0.0037
0.0451
0.0818
0.1913
Avg
0.0690
0.0953
0.1016
0.1246
Max
0.1174
0.1545
0.1217
0.1771
Ω
Min
0.4952
0.2239
0.1568
0.1047
Avg
0.6002
0.2686
0.2531
0.2064
Max
0.7176
0.3389
0.3965
0.3439
Δ
Min
0.0714
0.0819
0.1260
0.1274
Avg
0.1180
0.1358
0.1621
0.1766
Max
0.1795
0.1717
0.2213
0.2326
Sproblem-04-02
IGD
Min
0.0359
0.0875
0.1230
0.1063
Avg
0.0676
0.1281
0.1494
0.1633
Max
0.0849
0.1936
0.2088
0.2155
Ω
Min
0.4427
0.1688
0.0903
0.1209
Avg
0.5645
0.3179
0.2060
0.2678
Max
0.6992
0.4287
0.3799
0.3596
Δ
Min
0.0714
0.0819
0.0961
0.1274
Avg
0.1011
0.1358
0.1621
0.1766
Max
0.1721
0.1617
0.2213
0.2326
Sproblem-05-02
IGD
Min
0.0031
0.0361
0.0485
0.0749
Avg
0.0496
0.0896
0.1051
0.0912
Max
0.0946
0.1339
0.1578
0.1193
Ω
Min
0.4894
0.1839
0.1134
0.1214
Avg
0.6634
0.2975
0.1727
0.2304
Max
0.7518
0.3814
0.2956
0.3167
Δ
Min
0.0659
0.0845
0.1332
0.1016
Avg
0.1199
0.1495
0.1731
0.1642
Max
0.1734
0.2009
0.2087
0.2034
Sproblem-06-02
IGD
Min
0.0370
0.1598
0.1252
0.1359
Avg
0.0738
0.2015
0.1717
0.1893
Max
0.1061
0.2427
0.2069
0.2272
Ω
Min
0.5693
0.0629
0.0904
0.1441
Avg
0.7411
0.1092
0.1469
0.1897
Max
0.8779
0.1721
0.1984
0.2366
Δ
Min
0.0530
0.1177
0.0620
0.1199
Avg
0.0922
0.1518
0.1372
0.1672
Max
0.1681
0.2024
0.1597
0.2371Minimum value, mean value, and maximum value can only show the solution effect of each algorithm from the macro level. Table5 lists the statistical difference between the IMOALO and other algorithms based on the T-test. The bold font represents that it is significantly different at the significant level 0.05. It can be seen that IGD, Δ, and Ω measures of IMOALO have significant differences on almost all the problems with other three algorithms from Tables 4 and 5. Therefore, at 95% confidence level, the proposed IMOALO algorithm has significant advantages over other algorithms. The box charts of three performance measures are shown in Figure 11. It can be seen from the figure that Ω measures of IMOALO are greater than in other algorithms; meanwhile, Δ and Ω measures of IMOALO are smaller than in other algorithms significantly, which further verifies the conclusion.Table 5
T-test of IMOALO vs. MOALO, MOPSO, and NSGA-II.
Test problems
Performance measures
p value of IMOALO vs.
MOALO
MOPSO
NSGA-II
Sproblem-01-02
IGD
0.0114
0.0003
0
Ω
0
0
0
Δ
0.1191
0.0045
0.0222
Sproblem-02-02
IGD
0.0043
0.0028
0.0001
Ω
0
0
0
Δ
0.0240
0
0.0004
Sproblem-03-02
IGD
0.0374
0.0110
0
Ω
0
0
0
Δ
0.2739
0.0091
0.0007
Sproblem-04-02
IGD
0.0001
0
0
Ω
0
0
0
Δ
0.0239
0.0001
0
Sproblem-05-02
IGD
0.0025
0
0.0018
Ω
0
0
0
Δ
0.0608
0.0013
0.0064
Sproblem-06-02
IGD
0
0
0
Ω
0
0
0
Δ
0.0007
0.008
0Figure 11
Box charts of three performance measures.Take Sproblem-04-02 as an example to analyse the effectiveness of adding right-shift operation on the scheduling results. There are 16 jobs, 8 machines, 1 reentrance, and 6 stages in the problem. Besides, the number of unrelated parallel machines at each stage is 1, 2, 1, 2, 1, and 1, respectively. Taking a nondominated solution 2-8-13-12-5-11-9-6-1-4-10-7-16-15-14-3 of IMOALO as an example, its objective function valuesCmax = 151.5 hour and TECmin = 4991 yuan. In Figure 12, the Gantt charts with right-shift operation under TOU electricity tariffs are illustrated, and Figure 13 shows the Gantt charts (Cmax = 151.5 hour and TECmin = 5133 yuan) without right-shift operation under TOU electricity tariffs. Comparisons show that the processing times of some operations have been shifted without affecting the production efficiency, and energy consumption cost is reduced by 2.76% to 142 yuan. In the processing cycle, the trend charts of total energy consumption of all machines are shown in Figure 14. It can be seen from Figure 14 that the electric load shifts obviously in some period. For example, in the vicinity where 45 hours and 75 hours are the periods with low electricity price, the total energy consumption of all machines increases after the right-shift procedure; on the contrary, in the vicinity where 55 hours and 115 hours are the periods with high electricity price, the total energy consumption of all machines decreases after the right-shift procedure. Obviously, the energy consumption cost can be saved by avoiding the periods with high electric price. To further prove the effectiveness of the right-shift operation, the above six small-scale problems run 20 times independently without considering right-shift operation under TOU electricity tariffs. Figure 15 shows the relative change of the average Cmax and TECmin of each problem (Sproblem is abbreviated as S), and the negative sign denotes relative decrease. From Figure 15, we can see that the energy consumption cost of each case has decreased. Although the makespan of most instances has increased slightly, it is acceptable that sacrificing a small amount of production efficiency for a large reduction in production cost. In summary, the RHFSP model considering energy consumption cost under the TOU electricity tariffs can reduce the energy consumption cost and enhance the competitiveness of enterprises; meanwhile, there is no significant impact on the makespan.Figure 12
Gantt charts with right-shift operation under TOU electricity tariffs.Figure 13
Gantt charts without right-shift operation under TOU electricity tariffs.Figure 14
Trend charts of real-time total energy consumption of all machines.Figure 15
Relative change of makespan and total energy consumption cost.


## 5. Parameter Analysis

### 5.1. Analysis of Machines with Different Power and Speed

Each stage contains several unrelated parallel machines with different power and speed in the RHFSP. For the purposes of cost saving, many enterprises mix new machines with old ones in practice. Although the new machine has a high processing capacity, it also consumes a large amount of energy per unit time. Taking the scheduling of 10 jobs, 2 reentrances, 2 stages, 2 parallel machines at each stage, and processing time ranges of [10, 40] as an example, the effects of different parameter combinations on the scheduling results are studied. In this case, the speed and power of machines are divided into three levels. Assuming that the idle power of all machines is SW = 1. The specific parameters are shown in Table 6. To ensure the validity of the comparison, all machines at one stage have the same energy efficiency ratio PW/V and each stage has the same production capacity. For example, the PW/V at the stage 1 is 2 and that at the stage 2 is 3. In addition, the total speed at every stage is 6. The Pareto fronts obtained by running each parameter combination once randomly based on IMOALO algorithm are shown in Figure 16. As shown in Figure 16, there is no significant difference on the makespan. Combining the high-power and low-power machines together is more energy efficient than using two identical machines with middle power. Although the faster machines consume more power, when assigning the jobs to the faster machines, the processing time of each operation is reduced. This helps to transfer the operations to the off-peak periods more flexibly.Table 6
Test results by three different settings of power and speed.
Test 1
Test 2
Test 3
Stage 1
Power
P
W
1,1
=
6, PW2,1=6
P
W
1,1
=
8, PW2,1=4
P
W
1,1
=
10, PW2,1=2
Speed
V
1,1
=
3, V2,1=3
V
1,1
=
4, V2,1=2
V
1,1
=
5, V2,1=1
Stage 2
Power
P
W
1,2
=
9, PW2,2=9
P
W
1,2
=
12, PW2,2=6
P
W
1,2
=
15, PW2,2=3
Speed
V
1,2
=
3, V2,2=3
V
1,2
=
4, V2,2=2
V
1,2
=
5, V2,2=1
Range ofCmax
[109, 124]
[108, 123]
[109, 124]
Range ofTECmin
[1730, 1777]
[1654, 1753]
[1613, 1720]Figure 16
Pareto fronts by different settings of speed and power.


### 5.2. Analysis of TOU Electricity Tariffs with Different Periods

In practice, the period of TOU electricity tariffs varies with season. In general, the period of on-peak in summer is longer than that in winter, and there are differences between holidays and working days. Thus, it is important to study how the period of TOU electricity tariffs impacts the scheduling results. Taking Sproblem-04-02 as an example, we just change the total period without changing the corresponding electricity price for each period in the following five tests. Table7 shows the specific parameters. The Pareto fronts obtained by each parameter combination based on IMOALO algorithm are shown in Figure 17.Table 7
Test results by different periods of TOU electricity tariffs.
Test 1
Test 2
Test 3
Test 4
Test 5
Total periods
24
48
72
96
120
Length of each period
7, 8, 5, 2, 2
14, 16, 10, 4, 4
21, 24, 15, 6, 6
28, 32, 20, 8, 8
35, 40, 25, 10, 10
Price of each period
0.42, 0.75, 1.15, 0.75, 0.42
Range ofCmax
[148, 166.5]
[149, 165]
[148.5, 157]
[148, 159]
[148, 161]
Range ofTECmin
[4788, 5251]
[4706, 5123]
[4795, 5039]
[4520, 4759]
[4460, 4729]Figure 17
Pareto fronts by different periods of TOU electricity tariffs.As can be seen from Table7 and Figure 17, maintaining the same electricity price in each period, energy consumption cost is affected obviously by the length of total periods. However, the change has little effect on the makespan, and the lower bound of the makespan remains near 148 hours. The cure of Pareto front shows a downward trend with the increase of the periods. Tracing it to its cause, with increasing period of TOU electricity tariffs, there is more space for the operations transferring to off-peak periods after adding the right-shift operation. Therefore, keeping the same electricity price in each period and the total number of TOU electricity tariffs periods, increasing the length of total periods appropriately can reduce energy consumption cost effectively and maintain the makespan unchanged.


## 5.1. Analysis of Machines with Different Power and Speed

Each stage contains several unrelated parallel machines with different power and speed in the RHFSP. For the purposes of cost saving, many enterprises mix new machines with old ones in practice. Although the new machine has a high processing capacity, it also consumes a large amount of energy per unit time. Taking the scheduling of 10 jobs, 2 reentrances, 2 stages, 2 parallel machines at each stage, and processing time ranges of [10, 40] as an example, the effects of different parameter combinations on the scheduling results are studied. In this case, the speed and power of machines are divided into three levels. Assuming that the idle power of all machines is SW = 1. The specific parameters are shown in Table 6. To ensure the validity of the comparison, all machines at one stage have the same energy efficiency ratio PW/V and each stage has the same production capacity. For example, the PW/V at the stage 1 is 2 and that at the stage 2 is 3. In addition, the total speed at every stage is 6. The Pareto fronts obtained by running each parameter combination once randomly based on IMOALO algorithm are shown in Figure 16. As shown in Figure 16, there is no significant difference on the makespan. Combining the high-power and low-power machines together is more energy efficient than using two identical machines with middle power. Although the faster machines consume more power, when assigning the jobs to the faster machines, the processing time of each operation is reduced. This helps to transfer the operations to the off-peak periods more flexibly.Table 6
Test results by three different settings of power and speed.
Test 1
Test 2
Test 3
Stage 1
Power
P
W
1,1
=
6, PW2,1=6
P
W
1,1
=
8, PW2,1=4
P
W
1,1
=
10, PW2,1=2
Speed
V
1,1
=
3, V2,1=3
V
1,1
=
4, V2,1=2
V
1,1
=
5, V2,1=1
Stage 2
Power
P
W
1,2
=
9, PW2,2=9
P
W
1,2
=
12, PW2,2=6
P
W
1,2
=
15, PW2,2=3
Speed
V
1,2
=
3, V2,2=3
V
1,2
=
4, V2,2=2
V
1,2
=
5, V2,2=1
Range ofCmax
[109, 124]
[108, 123]
[109, 124]
Range ofTECmin
[1730, 1777]
[1654, 1753]
[1613, 1720]Figure 16
Pareto fronts by different settings of speed and power.


## 5.2. Analysis of TOU Electricity Tariffs with Different Periods

In practice, the period of TOU electricity tariffs varies with season. In general, the period of on-peak in summer is longer than that in winter, and there are differences between holidays and working days. Thus, it is important to study how the period of TOU electricity tariffs impacts the scheduling results. Taking Sproblem-04-02 as an example, we just change the total period without changing the corresponding electricity price for each period in the following five tests. Table7 shows the specific parameters. The Pareto fronts obtained by each parameter combination based on IMOALO algorithm are shown in Figure 17.Table 7
Test results by different periods of TOU electricity tariffs.
Test 1
Test 2
Test 3
Test 4
Test 5
Total periods
24
48
72
96
120
Length of each period
7, 8, 5, 2, 2
14, 16, 10, 4, 4
21, 24, 15, 6, 6
28, 32, 20, 8, 8
35, 40, 25, 10, 10
Price of each period
0.42, 0.75, 1.15, 0.75, 0.42
Range ofCmax
[148, 166.5]
[149, 165]
[148.5, 157]
[148, 159]
[148, 161]
Range ofTECmin
[4788, 5251]
[4706, 5123]
[4795, 5039]
[4520, 4759]
[4460, 4729]Figure 17
Pareto fronts by different periods of TOU electricity tariffs.As can be seen from Table7 and Figure 17, maintaining the same electricity price in each period, energy consumption cost is affected obviously by the length of total periods. However, the change has little effect on the makespan, and the lower bound of the makespan remains near 148 hours. The cure of Pareto front shows a downward trend with the increase of the periods. Tracing it to its cause, with increasing period of TOU electricity tariffs, there is more space for the operations transferring to off-peak periods after adding the right-shift operation. Therefore, keeping the same electricity price in each period and the total number of TOU electricity tariffs periods, increasing the length of total periods appropriately can reduce energy consumption cost effectively and maintain the makespan unchanged.


## 6. Conclusions and Future Work

This paper mainly studies the RHFSP under TOU electricity tariffs with the objective of minimizing the makespan and energy consumption cost. The effectiveness of the proposed algorithm is evaluated by considering the benchmark problems. From the results, we can conclude that the proposed IMOALO algorithm can solve the RHFSP effectively and it is significantly superior to other algorithms in terms of convergence, dominance, and diversity measures of nondominated solutions. In addition, parameter analysis shows that the energy efficiency of machines and period of TOU electricity tariffs have great impact on the scheduling results. Under the TOU electricity tariffs, although the total electricity consumption has not decreased, the energy consumption cost can be saved by avoiding the periods of high electric price. Meanwhile, it helps to promote the use of green energy to generate electricity in low valleys, such as wind power, thus saving fossil energy and reducing pollutant emissions. In the future, we will further study the RHFSP, such as designing better coding and decoding methods and designing better algorithms and joint optimization of production scheduling and maintenance.



---

*Source: 8565921-2020-02-22.xml*