Sage Journals: Discover world-class research

Abstract

Recently, the ow shop scheduling problem with deteriorating jobs has gained increasing concern from academic communities and industrial areas. The de- teriorating job is that the processing time of the jobs depends on their starting time. Due to the essential complexity of this problem, most studies focus on the two and three stages setting, and there are few studies that have considered a multiple stage setting. In this paper, a multiobjective ow shop deteriorating scheduling problem is considered, where the objectives are to minimize the makespan and the total tardiness, simultaneously. In order to solve it e_ciently, a novel adaptive multipopulation mul- tiobjective genetic algorithm is proposed. In the proposed algorithm, multiple scalar optimization problems of the multiobjective ow shop deteriorating scheduling prob-lem are developed, which will be introduced into the iteration course in multiple stages. An adaptive multipopulation strategy is designed to construct multiple subpopulations to search the optimal solutions of several scalar optimization problems in parallel. In addition, some special strategies, i.e. selection, crossover, mutation and the evolution of external archives are designed to improve the performance of the adaptive multi-population multiobjective genetic algorithm for the investigated multiobjective ow shop deteriorating scheduling problem. Based on a set of test instances on the multiob-jective ow shop deteriorating scheduling problem, simulation experiments are carried out to examine the performance of adaptive multipopulation multiobjective genetic al-gorithm in comparison with several peer multiobjective evolutionary algorithms. The experimental results show that the proposed adaptive multipopulation multiobjective genetic algorithm performs well when solving the multiobjective ow shop deteriorating scheduling problem.

Keywords

Flow shop deteriorating scheduling problem deteriorating effect multiobjective evolutionary algorithm genetic algorithm multipopulation

Introduction

The production scheduling problem is one of the most well-known and difficult combinational optimization problems since it has widespread application in manufacturing.^1–4 In the classical scheduling problems, the processing time of a job is considered to be constant. However, the scheduling problem with this assumption maybe a limit to its application in a real-world case.^5,6 Recently, omitting this assumption and considering a variable processing time of a job has attracted many researchers’ interest in the production scheduling field.^7–9 Gupta et al. proposed a deteriorating scheduling model where the processing times of jobs depend on their starting time with a polynomial function.¹⁰ This scheduling model has widespread application in the manufacturing and service industries, such as steel-making, clean maintenance and fire fighting.

The flow shop scheduling is one of the most well-known scheduling problems in the engineering manufacturing and academic fields, and it appears in many real-world applications.^11–13 Recently, lots of researchers have studied the flow shop deteriorating scheduling problem (FSDSP). Zhao et al. considered a two-machine no-wait flow shop scheduling problem with deteriorating jobs and machine availability constraints, where the actual processing time of each job was a proportional function of its starting time.¹⁴ Zhao et al. considered the chain precedence constraints and proposed a two-machine flow shop scheduling with deteriorating jobs.¹⁵ Lee et al. investigated the two-machine scheduling problem with deteriorating jobs.¹⁶ Wang et al. proposed a three-machine flow shop scheduling problem with a deteriorating effect under the objective of minimizing the makespan.¹⁷

It is noticeable that existing studies on the flow shop deteriorating scheduling problem focus on two or three stages (machines), and there is little research on a multi-stage setting. However, research on the multi-stage flow shop deteriorating scheduling problem is necessary since it has widespread application in manufacturing systems. Mosheiov studied the complexity of the multi-stage flow shop scheduling problem with a deteriorating effect, and demonstrated that this kind of problem is non-deterministic polynomial (NP)-hard.¹⁸ Sun et al. considered the no-wait, no-idle multi-stage flow shop deteriorating scheduling problem with dominating machines under the objective of minimizing the makespan.¹⁹ Lee et al. investigated a multi-stage flow shop scheduling problem with deteriorating effect, where the objective was to minimize the total completion time.²⁰ Bank et al. applied a particle swarm optimization and simulated annealing algorithms to solve the flow shop scheduling problem with a deteriorating effect, where the objective was to minimize the total tardiness.²¹

Since many real-world applications usually involve multiple scheduling criteria,²² multiobjective flow shop deteriorating scheduling problems (MOFSDSPs) have gained increasing concern. Cheng et al. considered the objectives of minimizing the total completion time and makespan in two-stage flow shop deteriorating scheduling,²³ the constrain method was used to transform it as a single objective optimization problem, where the objective is to minimize the total completion time subject to the makespan. Cheng et al. proposed the two-machine flow shop deteriorating scheduling problem with the objectives of minimizing the completion time and the total flow time, the weighted sum method was used to transform it into one single objective optimization problem.²⁴ In fact, the major imperfection of the constrain method and the weighted sum method are that the preference information of the decision maker on the optimization problem must be given subjectively in advance.

However, the decision maker is not always experienced enough in real-word engineering manufacturing optimization problems, and it may lead to a great gap between the actual and expected solution. An alternative idea is to get a set of nondominated solutions, which would be provided to the decision maker to choose from. It is more flexible since the decision maker usually prefers one nondominated solution set instead of one solution.

By analyzing the existing studies, we conclude that prior research is mainly focused on the single objective flow shop deteriorating scheduling problem. However, it is difficult to meet the decision makers’ demands when taking multiple criteria into full account in making a schedule decision. Although the multiobjective flow shop scheduling problem has been considered in the work by Cheng et al., they investigated the two-machine setting, and only one optimal solution can be obtained by utilizing their proposed algorithm.^23,24 However, in an actual flow shop environment, there are usually multiple machines, and the decision makers want to get a set of optimal solutions to support their production management. In this case, the existing model and algorithm will not be suitable. To handle this, the general MOFSDSP needs to be addressed, and the production process is comprised of multiple machines. Also, in order to better describe a practical flow shop, besides the traditional constraints, e.g. the precedence constraints, the practical perspective, called the deteriorating effect, should be introduced. To do so, this work establishes the MOFSDSP, and its objectives are to minimize the makespan and the total tardiness simultaneously. In addition, a novel adaptive multipopulation multiobjective genetic algorithm (AMP-MOGA) is adopted to solve the proposed model based on its characteristics.

Compared with the existing research, we have three contributions.

The general multiobjective flow shop deteriorating scheduling problem is proposed to better describe the practical scheduling problem. It optimizes the objectives of minimizing the makespan and the total tardiness simultaneously when the decision maker wants to maximize the machine utilization and customers’ satisfactory degree.

To solve the proposed problem, a novel AMP-MOGA is designed, which includes developing the scalar optimization problem, constructing the multipopulation and the evolution of the multipopulation.

Via experiments on some test instances and comparing with the investigated algorithms in the literature, this work validates the effectiveness and feasibility of the proposed algorithm for solving the MOFSDSP.

The reminder of this paper is organized as follows. The ‘Problem formulation’ section is the problem definition in which the formulation and notations are described and a mixed integer programming model is presented. The solution method is proposed in the ‘Proposed algorithm’ section. Simulation experiments are carried out and the analysis on the experimental results are shown in the ‘Experimental studies’ section. The ‘Conclusion and future research’ section gives the conclusion and outlooks the future work.

Problem formulation

The MOFSDSP can be described as follows. n jobs need to be processed on m machines following the same route, and the jobs’ processing time depends on its starting time. The objectives are to minimize the makespan and the total tardiness simultaneously. The first objective is to maximize the machine utilization, while the second objective is to maximize the customers’ satisfactory level. The following assumptions are invoked for the investigated MOFSDSP.

Each machine can process no more than one job at any time, and each job can be processed on only one machine at any time.

Once a job starts to be processed on a machine, the process cannot be interrupted before completion.

The number of jobs and their normal processing times on each machine are deterministic.

All machines are persistently available, and machine breakdown is not allowable.

All jobs are ready for processing at the beginning and have no precedence constraint among them.

The parameters and decision variables are defined as follows.

Indices:

$J$ : the job set, $J = {1, 2, 3, \dots, n}$ , where $n$ is the number of jobs;

$M$ : the machine set, $M = {1, 2, 3, \dots, m}$ , where $m$ is the number of machines.

Symbol variables:

$p_{ij}$ : the normal processing time of job $j$ on machine $i$ ;

$α_{ij}$ : the deteriorating coefficient of job $j$ on machine $i$ ;

$d_{j}$ : the due date of job $j$ ;

$S_{ij}$ : the starting time of job $j$ on machine $i$ ;

$C_{ij}$ : the completion time of job $j$ on machine $i$ ;

$p'_{ij}$ : the actual processing time of job $j$ on machine $i$ , which is a linear function of its starting time, $p'_{ij} = p_{ij} + α_{ij} \cdot S_{ij}$ ;

$C_{\max}$ : the maximum completion time, that is, the makespan;

$T_{j}$ : the tardiness of job $j$ ;

$G$ : an infinity positive number.

Decision variables:

$x_{hj}$ : 0–1 integer decision variable, if job $h$ is followed by job $j$ , $x_{hj} = 1$ , otherwise $x_{hj} = 0$ .

Based on the above description and defined parameters, the mathematical model for the mOFSDSP can be presented by the following formulas

min C_{max}

(1)

min \sum_{j = 1}^{n} T_{j}

(2)

subject to

\begin{matrix} S_{ij} + p'_{ij} \leq S_{i + 1, j}, i = 1, 2, 3, \dots, m - 1, j = 1, 2, 3, \dots, n \\ S_{ih} + p_{ih} \leq S_{ij} + G \times (1 - x_{hj}), i = 1, 2, 3, \dots, m, \end{matrix}

(3)

h = 1, 2, 3, \dots, n, j = 1, 2, 3, \dots, n

(4)

p'_{ih} = p_{ij} + α \cdot S_{ij}, i = 1, 2, 3, \dots, n, j = 1, 2, 3, \dots, m

(5)

x_{hj} + x_{jh} = 1, h = 1, 2, 3, \dots, n, j = 1, 2, 3, \dots, n

(6)

C_{\max} \geq C_{mj}, j = 1, 2, 3, \dots, n

(7)

T_{j} ⩾ \max {C_{mj} - d_{j}, 0}, j = 1, 2, 3, \dots, n

(8)

S_{ij} \geq 0, C_{ij} \geq 0, i = 1, 2, 3, \dots, m, j = 1, 2, 3, \dots, n

(9)

x_{hj} \in {0, 1}, h = 1, 2, 3, \dots, n, j = 1, 2, 3, \dots, n

(10)

where the objectives given by equations (1) and (2) represent minimizing the makespan and minimizing the total tardiness, respectively. The constraint given by equation (3) ensures that each job can be processed on only one machine at any time. The constraint given by equation (4) ensures that each machine can process only one job at any time. The constraint given by equation (5) defines that the actual processing time of the job is a linear function of its starting time. The constraint given by equation (6) states the order relation of different jobs. The constraint given by equation (7) defines the makespan, and the constraint given by equation (8) defines the tardiness of job $j$ . The constraint given by equation (9) represents the range of variables. The constraint given by equation (10) represents that decision variable can take values of 0 or 1.

According to the three-field notation introduced by Graham,²⁵ the MOFSDSP can be denoted as $F ∣ p'_{ij} = p_{ij} + α_{ij} \cdot t ∣ C_{\max}, \sum T_{j}$ . As the above description, the goal for the proposed algorithm in this study is to find a set of nondominated solutions to minimize the makespan and the total tardiness simultaneously, which will be described in detail as follows.

Proposed algorithm

Evolutionary algorithms are stochastic optimization algorithms based on principles of natural selection and genetics which have been utilized to solve many optimization problems,^26–29 and it has been accepted as a basic tool for solving the multiobjective optimization problem.^30–32,35 The Multiobjective evolutionary algorithm based on decomposition (MOEA/D), proposed by Zhang et al. is a multiobjective evolutionary algorithm based on a decomposition approach, and it transforms the multiobjective optimization problem into a number of scalar optimization problems, of which optimal solutions are also the Pareto optimal solutions of the multiobjective optimization problem.³³

In the MOEA/D, each individual in the population associated with a different scalar optimization problem, and its solution replacement and selection operations are mainly based on the objective value of its corresponding problem. Inspired by the methodology of the MOEA/D, this study proposes an adaptive multipopulation strategy, which can realize the idea of utilizing a subpopulation to search the optimal solution of one scalar optimization problem. In order to balance the exploration and exploitation, the multipopulation would be constructed for the scalar optimization problems at each iteration based on the distribution of populations in the objective space and decision space. In the following, we will describe the AMP-MOGA in detail.

Scalar optimization problems construction method

In fact, a multiobjective optimization problem is composed of many or even infinite scalar optimization problems. For the MOFSDSP, let $w_{1}$ and $w_{2}$ be the weights of $C_{\max}$ and $\sum_{j = 1}^{n} T_{j}$ respectively, the objective value of one scalar optimization problem corresponding to this weight can be calculated with the formula below

min f = w_{1} \cdot C_{max} + w_{2} \cdot \sum_{j = 1}^{n} T_{j}

(11)

With this method, if multiple weight vectors are determined in advance, the MOFSDSP can be transformed into multiple ordinary scalar optimization problems. In order to solve them simultaneously, we can divide the whole population into multiple subpopulations, and each subpopulation solves one scalar optimization problem. In this study, we consider a set of $N$ different weight vectors (scalar optimization problems) to transform the MOFSDSP to some scalar optimization problems

W = {(w_{1}^{1}, w_{2}^{1}), (w_{1}^{2}, w_{2}^{2}), \dots, (w_{1}^{N}, w_{2}^{N})}

(12)

In the proposed algorithm, all the weight vectors are divided into multiple groups, and each group contains some uniform distributed scalar optimization problems. As shown in Figure 1, there are 10 scalar optimization problems and three groups developed. In the search process, the three groups are introduced by multiple stages to be solved. For the example, the whole search process is divided into three stages. In the first stage, group 1 is introduced as the current solved problem set. If the condition that allows us to introduce the next group is satisfied, then group 2 is added to the current solved problem set, and group 1 and group 2 are all of the current solved problems. Group 3 is added in the same manner. This method can utilize the good individuals found in the last stage and help to construct the higher quality subpopulation for the newly introduced scalar optimization problems.

Figure 1.

The method of dividing the single objective problems into multiple groups.

Population initialization method

As one of the classical combination optimization problems, an order encoding scheme can represent a feasible and complete scheduling solution. In this study, an order encoding scheme is used, and each individual is defined as a sequence of $n$ jobs, as is similar with most studies for the flow shop scheduling problem. For example, the individual $(3, 1, 4, 2)$ represents the four jobs that are processed as $3 \to 1 \to 4 \to 2$ . An initial population with good diversity can improve the exploration ability. In order to maintain the diversity of the initial population, this study generates the initial population randomly in the decision space.

Multipopulation construction method

From the above discussion, multiple scalar optimization problems can be constructed by different weight vectors, which will be introduced into the current solved problem set in multiple stages. In order to solve the current solved problem set in parallel, this study proposes an adaptive multipopulation strategy, where multiple subpopulations are constructed for the current solved problems, based on the distribution of population in the objective space and decision space at each iteration. A subpopulation contains the best individual of its scalar optimization problem and similar individuals with this best individual. Therefore, the method of constructing multipopulation can be divided into two steps:

identify the best individuals found for each current solved problem;

select the most similar individuals with the best individuals to construct their corresponding subpopulation.

It is worth noting that each individual only belongs to one subpopulation in the proposed adaptive multipopulation strategy. The method of constructing the multipopulation is shown in Figure 2.

Figure 2.

Pseudo-code for constructing the multipopulation.

Due to the characters in the investigated MOFSDSP, the similar degree between two individuals can be measured by the total difference of jobs’ completion time on the last machine, which is shown by equation (13)

Sim (p, q) = \sum_{l = 1}^{n} ∣ C_{pl} - C_{ql} ∣

(13)

where $p$ and $q$ are the two different individuals and $C_{pl}$ and $C_{ql}$ represent the job’s completion time in the $l th$ position on the last machine of individual $p$ and individual $q$ , respectively. The smaller the $Sim (p, q)$ is, the more similar they are.

Genetic operations

In the proposed AMP-MOGA, multiple subpopulations are constructed and evolved to search for the optimal solutions of their corresponding scalar optimization problems in parallel. Each constructed subpopulation would undergo the genetic operations (selection, crossover and mutation) at every generation.

In order to explore the whole of the Pareto front, the information exchange mechanism among the different subpopulations is considered in the selection operation. One of the parent individuals is selected from the current subpopulation, and the other one is selected from the same subpopulation, the other subpopulation or the external archive. After selecting a pair of parent individuals, the order crossover operation is used to produce offspring individuals and the swap mutation scheme is executed upon the offspring individuals.

In order to avoid losing the useful information found in the search process, an external archive is used to store the nondominated solution found. It will be updated by the newly-generated individuals at each generation according to the Pareto rule. If one solution is dominated by any solution in the external archive, it will be discarded. If one solution is nondominated with all the solutions in the external archive, then it will be added to the external archive. If one solution dominates some solutions in the external archive, then it will be added to the external archive and the dominated solutions are deleted. In order to refine and extend the external archive, the genetic operations are also executed to the external archive.

Based on the above description, the framework of the AMP-MOGA in solving the MOFSDSP is shown in Figure 3.

Figure 3.

The framework of the AMP-MOGA.

Experimental studies

In this section, the simulation experiments are carried out to examine the performance of the AMP-MOGA in solving the MOFSDSP. Several state-of-the-art algorithms are chosen as the compared algorithms. The involved algorithms include NSGAII which is one of the most classical algorithms,³⁴ MOEA/D which is the original idea of the AMP-MOGA,³³ and Bi-objective multi-start simulated-annealing (BMSA) which is a novel multiobjective optimization algorithm for solving a multiobjective flow shop scheduling problems.³⁶

Test instances

Several test instances with different sizes are generated randomly. The number of machines are set to 2, 5 and 10, and the number of jobs are set to 10, 20, 30, 40 and 50, respectively. Therefore, there are in total 15 test instances. The processing times of the jobs on each machine are generated from U[1,20] and the deteriorating coefficient of each job on each machine is generated from U[0,0.3]. The due date of the jobs is generated from U[0,C], where C is the makespan of a solution generated randomly.

Experimental setting

The parameter setting of the AMP-MOGA is as follows. The population size is set to 100. The allowable maximum subpopulation size is set to 10, and the total number of scalar optimization problem is 50. The crossover and mutate probability is set to 1.0 and 0.5, respectively. The total number of function evaluations is taken as the stop condition in all experiments, and it is set to 10,0000. Every 20,000 function evaluations, 10 scalar optimization problems (one group) are introduced. The framework and parameter setting of NSGAII and MOEA/D are referred to in the study by Chang et al.,³⁷ and the parameter setting of BMSA is referred to in its original study.

For all the investigated algorithms for the test problem, 30 independent runs are executed and all experimental results are averaged over 30 runs. In order to compare the experimental results clearly, the $t$ -test is used. In the following experiments, the symbols (‘+’, ‘-’ or ‘∼’) denotes the statistical results of comparing the proposed algorithm with the compared algorithms by the one-tailed $t$ -test with 58 degrees of freedom at a 0.05 level of significance. The $t$ -test results are shown as ‘+’, ‘-’ or ‘∼’ when the proposed algorithm is significantly better than, significantly worse than, or statistically equivalent to the compared algorithm.

Experimental results and analysis

To have a fair comparison, the following three performance metrics are used to evaluate the performance of the investigated algorithms in our experiments.

$C - metric$ :³⁸ this metric is evaluated by comparing the coverage of two nondominated solution sets. Let $X$ and $Y$ be two approximated nondominated solution sets obtained by two different algorithms, $C (X, Y)$ is defined as the percentage of the solutions in $Y$ that are dominated by at least one solution in $X$ , and it can be calculated as equation (14). It is worth noting that the value $C (X, Y) = 1$ means all solutions in $Y$ are dominated by the solutions in $X$ , while $C (X, Y) = 0$ implies no solution in $Y$ is dominated by the solutions in $X$ . Note that always both directions have to be considered, since $C (X, Y)$ is not necessarily equal to $1 - C (Y, X)$

C (X, Y) = \frac{∣ y \in Y ∣ \exists x \in X : x ≻ y ∣}{∣ Y ∣}

(14)

$GD - metric$ :³⁹ this metric is evaluated by computing the average distance from the nondominated solutions to the optimal nondominated solution set as equation (15). $\bar{P}$ is the nondominated solution set obtained by the investigated algorithms, $P^{*}$ is the optimal nondominated solution set, $d (v, P^{*})$ is the Euclidean distance in the objective space from one solution in $\bar{P}$ to its nearest point in $P^{*}$ . Since we can not get the $P^{*}$ of the MOFSDSP, this paper combines all the nondominated solutions obtained by the investigated algorithms, and the dominated solutions are discarded, then the left solutions will be seen as the optimal nondominated solution set

GD (\bar{P}, P^{*}) = \frac{\sum_{v \in \bar{P}} d (v, P^{*})}{∣ \bar{P} ∣}

(15)

$IGD$ -metric:⁴⁰ this metric is used to evaluate the average distance from $P^{*}$ to $\bar{P}$ , and is given by equation (16). $d (v, \bar{P})$ is the Euclidean distance from one solution $v$ in $P^{*}$ to its nearest solution in $\bar{P}$ . The difference between the $GD$ -metric and $IGD$ -metric is that the $IGD$ -metric can measure the approximation and distribution of the nondominated solution, while the $GD$ -metric can only measure its approximation. It is noticeable that all of the objectives should be normalized firstly to evaluate $GD$ -metric and the $IGD$ -metric

IGD (\bar{P}, P^{*}) = \frac{\sum_{v \in P^{*}} d (v, \bar{P})}{∣ P^{*} ∣}

(16)

In the following experiments, we will compare the investigated algorithms in the $C$ -metric, $GD$ -metric and $IGD$ -metric. Table 1, Table 2 and Table 3 show the experimental results for the three metrics in all the test instances. In Table 1, the symbols ‘A’, ‘B’, ‘C’ and ‘D’ represent AMP-MOGA, NSGAII, MOEA/D and BMSA, respectively. From the experimental results, the following conclusions can be observed.

Table 1.

Comparison of the experimental results for the three algorithms via the $C$ -metric.

$m \times n$	C(A,B)	C(B,A)	t-test	C(A,C)	C(C,A)	t-test	C(A,D)	C(D,A)	t-test
$2 \times 10$	0.92	0.00	+	0.00	0.00	~	0.00	0.00	~
$2 \times 20$	0.99	0.00	+	0.32	0.20	+	1.00	0.00	+
$2 \times 30$	1.00	0.00	+	0.77	0.18	+	1.00	0.00	+
$2 \times 40$	0.87	0.13	+	1.00	0.00	+	0.98	0.05	+
$2 \times 50$	1.00	0.00	+	1.00	0.00	+	1.00	0.00	+
$5 \times 10$	0.99	0.00	+	0.05	0.00	+	0.02	0.01	~
$5 \times 20$	1.00	0.00	+	1.00	0.00	+	0.92	0.05	+
$5 \times 30$	1.00	0.00	+	0.77	0.12	+	0.95	0.03	+
$5 \times 40$	0.96	0.02	+	1.00	0.00	+	0.90	0.12	+
+	0.85	0.03	+	1.00	0.00	+	0.52	0.42	+
$10 \times 10$	0.98	0.00	+	0.02	0.01	~	0.06	0.02	~
$10 \times 20$	1.00	0.00	+	1.00	0.00	+	0.80	0.18	+
$10 \times 30$	1.00	0.00	+	1.00	0.00	+	0.86	0.08	+
$10 \times 40$	1.00	0.00	+	1.00	0.00	+	0.57	0.26	+
+	0.80	0.20	+	1.00	0.00	+	0.86	0.13	+

Table 2.

Comparison of the experimental results for the three algorithms via the $GD$ -metric.

$m \times n$	AMP-MOGA	NSGAII	t-test	MOEA/D	t-test	BMSA	t-test
$2 \times 10$	0.0000	0.2728	+	0.0001	~	0.0000	~
$2 \times 20$	0.0043	0.2203	+	0.0059	~	0.0532	+
$2 \times 30$	0.0215	0.3252	+	0.1239	+	0.1758	+
$2 \times 40$	0.0375	0.0538	+	1.0804	+	0.0825	+
$2 \times 50$	0.0060	0.0205	+	1.1787	+	0.0168	+
$5 \times 10$	0.0004	0.1743	+	0.0004	~	0.0010	+
$5 \times 20$	0.0421	0.2212	+	1.0455	+	0.0853	+
$5 \times 30$	0.0654	0.3774	+	0.7793	+	0.1436	+
$5 \times 40$	0.0216	0.1082	+	1.2776	+	0.0396	+
$5 \times 50$	0.0385	0.0515	+	1.2780	+	0.0394	~
$10 \times 10$	0.0052	0.2450	+	0.0059	~	0.0057	~
$10 \times 10$	0.0669	0.2664	+	0.9881	+	0.0911	+
$10 \times 10$	0.0287	0.2075	+	1.1249	+	0.0598	+
$10 \times 10$	0.0690	0.1461	+	1.2486	+	0.0870	+
$10 \times 10$	0.0287	0.0663	+	1.2615	+	0.0360	+

Table 3.

Comparison of the experimental results for the three algorithms via the $IGD$ -metric

$m \times n$	AMP-MOGA	NSGAII	t-test	MOEA/D	t-test	BMSA	t-test
$2 \times 10$	0.0000	0.2796	+	0.0159	+	0.0001	~
$2 \times 20$	0.0124	0.2396	+	0.0341	+	0.0931	+
$2 \times 30$	0.0172	0.2397	+	0.1382	+	0.1575	+
$2 \times 40$	0.0259	0.0865	+	1.0696	+	0.1417	+
$2 \times 50$	0.0100	0.0687	+	1.1898	+	0.0915	+
$5 \times 10$	0.0004	0.1575	+	0.0131	~	0.0004	~
$5 \times 20$	0.0399	0.2239	+	1.0834	+	0.1490	+
$5 \times 30$	0.0542	0.3465	+	0.8148	+	0.1354	+
$5 \times 40$	0.0222	0.0934	+	1.2353	+	0.0694	+
$5 \times 50$	0.0325	0.0516	+	1.2203	+	0.0495	+
$10 \times 10$	0.0211	0.2455	+	0.1338	~	0.0263	~
$10 \times 20$	0.1060	0.2770	+	0.9336	+	0.1760	+
$10 \times 30$	0.0710	0.1807	+	1.0994	+	0.1083	+
$10 \times 40$	0.0454	0.1408	+	1.1838	+	0.0499	~
$10 \times 50$	0.0186	0.0581	+	1.2084	+	0.0378	+

Firstly, AMP-MOGA always performs better than NSGAII in terms of the three metrics in all the test instances. As shown in Table 1, most values of $C$ (A,B) are equal to 1.00, while almost all values of $C$ (B,A) are equal to zero. This means that all dominated solutions generated by NSGAII are dominated by those generated by AMP-MOGA. The similar observations also can be obtained by the $GD$ -metric and $IGD$ -metric. The values of the $GD$ -metric and $IGD$ -metric for AMP-MOGA in all the test instances are smaller than those of the NSGAII. This shows that the nondominated solution set obtained by AMP-MOGA is much closer to the optimal set and even distribution. In AMP-MOGA, the MOFSDSP is transformed into a multiple scalar optimization problem, which can be used to make its search only focus on the optimal solutions of all generated scalar optimization problems. The multipopulation strategy can enhance its exploitation ability to achieve the true Pareto front. The significant advantage of AMP-MOGA over NSGAII shows that these two operations do improve the performance of AMP-MOGA.

Secondly, the AMP-MOGA outperforms MOEA/D significantly in almost all of the test instances, while the AMP-MOGA exhibits the same performance in a few test instances. For example, most values of $C$ (A,C) are equal to 1.00 and almost all of the values are equal to 0.00. The similar results can also be observed when comparing the performance of the AMP-MOGA with the MOEA/D in terms of $GD$ -metric and $IGD$ -metric, which indicates that the nondominated solution set obtained by the AMP-MOGA is much closer to the true Pareto front than those by MOEA/D. This happens because each generated scalar optimization problem would be solved by using a subpopulation in the AMP-MOGA, rather than utilizing several neighbor dependent individuals in the MOEA/D. The experimental results show that this multipopulation strategy is very helpful to enhance the exploitation ability in searching the optimal solution of scalar optimization problem, and can make the population closer to the true Pareto optimal solutions.

Finally, compared with the BMSA, AMP-MOGA also exhibits the superiority in many test instances. The experimental results indicate that the nondominated solutions obtained by the AMP-MOGA can dominate almost all of the solutions obtained by BMSA, and they are much closer to the Pareto front and even the distribution.

In order to illustrate the nondominated solution obtained by the investigated algorithm, two instances are chosen to show the nondominated solution sets obtained by the proposed algorithm and the compared algorithms in Figures 4 and 5. Compared to the compared algorithms, the proposed algorithm can get the nondominated solution set with better approximation and more uniform distribution.

Figure 4.

Nondominated solutions obtained by the different algorithms for $2 \times 30$ .

Figure 5.

Nondominated solutions obtained by the different algorithms for $5 \times 30$ .

Conclusion and future research

This work addresses a general MOFSDSP for the first time, and its goal is to minimize the makespan and the total tardiness simultaneously. In order to solve it, an AMP-MOGA is proposed. Simulation experiments are carried out on some stochastic instances, and the experimental results show that the proposed algorithm can solve the model effectively and efficiently, and can generate an approximated Pareto solution set of a general multiobjective flow shop deteriorating scheduling problem. The proposed algorithm can be used to guide decision makers in making better decisions when the deteriorating effect occurs in a general flow shop, and it can provide a new method to find a good scheduling decision.

For the future work, it is straightforward to research a more complicated and realistic deteriorating scheduling problem, e.g. the hybrid flow shop deterioration scheduling problem. It is also necessary to investigate the uncertainty in the the flow shop deteriorating scheduling problem because the uncertainty usually appears in the manufacturing systems,^41,42 e.g. the machine breakdown, job rework and undetermined processing time.

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 is supported by the National Science Foundation for Distinguished Young Scholars of China (grant numbers 71325002, 61225012); the Major International Joint Research Project of NSFC (grant number 71620107003); the National Nature Science Foundation of China (grant numbers 71671032, 61525302, 61590922); the Fundamental Research Funds for the Central Universities (grant number N160402002); Shandong Provincial Natural Science Foundation, China (grant number ZR2016FP02), Qingdao Postdoctoral Research Project (grant number 2016027).

References

Pinedo

Scheduling, theory, algorithms and systems[M]. New Jersey: Prentice Hall, 2002.

Xie

Zhang

Shao

. An effective hybrid teaching–learning-based optimization algorithm for permutation flow shop scheduling problem[J]. Adv Eng Softw 2014; 77: 35–47. http://www.sciencedirect.com/science/article/pii/S0965997814001173

Pan

Mao

. A discrete teaching-learning-based optimisation algorithm for realistic flowshop rescheduling problems. Eng Appl Artif Intell 2015; 37: 279–292.

Zhang

Jiang

. Low-carbon scheduling and estimating for a flexible job shop based on carbon footprint and carbon efficiency of multi-job processing. P I Mech Eng B-J Eng 2015; 229(2): 328–342.

Jin

Zhang

Shao

. Mathematical modeling and a memetic algorithm for the integration of process planning and scheduling considering uncertain processing times. P I Mech Eng B-J Eng 2016; 32(32): 245–256.

Shahmoradi-Moghaddam

Akbari

Sadjadi

. A scenario-based robust optimization approach for batch processing scheduling. P I Mech Eng B-J Eng 2016; 230(12): 2286–2295.

Cheng

TCE

Ding

Lin

BMT

. A concise survey of scheduling with time-dependent processing times. Eur J Oper Res 2004; 152(1): 1–13.

Cheng

. Ant colony algorithms for a two-agent scheduling with sum-of processing times-based learning and deteriorating considerations. J Intell Manuf 2012; 23(5): 1985–1993.

Wang

Y P

Huang

. Multiobjective optimisation design for enterprise system operation in the case of scheduling problem with deteriorating jobs. Enterp Inf Syst 2016; 10(3): 268–285.

10.

Gupta

JND

Gupta

. Single facility scheduling with nonlinear processing times. Comput Ind Eng 1988; 14(4): 387–393.

11.

Sun

Zhang

Gao

. Multi-objective optimization algorithms for flow shop scheduling problem: A review and prospects. Int J Adv Manuf Tech 2011; 55(5–8): 723–739.

12.

Liu

Ullah

Zhang

. An improved genetic algorithm for robust permutation flowshop scheduling. Int J Adv Manuf Tech 2011; 56(1–4): 345–354.

13.

Seidgar

Zandieh

Fazlollahtabar

. Simulated imperialist competitive algorithm in two-stage assembly flow shop with machine breakdowns and preventive maintenance. P I Mech Eng B-J Eng 2016; 230(5): 934–953.

14.

Zhao

Tang

. A note on two-machine no-wait flow shop scheduling with deteriorating jobs and machine availability constraints. Optim Lett 2011; 5(1): 183–190.

15.

Zhao

Tang

. Two-machine flow shop scheduling with deteriorating jobs and chain precedence constraints. Int J Prod Econ 2012; 136(1): 131–136.

16.

Lee

Yen

Chung

. Total tardiness minimizaton in permutation flow shop with deterioration consideration. Appl Math Model 2014; 38(13): 3081–3092.

17.

Wang

. Minimizing makespan in three-machine flow shops with deteriorating jobs. Comput Oper Res 2013; 40(2): 547–557.

18.

Mosheiov

. Complexity analysis of job-shop scheduling with deteriorating jobs. Discrete Appl Math 2002; 117(1): 195–209.

19.

Sun

Wang

. Flow shop makespan minimization scheduling with deteriorating jobs under dominating machines. Int J Prod Econ 2012; 138(1): 195–200.

20.

Lee

Chung

. Minimizing the total completion time in permutation flow shop with machine-dependent job deterioration rates. Comput Oper Res 2009; 36(6): 2111–2121.

21.

Bank

Ghomi

SMTF

Jolai

. Application of particle swarm optimization and simulated annealing algorithms in flow shop scheduling problem under linear deterioration. Adv Eng Softw 2012; 47(1): 1–6.

22.

Kumar

Padmanaban

Rajkumar

. Minimizing makespan and total flow time in permutation flow shop scheduling problems using modified gravitational emulation local search algorithm. P I Mech Eng B-J Eng 2018; 232(3): 534–545.

23.

Cheng

Tadikamalla

Shang

. Two-machine flow shop scheduling problem with deteriorating jobs: Minimizing the weighted sum of makespan and total completion time. J Oper Res Soc 2014; 124(1): 188–197.

24.

Cheng

Tadikamalla

Shang

. Bicriteria hierarchical optimization of two-machine flow shop scheduling problem with time-dependent deteriorating jobs. Eur J Oper Res 2014; 234(3): 650–657.

25.

Graham

Lawler

Lenstra

. Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann Discrete Math 1979; 5(4): 287–326.

26.

Moparthi

Das

Uppaluri

. Optimization of heat fluxes on the heater and the design surfaces of a radiating-conducting medium. Numer Heat Tr A-Appl 2009; 56(10): 846–860.

27.

Ajith

Das

Uppaluri

. Boundary surface heat fluxes in a square enclosure with an embedded design element[J]. J Thermophys Heat Tr 2010; 24(4): 845–849. http://arc.aiaa.org/doi/abs/10.2514/1.49910?journalCode=jtht

28.

Das

Mishra

Kumar

. An inverse analysis for parameter estimation applied to a non-Fourier conduction-radiation problem. Heat Transfer Eng 2011; 32(6): 455–466.

29.

Singla

Das

. Application of decomposition method and inverse prediction of parameters in a moving fin. Energ Convers Manage 2014; 84: 268–281.

30.

Mondal

Sarangi

Pettersson

. CuDZn separation by supported liquid membrane analyzed through multi-objective genetic algorithms. Hydrometallurgy 2011; 107(3): 112–123.

31.

Singh

Das

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

32.

Pettersson

Saxen

Deb

. Genetic algorithm-based multicriteria optimization of ironmaking in the blast furnace. Mater Manuf Process 2009; 24(3): 343–349.

33.

Zhang

. MOEA/D: A multiobjective evolutionary algorithm based on decomposition. IEEE T Evolut Comput 2007; 11(6): 712–731.

34.

Deb

Pratap

Agarwal

. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE T Evolut Comput 2002; 6(2): 182–197.

35.

Garg

Jain

Bhushan

. Modelling and multi-objective optimization of process parameters of wire electrical discharge machining using non-dominated sorting genetic algorithm-II. P I Mech Eng B-J Eng 2012; 226(12): 1986–2001.

36.

Lin

Ying

. Minimizing makespan and total flowtime in permutation flowshops by a bi-objective multi-start simulated-annealing algorithm. Comput Oper Res 2013; 40(6): 1625–1647.

37.

Chang

Chen

Zhang

. MOEA/D for flowshop scheduling problems. In: Proceedings of 2008 IEEE world congress on computational intelligence on evolutionary computation, Hong Kong, 1–6 June 2008, pp. 1433–1438. New York: IEEE.

38.

Zitzler

. Performance assessment of multiobjective optimizers: An analysis and review. IEEE T Evolut Comput 2003; 7(2): 117–132.

39.

Van Veldhuizen

. Multiobjective evolutionary algorithms: Classifications, analyses, and new innovations. Evol Comput 1999; 8(2): 125–147.

40.

Zhang

Zhou

Jin

. RM-MEDA: A regularity model-based multiobjective estimation of distribution algorithm. IEEE Trans Evolut Comput 2008; 12(1): 41–63.

41.

Tian

Zhou

Chu

. A chance constrained programming approach to determine the optimal disassembly sequence. IEEE Trans Autom Sci Eng 2013; 10(4): 1004–1013.

42.

Tian

Zhou

Chu

. Stochastic cost-profit tradeoff model for locating an automotive service enterprise[J]. IEEE Trans Autom Sci Eng 2015; 12(2): 580–587. http://ieeexplore.ieee.org/abstract/document/6736129/

Multiobjective flow shop deteriorating scheduling problem via an adaptive multipopulation genetic algorithm

Abstract

Keywords

Introduction

Problem formulation

Proposed algorithm

Scalar optimization problems construction method

Population initialization method

Multipopulation construction method

Genetic operations

Experimental studies

Test instances

Experimental setting

Experimental results and analysis

Conclusion and future research

Footnotes

Declaration of conflicting interests

Funding

References