Sage Journals: Discover world-class research

Abstract

The flow shop scheduling problem has been widely studied in recent years, but the research on multi-objective flow shop scheduling with green indicators is still relatively limited. It is urgent to strengthen the research on effective methods to solve such interesting problems. To consider the economic and environmental factors simultaneously, the paper investigates the multi-objective permutation flow shop scheduling problems (MOPFSP) which minimizes the makespan and total carbon emissions. Since MOPFSP is proved to be a NP-hard problem for more than two machines. A hybrid cuckoo search algorithm (HCSA) is proposed to solve the problems. Firstly, a largest-order-value method is proposed to enhance the performance of HCS algorithm in the solution space of MOPFSP. Then, an adaptive factor of step size is designed to control the search scopes in the evolution phases. Finally, a multi-neighborhood local search rule is addressed in order to find the optimal sub-regions obtained by the HCSA. Numerical experiments show that HCSA can solve MOPFSP efficiently.

Keywords

Multi-objective permutation flow shop cuckoo search algorithm carbon efficiency green dispatch

Introduction

Recently, with the increasingly severe environmental problems in the manufacturing industry, the green manufacturing has received considerable attention.^1,2 The problem model studied in this paper contains environmental indicators, which meets the current needs of ecological environment governance. According to a survey by Fang et al.,³ most of the world’s energy consumption comes from the industrial sector, and manufacturing companies have become one of the main factors for global warming. On the one hand, the control of greenhouse gas emissions by laws and regulations makes manufacturing companies have to limit carbon emissions; on the other hand, the high taxes brought by carbon emissions also make manufacturers seek practical and feasible ways to processed products.⁴

Scheduling time, processing cost, and product quality are the three most common optimization indicators for traditional production scheduling problem.⁵ When the environmental and energy-saving problems are increasingly severe in the manufacturing industry, green indicators and economic indicators should be considered at the same time in order to meet the scheduling demands. The multi-objective permutation flow shop problem (MOPFSP) with green indicators studied in this paper has a strong industrial background.⁶ In terms of computational complexity, the permutation flow shop scheduling problem (PFSP) of more than two machines has been proved to be an NP-hard problem,⁷ so MOPFSP also belongs to the NP-hard problem. In summary, it is of great engineering and academic significance to solve the MOPFSP with green indicators.

In the past few decades, the MOPFSP and green manufacturing has been studied extensively. However, only few researchers have considered both economic and environmental indicators. Luo et al.⁸ designed an ant colony optimization method to address the multi-objective mixed FSP with power consumption. Ding et al.⁹ studied the multi-objective flow shop scheduling problem with total carbon emissions, and proposed an improved iterative greedy algorithm. Liu et al.¹⁰ proposed an adaptive multi-objective genetic algorithm that can effectively address a class of pipeline shop scheduling problems with two optimization indicators of carbon emissions and total weighted delay. Ding et al.¹¹ addressed an iterative greedy algorithm based on non-dominated solution structure characteristics for solving the dual-objective flow shop scheduling problem with total carbon emissions. Tang et al.¹² presented a modified particle swarm optimization algorithm, which can solve the flexible flow shop scheduling problem based on the two goals of energy consumption and maximum completion time. Lu¹³ proposed a hybrid multi-objective backtracking search algorithm based on machine setup time and workpiece transportation time to solve the MOPFSP with energy consumption. Wang and Tian¹⁴ established a dual-objective optimization model for the selection of milling parameters such that power consumption and process time are minimized, and proposed an improved artificial bee colony (ABC) intelligent algorithm to handle the dual-objective optimization mode. Fu and Tian¹⁵ proposed a scheduling model can make an interaction between the energy consumption and the production cost to realize an efficient and sustainable production process. In summary, the research on MOPFSP with green indicators is still relatively limited, and it is urgent to develop effective methods for solving such important problems.

The CS (cuckoo search) algorithm is an algorithm that effectively solves the optimization problem by simulating the brood parasitism of some species of cuckoos that proposed by Yang and Deb.¹⁶ This algorithm searches according to the flight mechanism of cuckoos at the time of spawning, which can quickly and efficiently solve continuous optimization problems.¹⁷ Compared with other meta-heuristic algorithms, Cuckoo’s algorithm has better performance and efficiency in solving multi-objective optimization problems. Sheli and Chaudhuri¹⁸ verified the CS algorithm and compared with some classical Algorithms: GAs and PSO. From simulation and comparison, it is evident that CS is much better and efficient than the GAs and PSO for multi-objective functions. This is because in the case of CS, there are fewer parameters that require precise control. It is clear that once the number of nests is fixed, there is only one parameter discovery probability that needs to be adjusted. It should be noted that in the absence of discovery probability interference, the CS convergence speed of all the above test functions is very fast and the efficiency is high. Therefore, compared with other meta-heuristic algorithms, CS is more versatile and robust in many optimization problems. The robust optimization algorithm can be easily applied to multi-objective optimization problems. In recent years, the CS algorithm has also been extended to solve single-objective production scheduling problems with economic indicators. Li and Yin¹⁹ used NEH heuristics to generate part of the initial population and designed a hybrid CS algorithm with local search to solve the single-objective PFSP problem. Marichel et al.²⁰ designed NEH rules to initialize part of the population at the initial stage of the CS algorithm, and then used it to solve a single-objective multi-stage mixed-line shop floor scheduling problem. Alaa and Alobaidi²¹ improved the Lévy flight equation in the CS algorithm, and enhanced the search for the optimal individual neighborhood of the population. The proposed algorithm was used to solve the single-objective flexible job shop scheduling problem. Wang et al.²² used the NEH rule to generate part of the initial population, and then proposed a Cuckoo algorithm with local search for solving a single-target pipeline shop scheduling problem. Zhang et al.²³ proposed a dynamic adaptive cuckoo search algorithm (DACS). They introduced feedback into the algorithm framework, established a closed-loop control system for the parameters of the CS algorithm, and used Rechenberg’s 1/5 rule as an evolutionary evaluation index. However, the above literatures set the step size control factor to a certain constant and did not adjust it dynamically. In fact, as the number of iterations of algorithm increases, if the step size control factor is set too large, the cuckoo algorithm’s search tends to deviate high quality solution region, resulting poor performance; if the step size control factor is set too small, the algorithm is easy to fall into a local optimum and premature. Therefore, it is of great significance to design cuckoo algorithm that can dynamically adjust step size control factor to solve the green flow shop scheduling problem.

A hybrid cuckoo search algorithm is proposed to solve MOPFSP with the objective of minimizing the completion time and total carbon emissions in this paper. on one hand, an adaptive adjust strategy for step size control factor is presented to make the cuckoo algorithm have faster convergence speed and better global search performance; on the other hand, a multi-neighbor local search mechanism is also designed to improve the performance of HCS algorithm. To this end, a better balance between global and local search of the algorithm is achieved. Finally, the effectiveness of HCS is verified through simulation experiments and algorithm comparison.

Problem statement

Low carbon MOPFSP descriptions

Production scheduling is to allocate a set of machining tasks in time to an available set of machining machines to meet a performance index.²⁴ It mainly consists of two factors: performance indicator and scheduling schemes.^25,26 The performance indicators of production scheduling are classified into three categories: maximum capacity indicators, cost indicators, and customer satisfaction indicators.²⁷ Among them, the maximum capacity indicators include minimizing the maximum completion time and maximum productivity. The cost indicators include minimizing operating costs and maximizing revenue.²⁸ Customers satisfaction indicators include minimizing early or late penalties. Additionally, green indicators like energy consumption, carbon emissions have been considered in recent years.

The scheduling scheme generally represents a solution to a production scheduling problem, which is the arrangement of the processing order of processing workpieces on various machines.²⁹ It can be usually expressed by a Gantt chart, as shown in Figure 1.

Figure 1.

Gantt chart.

According to the description of the mentioned above, the MOPFSP with low carbon can be introduced as follows. There are m machines in the shop floor. The workpieces set is J = {1, 2, …, n}. The machine set is M = {1, 2, …, m}. The speed set is S = {v₁, v₂, …, v_s}. T_i,k represents the standard machining time of workpiece i on machine k; V_i,k represents the machining speed of workpiece i on machine k; T_i,k/V_i,k represents the real machining time of workpiece i when machining on machine k at speed V_i,k. Q_k,v represents the unit energy consumption when machine k works at speed v; Q_k represents the unit energy consumption when machine k is in standby state. When machine k works at speed v at time t, $x_{kv} (t) = 1$ , and otherwise, $x_{kv} (t) = 0$ ; at time t, the machine is in standby state $y_{k} (t) = 1$ , and otherwise, $y_{k} (t) = 0$ ; $π = (j_{1}, j_{2}, \dots, j_{n})$ is some sort of all workpieces; ∏ is different sort the set of π; C(j,k)_i = (1, 2, …, n) is the completion time of workpiece j_i on machine k.

Two processing rules of PFSP are given: ① After the workpiece I∈J is processed on the machine (k − 1) ∈M, the workpiece j∈J can be processed on the machine k∈M. ② Each machine cannot process multiple workpieces at the same time. Assume that the workpieces j₁ to j_m are sequentially processed on machine 1 to machine m in order. Therefore, the multi-objective models of PFSP can be described based on economic and environmental indicators.

For the economic indicator, the longest completion time is considered. Its mathematical model is written as

C_{max} = C (j_{n}, m)

(1)

For the green indicator, assuming $ε$ is the amount of CO₂ emissions per unit energy consumption, the total CO₂ emissions calculation equation is considered as:

\begin{matrix} C_{c o_{2}} = ε C_{T} = ε \int_{0}^{C_{max}} (\sum_{v = 1}^{s} \sum_{k = 1}^{m} {Q_{k}}_{, v} x_{kv} (t) \\ + \sum_{k = 1}^{m} Q_{k} y_{k} (t)) \end{matrix} dt

(2)

Among them, C_T represents total energy consumption; $C_{C O_{2}}$ represents total CO₂ emissions, hereinafter referred to as total carbon emissions (TCE).

In order to calculate the total CO₂ emission, a rate matrix A_n×m for the machine needs to be constructed, where $A_{i, k} \in {1, 2,, s}$ . Assuming s = 3, $A_{i, k} \in {1, 2, 3}$ , n = 3, m = 2, then one of the cases of matrix A is expresses as follows:

A_{3 \times 2} = [\begin{matrix} \begin{matrix} 1 & 2 \end{matrix} \\ \begin{matrix} 2 & 2 \end{matrix} \\ \begin{matrix} 3 & 1 \end{matrix} \end{matrix}]

(3)

Where A₃₁ represents the machining speed of third workpieces when machining on first machine is 3.

Furthermore, the constraints of the low carbon MPFSP are given in the following.

C (j_{1}, 1) = T_{j 1, 1} / V_{j 1, 1}

(4)

C (j_{i}, 1) = C (j_{i - 1}, 1) + T_{j_{i}, 1} / V_{j_{i} - 1}

(5)

C (j_{1}, k) = C (j_{1}, k - 1) + T_{j_{1}, k} / V_{j_{1}, k}

(6)

C (j_{i}, k) = max {C (j_{i - 1}, k), C (j_{i}, k - 1)} + T_{j_{i}, k} / V_{j_{i}, k}

(7)

For the low carbon MPFSP, it is impossible to obtain the global optimal solution of makespan and TCE simultaneously. But a set of solutions can be obtained: the continued optimization of any one target must sacrifice the effective solution of other objective function values.^27,30 The set of such effective solutions is called a non-inferior solution, which is a Pareto solution set.

Hybrid cuckoo algorithm

Standard Cuckoo algorithm

The CS (cuckoo search) algorithm can effectively solve the optimization problem by simulating the brood parasitism of some species of cuckoos.³¹ Lévy-flights is a kind of action mode, the step size of random walk satisfies a heavy-tailed stable distribution. In this form of walking, the exploratory jumps of short distance and occasionally the longer distances working are interspersed. The trajectory of Lévy-flights on a two-dimensional plane is shown in Figure 2.³²

Figure 2.

Lévy-flights motion diagram on a two-dimensional plane.

The flight of many animals in nature conforms to the Lévy-flights model, and the flight of cuckoo is one of them.³³ When the cuckoo is searching, its flight path is the combination of various long and short distances. Each distance differs from the previous distances by a small angle.³⁴ Short distances occur most frequently, while the longer distances are rare. Lévy-flights may seem disorganized, but it is not. The distances and the angle of deviations follow a very definite statistical distribution. Through long-term observation of the cuckoo’s living habits, it is found that cuckoos only lay eggs and do not build nests.³⁵ And their eggs often lay in the nests of different birds. Inspired by this nature phenomenon, a new search algorithm–cuckoo search algorithm (CS) in cuckoo’s nest-seeking behavior is proposed.³⁶ Each nest represents a potential solution. The host bird may find that the egg is not its own egg. It may abandon the egg and or the entire nest. Cuckoo birds lay eggs in this way, so that the nest position is continuously optimized.

The pseudocode of the standard cuckoo search algorithm is given in Table 1.

Table 1.

The standard cuckoo search algorithm.

Begin
Objective function

f (x), x = (x_{1}, x_{2}, \cdot \cdot \cdot x_{d})^{T}

Generate initial population of n host nests

x_{i} = (i = 1, 2, \cdot \cdot \cdot, n)

While (t < Max Generation) or (stop criterion)
Get a cuckoo randomly by Lévy flights
Evaluate its quality/fitness

F_{i}

Choose a nest among n (say, j) randomly
If (

F_{i} > F_{j}

)
replace j by the new solution;
End
A fraction (

p_{a}

) of worse nests are abandoned and new ones are built;
Keep the best solutions (or nests with quality solutions);
Rank the solutions and find the current best
End while
Postprocess results and visualization
End

The flowchart of the standard CS algorithm is given in Figure 3.

Figure 3.

Flowchart of the standard CS algorithm.

There are two ways to update individuals in the cuckoo search algorithm, the first is to use Levi’s flight equation:

x_{i, t + 1} = x_{i, t} + α \oplus Levy (λ)

(11)

Among them, $x_{i, t + 1}$ , $x_{i, t}$ are the position vectors of the ith individual at kth and (k+1)th generations; ⊕ represents a point multiplication; $α$ is a step factor controlling the step size, and in most cases, $α = O (1)$ ; $Levy (λ)$ is levy flight search path.

As can be seen from equation (11), this distribution makes a continuous distribution of cuckoo birds form a probability distribution with heavy tails, which can expend the search range, increase population diversity, and easily converge to global optimum.

The second update method is to determine whether to generate new individuals according to the relationship between a fixed discovery probability $P_{a}$ and a random number $β$ , the update equation is as follows:

x_{i, t + 1} = x_{i, t} + γ H (P_{a} - β) \oplus [x_{o, t} - x_{k, t}]

(12)

Among them, $γ$ and $β$ both obey uniform distribution and $γ, β \in U [0, 1]$ ; $x_{i, t}, x_{o, t}, x_{k, t}$ are three different random in the individuals of tth generation; H is the Heaviside function, and its calculation equation is:

H (P_{a} - B) = {\begin{matrix} 0 & (P_{a} > β) \\ 0.5 & (P_{a} = β) \\ 1 & (P_{a} < β) \end{matrix}}

(13)

Hybrid cuckoo algorithm

Adaptive step size factor

Although the CS algorithm is more effective than other swarm optimization algorithms, it has its own inherent shortcomings: Levi’s flight is a Markov chain, which is only related to the current situation and has large randomness. Therefore, convergence accuracy and search depth are two shortcomings of the CS algorithm. The CS algorithm defines a step size control factor $α$ in equation (11), which is generally set to a fixed constant in the standard algorithm (e.g. the value is usually 0.01). If $α$ is set too large, it will easily cause the search of algorithm deviate from high-quality solution, which will slow down the convergence speed; on the contrary, if $α$ is set too small, the CS algorithm will easily get into the local optimal solution prematurely, resulting in weak algorithm performance. Therefore, the improvement of the $α$ can enhance the performance of algorithm effectively. If a large $α$ is used in the early stage of algorithm search, it is beneficial to easily locate the area of high-quality solution in the global scope; at the same time, as the algorithm search advances, the $α$ should be gradually reduced to strengthen the fine search of the local optimal solution region in order to improve the algorithm performance and convergence speed. This paper modified the standard CS algorithm from the step size control factor: replace the original fixed step size control factor with a dynamic step size control factor.

In this paper, the standard cuckoo search algorithm is improved from step size control factors: replacing fixed step size control factors with dynamic step size control factors. In the optimization process, when the individual quality gradually improves, the search scope is appropriately reduced to strengthen the search depth, which is conducive to searching for better solutions. The reasonable step size control factor should gradually decrease with the increase of the evolutionary algebra, so that the algorithm can easily find high-quality individuals in the later stage of evolution.

This paper adaptively adjusts the step size control factor $α$ according to the following aspects: the cosine function is introduced to make a decrease as the evolution generation increases and an improved equation for $α$ is proposed:

α^{(k + 1)} {\begin{matrix} α_{max} \cos (\frac{π}{2} \frac{k}{T_{max}}) & R \leq 0.2 \\ α^{k} & 0.2 < R < 0.5 \\ α_{min} & 0.5 \leq R \end{matrix}}

(14)

Where, R is the ratio of the current evolution generation to the total evolution generation; $α_{min}$ is the lower limit of $α$ ; $α_{max}$ is the upper limit of $α$ ; $T_{max}$ is the maximum number of iterations; $k$ is evolution generation. At the beginning of HCS algorithm, R ≤ 0.2. At this time, there should be a large step to find the high-quality solution area. Therefore, the step control factor $α$ should gradually decreases as the evolutionary algebra increases; when 0.2 < R < 5, the further search will be applied in the high-quality solution area, and should strengthen the local fine search ( $α$ remains unchanged); at the later stage of the algorithm, the R ≥ 5. At this time, the individual gradually approaches the Pareto front, without the need for large steps, so keep the $α$ in lower bound.

Multi-neighborhood local search

In order to further improve local search accuracy of the cuckoo algorithm, a multi-neighborhood local search strategy is proposed in this paper to perform fine search based on different neighborhoods. Specifically, it performs a local search based on three neighborhoods on individuals in the current non-inferior solution set of the algorithm. The three neighborhood searches are: interchange local search, insert local search, 2-opt local search. The specific definitions are as follows:

Interchange local search: Sort each workpiece, randomly select two different locations, and exchange the workpiece at the location. For example, 10 workpieces are sorted as [4, 2, 7, 1, 3, 5, 9, 8, 10, 6], and two positions p₁ = 3 and p₂ = 9 are generated randomly. Nine workpieces 10 swap positions and get a new sort [4, 2, 10, 1, 3, 5, 9, 8, 7, 6]. Then, the workpiece 7 at position 3 and the workpiece 10 at position 9 are exchanged to obtain a new order [4, 2, 10, 1, 3, 5, 9, 8, 7, 6].

Insert local search: This step can be divided into front insert and post insert. Sort the workpieces of each individual and randomly select two different positions p₁ and p₂, assuming p₁ > p₂. Post-insertion means inserting the workpiece at position p₁ into position p₂, and the workpieces at positions p₁+1 ∼ p₂. Move forward one position; Insert forward refers to insert the workpiece of position p₂ into position p₁, and the workpieces of positions p₁ ∼ p₂ − 1 are moved backward one position. For example, the 10 workpieces are sorted as [4, 2, 7, 1, 3, 5, 9, 8, 10, 6], and two positions p₁ = 3 and p₂ = 9 are randomly generated. According to the above, after inserting, the new order is [4, 2, 1, 3, 5, 9, 8, 10, 7, 6,], and the new order obtained by the previous insertion is [4, 2, 10, 7, 1, 3, 5, 9, 8, 6].

2-opt local search: Sort each workpiece, randomly select two different positions p₁ and p₂, and sort the workpieces of p₁ ∼ p₂ in reverse order. For example, 10 workpieces are sorted as [4, 2, 7, 1, 3, 5, 9, 8, 10, 6], and two positions p₁ = 3 and p₂ = 9 are randomly generated. According to the above, the new order is [4, 2, 10, 8, 9, 5, 3, 1, 7, 6].

Let $π (X)$ be the workpiece ordering of the individual X based on the LOV rule, $π (X')$ be the workpiece ordering of the individual X′ based on the LOV rule, and k is the number of perturbations or explorations. The specific steps of performing a multi-neighborhood local search on individual X are as follows:

The disturbance phase. ① Let k = 0; ② Randomly select 2 different positions p₁ and p₂, $π (X) = Insert (π (X), p_{1}, p_{2})$ , $k = k + 1$ ; ③ If k < 2, return to step ②.

Exploration phase. ① Set k = 0, t = 0; ② randomly choose two different positions p₁ and p₂; if $t = 0, π (X') = Insert (π (X), p_{1}, p_{2})$ , otherwise if $t = 1, π (X') = Interchange (π (X), p_{1}, p_{2})$ , otherwise if $t = 2, π (X') = 2 - opt (π (X), p_{1}, p_{2})$ ; ③ if $π (X') < π (X)$ , then $π (X) = π (X')$ , otherwise t = t+1; ④ if k < 30, skip to step ⑤. Otherwise, stop exploring and output $π (X)$ and $X$ ; ⑤ If t < 3, return to step ②, otherwise t = 0, return to step ②.

Steps of HCS algorithm to solve MOPFSP

The main steps to solve MOPFSP based on the improved HCS algorithm are as follows:

Parameter initialization. Set the population size N; the upper and lower bounds of individuals, and initialize the population W within the bounds; set the maximum number of iterations $g_{ene}$ or the algorithm running time T_r.

Individual discretization. The LOV rule is used to transform continuous individuals into discrete sorting; two objective function values for each individual are calculated.

Individual update. An individual $x_{i}$ is randomly selected, and the individual is updated using Levi’s flight according to equation (11) to generate a new individual $x_{i 1}$ ; the new and old individuals are optimized using non-dominated principle. If they do not control each other, then randomly retained one and stored in $x_{i 1}$ .

Application of abandonment probability. Determine whether to operate on the individual $x_{i 1}$ retained in step (3) according to the discard probability. If you want to operate it, use equation (12) to update and obtain a new individual $x_{i 2}$ . Finally, use the non-dominated principle to optimize the new and old individuals. If they do not control each other, then randomly retained one and stored in $x_{i 1}$ .

Keep the Pareto front. The non-dominated principle is used to find the Pareto front of the current generation, and the individuals of the Pareto front of the current generation are stored in the Pareto solution set $P^{(t)}$ .

Multi-neighborhood search. The multi-neighborhood search is performed on the sort order corresponding to each individual $X^{P^{(t)}}$ in the current generation set $P^{(t)}$ to obtain the updated Pareto solution set $P^{(t)'}$ of this generation

Record the current Pareto solution set. Fuse the updated Pareto solution set $P^{(t)'}$ and the Pareto solution set P retained in the (t − 1)th generation, use the non-dominated principle to find the current t-generation Pareto solution set P, and use this set P instead of the current generation of inferior solution set $P^{(t)'}$ for easy use in the next generation.

The step size control factor $α$ is updated according to equation (14). Each generation must judge and update the step size control factor.

(9) Termination conditions. If the current number of iterations is less than the maximum number of iterations $g_{ene}$ or the evolution time is less than the algorithm running time T_r, repeat steps (2)–(8); otherwise output the current Pareto set P and end the algorithm.

Based on the above steps, the algorithm flow chart of using HC algorithm to solve MOPFSP is shown in Figure 4.

Figure 4.

Flow chart of HCS.

Numerical experiments

In order to verify that the algorithm in this chapter is feasible and effective, this chapter first selects six classic benchmark test functions for verification as shown in Table 2.

Table 2.

Test function.

Function	Dimension	Range	Theoretical value
$f_{1} (x) = \sum_{i = 1}^{d - 1} [{(1 - x_{i})}^{2} + 100 {(x_{i + 1} - {x_{i}}^{2})}^{2}]$	10	$[- 100, 100]$	0
$f_{2} (x) = \sum_{i = 1}^{d} {x_{i}}^{2}$	50	$[- 5.12, 5.12]$	0
$f_{3} (x) = 10 d + \sum_{i = 1}^{d} [{x_{i}}^{2} - 10 \cos (2 π x_{i})]$	20	$[- 5.12, 5.12]$	0
$f_{4} (x) = \sum_{i = 1}^{n} [{x_{i}}^{2} - 10 \cos (2 π x_{i}) + 10]$	10	$[- 5.12, 5.12]$	0
$f_{5} (x) = - \cos (x) \cos (y) \exp [- (x - π)^{2} - (y - π)^{2}]$	2	$[- 100, 100]$	−1
$f_{6} (x) = 1 + \frac{1}{4000} \sum_{i = 1}^{d} {x_{i}}^{2} - Π_{i = 1}^{d} \cos (\frac{x_{i}}{\sqrt{i}})$	100	$[- 600, 600]$	0

In this experiment, a simulation program written in MATLAB 7.1 was used. The operating environment was a Windows 7 professional operating system. The hardware configuration was a Celeron (R) Dual-core CPU T3100, a 1.90 GHZ processor, and a 2G memory laptop.

Among the six benchmark test functions, there are both high-dimensional and low-dimensional functions. Perform 20 independent experiments on each of them to find the minimum, maximum, average, and variance, and compare them with the basic cuckoo algorithm. It can be seen from Table 3 that for the minimum, maximum, or average value of HCS, the calculation accuracy is significantly improved compared with the basic CS. Meanwhile, the optimal solution obtained by HCS is closer to the theory value. The optimal values of functions $f_{1}$ and $f_{6}$ are increased by $10^{- 2}$ , the optimal value of function $f_{2}$ is increased by $10^{- 1}$ , and the optimal value of function $f_{4}$ is increased by $10^{- 5}$ , especially the performance of function $f_{5}$ is more obvious, and the theoretical optimal value is reached each time. From the experimental results, the HCS algorithm proposed in this paper performs well.

Table 3.

Experimental comparison between CS and HCS.

Function	Algorithm	Minimum	Maximum	Average	Variance
$f_{1}$	CS	462.9039	3.1197e + 00	1.4446e + 00	6.7116e + 005
	HCS	4.8562	158.8805	25.4291	1.4115e + 003
$f_{2}$	CS	7.4681	18.0782	11.7679	8.1463
	HCS	0.8318	3.0577	1.8499	0.3465
$f_{3}$	CS	111.8739	131.4907	120.5582	32.4853
	HCS	106.2796	133.0725	114.5563	42.6203
$f_{4}$	CS	2.4898	5.1542	3.3210	0.5428
	HCS	1.5285e − 005	1.1551	0.0580	0.0667
$f_{5}$	CS	−1.0000	−0.9952	−0.9996	1.1418e − 006
	HCS	−1	−1	−1	0
$f_{6}$	CS	121.0992	199.6183	150.3869	511.1894
	HCS	82.7011	147.4886	112.0223	224.0648

The following shows the convergence curve of the average fitness of the six test functions in 20 independent experiments. The ordinate of Figure 9 is the average fitness, while the other graphs are all the log of the average fitness.

Figures 5 to 10 are the convergence curves of the HCS and CS algorithms in this chapter. It can be intuitively seen that the HCS algorithm converges faster than the CS algorithm and has fewer iterations.

Figure 5.

$f_{1}$ Curves of the objective function value.

Figure 6.

$f_{2}$ Curves of the objective function value.

Figure 7.

$f_{3}$ Curves of the objective function value.

Figure 8.

$f_{4}$ Curves of the objective function value.

Figure 9

$f_{5}$ Curves of the objective function value.

Figure 10.

$f_{6}$ Curves of the objective function value.

To further verify the effectiveness and superiority of the HCS algorithm to solve MOPFSP, this paper selects 10 kinds of test instances with different sizes, and use the standard CS algorithm and INSGA-II algorithm³⁷ for comparison experiments.

In the test problem, the processing time of the of the workpiece on each machine is generated according to the size of the problem using random number ranging from [1, 100]; the machine speed gear was set to $A_{i, k} \in {1, 2, 3}$ . In order to find the HCS algorithm parameters with the least number of iterations and the best robustness, four parameters (The step size control factor $α$ , population size, discovery probability $P_{a}$ , and random number $β$ ) that affect the HCS algorithm are selected as control factors. Considering the optimization method of experimental design, each parameter takes three levels: The step size control factor is 0.1, 0.2, and 0.3; the population size is 10, 30, and 50; the discovery probability is 0.25, 0.5, and 0.75; the random number is 0.25, 0.5, and 0.75. Since the experiment has four parameters, the orthogonal test table of L9(34) is selected for experimental research. The specific scheme is shown in Table 4.

Table 4.

Matrix experiments with L9(34).

Experiment number	$α$	$P_{a}$	$β$	Number of population
1	0.1	0.25	0.25	10
2	0.1	0.5	0.5	30
3	0.1	0.75	0.75	50
4	0.2	0.25	0.5	50
5	0.2	0.5	0.75	10
6	0.2	0.75	0.25	30
7	0.3	0.25	0.75	30
8	0.3	0.5	0.25	50
9	0.3	0.75	0.5	10

The Rastrigin benchmark function is used to test the HCS performance, (x, y) ∈ [−5,5]. As shown in Figure 11, this function has many local minimum points in the domain of definition, which has strong oscillation characteristics. During the test, the maximum number of iterations per run is 1000, and the error is less than 10⁻⁶. Each function is optimized 20 times, and then the average number of iterations is taken. The test results are shown in Table 5.

Figure 11.

Space map of Rastrigin function.

Table 5.

The performance of HCS.

Experiment number	1	2	3	4	5	6	7	8	9
Number of iterations	26	46	63	97	88	34	557	316	833
Convergence rate	0.2	0.9	1	1	1	1	0.6	1	0.1

It can be seen from Table 5 that when the step size control factor $α$ , population size, discovery probability $P_{a}$ , and random number $β$ are respectively $α$ = 0.2, population size = 30, $P_{a}$ = 0.75, $β$ = 0.25, the convergence rate of the HCS algorithm is the largest and the number of iterations is relatively small. Therefore, in the experiment, the population size of HCS algorithm is 30; the discovery probability of HCS algorithm is 0.25. On account of the fixed value of step size control factor $α$ is 0.01 in standard CS algorithm, setting the value range of step size control factor to [0.01, 0.2] in the HCS algorithm.

In the INSGA-II algorithm, the mutation probability is 0.3 and the crossover probability is 0.9. In the CS algorithm, the abandonment probability is 0. 25; the step size control factor is 0.01. This paper uses 50n (unit: ms) as the termination condition for each algorithm, where n is the number of work piece of each problem size. This allows all algorithms to run at the same time when testing the same problem size, ensuring fair comparisons. Each algorithm runs independently 20 times for test problem.

The analysis indicators used is this paper are multi-objective analysis indicators proposed in literature,³⁸ which are $R_NDS (S_{r})$ and $NDS_NUM (S_{r})$ respectively, and the calculation equation is as follows:

R_NDS (S_{r}) = | S_{r} - {x \in S_{r} | \exists y \in S : y ≺ x |} / | S_{r} | |

(15)

NDS_NUM (S_{r}) = | S_{r} - {x \in S_{r} | \exists y \in S : y < x |} |

(16)

Where $S_{r}$ refers to the Pareto solution set of the algorithm r; $S$ refers to the union of the Pareto solution set of the K algorithms, which can be expressed as $S = S_{1} \cup \cdot \cdot \cdot \cup S_{r} \cup \cdot \cdot \cdot S_{k}$ ; $y < x$ means that the individual y completely dominates the individual x; $| S_{r} |$ refers to the individuals in the $S_{r}$ set; $NDS_NUM (S_{r})$ refers to the number of undominated individuals in algorithm r; $R_NDS (S_{r})$ refers to the ratio of the number of undominated individuals in algorithm r to the total number of individuals in the Pareto solution set in algorithm r. $R_NDS (S_{r}) = 1$ means all the Pareto individuals in the $S_{r}$ set are not dominated; $R_NDS (S_{r}) = 0.9$ means that 90% of Pareto individuals in $S_{r}$ are not dominated.

The data results of each problem size in this paper can be found in Tables 6 and 7. The comparison data of HCS algorithm and CS algorithm are shown in Table 6. The comparison data of HCS algorithm and INSGA-II algorithm are shown in Table 7. According to the definition of S above, S in Table 6 can be expressed as $S = S_{HC} \cup S_{CS}$ , S in Table 7 can be expressed as $S = S_{HC} \cup S_{INSGA - II}$ ; $R_NDS_HCS$ is the average ratio of 20 $R_NDS (S_{HC})$ data, $R_NDS_CS$ is the average ratio of 20 $R_NDS (S_{CS})$ data, and $R_NDS_INSGA - II$ is 20. The average ratio of $R_NDS (S_{INSGA - II})$ data, $NDS_NUM_CS$ represents the average number of 20 $NDS_NUM (S_{CS})$ data, $NDS_NUM_INSGA - II$ represents the average number of 20 $NDS_NUM (S_{INSGA - II})$ data.

Table 6.

Statistical results of HCS and CS.

Problem size	HCS		CS
	R_NDS_HCS	NDS_NUM_HCS	R_NDS_CS	NDS_NUM_CS
10_5	1	3	0.025	0.05
20_5	1	1	0	0
30_5	1	4	0	0
40_5	1	4.6	0	0
50_10	1	3.05	0	0
60_10	1	2.95	0	0
70_10	1	1.9	0	0
90_20	1	4.85	0	0
90_30	1	4.8	0	0
100_30	1	5.9	0	0

Table 7.

Statistical results of HCS and INSGA-II.

Problem size	HCS		INSGA-II
	R_NDS_HCS	NDS_NUM_HCS	R_NDS_ INSGA-II	NDS_NUM_ INSGA-II
10_5	1	3	0.96	2.85
20_5	0.8	2.6	0.35	0.25
30_5	0.9875	3.95	0.175	0.6
40_5	0.91	3.95	0.3	1.35
50_10	0.925	2.55	0.3	0.85
60_10	0.66	1.9	0.5	1
70_10	0.8	1.6	0.575	1.1
90_20	0.82	3.5	0.379	1.15
90_30	0.8375	4.4	0.2975	0.85
100_30	0.752	3.55	0.59	1.7

It is obvious that $R_NDS_HCS$ is all 1 and $R_NDS_CS$ is almost 0 from Table 6, indicating that when solving the above-mentioned problem size MOPFSP, the HC algorithm completely dominates the standard CS algorithm, and the number of $NDS_NUM_HCS$ is in the range of 3–6, in accordance with the population size of 30; From Table 7, we can see that $R_NDS_HCS$ is greater than $R_NDS_INSGA - II$ , and there are eight problem sizes $R_NDS_HCS$ greater than $R_NDS_INSGA - II$ , indicating that more than 80% of the Pareto individuals of the HC algorithm dominate the Pareto individuals of the INSGA-II algorithm, while in the other two problem sizes, The ratio is above 65%. The operation of size 10_5 and size 100_30 are shown in Figures 12 and 13. It is obvious that although the Pareto solution set found by the INSGA-II algorithm and the HC algorithm overlap, they all dominate the standard CS algorithm. It can be seen from Figure 12 that the Pareto front of the HCS algorithm is at the bottom left of the other two algorithms, indicating that the Pareto solution set of the HC algorithm completely controls the Pareto solution set of the other two algorithms. As the size of the problem increases, compared with the standard CS algorithm and INSGA-II algorithm, the distance between the Pareto front of the HCS algorithm and the Pareto front of the other two algorithms increases, and the superiority of optimization is more and more obvious.

Figure 12.

A Pareto solution point graph of three algorithms when the problem size is 10_5.

Figure 13.

A Pareto solution point graph of three algorithms when the problem size is 100_30.

The comparison results between the INSGA-II and HCS from running times are shown in Figure 14. We can clearly see that the running time of INSGA-II is much longer than HCS when the size of instances is large, and INSGA-II get fewer effective solution compare to HCS. Therefore, the HCS algorithm has better solution speed when solving large-size instances problem.

Figure 14.

Running time of algorithms.

To sum up, HCS algorithm is more efficient than INSGA-II algorithm and CS algorithm in solving MOPFSP of all the above problem sizes.

At the same time, the HCS algorithm was used to investigate the wire and cable production scheduling problem of a wire and cable factory in Jiangsu Changzhou. The production process of the factory’s pre-formed cable consists of five steps: monofilament drawing, monofilament annealing, conductor stranding, insulation extrusion, and cable formation. The five links are processed on five specific machines, and the processing machines in each link can set the processing speed by adjusting the gear. In recent years, the company has actively responded to green production, energy saving, and energy reduction, and considered both economic indicators (makespan) and environmental indicators (TCE) in its production process. Obviously, the production scheduling problem of this pre-formed cable is a typical MOPFSP. At present, the production scheduling of this cable factory is manually ordered and scheduled by the dispatcher based on experience after number the work piece. This paper uses the actual production data of 30 types of cables produced by the factory as test examples, and uses the HCS algorithm to run a 1.5 s solution. The target value comparison of HCS algorithm is shown in Figure 15.

Figure 15.

HCS target value comparison.

Furthermore, the dispatcher is asked to give a manual dispatching plan within 5 min. The HCS algorithm obtained the scheduling scheme S1–S4. The scheduling scheme T1 obtained by dispatcher through experience is shown in Table 8. As can be seen from Table 8, S1–S4 are significantly better than T1. The results show that the HCS algorithm can solve practical MOPFSP problems quickly and effectively.

Table 8.

Scheduling plan.

Plan	Work piece scheduling sort														C _max	TCE
	1	2	3	4	5	6	7	8	9	10	11	12	13	14
	16	17	18	19	20	21	22	23	24	25	26	27	28	29
T1	27	26	15	8	2	25	10	4	11	7	18	14	21	28	1108	9764930
	3	6	9	20	30	5	29	19	23	16	13	12	1	17
S1	18	12	28	24	10	5	15	2	27	9	26	4	11	8	1035	9750170
	29	16	23	25	3	30	7	21	20	1	13	6	14	17
S2	18	12	27	2	24	10	5	15	9	26	21	29	23	28	1039	9749536
	16	25	30	7	4	22	8	1	20	19	13	14	3	6
’S3	18	27	2	12	24	10	5	15	26	21	29	20	8	22	1056	9744074
	11	16	25	30	9	28	23	19	1	6	14	3	17	13
S4	18	28	9	26	15	5	10	24	27	12	2	4	8	19	131042	9748265
	16	25	30	7	21	20	11	1	22	23	3	6	14	17

Conclusion

Nowadays, with the increasingly severe environmental problems in the manufacturing industry, the green manufacturing has received considerable attention. Although the flow shop scheduling problem has been widely studied in recent years, but the research on multi-objective flow shop scheduling with green indicators is still relatively limited. In this research a hybrid cuckoo algorithm is proposed to solve the green MOPFSP with environmental indicators, which meets the current needs of ecological environment governance. The main contributions of this paper are as follows:

The LOV rule is used to transform the individuals in the HCS algorithm from the real number vector to the workpiece ordering, so that it can be easily searched in the solution space of MOPFSP;

An adaptive step size control factor is designed to control the search range of the evolution phase of the algorithm and makes the algorithm easy to find high-quality individuals in the later stages of evolution;

An multi-neighborhood local search method is proposed for detailed search of high-quality solution regions, so that the high-quality solution area found by the global search of the HCS algorithm can be searched more carefully;

The HCS algorithm uses the proposed adaptive step size control factor and multi-neighborhood local search to balance the global and local search of the algorithm, and improves the performance and convergence speed of the algorithm. The results of simulation and algorithm comparison show that HCS algorithm can solve MOPFSP quickly, and its performance is better than CS algorithm and INSGA-II algorithm. The effectiveness of the HCS algorithm in solving MOPFSP is verified.

Some future works may be done from following aspects: (1) Regarding the future research of cuckoo algorithm in complex production scheduling, we can consider extending it to more complex scheduling problems than MOPFSP, especially the uncertain green scheduling problem. (2) It is interesting to present some heuristic algorithms to generate initial population instead of random procedure used in this paper so as to further improve the algorithms performance.

Footnotes

Acknowledgements

The authors would like to thank the referees for their helpful comments and suggestions.

Handling Editor: James Baldwin

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This paper is supported by National Science Foundation of China (No. 51875171), and the Fundamental Research Funds for the Central Universities (2019B21614).

ORCID iD

Wenbin Gu

References

Fang

Uhan

Zhao

, et al. A new approach to scheduling in manufacturing for power consumption and carbon footprint reduction. J Manuf Syst 2011; 30(4): 234–240.

Cui

. Multi-objective flexible flow shop scheduling problem with renewable energy. Comput Integr Manuf Syst 2018; 24: 2792–2807.

Fang

Nelson

, et al. Flow shop scheduling with peak power consumption constraints. Ann Oper Res 2013; 206(1): 115–145.

Yang

Deb

. Multi-objective cuckoo search for design optimization. Comput Oper Res 2013; 40: 1616–1624.

Yenisey

Yagmahan

. Multi-objective permutation flow shop scheduling problem: Literature review, classification and current trends. Omega 2014; 45:119–135.

. Multi-objective discrete artificial bee colony algorithm for multi-objective permutation flow shop scheduling problem with sequence dependent setup times. IEEE Trans Eng Manage 2017; 64(2): 149–165.

Wang

Tang

. A machine-learning based memetic algorithm for the multi-objective permutation flowshop scheduling problem. Comput Oper Res 2017; 79: 60–77.

Luo

Huang

, et al. Hybrid flow shop scheduling considering machine electricity consumption cost. Int J Prod Econ 2013; 146: 423–439.

Ding

Song

, et al. Carbon efficient scheduling of flow shops by multi-objective optimization. Eur J Oper Res 2016; 248: 758–771.

10.

Liu

Huang

. Reduction of power consumption and carbon footprints by applying multi-objective optimization via genetic algorithms. Int J Prod Res 2014; 52: 337–352.

11.

Ding

Song

. Carbon efficient scheduling of flow shops by multi-objective optimization. Eur J Oper Res 2015; 248: 1–14.

12.

Tang

. Energy-efficient dynamic scheduling for a flexible flow shop using an improved particle swarm optimization. Comput Indus 2015; 81: 82–95.

13.

. Energy-efficient permutation flow shop scheduling problem using a hybrid multi-objective backtracking search algorithm. J Clean Prod 2017; 144: 228–238.

14.

Wang

Tian

. Dual-objective program and improved artificial bee colony for the optimization of energy-conscious milling parameters subject to multiple constraints. J Clean Prod 2020; 245: 118–129.

15.

Tian

. Stochastic multi-objective modelling and optimization of an energy-conscious distributed permutation flow shop scheduling problem with the total tardiness constraint. J Clean Prod 2019; 226: 515–525.

16.

Yang

Deb

. Cuckoo search via Lévy flights. In: Proceedings of world congress on nature & biologically inspired computing, India, 29 December 2009, pp.210–214. IEEE Publications.

17.

Wang

Zhong

Yin

. Orthogonal crossover cuckoo search algorithm with external archive. J Comput Res Dev 2015; 52: 2496–2507.

18.

Sheli

Chaudhuri

. Cuckoo search algorithm using lèvy flight: a review. Mod Educ Comput Sci 2013; 12: 10–15.

19.

Yin

. A hybrid cuckoo search via lévy flights for the permutation flow shop scheduling problem. Int J Prod Res 2013; 51: 4723–4754.

20.

Marichel

Prabaharan

Yang

. Improved cuckoo search algorithm for hybrid flow shop scheduling. Appl Soft Comput J 2014; 19: 93–101.

21.

Alaa

Alobaidi

. Two improved cuckoo search algorithm for solving the flexible job shop scheduling problem. Int J Percept Cogn Comput 2016; 2: 25–31.

22.

Wang

Sun

, et al. A new cuckoo search algorithm with hybrid strategies for flow shop scheduling problem. Soft Comput 2017; 21: 4297–4307.

23.

Zhang

Wang

Q-D

. Dynamic adaptation cuckoo search algorithm. Control Decis 2014; 29: 617–622.

24.

Gao

, et al. Energy-efficient permutation flow shop scheduling problem using a hybrid multi-objective backtracking search algorithm. J Clean Prod 2017; 144: 228–238.

25.

Wang

Huang

. A species based multi-objective evolutionary algorithm for multi-objective flow shop scheduling problem. In: 2015 IEEE congress on evolutionary computation, Sendai, Japan, 25–28 May 2015, pp.3243–3247, IEEE.

26.

Wan

Wang

, et al. Band selection based on chaotic cuckoo search algorithm for hyperspectral image. Microelectron Comput 2018; 35: 124–129.

27.

Nasiri

Yazdan

Jolai

. Simulation optimization approach for optimizing jobs dispatching rule in an open shop scheduling problem. Int J Comput Integr Manuf 2017; 30: 1239–1252.

28.

Bai

Zhang

. Flexible open shop scheduling problem to minimize makespan. Comput Oper Res 2015; 67: 207–215.

29.

. Multi-objective local search algorithm-based decomposition for multi-objective permutation flow shop scheduling problem. IEEE Trans Eng Manage 2015; 62: 544–557.

30.

Sha

Hsu

. A new particle swarm optimization for the open shop scheduling problem. Comput Oper Res 2008; 35: 3243–3261.

31.

Zheng

Zhou

. A novel cuckoo search optimization algorithm base on gauss distribution. J Comput Inform Syst 2012; 8: 1–8.

32.

Zhu

Wang

. Cuckoo search algorithm with RNA crossover operation for PID control of overhead cranes. J Zhejiang Univ 2017; 51: 1397–1404.

33.

Mang

. Two-dimensional Renyi gray entropy image threshold selection based on chaotic cuckoo search optimization. CAAI Trans Intell Syst 2018; 13(1): 152–158.

34.

Zhang

, et al. The study onimage matching method based on cuckoo search. J Zhengzhou Univ 2017; 49(4): 51–56.

35.

Daniel

Anitha

Gnanaraj

. Optimum laplacian wavelet mask based medical image using hybrid cuckoo search-grey wolf optimization algorithm. Knowl Based Syst 2017; 131: 58–69.

36.

Tao

Zhang

Xin

, et al. Optimal valve control in water distribution systems based on cuckoo search. J Tongji Univ 2016; 44: 600–604.

37.

Wang

. An improved non-dominated sorting genetic algorithm for multi objective problem. Math Probl Eng 2016; 2006: 1–7.

38.

Qian

Rong

, et al. A hybrid differential evolution algorithm for the multi objective reentrant job-shop scheduling problem. In: IEEE international conference on control and automation (ICCA), Hangzhou, China, 12–14 June 2013, pp.485–489, IEEE.

An energy-efficient multi-objective permutation flow shop scheduling problem using an improved hybrid cuckoo search algorithm

Abstract

Keywords

Introduction

Problem statement

Low carbon MOPFSP descriptions

Related concepts of multi-objective problem

Hybrid cuckoo algorithm

Standard Cuckoo algorithm

Hybrid cuckoo algorithm

Adaptive step size factor

Multi-neighborhood local search

Steps of HCS algorithm to solve MOPFSP

Numerical experiments

Conclusion

Footnotes

Acknowledgements

Declaration of conflicting interests

Funding

ORCID iD

References