A multi-objective flexible job-shop cell scheduling problem with sequence-dependent family setup times and intercellular transportation by improved NSGA-II

Abstract

With the development of Industry 4.0 and requirement of smart factory, cellular manufacturing system (CMS) has been widely concerned in recent years, which may leads to reducing production cost and wip inventory due to its flexibility production with groups. Intercellular transportation consumption, sequence-dependent setup times, and batch issue in CMS are taken into consideration simultaneously in this paper. Afterwards, a multi-objective flexible job-shop cell scheduling problem (FJSCP) optimization model is established to minimize makespan, total energy consumption, and total costs. Additionally, an improved non-dominated sorting genetic algorithm is adopted to solve the problem. Meanwhile, for improving local search ability, hybrid variable neighborhood (HVNS) is adopted in selection, crossover, and mutation operations to further improve algorithm performance. Finally, the validity of proposed algorithm is demonstrated by datasets of benchmark scheduling instances from literature. The statistical result illustrates that improved method has a better or an equivalent performance when compared with some heuristic algorithms with similar types of instances. Besides, it is also compared with one type scalarization method, the proposed algorithm exhibits better performance based on hypervolume analysis under different instances.

Keywords

Cellular manufacturing system flexible job-shop cell scheduling intercellular transportation times sequence-dependent family setup time energy consumption multi-objective optimization

Introduction

With the globalization of market, the increased level of competition puts forward higher requirement for manufacturing systems, how to quicker and accurate response to customers’ desiring to purchase multiple varieties of high-quality and low-cost products is an urgent problem. Consequently, production mode of multi-variety and small-batch in manufacture has received widespread attention recently by most manufacturing firms. Meanwhile, flexible manufacturing^1,2 is developed to meet such challenges. As an application of group technology, cellular manufacturing system (CMS)^3,4 can handle production control in each cell independently, which outperforms traditional system in reducing production cost, production time, and wip inventory,^5–7 especially in the semiconductor industry.^8,9 Temporarily, lot-splitting process in CMS can respond rapidly to requirement of production mode of multi-variety and small-batch. Besides, manufacturing industry is facing challenges of energy conservation and emission reduction currently. Therefore, CMS considering lot-splitting process and energy consumption is most effective production way to ward multi-variety and small-batch energy-saving production.

In CMS, different machines and jobs are aggregated into one cell, which possesses the capability of processing the production of part families. However, in contrary to original intention of CMS, assigning all machines and parts in the same cell, it is difficult to achieve in practice, that is, some exception parts (EP), are permitted to be machined in more than one cell for reducing number of dedicated machines. For example, in wafer pretreatment of semiconductor manufacturing, some successive operations of wafer need to be processed between expensive and fixed machines among different cells, which leads to intercellular transportation and prolongs makespan of cell parts scheduling (CPS), which plays a crucial role in the operation of CMS. Hence, parts inter-cell processing is beneficial for enterprises to reduce machine costs. But it brings task for CPS, of which the goal is to determine a part sequence and minimize some effectiveness measures, such as makespan and total transportation cost.^10–13

Furthermore, with the rapid development of green manufacturing technology, energy saving, and emission reduction has become an unavoidable consideration for enterprises. In recent years, more scholars have paid attention to energy consumption of semiconductor industry. Hu et al.¹⁴ proposed energy savings approaches for high-tech manufacturing factories for a semiconductor manufacturing wafer fab. Wang et al.¹⁵ proposed a fuzzy nonlinear programing approach for planning energy-efficient wafer fabrication factories, thereinto, the total power consumption is obtained by summing the power consumptions of all the products in wafer fab. Lin et al.¹⁶ investigated a flow shop scheduling problem with low carbon emission into consideration. For specific scheduling problems, Li et al.¹⁷ studied a multi-objective energy-saving scheduling in a permutation flow line shop. Iqbal et al.¹⁸ developed a mathematical model to minimize the idle energy based on job sequence in a cellular manufacturing system. However, energy consumption is seldom attempted in FJCSP. Besides, due to the inevitable intercellular transportation in CMS, energy consumption is becoming more complicated in modern manufacturing system. Therefore, in this study, energy consumption is calculated as an objective, so as to acquire a scheduling scheme which can provide a better energy saving and emission reduction scheduling scheme.

Besides, jobs are usually grouped into different part families, which generates setup times between two different families on machines in CMS. Li et al.¹⁹ assumed setup time is sequence-independent and included it in the processing time of CMS minimized the makespan and balance the total workload in CMS with consideration sequence-independent setup times, machine sharing, and flexible routes to solve a CPS problem. However, in practical production, setup times between different parts tend to be related to the sequence of them. Sequence-dependent setup times (SDST) are widely studied especially in traditional manufacturing system. Costa et al.²⁰ developed a hybrid genetic algorithm to minimize the makespan with SDST in a flow-line shop. Abdelmaguid²¹ and Shen et al.²² taken SDST into consideration to solve flexible job shop scheduling problem (FJSP). It can be inferred from the above literature most studies focus on sequence-independent in CMS, sequence-dependent in traditional FJSP, and flowline cell scheduling. Few references can be found to combine SDST with FJCSP. Considering SDST adds complexity to CMS, but it is more suitable for actual production, such as semiconductor wafers process.⁹ Meanwhile, in some real production process, job needs to be split into several batches. For instance, production unit in semiconductor manufacturing is called a wafer but the process comprises the concurrent processing of several wafers, where one lot contains at most 25 wafers.²³ Investigation shows that batch processing can lead to the reduction of makespan, which is better than overall processing of part families.²⁴ Xu²⁵ studied the quality control of multi-variety mixed in production shopfloor. Huang and Yu²⁶ mentioned that applications of lot-splitting in manufacturing processes may increase complexity of scheduling but are rewarding for efficiency and flexibility of scheduling results under some manufacturing circumstances, such as printing, paints, or chemical production. Defersha and Bayat Movahed²⁷ developed a linear programing model with lot streamlining in flexible job shop. Vaez et al.²⁸ proposed a mathematical model with consideration lot-sizing in scheduling problem, which aimed to minimize CO₂ emissions while maximize the total profit. However, batch issue is only widely attempted in traditional shop scheduling and few researches about batch can be found in FJCSP. Accordingly, to fill up above gaps, SDST and job batch are considered in this paper.

Due to global searching capability, genetic algorithm (GA) is an effective tool to solve single objective optimization problem in mechanical engineering and production process.²⁹ Furthermore, nondominated sorting genetic algorithm (NSGA-II) is served as a multi-objective optimization algorithm to seek for a Pareto-optimal set in shop scheduling and mechanical manufacturing (e.g. mechanical cooling tower).^30–34 However, pure dominance-based multi-objective evolutionary algorithm (MOEA) such as NSGA-II usually have the deficiency of solution diversity.³⁵ In previous studies, local search techniques were designed to improve the quality of local area individuals and they were incorporated into the MOEA to improve the solution diversity.³⁶ More researchers embedded local search into heuristic algorithms to improve performance of algorithm. For instance, Wu and Che³⁷ investigated an adaptive multi-objective VNS to deal with flow shop scheduling problem and verified performance of proposed algorithm was better than NSGA-II. An et al.³⁸ adopted hybrid VNS into improved biogeography-based optimization (BBO) algorithm to amend local search ability in a hybrid multi-objective FJSP. Therefore, in this study, a hybrid variable neighborhood search (HVNS) is utilized to enhance the local searching capability of NSGA-II to deal with the multi-objective optimization problem.

Based on aforesaid discussion, previous work generally considered classical objectives (e.g. makespan, cost) in flowline cell scheduling, or cogitated setup times and batch but neglect energy consumption in FJCSP. Simultaneous consideration of intercellular transportation consumption, sequence-dependent setup times, and batch sizes in flexible job-shop cell scheduling has not yet done. Meanwhile, since FJSP is a more complicated NP-hard problem than job shop scheduling, this brings new challenge to FJCSP optimization.³⁹ The main contribution of this paper can be summarized as: (1) to better react to green manufacturing and requirement of production mode, a novel mathematical model is proposed for FJCSP by taking makespan, total cost, and total energy consumption into consideration; (2) to enhance local search ability of NSGA-II for solving complex FJCSP, a HVNS is designed to amend performance of algorithm; (3) to verify the validity of proposed algorithm, comparisons with six heuristic methods based on benchmark instances and another kind of method from literature is analyzed.

The rest of this paper is arranged as follows. Section 2 provides the basic elements of FJCSP. In Section 3, HVNS, elite storage strategy (ESS), and improved algorithm framework is introduced in detail. Section 4 analyzes the effectiveness of improved algorithm by comparisons with seven algorithms. Section 5 presents the conclusions and future directions.

Problem description and formulation

In this section, the problem is descripted at first. After that, some basic assumptions are provided, as well as the related notations are utilized in this study. Next, the formulas about total energy consumption and total costs are displayed to show the computation of each component. Finally, a multi-objective optimization model is established.

Problem description

In FJCSP, there exist two sets, that is, a set includes $n$ jobs $J = {J_{1}, J_{2}, \dots, J_{n}}$ and a set composed of $m$ machines $M = {M_{1}, M_{2}, \dots, M_{m}}$ . For each job $J_{i}$ , the sequence of processing consists of $n_{i}$ sequential operations ${O_{i, 1}, O_{i, 2}, \dots, O_{i, n_{i}}}$ . In this study, jobs can be classified into multiple parts. At the same time, each job in per part is processed in two equal batches, which means that each batch of job $J_{i}$ also has $n_{i}$ consecutive operations. Especially, flexible processing route of FJSP will result in that at least one operation $O_{ij}^{b}$ can be processed on multiple machines, that is, alternative machine set ${AMS}_{i, j}^{b}$ . Furthermore, processing time and energy consumption of identical operation vary regarding different machines. Thus, three problems are contained in FJCSP: (1) machine selection (MS), due to each $O_{ij}^{b}$ will be processed on the appropriate machine $M_{k}$ selected from the set ${AMS}_{i, j}^{b}$ ; (2) operation sequence (OS): because at least one machine have the ability of process several different operations, it is necessary to optimize the sequence of processing operation on each machine to acquire a less makespan; (3) intercellular transportation (IT): some exceptional parts are essential to be processed in more than two cells, which would create intercellular transportation energy consumption. In addition, due to jobs are classified into parts, there exists sequence-dependent setup time between different parts.

Assumptions and notations

To concentrate the study of FJSP in CMS, the model is based on following assumptions.

(a) The number of cells, part families, and layout of cell is known.

(b) Machine fault is ignored.

(d) All jobs have the same priority.

(e) The buffer of input and output is not limited.

(f) Each operation can be distributed to one of available machines.

(g) The processing time of operations for each part family on machines is known.

(h) The machines and jobs are available at time 0.

(i) The intracellular transportation time is 0.

(j) Each machine can process at most one operation.

The symbols, parameters, and variables are listed, as shown in Table 1.

Table 1.

The variables and parameters involved in the model.

Symbol descriptions
Indices
$i, a$	The index for jobs, $i, a = 1, 2, \dots, n$ .
$j, l$	The index for operations of jobs, $j, l = 1, 2, \dots, \max {n_{i}, n_{a}}$ .
$g, k, h$	The index for machines, $g, k, h = 1, 2, \dots, m$
$b$	The index for batches, $b \in {1, 2, \dots, B} .$
$c$	The index for cells, $c \in {1, 2, \dots, N} .$
$f$	The index for part families, $f \in {1, 2, \dots, F} .$
Parameters
$m$	The number of machines
$n$	The number of jobs
$B$	The number of batches
$F$	The number of part families
$N$	The number of cells
$n_{i}$	The number of the operations for job $i$ , $i = 1, 2, \dots, n$
$D_{i}$	The demand of job $i$
$x_{ib}$	Production quantity of $b^{th}$ batch of job $i$ , $i = 1, 2, \dots, n$ , $b = 1, 2, \dots, B .$
$O_{ik}$	The job $i$ processed on machine $k$
$O_{ij}^{b}$	The batch $b$ in operation $j$ from job $i$
$O_{ijk}^{b}$	The batch $b$ in operation $j$ from job $i$ processed on machine $k$
$F_{i}$	Finish time of $O_{i}$
$F_{ik}$	Finish time of $O_{ik}$
$F_{ik}^{b}$	Finish time of $O_{ik}^{b}$
$S_{ik}^{b}$	Start time of $O_{ik}^{b}$
$P_{ik}^{b}$	Processing time of $O_{ik}^{b}$
$p_{k}$	The processing power of machine $k$ per unit time
$p_{ijk (j + 1) h}^{b}$	The intercellular transportation power of machines between $O_{ijk}^{b}$ and $O_{i (j + 1) k}^{b}$ per unit time
$T_{cc'}$	The intercellular transportation time from cell $c$ to cell $c'$
$S_{ff'}$	Setup time for part family $f'$ if processed immediately after part family $f$
$h_{cost}$	The handling cost of each batch
$M$	A large positive number
$T_{ijk}^{b}$	The processing time of $O_{ijk}^{b}$
$c_{k}$	The processing cost of on machine $k$ per unit time
$c_{setup}$	The setup cost per unit time
$C_{\max}$	The makespan
$Q$	The total energy consumption
$Q_{ck}$	The total processing energy consumption
$Q_{dk}$	The total intercellular transportation energy consumption
Decision variables
$w_{ijk}^{b}$	If $O_{ij}^{b}$ processed on machine $k$ in a flexible environment, $w_{ijk}^{b} = 1$ ; otherwise $w_{ijk}^{b} = 0$ .
$u_{ijalk}^{b_{1} b_{2}}$	If $O_{ij}^{b_{1}}$ precedes $O_{al}^{b_{2}}$ on machine $k$ , $u_{ijalk}^{b_{1} b_{2}} = 1$ ; otherwise $u_{ijalk}^{b_{1} b_{2}} = 0$ .
$X_{kc}$	If machine $k$ is located in cell $c$ , $X_{kc} = 1,$ ; otherwise $X_{kc} = 0$ .
$Y_{if}$	If job $i$ belongs to part family $f$ , $Y_{if} = 1$ ; otherwise $Y_{if} = 0$ .
$x_{ijk}^{b}$	If $O_{ij}^{b}$ processed on machine of number $k$ , $x_{ijk}^{b} = 1$ ; otherwise $x_{ijk}^{b} = 0$ .

Objective function

In this paper, the objective function of the optimization model is to minimize makespan, total energy consumption, and total costs.

Makespan

The first objective makespan $f_{1}$ equals the largest finish time of all jobs.²⁶ That is, the time the last job finished is the makespan of the schedule.

\begin{matrix} f_{1} = max_{i} {max_{k} {max_{b} {S_{ik}^{b} + P_{ik}^{b}}}}, i = 1, 2, \dots, n, \\ b \in {1, 2, \dots, B}; k = 1, 2, \dots, m . \end{matrix}

(1)

Total energy consumption

The second objective total energy consumption $f_{2}$ equals the sum of the processing energy consumption $Q_{ck}$ and transportation energy consumption $Q_{dk}$ , which is shown in equation (2). Thereinto, the processing energy consumption $Q_{ck}$ is sum of processing time of each batch multiplied by energy consumption per unit processing time on each machine, the transportation energy consumption $Q_{dk}$ is sum of intercellular transportation time of two successive operation of each batch multiplied by the transportation power of machines.

f_{2} = Q_{ck} + Q_{dk},

(2)

where

Q_{ck} = \sum_{k = 1}^{m} p_{k} (\sum_{i = 1}^{n} \sum_{b = 1}^{B} \sum_{j = 1}^{n_{i}} x_{ijk}^{b} T_{ijk}^{b}),

(3)

\begin{matrix} Q_{dk} = \sum_{i = 1}^{n} \sum_{j = 1}^{n_{i} - 1} \sum_{b = 1}^{B} \sum_{k = 1}^{m} \sum_{h = 1}^{m} \sum_{c = 1}^{N} \sum_{c^{'} = 1}^{N} x_{ijk}^{b} X_{kc} x_{i (j + 1) h}^{b} \\ X_{h c^{'}} T_{c c^{'}} p_{ijk (j + 1) h}^{b}, \end{matrix}

(4)

Total cost

The total costs $f_{3}$ includes the processing time cost $C_{M}$ , setup costs $C_{setup}$ , and batch costs $C_{sublot}$ , which is shown in equation (5), where $C_{M}$ is equal to the total processing time when machines are not idle multiplied by the cost per unit processing time, $C_{setup}$ equals total setup time between two successive operation of all batches multiplied by the setup cost per unit time, $C_{sublot}$ is equivalent to sum of number of all batches times handling cost of each batch.²⁶

f_{3} = C_{M} + C_{setup} + C_{sublot},

(5)

C_{M} = \sum_{k = 1}^{m} c_{k} (\sum_{i = 1}^{n} \sum_{j = 1}^{n_{i}} \sum_{b = 1}^{B} x_{ijk}^{b} T_{ijk}^{b}),

(6)

\begin{matrix} C_{setup} = \sum_{k = 1}^{m} \sum_{i = 1}^{n} \sum_{j = 1}^{n_{i}} \sum_{b = 1}^{B} \sum_{a = 1}^{n} \sum_{l = 1}^{n_{a}} \sum_{b_{2} = 2}^{B} \sum_{f = 1}^{F} \sum_{f^{'} = 1}^{F} \\ x_{ijk}^{b_{1}} x_{alk}^{b_{2}} Y_{if} Y_{af'} S_{ff'} c_{setup}, \end{matrix}

(7)

C_{sublot} = \sum_{i = 1}^{n} n_{i} B h_{cost},

(8)

Constraints

Optimization model include batch constraints, sequence constraints, and time constraints, which are shown in equations (9)–(15).

x_{ib} = D_{i} / B,

(9)

\sum_{k = 1}^{m_{ij}} w_{ijk}^{b} = 1,

(10)

w_{ijk}^{b} \leq x_{ijk}^{b},

(11)

\begin{matrix} \sum_{k = 1}^{m} w_{alk}^{b_{2}} S_{alk}^{b_{2}} \geq F_{ijk}^{b_{1}} + \sum_{f = 1}^{F} \sum_{f^{'} = 1}^{F} Y_{if} Y_{a f^{'}} S_{f f^{'}} \\ - {Mu}_{ijalk}^{b_{1} b_{2}} - M (2 - x_{ijk}^{b_{1}} - x_{al k}^{b_{2}}), \end{matrix}

(12)

\begin{matrix} \sum_{k = 1}^{m} w_{ijk}^{b_{1}} S_{ijk}^{b_{1}} \geq F_{al k}^{b_{2}} + \sum_{f = 1}^{F} \sum_{f^{'} = 1}^{F} Y_{a f^{'}} Y_{if} S_{f^{'} f} \\ - {Mu}_{alijk}^{b_{2} b_{1}} - M (2 - x_{ijk}^{b_{1}} - x_{al k}^{b_{2}}), \end{matrix}

(13)

\begin{matrix} \sum_{k = 1}^{m} w_{ijk}^{b_{1}} S_{ijk}^{b_{1}} \geq \sum_{k = 1}^{m} \sum_{k = 1}^{m} \sum_{g = 1}^{m} w_{ijk}^{b_{1}} w_{i (j - 1) k}^{b_{1}} \\ (F_{i (j - 1) k}^{b_{1}} + \sum_{c = 1}^{C} \sum_{c^{'} = 1}^{C} X_{kc} X_{g c^{'}} T_{c^{'} c}), \end{matrix}

(14)

F_{ijk}^{b} = S_{ijk}^{b} + T_{ijk}^{b} .

(15)

In the model, equation (9) indicates that the batch size is same for each job. Equation (10) indicates that only one machine can be selected for $O_{ij}^{b}$ . Equation (11) illustrates that value of $w_{ijk}^{b}$ is 0 or 1. If $O_{ij}^{b}$ processed on machine of number $k$ , that is to say, $x_{ijk}^{b} = 1$ , value of $w_{ijk}^{b}$ can be 0 or 1; otherwise, value of $w_{ijk}^{b}$ can only be 0. Equations (12) and (13) show that start time of $O_{ijk}^{b_{1}}$ depends on the sequence of operations between $O_{ijk}^{b_{1}}$ and $O_{alk}^{b_{2}}$ and sequence-dependence setup times. Equation (14) indicates that the start time of $O_{ij}^{b_{1}}$ depends on the defined precedence of its operation $O_{i (j - 1)}^{b_{1}}$ and sequence-dependent setup times. Equation (15) displays that finish time of $O_{ijk}^{b}$ equals the start time of $O_{ijk}^{b}$ plus processing time of $O_{ijk}^{b}$ .

Illustrative example

To better understand the model, we combine with one 4/2/4/2 instance from literature¹³ to illustrate. Thereinto, there are four parts, two part families, four types of machines, and two cells independently, which is shown in Table 2. The two part families are presented as: [ $J_{1}$ , $J_{2}$ ], [ $J_{3}$ , $J_{4}$ ]. The jobs in the same square bracket means the jobs are in same family. Meanwhile, there exists setup time between different families. In addition, the four types of machines are presented as: [ $M_{1}$ , $M_{2} (2)$ ], [ $M_{3} (2)$ , $M_{4}$ ], which are distributed seperately in two cells. Thereinto, $M_{3} (2)$ means that there are two identical parallel machines for machine 3. Therefore, there are six machines in this instance. Finally, based on the above model, we give one Gantt chart of 4/2/4/2 instance, which is shown in Figure 1. In this paper, each job is divided into two equal batches, therefore, the index $J a^{b}, c$ in Gantt chart symbolizes that $c^{th}$ operation in $b^{th}$ batch of job $a$ . Besides, pure gray part in the Gantt chart represents sequence-dependent family setup time.

Table 2.

The data of 4/2/4/2 instance.

Cell number	Cell 1	Cell 2
Machine number	M1, M2(2)	M3(2), M4
Family number	Part family 1	Part family 2
Job number	job1, job 2	job 3, job 4

Figure 1.

The first solution of 4/2/4/2 instance ( $f_{1} = 19.5, f_{2} = 160.5, f_{3} = 330.5$ ).

Method and algorithm

In this section, a brief description of the standard NSGA-II and improvement motivation are introduced at first. Then, a hybrid variable neighborhood search is provided. Last, the overall process of proposed HVNS-NSGA-II with specific improvements is summarized.

NSGA-II and improvement motivations

NSGA-II⁴⁰ is served as a multi-objective optimization algorithm to seek for a Pareto-optimal set. In the whole process of NSGA-II, the most core operations owe to the calculation of fast non-dominated sorting and crowding distance. The former one, that is, fast non-dominated sorting, ensures the convergence of the solutions. When the solution is closer to the Pareto-optimal front, it shows a better quality. The latter one, that is, crowding distance, keeps diversity of population.

Hybrid variable neighborhood search (HVNS)

Variable neighborhood search (VNS) is presented by Mladenović and Hansen⁴¹ firstly, which was used to avoid poor local optimization by changing neighborhood systematically and had been rapidly and successfully adopted in various fields. Recently, VNS has been widely studied in shop scheduling problems,⁴² such as job-shop scheduling problem (JSP).

There are several neighborhood structures in VNS.⁴³ Thereinto, machine-oriented idle time neighborhood, N5 neighborhood, random whole neighborhood (RWN) are adopted into NSGA-II. Compared with other neighborhood structures, the first structure is more complex and efficient. Figures 2 and 3 illustrate the operation movement of the same machine and cross-machine by a Gantt chart, respectively. In Figure 2, transferring operation $O_{1, 1}$ before $O_{2, 2}$ on the same machine, the makespan can decline from 18 to 12. In Figure 3, if moving operation $O_{3, 3}$ on machine $M_{1}$ to the position after $O_{1, 1}$ on machine $M_{2}$ , the makespan declines from 18 to 15. It’s noted that the processing time of operation $O_{3, 3}$ on machine $M_{2}$ has been changed to 3. As a consequence, it can be seen that makespan can be reduced by machine-oriented idle time neighborhood structure.

Figure 2.

Operation movement on the same machine: (a) original Gantt chart and (b) changed Gantt chart.

Figure 3.

Operation movement across machines: (a) original Gantt chart and (b) changed Gantt chart.

The proposed HVNS-NSGA-II

Encoding and decoding

In general, chromosomes are encoded according to real operations and machines in FJSP. OS of the chromosome is encoded by number of job. For example, the second “3” in OS [3 1 2 2 1 3] stands for the second operation of job $J_{3}$ . The occurrence times of job number mean the number of operations. However, chromosome of MS is index of the machine instead of machine names. For example, the second “3” in MS [1 3 2 3 2 1] denotes that the $O_{2, 2}$ will be processed on the third machine in the constituted alternative set $AMS = {M_{1}, M_{2}, M_{3}}$ , which is equals to $M_{3}$ under this circumstance. To make it easier to understand, Table 3 shows the production data of an instance. Accordingly, the encoding processing is listed in Figure 4. And the scheduling Gantt chart related to the chromosome is shown in Figure 2(a). During the chromosome decoding, all operations are assigned to machine from left to right, the start time of jobs is determined by equation (16).

Table 3.

The production data of an instance.

Job	Operation	Processing time $P_{ijk}$
		$M_{1}$	$M_{2}$	$M_{3}$
	$O_{1, 1}$	2	3	—
$J_{1}$	$O_{1, 2}$	4	6	3
	$O_{1, 3}$	2	—	5
	$O_{2, 1}$	7	—	2
$J_{2}$	$O_{2, 2}$	3	2	5
	$O_{2, 3}$	4	9	2
	$O_{3, 1}$	3	—	5
$J_{3}$	$O_{3, 2}$	6	2	—
	$O_{3, 3}$	4	3	5

Figure 4.

Encoding process of chromosome for instance.

Selection

In traditional NSGA-II, non-dominated sorting and crowding distance are utilized to sort objectives. Especially, if there are multiple Pareto frontier solutions, crowding distance combined with roulette wheel selection strategy is used for individual selection. However, in multi-objective optimization, most of crowding distance is infinite, which brings much difficulty to maintain the diversity of population solutions. Fortunately, Niche technology exhibits good performance on ensuring the diversity of individuals in cross pool to some extent, in which Hamming distance and Euclidean distance is used to evaluate similarity of multiple Pareto frontier solutions and then calculating the shared fitness value of individuals. Meanwhile, roulette wheel is used to select the Pareto front individuals to enter cross pool. The specific operation process is shown in Figure 5.

Figure 5.

Tournament selection diagram.

Crossover

Crossover of processing sequence in chromosomes adopts generalized precedence operation crossover (POX) operation⁴⁴ and uniform crossover operation⁴⁵ strategies. Multi-point preservative crossover (MPX)^46,47 is adopted for the crossover of machines with chromosome processing allocation. These two type crossover operations are described in detail below.

Precedence operation crossover (POX)

POX operation is implemented in this study, which depicts in Figure 6, and detailed operation process is shown as follows. Parent 1 and Parent 2 generate two offsprings after crossover. The process of crossover consists of three steps. Firstly, all jobs need to be divided into two sets, that is, $j_{1}$ and $j_{2} . j_{1}$ included in Parent 1 is inherited to offspring 1 and $j_{2}$ included in Parent 2 is copied to offspring 2. Then, maintain their position. Finally, $j_{2}$ included in parent 2 is copied to offspring 1 and $j_{1}$ included in Parent 1 is copied to offspring 2.

Figure 6.

POX operation ( $j_{1} = {2}, j_{2} = {1, 3})$

Uniform crossover

The operation of uniform crossover can be seen in Figure 7. Firstly, a set of number called Alpha is generated randomly by 0 or 1 with same length of chromosome. Parent 1 is swapped to Parent 2 corresponding to the position that equals 0 can be used as offspring 1. Parent 1 is swapped to Parent 2 corresponding to the position that equals 1 can be used as offspring 2. Eventually, two offspring are formed.

Figure 7.

Uniform crossover operation.

Multi-point preservative crossover (MPX)

Multi-point preservative crossover (MPX) only cross selected machine in paternal chromosome, operation sequence of offspring is same with parents. The process of MPX can be seen in Figure 8. Firstly, a set of number called $R$ is generated randomly by 0 or 1 with same length of chromosome. Then, positions of operation that equals 1 in $R$ are chosen in Parent 1 and Parent 2 and allocate them as offspring. Finally, selected positions in offspring change other machines.

Figure 8.

MPX crossover operation based on machine.

Based on the above consideration, the details of crossover operation are depicted by pseudo-code presented in Algorithm 1.

Algorithm 1. The pseudo-code of crossover operation.
Input: N, Chrom, across_number, Total_gx, indivi_process, XOVR, PN1: Num = floor(N = 2);2: fori = 1: 2: Num do3: S = $\emptyset$ ;4: ws = randi([1; total_gx]; 1; total_gx);5: across_number =10; % Determine the number of crossings.6: S_i = Chrom(i,:); % Select individual.7: S_j = Chrom(j,:); % Select individual.8: if XOVR > rand then9: S₁ = S_i (,1:total_gx);10: S₂ = S_j (,1:total_gx);11: Post = undrid(total_gx); chazhi = total_gx-Post;12: if chazhi ≤ ws(across_number) then13: [S₁₁, S₂₂] = Uniform(S₁, S₂) % The uniform cross of OS vector.14: else15: [S₁₁, S₂₂] = POX(S₁, S₂) % The generalized precedence operation crossover(POX) of OS vector.16: end if17: S = MPX(S₁₁, S₂₂) % The multi-point preservative crossover (MPX) of MS vector18: else19: S = [S, S_i, S_j]20: end if21: Pop1_VNS = N5_VNS(S); % N5 neighborhood and output non-dominated individuals.22: Pop2_VNS = Machine_VNS(Pop1_VNS); % machine-oriented idle time neighborhood and output23: S = [S; Pop2_VNS];24: end for25: Pop_mig = Select_population(S); % Sort and select N = 2 habitats.Output: Pop_mig

Algorithm 1. The pseudo-code of crossover operation.

Input: N, Chrom, across_number, Total_gx, indivi_process, XOVR, PN1: Num = floor(N = 2);2: fori = 1: 2: Num do3: S =

\emptyset

;4: ws = randi([1; total_gx]; 1; total_gx);5: across_number =10; % Determine the number of crossings.6: S_i = Chrom(i,:); % Select individual.7: S_j = Chrom(j,:); % Select individual.8: if XOVR > rand then9: S₁ = S_i (,1:total_gx);10: S₂ = S_j (,1:total_gx);11: Post = undrid(total_gx); chazhi = total_gx-Post;12: if chazhi ≤ ws(across_number) then13: [S₁₁, S₂₂] = Uniform(S₁, S₂) % The uniform cross of OS vector.14: else15: [S₁₁, S₂₂] = POX(S₁, S₂) % The generalized precedence operation crossover(POX) of OS vector.16: end if17: S = MPX(S₁₁, S₂₂) % The multi-point preservative crossover (MPX) of MS vector18: else19: S = [S, S_i, S_j]20: end if21: Pop1_VNS = N5_VNS(S); % N5 neighborhood and output non-dominated individuals.22: Pop2_VNS = Machine_VNS(Pop1_VNS); % machine-oriented idle time neighborhood and output23: S = [S; Pop2_VNS];24: end for25: Pop_mig = Select_population(S); % Sort and select N = 2 habitats.Output: Pop_mig

Mutation

Mutation is an effective technique to improve population diversity, two mutation operations are adopted in this paper. One is RWN for processing sequence, which choose rearranged position arbitrarily and rearrange them. It can be seen from Figure 9. Another mutation is for machine selection, machine with the shortest processing time is selected to replace genes, as can be seen in Figure 10.

Figure 9.

Random whole neighborhood.

Figure 10.

Machine chain mutation operation diagram.

Based on the above consideration, the details of mutation operation are depicted by pseudo-code presented in Algorithm 2.

Algorithm 2. The pseudo-code of modified mutation operation.
Input: N, Chrom, Total_gx, indivi_process, MUTR, PN, B1, T, temchrom = $\emptyset$ .1: [NIND,∼] = size(Chrom);2: fori = 1: NIND do3: cirnumber = 10;4: S₀ = Chrom(i,:);5: Wtemp = cell(1,PN);6: if MUTR > rand then7: while cirnumber > 0 do8: S=RWN_VNS(S0); % RWN neighborhood and output non-dominated individuals.9: temchrom(end + 1,:) = S;10: forj = 1:Total_gx do11: gx = find(B1(S(j),:) == 1);12: Wtemp{1,S(j) = gx;13: end for14: forj = 1:Total_gx do15: temptime = T[S(j),Wtemp{1,S(j)}(1)];16: [∼,minindex] = find(temptime == min (temptime));17: S(j + Total gx) = minindex(unidrnd (length(minindex)));18: Wtemp{1,S(j)}(1) = [];19: end for20: S = N5_VNS(S); % N5 neighborhood and output non-dominated individuals.21: temchrom(end + 1,:) = S;22: cirnumber = cirnumber − 1;23: end while24: else25: temchrom(end + 1,:) = N5_VNS (S0);26: end if27: end for28: newchrom = Machine_VNS (temchrom(1,:)); % machine-oriented idle time neighborhood29: total_chrom = unique([temchrom;newchrom],‘rows’);30: Pop_mig = Select_population(total_chrom); % Sort and select N = 2 habitats.Output: Pop_mig.

Algorithm 2. The pseudo-code of modified mutation operation.

Input: N, Chrom, Total_gx, indivi_process, MUTR, PN, B1, T, temchrom =

\emptyset

.1: [NIND,∼] = size(Chrom);2: fori = 1: NIND do3: cirnumber = 10;4: S₀ = Chrom(i,:);5: Wtemp = cell(1,PN);6: if MUTR > rand then7: while cirnumber > 0 do8: S=RWN_VNS(S0); % RWN neighborhood and output non-dominated individuals.9: temchrom(end + 1,:) = S;10: forj = 1:Total_gx do11: gx = find(B1(S(j),:) == 1);12: Wtemp{1,S(j) = gx;13: end for14: forj = 1:Total_gx do15: temptime = T[S(j),Wtemp{1,S(j)}(1)];16: [∼,minindex] = find(temptime == min (temptime));17: S(j + Total gx) = minindex(unidrnd (length(minindex)));18: Wtemp{1,S(j)}(1) = [];19: end for20: S = N5_VNS(S); % N5 neighborhood and output non-dominated individuals.21: temchrom(end + 1,:) = S;22: cirnumber = cirnumber − 1;23: end while24: else25: temchrom(end + 1,:) = N5_VNS (S0);26: end if27: end for28: newchrom = Machine_VNS (temchrom(1,:)); % machine-oriented idle time neighborhood29: total_chrom = unique([temchrom;newchrom],‘rows’);30: Pop_mig = Select_population(total_chrom); % Sort and select N = 2 habitats.Output: Pop_mig.

Elite storage strategy (ESS)

After crossover, mutation and local search, Pareto non-dominant sorting and crowding distance are used to stratify the population, and a new population is generated. To prevent the optimal solution lost in iteration process, the elite memory bank $P$ of population was established, wherein, the capacity of $P$ is $N$ . The number of Pareto front is assumed as $H$ . If $H$ is greater than $N$ , the first $N$ solutions in $H$ is selected into $P$ . Otherwise, the solutions of Pareto front are stored in $P$ .

The framework of proposed HVNS-NSGA-II algorithm

Based on the above consideration, the details of HVNS-NSGA-II are depicted by pseudo-code presented in Algorithm 3.

Algorithm 3. The pseudo-code of the proposed HVNS-NSGA-II algorithm

Input: N, Chrom, Total_gx, indivi_process, XOVR, MUTR, PN, B1, T, temchrom =

\emptyset

.1: Pop = Intialization(N);2: ns_pop = nondominant_sort(Chrom);3: bestchrom = [];4: for gen = 2:MAXGEN do5: select_pop = selection(ns_pop);6: bestchrom = [bestchrom; select_pop];7: select_pop = select_pop(1:Total gx*2);8: cir_number = size(select_pop,1);9: fori = 1:cir_number do10: select_pop(i,:) = N5_VNS(select_pop(i,:)); % N5 neighborhood and output non-dominated individuals.11: end for12: POP_acr = across(N, Chrom, Total_gx, indivi_process, XOVR, PN, Temp_memory);13: POP_mut = mutation(N, Chrom, Total_gx, indivi_process, MUTR, PN, B1, T, temchrom);14: G_gen = Pop

\cup^{} Pop_acr \cup^{} Pop_mut

; % Combine habitats15: G_gen = unique(G_gen,‘rows’);16: new_gen = [ns_pop(:,1:Total_gx*2);G_gen];17: dc_pop = nondominant_sort(new_gen);18: ns_pop = generate_gen(dc_pop);19: end forOutput: ns_pop.

Results and comparative analysis

In this section, multiple experiments are designed and make comparisons with seven algorithms to verify effectiveness of proposed HVNS-NSGA-II method. Two types of metrics are adopted to evaluate quality and diversity of the obtained non-dominated solutions through proposed algorithm. Effectiveness and superiority of the presented algorithm is verified by comparison with some other commonly used heuristic algorithms. Besides, comparison with one conic scalarization method (CSM)¹³ further demonstrates the performance of proposed algorithm.

Design of experiments

In this subsection, environment setting, data source, and performance metrics are separately introduced.

Environment setting

All of the experiments and algorithms are written and implemented in MATLAB 2018a, with Intel^® Core^TM i5-760Qm CPU @ 2.80 GHz and 8.00 GB RAM.

Data Source

To verify the performance of proposed method, dataset from literature¹³ is utilized, which includes twelve instances. Taking p/m/l/k to represent the general representation of each instance. Thereinto, $p$ represents number of parts, $m$ means number of part families, $l$ stands for type of machines, and $k$ is cells. The detailed instance explanation of the instances are similar to Section 2.5.

In this paper, the value of processing cost (Pc) on machine $k$ per unit time $c_{k}$ , setup cost (Sc) per unit time $c_{setup}$ , handling cost of each batch (Hcb) $h_{cost}$ , processing energy consumption (Pec) per unit time $p_{k}$ , intercellular transportation energy consumption (Iec) per unit time $p_{ijk (j + 1) h}^{b}$ are listed in Table 4. Besides, we divided each job into two equal batches, that is, the processing time of each batch is half of original data. Besides, in this paper, we set handling cost of each batch $h_{cost}$ to be 10²⁴.

Table 4.

Parameter settings for objective calculation.

Notation	Pc	Sc	Hcb	Pec	Iec
Value	3	4	5	3	6

Performance metrics

Non-dominated solutions metrics

To evaluate performance of obtained solutions, three metrics are adopted, namely the number of obtained non-dominated solutions $N_{≺}$ shown in equation (16), the ratio of the obtained non-dominated solutions $R_{≺}$ in equation (17) and average distance of the obtained non-dominated front to Pareto front $D_{≺}$ in equation (18).⁴⁸ It is supposed that $S_{p}$ denotes the reference Pareto solution set, while $S_{k}$ represents the solution set obtained by the proposed algorithm.

N_{≺} (S^{k}) = | S^{k} - {x \in S^{k} | \exists y \in S^{k} : y ≺ x} |,

(16)

R_{≺} (S^{k}) = \frac{N_{≺} (S^{k})}{| S^{k} |},

(17)

D_{≺} (S^{k}) = \frac{1}{| S^{p} |} \sum_{p \in S^{p}} d_{p} (S^{k}),

(18)

d_{p} (S^{k}) = min_{x \in S^{k}} {\sqrt{\sum_{i = 1}^{w} {(\frac{f_{i} (x) - f_{i} (p)}{f_{i}^{\max} (.) - f_{i}^{\min} (.)})}^{2}}},

(19)

where $d_{p} (S^{k})$ in equation (19) means the shortest normalized distance between the solution set $S^{k}$ and a reference solution $p \in S^{p}$ , $w$ denotes the number of objectives, $f_{\max}$ and $f_{\min}$ represent maximum and minimum value of the i^th objective in the reference Pareto set $S^{p}$ , respectively. $f_{i} (\cdot)$ is the $i^{th}$ objective value. It is noted that if $f_{i}^{\max} (\cdot) = f_{i}^{\min} (\cdot)$ , we let $f_{i}^{\max} (\cdot) - f_{i}^{\min} (\cdot)$ is equal to 0.5.

From above formulas, $N_{≺} (S^{k})$ denotes the efficiency of the proposed method, it is obviously to find that when $N_{≺}$ is larger, the obtained solution set is better. $R_{≺} (S^{k})$ is utilized to assess the quality of solutions among acquired solutions set, and $D_{≺} (S^{k})$ represents the average value of those shortest normalized distances between all reference solutions and the obtained solution set $S^{k}$ . Consequently, the higher $R_{≺} (S^{k})$ , the better performance of the set $S^{k}$ . On the contrary, the smaller value of $D_{≺} (S^{k})$ designates the better distribution of obtained solution set.

Hypervolume

Hypervolume (HV) is an outstanding and widely used indicator to evaluate the comprehensive performance of different algorithms, which characterizes the magnitude of the volume dominated by Pareto front sets rather than reference point $R$ .^49,50 It should be noted that a higher HV signifies that the solution set has better diversity and convergence.⁵¹ In this study, normalized objectives values were adopted to compute HV indicator shown in equation (20).

\begin{matrix} HV = Volume \\ (\cup_{X \in S} [f_{1}^{n} (X), 1.1] \times [f_{2}^{n} (X), 1.1] \times \dots \times [f_{g}^{n} (X), 1.1]), \end{matrix}

(20)

where $S$ is final solution set, $R$ is the $g$ -dimensional reference point and $R = [1.1, 1.1, \dots, 1.1]^{T}$ .

Indicator of makespan

It is worth noting that comparison of one objective function result can verify the efficiency between signal objective and multi-objective optimization algorithm.⁴⁸ In this paper, we compare makespan $f_{1}$ with conic scalarization method (CSM). Since batch issue is not considered in CSM, we set $f_{3}^{'}$ as the total costs excluding batch costs $C_{sublot}$ . The indicator Imp of makespan is calculated between the proposed algorithm and CSM, which is defined as follows:

Imp = [\frac{(f_{1} - f)}{f}] \times 100 %,

(21)

where $f_{1}$ is the makespan by the proposed algorithm HVNS-NSGA-II and $f$ is the makespan of CSM.

Parameter setting

In this paper, parameters, such as number of individuals and interactions of proposed algorithm are listed in Table 5.

Table 5.

Parameter settings for proposed algorithm.

Parameter	Number of individuals	Number of iterations	Selection rate	Crossover rate	Mutation rate	Tournament
Value	200	40	0.6	0.8	0.1	10

Comparisons with heuristic algorithms

In order to assess the validity and superiority of proposed HVNS-NSGA-II algorithm, computational results are discussed in this section with some other commonly used heuristic algorithms. In this Section, three objectives⁴⁸ in classical multi-objective optimization models for FJSP are compared, which are makespan $F_{1}$ , critical machine workload $F_{2}$ , and total workload $F_{3}$ .

Comparisons of four Kacem instances

To exhibit the performance of proposed algorithm, four algorithms including PSO + TS,⁵² HTSA,⁵³ and P-DABC⁵⁴ are employed and compared through four Kacem et al.⁵⁵ instances (4 × 5, 8 × 8, 10 × 7, and 10 × 10 instances).

Table 6 exhibits computational results of different algorithms, it finds that HVNS-NSGA-II has a higher efficiency than other methods when deal with four Kacem instances. In comparison with PSO + TS, the proposed HVNS-NSGA-II algorithm not only can acquire superior solutions but also obtain richer optimal solutions. Similarly, the proposed algorithm obtains much richer optimal solutions than PSO + TS, especially for 10 × 10 instance. When compared with HTSA, the proposed algorithm again obtains much richer optimal solutions than HTSA algorithm for 4 × 5 and 8 × 8 instance. For the medium and large scale instance 10 × 7 and 10 × 10, the solutions obtained by proposed algorithm have the same quality and quantity. In comparison with P-DABC, the proposed algorithm gets much richer optimal solutions for 4 × 5 instance. The solutions of other three instances show the same performance between the proposed algorithm and P-DABC.

Table 6.

Comparison of results on the four Kacem instances.

Instance	Func.	PSO + TS		HTSA			P-DABC			HVNS-NSGA-II
4 × 5	$F_{1}$	11		11	12	N/A	11	12	13	11	11	12	13
	$F_{2}$	10		10	8	N/A	10	8	7	9	10	8	7
	$F_{3}$	32		32	32	N/A	32	32	33	34	32	32	33
8 × 8	$F_{1}$	14	15	14	15	N/A	14	15	16		15	16	16
	$F_{2}$	12	12	12	12	N/A	12	12	13		12	11	13
	$F_{3}$	77	75	77	75	N/A	77	75	73		75	77	73
10 × 7	$F_{1}$	N/A		11	11	N/A	11	12	12		11	12	–
	$F_{2}$			11	10	N/A	11	11	12		11	12	–
	$F_{3}$			61	62	N/A	63	61	60		61	60	–
10 × 10	$F_{1}$	7		7	7	8	7	8	8		7	8	8
	$F_{2}$	6		5	6	5	5	5	7		5	5	7
	$F_{3}$	43		43	42	42	43	42	41		43	42	41

N/A means there is no data in the literature.

Comparisons of four BRdata instances

In this subsection, comparisons are made among some heuristic algorithms from literature on four BRdata instances (Mk01, Mk03, Mk05, Mk08).⁵⁶ Three heuristic algorithms are selected to compare, that is, MOGA algorithm by Wang et al.,⁵⁷ BEG-NSGA-II algorithm by Deng et al.,⁴⁴ and PSO + RRHC by Kato et al.⁵⁸ The comparative results are presented in Table 7.

Table 7.

Comparison of results on four BRdata instances.

Instance	MOGA			BEG-NSGA-II			PSO + RRHC			HVNS-NSGA-II
Instance	$F_{1}$	$F_{2}$	$F_{3}$	$F_{1}$	$F_{2}$	$F_{3}$	$F_{1}$	$F_{2}$	$F_{3}$	$F_{1}$	$F_{2}$	$F_{3}$
Mk01	40	36	169	40	36	169	42	42	166	40	36	167
	42	39	158	42	39	158	43	42	165	41	37	164
	43	40	155	43	40	155	43	43	161	42	36	165
	44	40	154	44	40	154	44	36	172	42	38	162
				47	36	167	44	37	166	43	40	156
				47	37	165	44	44	160	43	39	159
				49	37	164	45	36	170	44	40	154
				50	38	162	45	42	162	44	38	160
							45	45	157	45	39	158
							46	37	164	45	37	163
							46	46	155	46	42	153
							48	46	154
							49	45	155
							49	46	153
							50	37	163
Mk03	204	133	884	204	133	884	N/A			204	204	867
	204	135	882	204	135	882				208	204	865
	204	144	871	204	144	871				211	211	860
	204	199	855	204	199	855				213	213	851
	213	199	850	213	199	850				221	221	846
	214	210	849	214	210	849				222	222	842
	221	199	847	221	199	847				225	216	850
	222	199	848	222	199	848				225	221	844
	230	177	848	230	177	848				226	222	840
	231	188	848	231	188	848				231	231	838
										240	240	834
										249	249	832
										258	258	830
										267	267	826
										276	276	824
Mk05	173	173	683	173	173	683	177	177	689	178	173	683
	175	175	682	175	175	682	178	176	692	178	178	680
	176	176	679	179	179	679	178	177	690	179	179	679
	183	183	677	183	183	677	179	177	688	183	183	678
	185	185	676	193	193	675	180	175	692	184	184	677
				199	199	674	181	176	688	185	185	676
							184	179	687	187	183	677
							186	185	683	191	191	675
							187	176	687	197	197	674
							189	187	679	203	203	673
							196	190	678	209	209	672
							199	193	677
							202	202	676
Mk08	523	497	2534	523	515	2524	556	554	2580	523	523	2524
	523	515	2524	523	497	2534	556	556	2546	524	524	2519
	524	524	2519	524	524	2519	557	554	2536	533	533	2514
	578	578	2489	541	533	2516	558	551	2515	542	542	2509
	587	587	2484	542	542	2511	559	545	2545	551	551	2504
				560	560	2505	561	542	2531	560	560	2499
				578	578	2489	563	542	2531	569	569	2494
				587	587	2484	565	533	2525	578	578	2489
							568	560	2514	587	587	2484
							570	569	2513
							577	569	2505
							584	578	2500
							590	578	2493
							596	587	2484
							601	527	2761

N/A means there is no data in the literature.

In comparison with MOGA, the proposed algorithm obtains superior and richer optimal solutions for each instance. When compared with BEG-NSGA-II, for Mk01 and Mk05 instance, the proposed algorithm has superior and richer optimal solutions. For Mk03 and MK08 instance, solution proposed algorithm obtains solutions with the same quality and quantity. In comparison with PSO + RRHC, all instances have obtained either same or richer solutions. Taking Mk08 instance as an example, the Gantt chart of the proposed method is shown in Figure 11. It is worth noting that there is a little difference from the Gantt chart explanation in Section 2.5, the mark $Ja, b$ in Gantt chart Figure 11 symbolize that $b^{th}$ operation in of job $a$ .

Figure 11.

The first solution of MK08 ( $F_{1} = 523, F_{2} = 523, F_{3} = 2524$ ).

Performance analysis

Based on mentioned three metrics in Section 4.1.3, the performance of the proposed HVNS-NSGA-II is shown in Table 8. It can be seen that the value $R_{≺}$ of Kacem instances is 100%, that is, all solutions obtained by proposed algorithm has better optimal Pareto set than other heuristic algorithms. Even though $R_{≺}$ of BRdata is a relatively smaller than that of Kacem, the value $D_{≺}$ is much lower with the complexity of the instance. This means that the distribution of the obtained solution set is much better, even though there are no too many solutions.

Table 8.

The metrics result of different instances.

Instances	$N_{≺}$	$R_{≺}$ (×100%)	$D_{≺}$
Kacem
4 × 5	4	100	0
8 × 8	3	100	0.30
10 × 7	2	100	0.37
10 × 10	3	100	0.12
BRdata
Mk01	8	72.73	0.2922
Mk03	10	66.67	0.4878
Mk05	5	45.45	0.2226
Mk08	8	88.89	0.1504

To further compare the overall performance of proposed algorithm, the quality of normalized solution sets of each instance is evaluated by hypervolume (the bigger the better), and the results of Kacem and BRdata instances are shown in Tables 9 and 10 seperately. For the sake of comparison the ability of different algorithms to solve Kacem set problem, the Friedmantest⁵⁹ is used to assess whether there are significant differences in the effectiveness of HVNS-NSGA-II and other methods based on HV values, in which the significance level $α$ is 0.05. Thereinto, the tested $p$ values between HVNS-NSGA-II and PSO + TS/HTSA/P-DABC are 0.5637, 0.3173, 0.5637, respectively. Therefore, there is no significant difference between between HVNS-NSGA-II and PSO + TS/HTSA/P-DABC ( $p > α$ means that the performance of PSO + TS, HTSA, and P-DABC is similar with HVNS-NSGAII). To sum up, the Friedman’s test ranking of the four algorithms for solving Kacem set problem is HVNS-NSGA-II $\approx$ PSO + TS $\approx$ HTSA $\approx$ P-DABC. Homoplastically, the tested $p$ values between HVNS-NSGA-II and MOGA/BEG-NSGA-II/PSO + RRHC in BRdata instance are 0.3173, 0.3173, 0.0833. Overall, the Friedman’s test ranking of four algorithms for solving BRdata instance is HVNS-NSGA-II $\approx$ MOGA $\approx$ BEG-NSGA-II $\approx$ PSO + RRHC.

Table 9.

Hypervolumes of different algorithms for four Kacem instances.

Instance	PSO + TS	HTSA	P-DABC	HVNSNSGA-II
4 × 5	0.1210	0.5610	0.5810	0.5977
8 × 8	0.2460	0.2460	0.2510	0.2260
10 × 7	N/A	0.7443	0.1093	0.5093
10 × 10	0.0660	0.4760	0.1810	0.1810

N/A means there is no value.

Table 10.

Hypervolumes of different algorithms for four BRdata instances.

Hypervolumes	MOGA	BEG-NSGA-II	PSO + RRHC	HVNS-NSGA-II
MK01	0.8431	0.8673	0.5128	1.0436
MK03	0.6784	0.6784	N/A	0.5102
MK05	0.9721	0.9551	0.5763	0.8908
MK08	1.1731	1.1904	0.4540	0.9058

N/A means there is no value.

Comparisons with scalarization method

Based on the definition of makespan indicator in Section 4.1.3, comparison results of makespan $F_{1}$ on 12 instances with CSM are exhibited in Table 11, which only one optimal solution of proposed method is listed. According to Imp value, the results show that the efficiency of proposed algorithm. Take Instance 4 and Instance 10 as examples, the Gantt chart results are presented in Figures 12 and 13 respectively. It is worth noting that the mark $Ja, b$ in the Gantt charts symbolize that $b^{th}$ operation in of job $a$ and batch is not considered in comparisons with CSM.

Table 11.

Comparison of makespan $f_{1}$ on the twelve instances.

Instances	Parts/part families/machines/cells	$f_{1}$	$f_{2}$	$f_{3}^{'}$	CSM	Imp
Instances	Parts/part families/machines/cells	$f_{1}$	$f_{2}$	$f_{3}^{'}$	$f$	Imp
1	4/2/4/2	27	81	213	27	0%
2	6/2/4/2	28	108	246	28	0%
3	6/2/6/2	26	82	216	26	0%
4	7/3/4/2	37	151	303	37	0%
5	7/2/6/3	29	99	249	29	0%
6	7/3/6/3	29	111	249	29	0%
7	9/3/7/3	34	134	282	34	0%
8	8/4/8/4	29	107	249	29	0%
9	10/4/8/4	34	134	282	34	0%
10	10/4/10/4	31	113	261	31	0%
11	14/4/10/4	35	145	297	35	0%
12	15/4/12/4	31	129	273	31	0%

Figure 12.

The first solution for 7/3/4/2 instance ( $f_{1} = 37, f_{2} = 151, f_{3}^{'} = 303$ ).

Figure 13.

The first solution of 10/4/10/4 instance ( $f_{1} = 31, f_{2} = 113, f_{3}^{'} = 261$ ).

With the purpose of testing convergence of above solutions obtained in Table 11, we calculate HV indicators for all generations of each instance, which is shown in Figure 14. It can be seen from the figure all instances except Instance 1 converge in the second generation. This substantiates that proposed algorithm converges fast for problems with different cells and part families.

Figure 14.

The hyper volume indicator of twelve instances of CSM.

Conclusions and future studies

This study focuses on a multi-objective FJCSP. An improved non-dominated sorting genetic algorithm, namely HVNS-NSGA-II, is proposed to solve the FJCSP. The main contribution and findings of this study can be summarized as follows: (1) intercellular transportation, energy consumption, sequence-dependent family setup times, and batch sizes are taken into consideration simultaneously in the FJCSP; (2) a hybrid variable neighborhood search, composed of three types of structures, has been embedded into NSGA-II to improve the local exploitation capability of original NSGA-II for obtaining more optimal solutions in multi-objective FJCSP; (3) based on different case studies, comparisons with other heuristic algorithms from literature on two types of benchmark instances have been confirmed the higher effectiveness of HVNS-NSGA-II. Besides, the efficiency of proposed algorithm has been verified by comparison of makespan with one scalarization method.

In future research, the influence of maintenance on scheduling will be considered with many real-life constraints. In parallel, the local search capacity will be improved to obtain more optimal solutions and speed up the convergence of algorithm.

Footnotes

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 work was supported by Graduate Scientific Research and Innovation Foundation of Chongqing, China (CYB19008), and Fundamental Research Funds for the Central Universities (2019CDCGJX214).

ORCID iDs

Yaoyao Han

Fengshou Gu

References

Yan

. A scheduling procedure for a flow shop–like knowledgeable manufacturing cell with self-evolutionary features. Proc IMechE, Part B: J Engineering Manufacture 2016; 230(12): 2296–2306.

Chan

FTS

. The effects of scheduling flexibility on the performance of a flexible manufacturing system. Proc IMechE, Part B: J Engineering Manufacture 2003; 217(7): 899–918.

Wemmerlöv

Hyer

. Cellular manufacturing in the US industry: a survey of users. Int J Prod Res 1989; 27(9): 1511–1530.

Aalaei

Kayvanfar

Davoudpour

. Integrating multi-dynamic virtual cellular manufacturing systems into multi-market allocation and production planning. Proc IMechE, Part B: J Engineering Manufacture 2019; 233(2): 643–664.

Olorunniwo

Udo

. The impact of management and employees on cellular manufacturing implementation. Int J Prod Econ 2002; 76(1): 27–38.

Shanker

Vrat

. Some design issues in cellular manufacturing using the fuzzy programming approach. Int J Prod Res 1999; 37(11): 2545–2563.

Ghosh

Doloi

Dan

. Utilization-based grouping efficiency and multi-criteria decision approach in designing of manufacturing cells. Proc IMechE, Part B: J Engineering Manufacture 2017; 231(3): 505–522.

Neufeld

Gupta

JND

Buscher

. A comprehensive review of flowshop group scheduling literature. Comput Oper Res 2016; 70: 56–74.

Celano

Costa

Fichera

. Constrained scheduling of the inspection activities on semiconductor wafers grouped in families with sequence-dependent set-up times. Int J Adv Manuf Technol 2010; 46(5–8): 695–705.

10.

Neufeld

Teucher

Buscher

. Scheduling flowline manufacturing cells with inter-cellular moves: non-permutation schedules and material flows in the cell scheduling problem. Int J Prod Res 2020; 58: 6568–6584.

11.

Feng

Huang

, et al. Joint optimization of flowshop sequence-dependent manufacturing cell scheduling and preventive maintenance. In: IEEE international conference on industrial engineering and engineering management, Bali, Indonesia, 4–7 December 2016, pp.946–950. New York: IEEE.

12.

Meng

, et al. An ACO-based intercell scheduling approach for job shop cells with multiple single processing machines and one batch processing machine. J Intell Manuf 2016; 27(2): 283–296.

13.

Deliktas

Torkul

Ustun

. A flexible job shop cell scheduling with sequence-dependent family setup times and intercellular transportation times using conic scalarization method. Int Trans Oper Res 2019; 26(6): 2410–2431.

14.

Lin

Huang

, et al. Energy savings approaches for high-tech manufacturing factories. Case Stud Therm Eng 2020; 17: 100569.

15.

Wang

Chiu

Chen

. A fuzzy nonlinear programming approach for planning energy-efficient wafer fabrication factories. Appl Soft Comput 2020; 95: 106506.

16.

Lin

Tian

, et al. Flow shop scheduling with low carbon emission and variable machining parameters. Proc IMechE, Part B: J Engineering Manufacture 2019; 233(5): 1561–1572.

17.

Liu

Zhou

. Multi-objective energy-saving scheduling for a permutation flow line. Proc IMechE, Part B: J Engineering Manufacture 2018; 232(5): 879–888.

18.

Iqbal

Aziz

Jahanzaib

, et al. Integration of cell formation and job sequencing to minimize energy consumption with minimum make-span. Proc IMechE, Part B: J Engineering Manufacture 2017; 231(14): 2636–2651.

19.

Wang

Xiao

, et al. Dynamic parts scheduling in multiple job shop cells considering intercell moves and flexible routes. Comput Oper Res 2013; 40(5): 1207–1223.

20.

Costa

Cappadonna

Fichera

. A hybrid genetic algorithm for minimizing makespan in a flow-shop sequence-dependent group scheduling problem. J Intell Manuf 2017; 28(6): 1269–1283.

21.

Abdelmaguid

. A neighborhood search function for flexible job shop scheduling with separable sequence-dependent setup times. Appl Math Comput 2015; 260: 188–203.

22.

Shen

Dauzère-Pérès

Neufeld

. Solving the flexible job shop scheduling problem with sequence-dependent setup times. Eur J Oper Res 2018; 265(2): 503–516.

23.

Rato

Blue

Pinaton

, et al. Translation-invariant multiscale energy-based pca for monitoring batch processes in semiconductor manufacturing. IEEE Trans Autom Sci Eng 2017; 14(2): 894–904.

24.

Potts

Baker

. Flow shop scheduling with lot streaming. Oper Res Lett 1989; 8(6): 297–303.

25.

Ai-ming

Jian-min

Kun

. Excavation of critical resource node for quality control of multi-variety mixed production shopfloor based on complex network property. Proc IMechE, Part B: J Engineering Manufacture 2016; 230(1): 169–177.

26.

Huang

. An effective ant colony optimization algorithm for multi-objective job-shop scheduling with equal-size lot-splitting. Appl Soft Comput 2017; 57: 642–656.

27.

Defersha

Bayat Movahed

. Linear programming assisted (not embedded) genetic algorithm for flexible jobshop scheduling with lot streaming. Comput Ind Eng 2018; 117: 319–335.

28.

Vaez

Sabouhi

Jabalameli

. Sustainability in a lot-sizing and scheduling problem with delivery time window and sequence-dependent setup cost consideration. Sustain Cities Soc 2019; 51: 101718.

29.

Das

Mishra

Ajith

, et al. An inverse analysis of a transient 2-D conduction–radiation problem using the lattice Boltzmann method and the finite volume method coupled with the genetic algorithm. J Quant Spectrosc Radiat Transf 2008; 109(11): 2060–2077.

30.

Singh

Das

. An experimental and multi-objective optimization study of a forced draft cooling tower with different fills. Energy Convers Manag 2016; 111: 417–430.

31.

Singh

Das

. Simultaneous optimization of performance parameters and energy consumption in induced draft cooling towers. Chem Eng Res Des 2017; 123: 1–13.

32.

Singh

Das

. Exergy optimization of cooling tower for HGSHP and HVAC applications. Energy Convers Manag 2017; 136: 418–430.

33.

Singh

Das

. Improved quantification of exergy destruction in mechanical cooling tower considering all tower inlet parameters. J Heat Transf 2018; 140(5): 052002.

34.

Lebbar

El Abbassi

El Barkany

, et al. Solving the multi objective flow shop scheduling problems using an improved NSGA-II. Int J Oper Quant Manag 2018; 24(3): 211–230.

35.

Wang

Zhang

, et al. Two-objective robust job-shop scheduling with two problem-specific neighborhood structures. Swarm Evol Comput 2021; 61: 100805.

36.

Wang

Huang

, et al. A NSGA-II based memetic algorithm for multiobjective parallel flowshop scheduling problem. Comput Ind Eng 2017; 113: 185–194.

37.

Che

. Energy-efficient no-wait permutation flow shop scheduling by adaptive multi-objective variable neighborhood search. Omega 2020; 94: 102–117.

38.

Chen

, et al. An improved non-dominated sorting biogeography-based optimization algorithm for the (hybrid) multi-objective flexible job-shop scheduling problem. Appl Soft Comput 2021; 99: 106869.

39.

Tamssaouet

Dauzère-Pérès

Knopp

, et al. Multiobjective optimization for complex flexible job-shop scheduling problems. Eur J Oper Res. Epub ahead of print 29 April 2021. DOI: 10.1016/j.ejor.2021.03.069.

40.

Deb

Pratap

Agarwal

, et al. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans Evol Comput 2002; 6(2): 182–197.

41.

Mladenović

Hansen

. Variable neighborhood search. Comput Oper Res 1997; 24(11): 1097–1100.

42.

Bagheri

Zandieh

. Bi-criteria flexible job-shop scheduling with sequence-dependent setup times—variable neighborhood search approach. J Manuf Syst 2011; 30(1): 8–15.

43.

Gao

Wen

, et al. A hybrid algorithm based on a new neighborhood structure evaluation method for job shop scheduling problem. Comput Ind Eng 2015; 88: 417–429.

44.

Deng

Gong

, et al. A bee evolutionary guiding nondominated sorting genetic algorithm II for multiobjective flexible job-shop scheduling. Comput Intell Neurosci 2017; 2017: 1–20.

45.

Sathya Sofia

GaneshKumar

. Multi-objective task scheduling to minimize energy consumption and makespan of cloud computing using NSGA-II. J Netw Syst Manag 2018; 26(2): 463–485.

46.

Zhang

Liu

, et al. Applying genetic local search to solve the flexible job-shop scheduling problem. In: 2008 7th world congress on intelligent control and automation, Chongqing, China, 25–27 June 2008, pp.3929–3935. New York: IEEE.

47.

Liu

Zhang

Zhu

, et al. Novel multi-objective resource allocation and activity scheduling for fourth party logistics. Comput Oper Res 2014; 44: 42–51.

48.

Pan

Tasgetiren

. A discrete artificial bee colony algorithm for the multi-objective flexible job-shop scheduling problem with maintenance activities. Appl Math Model 2014; 38(3): 1111–1132.

49.

Zitzler

Thiele

. Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach. IEEE Trans Evol Comput 1999; 3(4): 257–271.

50.

Tian

Cheng

Zhang

, et al. PlatEMO: A MATLAB platform for evolutionary multi-objective optimization [educational forum]. IEEE Comput Intell Mag 2017; 12(4): 73–87.

51.

Yuan

Wang

, et al. A new dominance relation-based evolutionary algorithm for many-objective optimization. IEEE Trans Evol Comput 2015; 20(1): 16–37.

52.

Zhang

Shao

, et al. An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem. Comput Ind Eng 2009; 56(4): 1309–1318.

53.

Pan

Liang

. An effective hybrid tabu search algorithm for multi-objective flexible job-shop scheduling problems. Comput Ind Eng 2010; 59(4): 647–662.

54.

Pan

Gao

. Pareto-based discrete artificial bee colony algorithm for multi-objective flexible job shop scheduling problems. Int J Adv Manuf Technol 2011; 55(9-12): 1159–1169.

55.

Kacem

Hammadi

Borne

. Pareto-optimality approach for flexible job-shop scheduling problems: hybridization of evolutionary algorithms and fuzzy logic. Math Comput Simul 2002; 60(3–5): 245–276.

56.

Brandimarte

. Routing and scheduling in a flexible job shop by tabu search. Ann Oper Res 1993; 41(3): 157–183.

57.

Wang

Gao

Zhang

, et al. A multi-objective genetic algorithm based on immune and entropy principle for flexible job-shop scheduling problem. Int J Adv Manuf Technol 2010; 51(5-8): 757–767.

58.

Kato

ERR

de Aguiar Aranha

Tsunaki

. A new approach to solve the flexible job shop problem based on a hybrid particle swarm optimization and random-restart hill climbing. Comput Ind Eng 2018; 125: 178–189.

59.

Hogg

Ledolter

. Engineering statistics. New York, NY: Macmillan, 1987.