Sage Journals: Discover world-class research

Abstract

This study presents a blocking flow shop deteriorating scheduling problem which has a widespread application in manufacturing and service systems. In the investigated problem, there is no buffer between machines, and the actual processing time of jobs on each machine is described as a linear function of their starting time and normal processing time. In order to deal with this problem more efficiently, this study develops a hybrid chemical reaction optimization algorithm, where some special strategies are developed based on the problem characteristics, for example, solution representation, on-wall ineffective collision, decomposition, inter-molecule ineffective collision, and synthesis reactions. In addition, a variable neighborhood search is designed to strengthen the search ability of the chemical reaction optimization algorithm. Computational simulation experiments on a set of instances and performance comparisons are provided. They show that the proposed algorithm is superior to the standard chemical reaction optimization and genetic algorithm, which demonstrates that the proposed algorithm is a promising optimizer for the investigated problem.

Keywords

Flow shop deteriorating scheduling chemical reaction optimization variable neighborhood search

Introduction

Flow shop scheduling is one of the most well-known and difficult combination optimization problems,^1,2 and it has a widespread application in manufacturing systems, even in service systems.^3,4 In recent years, it has gained an increasing concern from operational and industrial communities.^5,6 As for the computational complexity, it has been proved that the flow shop scheduling problem with more than two machines is nondeterministic polynomial (NP)-hard in the strong sense.⁷ Therefore, the flow shop scheduling problem has been extensively studied in the past few years.^8–11

In order to make the scheduling models more suitable for real-world manufacturing systems, Gupta and Gupta¹² investigated a deteriorating scheduling model in a single machine case, where the processing time of jobs was an increasing function of their starting time. Since the deteriorating scheduling model can describe a scheduling problem more comprehensively, it has attracted much attention in manufacturing and service systems. The flow shop deteriorating scheduling problem has been extensively studied in recent years,^13–16 and it has been proven to be an NP-hard problem when there are more than two machines.¹⁷ The blocking flow shop scheduling problem is one of the best known branches of the flow shop scheduling problem.^18,19 It usually appears in the environment where the processed jobs are kept in the machines because of lack of intermediate storage²⁰ or storage is not allowed in the manufacturing process due to the technological requirements.²¹ In the blocking flow shop scheduling problem, there are no buffers between machines, and the jobs that have been completed processing on a machine has to remain on that machine until the next machine is available. Since the blocking flow shop scheduling problem is important in both academic and engineering applications, great attention has been paid to develop its effective techniques.^22–25 However, the blocking flow shop deteriorating scheduling problem has not attracted so much attention in existing studies. Over the past decades, some efforts have been made to the two-machine flow shop deteriorating scheduling problem.^26–28 Nevertheless, the existing scheduling model and solution techniques are not suitable for solving the blocking flow shop deteriorating scheduling problem when there are more than two machines in a blocking flow shop environment. Therefore, it is necessary to develop a suitable scheduling model and optimization algorithm to cope with this problem.

Chemical reaction optimization (CRO) algorithm is one of the best known population-based meta-heuristic algorithms.^29,30 It mimics the behavior of the molecules in a chemical reaction system microscopically and tries to capture the phenomenon that reactions give products with the lowest energy. Since the CRO is effective and easily implemented, it has gained a wide range of successful applications in vehicle routing problem,³¹ job shop scheduling problem,³² knapsack problem,³³ grid scheduling problem³⁴ in the past few years. Since the optimization problems we have to deal with become more and more complex, it is necessary to investigate the effective meta-heuristic frameworks to deal with real-world and large-scale optimization problems. Recently, the reasonable combination of two or more meta-heuristic techniques shows the superiority in improving the performance of algorithm, and it plays an important role in solving some optimization problems nowadays.³⁵ Therefore, this study aims to design a hybrid framework to make the CRO algorithm more powerful to deal with the complexity optimization problem like the investigated blocking flow shop deteriorating scheduling problem in this study.

Motivated by the existing research on the flow shop deteriorating scheduling problem, we can conclude that there are few studies focusing on the blocking flow shop deteriorating scheduling problem with more than two machines. However, there are multiple machines in the real-world situation, for example, in the production of steel, the molten steel undergoes a series of operations such as molding into ingots, unmolding, reheating, soaking, and preliminary rolling.³⁶ This is a classical blocking production environment due to the production technology and lack of storage capacity between the intermediate machines or work stations. In addition, the jobs in this situation could lose heat energy, and the longer processing time will be needed if they are processed later. In order to describe the practical production process like this situation, this article proposes a blocking flow shop deteriorating scheduling problem, where multiple machines in series are needed to process a set of jobs. A 0-1 mixed integer programming model is built to minimize the maximum completion time, that is, the makespan. In order to address this problem efficiently, a hybrid CRO algorithm is developed, where the solution representation and four elementary reactions are designed based on the problem characteristics. In addition, a variable neighborhood search (VNS) algorithm is designed to strengthen its search ability. Simulation experiments are carried out, and the experimental results demonstrate that the proposed algorithm is more effective than the compared algorithms in coping with this problem.

The rest of this article is organized as follows. The blocking flow shop deteriorating scheduling problem is formulated in section “Problem definition.” The basic idea of standard CRO (SCRO) is introduced in section “Basic idea of SCRO.” Section “Proposed algorithm” describes the proposed algorithm. The simulation experiments are carried out, and the analysis on the experimental results is shown in section “Computation results and comparisons.” Section “Conclusion” gives the conclusion and outlooks the future research.

Problem definition

The blocking flow shop deteriorating scheduling problem can be defined as follows. Each of n jobs from the set $J = {1, 2, \dots, n}$ has to be processed on m machines from the set $M = {1, 2, \dots, m}$ following the same route, and there is no intermediate buffer between different machines. Each job $j \in J$ has m operations $O (1, j), O (2, j), \dots, O (m, j)$ . The operation $O (i, j)$ corresponds to the processing of job j on machine i, and $p_{ij}$ and $p'_{ij}$ denote its normal processing time and actual processing time, respectively; $S_{ij}$ and $α_{ij}$ represent its starting time and deteriorating rate, respectively, where $p'_{ij}$ is defined as $p'_{ij} = p_{ij} + α_{ij} \cdot S_{ij}$ . At any time, each machine can only process one job, and each job can be processed on at most one machine. Since this flow shop case has no intermediate buffers, a job j, which has completed the processing of the operation $O (i, j)$ , cannot leave the machine i until the next machine $i + 1$ is available, $i = 1, 2, \dots, m - 1$ , $j = 1, 2, \dots, n$ . In other words, if the machine $i + 1$ is not free, then the machine i is blocked by the job j. Let $x_{hj}$ represent the order relation of jobs h and j, if job h is followed by job j immediately, then $x_{hj}$ is equal to 1, otherwise $x_{hj}$ is equal to 0. G denotes an infinite positive. The objective is to find a schedule such that the maximum completion time $C_{\max}$ is minimized

\min C_{\max}

(1)

\begin{array}{l} s . t . S_{i j} + G \cdot (1 - x_{h j}) \geq S_{i + 1, h}, \\ i = 1, 2, …, m - 1, h = 1, 2, …, n, \\ j = 1, 2, …, n \end{array}

(2)

S_{ij} \geq S_{i - 1, j} + p'_{i - 1, j}, i = 2, 3, \dots, m, j = 1, 2, \dots, n

(3)

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

(4)

p'_{ij} = p_{ij} + α_{ij} \geq S_{ij}, i = 1, 2, \dots, j = 1, 2, \dots, n

(5)

C_{\max} \geq S_{mj} + p'_{mj}, j = 1, 2, \dots, n

(6)

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

(7)

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

(8)

where equation (1) represents that the objective is to minimize the maximum completion time. Constraints (2) and (3) ensure that at any time, each job can be processed on one machine and each machine can process at most one job, and they also ensure that a job is allowed to leave if the next machine is free. Constraint (4) stipulates the order relation of the different jobs. Constraint (5) denotes that the actual processing time of jobs is an increasing linear function of their starting time. Constraint (6) defines the maximum completion time. Constraint (7) demonstrates the range of variables. Constraint (8) represents that the decision variables can take values of 0 or 1.

Basic idea of SCRO

CRO was proposed by Lam and colleagues^29,30 in 2010, which simulates the chemical reactions of a set of molecules microscopically and tries to capture the energy in the reaction process. In the following sections, the basic idea of SCRO is described in detail.

Elementary element of CRO

Molecule is an elementary element of CRO, and the molecular structure represents a solution of the investigated optimization problem. A molecule is composed of several atoms, which is characterized by the atom type, that is, bond length, angle, and torsion. The molecules are distinguished by the atoms and the atom type. In the SCRO, each molecule has two kinds of energies, which are called PE (potential energy) and KE (kinetic energy). The PE corresponds to the objective value of a molecule, whereas the KE indicates the ability of a molecule to escape from local optima. Let $ω$ be a molecule, and its PE can be shown as follows

P E_{ω} = f (ω)

(9)

Suppose that a new molecule $ω'$ is generated by $ω$ , the condition that allows $ω'$ to replace $ω$ in CRO is as follows

P E_{ω} + K E_{ω} \geq P E_{ω'}

(10)

Elementary reactions of CRO

CRO optimizes a problem by four elementary reactions called on-wall ineffective collision, decomposition, inter-molecular ineffective collision, and synthesis reactions. The new molecules will be generated based on the original molecules in the population by the four reactions. If some condition satisfies, the new molecules are allowed to replace the original molecules. The four elementary reactions are described as follows.

On-wall ineffective collision reaction

The on-wall ineffective collision occurs if a molecule $ω$ hits the wall and bounces back. The collision changes its molecular structure, and a new molecule $ω'$ is generated. The condition in formula (9) must be satisfied if $ω'$ is allowed to replace $ω$ . After the on-wall ineffective collision reaction, the KE of molecule $ω$ will transfer some percent of KE to the energy buffer, and the KE of molecule $ω'$ can be computed as follows

K E_{ω'} = (P E_{ω} + K E_{ω} - P E_{ω'}) \times q

(11)

where $q \in [KELossRate, 1]$ , and KELossRate is a parameter limiting the maximum percentage of KE lost at a time. $1 - q$ represents the KE lost to the energy buffer after the on-wall ineffective collision reaction, and the update of the buffer is shown as follows

buffer = buffer + (P E_{ω} + K E_{ω} - P E_{ω'}) \times (1 - q)

(12)

Decomposition reaction

The decomposition is described as the process of hitting the wall. This collision makes the molecule $ω$ decompose into two new molecules $ω'_{1}$ and $ω'_{2}$ . Two situations should be considered for the decomposition reactions: (1) the molecule $ω$ has sufficient energy to complete the decomposition and (2) the energy stored in the buffer is used to trigger the decomposition reaction.

Situation 1. The condition in which this situation occurs is as follows

P E_{ω} + K E_{ω} \geq P E_{{ω'}_{1}} + P E_{{ω'}_{2}}

(13)

The KE of $ω'_{1}$ and $ω'_{2}$ are shown as follows

K E_{ω_{1}'} = (P E_{ω} + K E_{ω} - P E_{ω_{1}'} - P E_{ω_{2}'}) \times q

(14)

K E_{ω_{2}'} = (P E_{ω} + K E_{ω} - P E_{ω_{1}'} - P E_{ω_{2}'}) \times (1 - q)

(15)

Situation 2. The condition in which this situation occurs is as follows

buffer + P E_{ω} + K E_{ω} \geq P E_{ω_{1}'} + P E_{ω_{2}'}

(16)

The KE of $ω'_{1}$ and $ω'_{2}$ are shown as follows

K E_{ω_{1}'} = (P E_{ω} + K E_{ω} - P E_{ω_{1}'} - P E_{ω_{2}'} + buffer) \times k_{1} \times k_{2}

(17)

K E_{ω_{2}'} = (P E_{ω} + K E_{ω} - P E_{ω_{1}'} - P E_{ω_{2}'} + buffer) \times k_{3} \times k_{4}

(18)

where $k_{1}$ , $k_{2}$ , $k_{3}$ , and $k_{4}$ are randomly generated from a uniform distribution $U [0, 1]$ . The buffer is updated as the following formula

b u f f e r = b u f f e r + (P E_{ω} + K E_{ω} - P E_{{ω^{'}}_{1}} - K E_{{ω^{'}}_{1}} - P E_{{ω^{'}}_{2}} - P E_{{ω^{'}}_{2}})

(19)

Inter-molecule ineffective collision reaction

The inter-molecule ineffective collision is used to mimic the process of the two molecules $ω_{1}$ and $ω_{2}$ colliding with each other and bouncing away. The two new molecules $ω'_{1}$ and $ω'_{2}$ are generated in this collision. The condition in which the inter-molecule ineffective collision occurs is as follows

P E_{ω_{1}} + K E_{ω_{1}} + P E_{ω_{2}} + K E_{ω_{2}} \geq P E_{ω_{1}'} + P E_{ω_{2}'}

(20)

The KE of the two new molecules are calculated as follows

K E_{ω_{1}'} = (P E_{ω_{1}} + K E_{ω_{1}} + P E_{ω_{2}} + K E_{ω_{2}} - P E_{ω_{1}'} - P E_{ω_{2}'}) \times k

(21)

K E_{{ω^{'}}_{2}} = (P E_{ω_{1}} + K E_{ω_{1}} + P E_{ω_{2}} + K E_{ω_{2}} - P E_{{ω^{'}}_{1}} - P E_{{ω^{'}}_{2}}) \times (1 - k)

(22)

where k is randomly generated from a uniform distribution $U [0, 1]$ .

Synthesis reaction

The process of the synthesis reaction is that two molecules $ω_{1}$ and $ω_{2}$ collide with each other and combine into a new molecule $ω'$ , and the condition to allow the synthesis reaction to happen is as follows

P E_{ω_{1}} + K E_{ω_{1}} + P E_{ω_{2}} + K E_{ω_{2}} \geq P E_{ω'}

(23)

The KE of the new molecules is as follows

K E_{ω'} = P E_{ω_{1}} + K E_{ω_{1}} + P E_{ω_{2}} + K E_{ω_{2}} - P E_{ω'}

(24)

Proposed algorithm

As it is stated for the SCRO, it utilizes the on-wall ineffective collision, decomposition, inter-molecular ineffective collision, and synthesis reactions to realize the exploration and exploitation to the solution space. In order to strength its search ability, this section develops a hybrid CRO algorithm, where the CRO and VNS are combined, called CRO-VNS. The solution representation, four elementary reactions, and neighborhood structures are presented based on the problem characteristics. Similar to the framework of the SCRO, the PE of a molecule is its objective value. The KE of molecules is calculated as follows: if the condition as formula (9) in on-wall ineffective collision reaction is met, the KE of a new molecule is calculated as formula (10); if the condition as formula (13) in decomposition reaction is met, the KE of two new molecules is calculated as formulas (14) and (15), or formula (16) is met, the formulas (17) and (18) are utilized to calculate the KE of two new molecules; if the condition as formula (20) in inter-molecule ineffective collision reaction is allowed, then the KE of two new molecules is calculated as formulas (21) and (22); if the condition as formula (23) in synthesis reaction is met, the KE of a new molecule is calculated as formula (24). The proposed CRO-VNS is described as follows.

Molecular structure representation

A suitable molecular structure or solution representation can increase the ability to find the optimal solution. In this study, the permutation representation of problem dimensions is used to represent a feasible and complete solution. For example, (3, 2, 1, 4, 5) is a molecular structure, and it represents that five jobs are processed on each machine as 3→2→1→4→5. Based on this representation, a set of molecules or solutions can be randomly generated.

On-wall ineffective collision reaction

In the SCRO, the on-wall ineffective collision is to change the selected molecule by rearranging the molecular structure and to generate a new molecule. In order to make a new molecule different from the previous one, the insert neighborhood and swap neighborhood structures are used. In the insert neighborhood, two positions are selected randomly, and the job in one position is inserted into the other position. While in the swap neighborhood, two positions are randomly generated, and the jobs in the two positions are swapped. If the condition in formula (10) is met, then let the new molecule replace the old one.

Decomposition reaction

The decomposition breaks one molecule into two or more molecules. In this study, the two swaps are utilized as follows: three positions are randomly selected, and the jobs on the three positions are randomly swapped. An example for the decomposition reaction is shown in Figure 1. The jobs 2, 5, and 3 are randomly selected. The molecule $ω'_{1}$ is generated by swapping the jobs 2 and 5, and the molecule $ω'_{2}$ is generated by swapping the jobs 5 and 3. The two new molecules are allowed to replace the original molecule when the condition in formula (13) is met.

Figure 1.

Illustration of the decomposition reaction.

Inter-molecule ineffective collision reaction

The inter-molecule ineffective collision makes two molecules collide, and two new molecules are developed. In this study, the order-based crossover³⁷ is utilized to generate two new molecules. Figure 2 shows an example. To produce a new molecule $ω'_{1}$ , a job block including the jobs 1, 5, and 4 is randomly selected from the molecule $ω_{1}$ , and it transmits to the new molecule $ω'_{1}$ directly; the other jobs are selected from the molecule $ω_{2}$ and inserted into $ω'_{1}$ as their relative order. The molecule $ω'_{1}$ is generated as the similar method, where the job block is selected from the molecule $ω_{2}$ , and the other jobs are selected from the molecule $ω_{1}$ . If the condition in formula (20) is met, the molecules $ω'_{1}$ and $ω'_{2}$ are allowed to replace the molecules $ω_{1}$ and $ω_{2}$ .

Figure 2.

Illustration of inter-molecule ineffective collision.

Synthesis reaction

The synthesis reaction is utilized to combine two molecules into a new molecule. In the proposed CRO-VNS, a distance preserving crossover³⁸ is applied to retain the valuable information from two molecules. An example for distance preserving crossover is shown in Figure 3. Two molecules $ω_{1}$ and $ω_{2}$ are randomly selected. The jobs 2, 5, and 3 are located into the same position in $ω_{1}$ and $ω_{2}$ , and they are stored into the new molecule $ω'$ directly; then, the other jobs are randomly generated. If the condition in formula (23) is met, let the molecule $ω'$ replace the molecules $ω_{1}$ and $ω_{2}$ .

Figure 3.

Illustration of synthesis reaction.

VNS

VNS is a meta-heuristic introduced by Mladenović et al.³⁹ that exploits the idea of neighborhood change, both in the decent to local minima and in the escape from the valleys containing them. It is obvious that the performance of local search method depends on the choice of neighborhood structures. For the blocking flow shop deteriorating scheduling problem in this study, the swap neighborhood and insert neighborhood are utilized. Since the computational resource is usually limited, the VNS is utilized to refine the best solution found at each iteration. The VNS in this study executes as Figure 4, where the numbers “1” and “2” represent the swap neighborhood and insert neighborhood, respectively.

Figure 4.

Variable neighborhood search algorithm.

Based on the discussion on the proposed algorithm, we can find that the inter-molecule ineffective collision reaction and synthesis reaction happen between two molecules, and decomposition and on-wall ineffective collision reaction take place in a molecule. The pseudo-code of the proposed CRO-VNS is shown in Figure 5, where the inter-molecule collision condition, inter-molecule ineffective collision condition, and decomposition condition are all algorithm parameters which are defined in section “Computation results and comparisons.” Note that the population P is a set of molecules.

Figure 5.

Pseudo-code of the proposed algorithm.

Computation results and comparisons

There are several meta-heuristics based on population which have been successfully applied into the combinatorial optimization problems. The genetic algorithm (GA) is one of the most famous population-based optimization algorithms, and it has been utilized to deal with production scheduling problem,⁴⁰ vehicle routing problems,⁴¹ and project scheduling problem.⁴² Its strong exploration and exploitation to the solution space motivates us to choose it as a compared algorithm in this study. In addition, the SCRO is also as a compared algorithm to verify the performance of the proposed CRO-VNS.

For the classical flow shop scheduling problem with makespan criterion, Taillard⁴³ presented a test bed consisting of a total of 120 problems of various sizes. These problems are divided into 12 subsets and each subset consists of 10 instances with the same size. In this study, we choose $20 \times 5$ , $20 \times 10$ , $20 \times 20$ , $50 \times 5$ , $50 \times 10$ , $50 \times 20$ , $100 \times 5$ , $100 \times 10$ , and $100 \times 20$ to test our method, where the first number is the job size and the second is the machine size. The parameter setting is as follows. The population size of CRO-VNS and SCRO is set to 20, the collision rate is set to 0.2, the decomposition condition is set to 10 mn, the synthesis condition is set to 10 mn, the initial kinetic energy for each molecule is set to 100 mn, and the energy buffer is set to 10 mn. The population of GA is set to 100, and the crossover probability and mutation probability are set to 0.8 and 0.2, respectively.

The proposed algorithm is coded in C++, and the experiments are executed on a Core-3.3-GHz PC with 2.0-GB memory. To make a fair comparison, the total number of fitness evaluation times is set to $ρ mn$ , where $ρ$ is a coefficient equal to $30, 50, 100$ ; m is the number of machines; and n is the number of jobs. Each instance runs 30 replications independently, and in each replication, we compute the percentage relative error (PRE) as shown in formula (25)

PRE (A) = \frac{(C_{i}^{A} - C_{i}^{b}) \times 100}{C_{i}^{b}}

(25)

where $C_{i}^{b}$ represents the best value found by the proposed and compared algorithms in the ith replication. Obviously, the smaller the $PRE (A)$ , the better result the algorithm A produces. Moreover, the average PRE (APRE) in all replications can be calculated as statistic for the solution quality. In addition, the t-test is used to analyze the experimental results more clearly.⁴⁴ In the following experiments, the symbols “s+,”“s−,” and “∼” denote the statistical results of comparing two algorithms by the one-tailed t-test with 58 degree of freedom at a 0.05 level of significance. The t-test results are shown as “s+,”“s−,” and “∼” when the proposed algorithm is significantly better than, significantly worse than, or statistically equivalent to the compared algorithms.

The experimental results with the different number of evaluating fitness times are shown in Tables 1 –3, respectively.

Table 1.

Computational experimental results of the three algorithms ( $ρ = 30$ ).

$n \times m$	CRO-VNS	SCRO	t-test	GA	t-test
$20 \times 5$	0.0352	0.0825	∼	0.1692	s+
$20 \times 10$	0.0878	0.1179	s+	0.1525	s+
$20 \times 20$	0.0396	0.1220	s+	0.1299	s+
$50 \times 5$	0.0551	0.2341	s+	0.2513	s+
$50 \times 10$	0.0876	0.2625	s+	0.2919	s+
$50 \times 20$	0.0399	0.1182	s+	0.1908	s+
$100 \times 5$	0.0663	0.1323	s+	0.1712	s+
$100 \times 10$	0.0752	0.1301	s+	0.1623	s+
$100 \times 20$	0.1229	0.2318	s+	0.2932	s+
Mean	0.0678	0.1590		0.2013

CRO-VNS: chemical reaction optimization–variable neighborhood search; SCRO: standard CRO; GA: genetic algorithm.

Table 2.

Computational experimental results of the three algorithms ( $ρ = 50$ ).

$n \times m$	CRO-VNS	SCRO	t-test	GA	t-test
$20 \times 5$	0.0226	0.0962	s+	0.1876	s+
$20 \times 10$	0.0371	0.0715	∼	0.1254	s+
$20 \times 20$	0.0321	0.1282	s+	0.1537	s+
$50 \times 5$	0.0972	0.1941	s+	0.2272	s+
$50 \times 10$ .	0.0626	0.2232	s+	0.2916	s+
$50 \times 20$	0.0315	0.1352	s+	0.2612	s+
$100 \times 5$	0.0912	0.1569	s+	0.1938	s+
$100 \times 10$	0.0692	0.1352	s+	0.163	s+
$100 \times 20$	0.1272	0.2295	s+	0.2721	s+
Mean	0.0634	0.1522		0.2084

CRO-VNS: chemical reaction optimization–variable neighborhood search; SCRO: standard CRO; GA: genetic algorithm.

Table 3.

Computational experimental results of the three algorithms ( $ρ = 100$ ).

$n \times m$	CRO-VNS	SCRO	t-test	GA	t-test
$20 \times 5$	0.0212	0.1035	s+	0.1255	s+
$20 \times 10$	0.0528	0.1372	s+	0.1385	s+
$20 \times 20$	0.0427	0.1298	s+	0.1291	s+
$50 \times 5$	0.1123	0.2012	s+	0.1772	s+
$50 \times 10$	0.0974	0.2523	s+	0.2835	s+
$50 \times 20$	0.0823	0.1331	∼	0.1582	s+
$100 \times 5$	0.1071	0.1941	s+	0.2132	s+
$100 \times 10$	0.0710	0.1682	s+	0.1562	s+
$100 \times 20$	0.1021	0.1953	s+	0.2612	s+
Mean	0.0765	0.1638		0.1825

CRO-VNS: chemical reaction optimization–variable neighborhood search; SCRO: standard CRO; GA: genetic algorithm.

Table 1 gives the experimental results with the number of evaluating fitness times 30 mn. It can be seen that the proposed CRO-VNS is the best performer among the three algorithms, and it can obtain the smallest APRE value for all the test instances. The CRO-VNS also has superiority in all the test instances. By observing the results via t-test, we can find that the CRO-VNS is significantly better than SCRO in eight test instances, and significantly better than GA in all the test instances. The experimental results with the total number of evaluating fitness times 50 mn are shown in Table 2. They are also in favor of the CRO-VNS. It can be seen that the CRO-VNS produces the best results than those of the other two algorithms in all the test instances. The results of t-test show that the CRO-VNS are significantly better than SCRO in eight test instances, and significantly better that GA in all the test instances. Table 3 shows the experimental results with the number of evaluating fitness times is 100 mn. It can be found that the CRO-VNS has the best APRE value in all the test instances. The experimental results on t-test indicate that the CRO-VNS performs significantly better than SCRO in eight test instances, and significantly better than GA in all the test instances.

According to the experimental results and analysis, we can find that the CRO-VNS is a promising optimizer in solving the blocking flow shop deteriorating scheduling problem compared with the SCRO and GA. That is to say, the performance of the CRO can be improved by utilizing and combining with the VNS.

Conclusion

This study presents the blocking flow shop deteriorating scheduling problem for the first time. In order to cope with this problem, a hybrid CRO is proposed, where the CRO and VNS are combined to strengthen the search ability. The computational simulation experiments are carried out. The results show that the proposed algorithm is more competitive than the compared algorithms, and it can provide a good decision for the decision-maker when the block and deterioration take place in a flow shop environment.

For the future work, it is interesting to research on the multi-objective design in the case of the blocking and deteriorating flow shop scheduling. It is also necessary to develop more efficient optimization algorithms to deal with this kind of complexity optimization problems like the investigated problem in this study.

Footnotes

Academic Editor: ZhiWu Li

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 financially supported by the Shandong Provincial Natural Science Foundation, China, under grant no. ZR2016FP02; the Qingdao Postdoctoral Research Project under grant nos 2016027 and 2016012; and the National Natural Science Foundation of China under grant nos 61673228, 51405075, and 21506014.

References

Pan

Suganthan

Liang

. A local-best harmony search algorithm with dynamic sub-harmony memories for lot-streaming flow shop scheduling problem. Expert Syst Appl 2011; 38: 3252–3259.

Marichelvam

Prabaharan

Yang

XS.

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

Che

Kats

Levner

An efficient bicriteria algorithm for stable robotic flow shop scheduling. Eur J Oper Res. Epub ahead of print 27 January 2017. DOI: http://dx.doi.org/10.1016/j.ejor.2017.01.033.

Seif

Minimizing tardiness and maintenance costs in flow shop scheduling by a lower-bound-based GA. Comput Ind Eng 2016; 97: 26–40.

Ribas

Companys

Tort-Martorell

Efficient heuristics for the parallel blocking flow shop scheduling problem. Expert Syst Appl 2017; 74: 41–54.

Yin

. An iterated local search for the multi-objective permutation flowshop scheduling problem with sequence-dependent setup times. Appl Soft Comput 2017; 52: 39–47.

Lenstra

Kan

AHGR

Brucker

Complexity of machine scheduling problems. Ann Discr Math 1977; 1: 343–362.

Leisten

Rajendran

Variability of completion time differences in permutation flow shop scheduling. Comput Oper Res 2015; 54: 155–167.

Deng

A hybrid discrete differential evolution algorithm for the no-idle permutation flow shop scheduling problem with makespan criterion. Comput Oper Res 2012; 39: 2152–2160.

10.

Yin

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

11.

Rahman

Sarker

Essam

A genetic algorithm for permutation flow shop scheduling under make to stock production system. Comput Ind Eng 2015; 90: 12–24.

12.

Gupta

JND

Gupta

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

13.

Wang

MZ.

Solution algorithms for the total weighted completion time minimization flow shop scheduling with decreasing linear deterioration. Int J Adv Manuf Tech 2013; 67: 243–253.

14.

Wang

MZ.

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

15.

Cheng

TCE

Yang

DL.

Common due-window assignment and scheduling of linear time-dependent deteriorating jobs and a deteriorating maintenance activity. Int J Prod Econ 2012; 135: 154–161.

16.

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–6.

17.

Mosheiov

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

18.

Tasgetiren

Kizilay

Pan

. Iterated greedy algorithms for the blocking flowshop scheduling problem with makespan criterion. Comput Oper Res 2017; 77: 111–126.

19.

Khorasanian

Moslehi

Two-machine flow shop scheduling problem with blocking, multi-task flexibility of the first machine, and preemption. Comput Oper Res 2017; 79: 94–108.

20.

Ronconi

DP.

A note on constructive heuristics for the flowshop problem with blocking. Int J Prod Econ 2004; 87: 39–48.

21.

Grabowski

Pempera

The permutation flow shop problem with blocking. A tabu search approach. Omega 2007; 35: 302–311.

22.

Wang

Pan

Suganthan

. A novel hybrid discrete differential evolution algorithm for blocking flow shop scheduling problems. Comput Oper Res 2010; 37: 509–520.

23.

Tasgetiren

Pan

Kizilay

. A populated local search with differential evolution for blocking flowshop scheduling problem. In: Proceedings of the IEEE conference on evolutionary computation, Sendai, Japan, 25–28 May 2015, pp.2789–2796. New York: IEEE.

24.

Ribas

Companys

Tort-Martorell

An efficient Discrete Artificial Bee Colony algorithm for the blocking flow shop problem with total flowtime minimization. Expert Syst Appl 2015; 42: 6155–6167.

25.

Han

Gong

Sun

A discrete artificial bee colony algorithm incorporating differential evolution for the flow-shop scheduling problem with blocking. Eng Optimiz 2015; 47: 927–946.

26.

Wang

Pan

Tasgetiren

MF.

A hybrid harmony search algorithm for the blocking permutation flow shop scheduling problem. Comput Ind Eng 2011; 61: 76–83.

27.

Rahnamayan

Tizhoosh

Salama

Opposition-based differential evolution algorithms. In: Proceedings of the IEEE conference on evolutionary computation, Vancouver, BC, Canada, 16–21 July 2006, pp.2010–2017. New York: IEEE.

28.

Lee

Shiau

Chen

. A two-machine flowshop scheduling problem with deteriorating jobs and blocking. Int J Prod Econ 2010; 124: 188–197.

29.

Lam

VOK

. Chemical-reaction-inspired metaheuristic for optimization. IEEE T Evolut Comput 2010; 14: 381–399.

30.

Lam

AYS

VOK

JJQ.

Real-coded chemical reaction optimization. IEEE T Evolut Comput 2012; 16: 339–353.

31.

Dam

Fournier-Viger

Chemical reaction optimization with unified tabu search for the vehicle routing problem. Soft Comput. Epub ahead of print 27 May 2016. DOI: 10.1007/s00500–016–2200–4.

32.

Pan

QK.

Chemical-reaction optimization for flexible job-shop scheduling problems with maintenance activity. Appl Soft Comput 2012; 12: 2896–2912.

33.

Truong

. Solving 0–1 knapsack problem by artificial chemical reaction optimization algorithm with a greedy strategy. J Intell Fuzzy Syst 2015; 28: 2179–2186.

34.

Lam

AYS

VOK

. Chemical reaction optimization for the grid scheduling problem. In: Proceedings of the IEEE international conference on communications, Cape Town, South Africa, 23–27 May 2010, pp.1–5. New York: IEEE.

35.

Neri

Cotta

Memetic algorithms and memetic computing optimization: a literature review. Swarm Evol Comput 2012; 2: 1–14.

36.

Hall

Sriskandarajah

A survey of machine scheduling problems with blocking and no-wait in process. Oper Res 1996; 44: 510–525.

37.

Davis

Job shop scheduling with genetic algorithms. In: Proceedings of the international conference on genetic algorithms, Pittsburgh, PA, 1985, pp.136–140. Hillsdale, NJ: Lawrence Erlbaum Associates.

38.

Merz

Freisleben

. A genetic local search approach to the quadratic assignment problem. In: Proceedings of the 7th international conference on genetic algorithms, East Lansing, MI, 19–23 July 1997, pp.465–472. San Francisco, CA: Morgan Kaufmann Publishers.

39.

Mladenović

Hansen

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

40.

Chang

Chen

Liu

. Solving the flexible job shop scheduling problem with makespan optimization by using a hybrid Taguchi-genetic algorithm. IEEE Access 2015; 3: 1740–1754.

41.

Karakatič

Podgorelec

A survey of genetic algorithms for solving multi depot vehicle routing problem. Appl Soft Comput 2015; 27: 519–532.

42.

Summerville

Uzsoy

Gaytán

A random keys genetic algorithm for a bicriterion project selection and scheduling problem. Int J Plan Sched 2015; 2: 110–133.

43.

Taillard

Some efficient heuristic methods for the flow shop sequencing problem. Eur J Oper Res 1990; 47: 65–74.

44.

Liu

Wang

WH.

A permutation-based dual genetic algorithm for dynamic optimization problems. Soft Comput 2008; 13: 725–738.

A blocking flow shop deteriorating scheduling problem via a hybrid chemical reaction optimization

Abstract

Keywords

Introduction

Problem definition

Basic idea of SCRO

Elementary element of CRO

Elementary reactions of CRO

On-wall ineffective collision reaction

Decomposition reaction

Inter-molecule ineffective collision reaction

Synthesis reaction

Proposed algorithm

Molecular structure representation

On-wall ineffective collision reaction

Decomposition reaction

Inter-molecule ineffective collision reaction

Synthesis reaction

VNS

Computation results and comparisons

Conclusion

Footnotes

Declaration of conflicting interests

Funding

References