An effective chemical reaction optimization for cyclic multi-type parts robotic cell scheduling problem with blocking

Abstract

The scheduling problem of cyclic multi-type parts robotic cell with blocking is studied in this paper. For simultaneously optimizing robotic move sequence and part input sequence, an effective chemical reaction optimization (ECRO) is proposed. In ECRO, a new encoding method, robotic activity encoding, is shown for transferring double sequence into single sequence. To construct feasible solution, a novel rule, order insertion (OI) rule, is presented. To obtain initial population more effectively, insertion robotic activity method (IRAM) is firstly addressed. What’s more, for enhancing the efficiency of ECRO, elementary reaction operators are designed according to properties of feasible solutions. From the simulation results, compare to stochastic generated solution method (SGSM), IRAM is outstanding. The performance of ECRO is better than branch and bound (BB) method and beam search (BS) algorithm.

Keywords

Robotic cell chemical reaction optimization OI rule IRAM

1 Introduction

Robotic cell is a kind of advanced production system. It is widely used in printed circuit board (PCB) electroplating lines, semiconductor manufacturing system, iron and steel industries, and aircraft manufacturing factories. The difference between robotic cell and classical flow-shop is that parts are moved from one tank to next tank by robot(s).

Recently, the robotic cell is applied to cyclically produce multi-type parts especially in the semiconductor manufacturing [17 , 35] and electroplating line fields [3 , 21]. This paper addresses the cyclic multi-type parts robotic cell scheduling problem with blocking. Blocking means when one part is finished on one tank, the part isn’t moved next tank because the robot is busy or the next tank is occupied. Finding a solution of the problem is equivalent to finding two types of correlative sequences: robotic move sequence and part input sequence.

To highlight the difference between this study and those published literatures, a literature review is shown. Considering the problem with two tanks, Sethi et al. [32] formulated the problem as a polynomial solvable travelling salesman problem if the robotic move sequence was given. For the same problem, a MinCycle algorithm [13] was provided that could simultaneously optimized robotic move sequence and part input sequence. Aneja and Kamoun [5] formulated the problem as a special traveling salesman problem and improved the MinCycle algorithm. Recently, for the problem with sequence dependent setup times, Majumder and Laha [25] developed a cuckoo search method that was indicated better than the simulated algorithm designed by Zarandi et al. [36].

For the problem with three tanks, Hall et al. [14] demonstrated that it was NP-hard and proposed a ThreeCell method based on arbitrary robotic move sequence and arbitrary part input sequence. Then the problem was transferred into generalized travelling salesman problem (GTSP) and an improved ThreeCell algorithm [34] was proposed. Zahrouni and Kamoun [35] also presented a more effective MinMPSCycle algorithm, and the performance of MinMPSCycle demonstrated that the CRM (concatenated robot move) sequences or the combination of one-unit cycles were not the best.

For more complicated case, Paul et al. [29] reported an adaptive time window (ATW) heuristic after part input sequence was given, while Carlier et al. [7] proposed an approximate decomposition method, in which part input sequence was firstly determined and robotic move sequence was secondly optimized. Besides, some researchers investigated the problem with fixed processing time [1 , 22], where parts must be unloaded from a tank and transported to next tank as soon as it is completely processed; and others studied the case with interval processing time [2–4 , 24], where parts can stay on the tank definitely after it completes processing. Whereas, only a few works [11, 15] focus on the multi-type parts robotic cell scheduling problem with more than three tanks and blocking.

In published literatures, three characteristics are shown: the problems with two or three tanks were mainly considered; heuristic methods were used for solving the problem; the mainly production strategy is CRM sequence or the combination of one-unit cycles. In this paper, for solving the problem, minimum part set (MPS) cycle is considered. And an effective chemical reaction optimization (ECRO) is developed to simultaneously optimize robotic move sequence and part input sequence.

Chemical reaction optimization (CRO) [19] is a new metaheuristic approach got by imitating chemical reaction. It possesses the virtues of both GA (genetic algorithm) and SA (simulated annealing) [20] and was successfully used to solve combinatorial optimization problem [12 , 33]. However, CRO isn’t used to solve the scheduling problem of cyclic multi-type parts robotic cell with blocking. In this study, the scheduling problem of cyclic multi-type parts robotic cell with blocking is considered and an ECRO is provided to solve the problem. In ECRO, robotic activity is reported for encoding. OI rule is proposed to construct feasible solution. To initialize population, IRAM is reported. For enhancing effectively of ECRO, properties of feasible solution are found and applied to design elementary operators. A number of experiments are conducted to test the performance of ECRO. The results demonstrate ECRO is outstanding.

This paper is structured as follows. The problem description is described in Section 2. The problem analysis is addressed in Section 3. An ECRO is introduced in Section 4. Computational results are shown in Section 5. Afterwards, conclusions are presented.

2 Problem description

In this study, robotic cell consists of m + 2 tanks and a robot. The tanks are represented by P₀, P₁, …, P_m, P_m+1, where P₀ and P_m+1 are inputting tank and outputting tank, respectively. Multi-type parts are processed by the robotic cell in the same time. There are totally n parts, denoted as J₁, …, J_n, which compose MPS. Each part enters robotic cell from P₀, and then is processed successively through P₁, …, P_m, and finally leaves the robotic cell from P_m+1. All parts have the same processing sequence, but the processing times may be different for a given tank if the type of parts is not same. Therefore, the problem considered in this paper is a flow shop. The robot transports part from one tank to next tank, and at any time the robot can handle one part at most, the tank can contain one part at most. The robot move of J_j(1 ≤ j ≤ n) from P_i to P_i+1 is called move [i, j](0 ≤ i ≤ m), which consists of three operations: (1) unload J_j from P_i; (2) move J_j from P_i to P_i+1; (3) load J_j onto P_i+1.

To facilitate describing and to avoid any confusion with common notations used in scheduling, a definition of notations is shown.

Decision variables:

t_i,j: The start time of move [i, j] (0 ≤ i ≤ m, 1 ≤ j ≤ n).

$y_{l, h}^{i, j}$ : Binary variables. Where $y_{l, h}^{i, j} = 1$ if t_i,j > t_l,h; and $y_{l, h}^{i, j} = 0$ otherwise (0 ≤ i, l ≤ m; 1 ≤ j, h ≤ n).

Parameters:

a_i,j: The lower bound of the processing time of J_j on P_i(1 ≤ i ≤ m, 1 ≤ j ≤ n).

d_i,j: It is the time that the robot performs move [i, j] (0 ≤ i ≤ m, 1 ≤ j ≤ n).

c_i,l: Void move time that the robot travels from P_i to P_l without move part (0 ≤ i, l ≤ m + 1).

T: Cycle time. It is the time elapsed between inputting the first part in an MPS and inputting the first part in next MPS.

τ_i: The ith robotic activity (0 ≤ i ≤ n (m + 1) -1).

job (i): The part that the robotic activity τ_i moves (0 ≤ i ≤ n (m + 1) -1).

Q (i): The index of tank which τ_i transports job (i) from (0 ≤ i ≤ n (m + 1) -1).

M: A large enough positive integer.

σ: The sequence of robotic activities.

σ (i): The (i + 1) th robotic activity in the sequence σ (0 ≤ i ≤ n (m + 1) -1).

δ: The sequence of parts.

δ (j): The jth part in the sequence δ(1 ≤ j ≤ n).

Rdone: Partial feasible schedule of robotic activities.

Rtodo: A set that contains the unscheduled robotic activities.

In this paper, following assumptions hold: $d_{i, j} \geq c_{i, i + 1} 1 \leq j \leq n, 0 \leq i \leq m$ (1) $c_{i, k} \leq c_{i, l} + c_{l, k} 0 \leq i, k, l \leq m + 1$ (2)

Inequality (1) shows that a move needs more time than a void move between the same pair of tanks. Inequality (2) is known as the triangle inequality.

The problem can be formulated as

Minimize T

Subject to

$\begin{matrix} (y_{i, j}^{i - 1, j} T + t_{i, j}) - (t_{i - 1, j} + d_{i - 1, j}) \geq \\ a_{i, j} 1 \leq i \leq m 1 \leq j \leq n \end{matrix}$ (3)

$\begin{matrix} y_{(i - 1), j}^{i, j} + y_{(i - 1), h}^{i, h} + y_{i, j}^{(i - 1), h} + y_{i, h}^{(i - 1), j} \geq 3 j \neq h, \\ 1 \leq i \leq m, 1 \leq j, h \leq n \end{matrix}$ (4) $\sum_{j = 1}^{n} y_{i, j}^{(i - 1), j} \leq 1 1 \leq i \leq m$ (5)

$\begin{matrix} t_{i, j} - t_{l, h} \geq d_{l, h} + c_{(l + 1), i} - M (1 - y_{l, h}^{i, j}) 0 \leq i, \\ l \leq m, 1 \leq j, h \leq n \end{matrix}$ (6)

$\begin{matrix} t_{l, h} - t_{i, j} \geq d_{i, j} + c_{(i + 1), l} - {My}_{l, h}^{i, j} 0 \leq i, l \leq m, \\ 1 \leq j, h \leq n \end{matrix}$ (7)

$\begin{matrix} t_{i, j} \geq d_{1, 0} + c_{1, i} i \neq 0 or j \neq 1 and 0 \leq i \leq m, \\ 1 \leq j \leq n \end{matrix}$ (8) $T \geq t_{i, j} + d_{i, j} + c_{(i + 1), 0} 0 \leq i \leq m, 1 \leq j \leq n$ (9) $t_{0, 1} = 0$ (10) $y_{l, h}^{0, 1} = 0 0 \leq l \leq m, 1 \leq h \leq n$ (11) $t_{i, j} \geq 0 0 \leq i \leq m, 1 \leq j \leq n$ (12) $T \geq 0$ (13) $y_{l, h}^{i, j} = {\begin{matrix} 1 t_{i, j} \geq t_{l, h} \\ 0 otherwise \end{matrix} 0 \leq i, l \leq m, 1 \leq j, h \leq n$ (14)

3 Problem analysis

In this section, a few properties of feasible solutions are presented. According to these properties, elementary reaction operators in ECRO can be constructed.

Solving the problem means determining robotic move sequence and part input sequence. For transferring two-dimension sequence into one-dimension sequence, robotic activity is given by definition 1.

Definition 1. Robotic activity, noted as τ_i+(m+1)(j-1)(1 ≤ j ≤ n, 0 ≤ i ≤ m), is defined as: $τ_{i + (m + 1) (j - 1)} = i + (m + 1) (j - 1)$

Example: The robotic cell is composed of six tanks (P₀, P₁, P₂, P₃, P₄, P₅). MPS is composed of three

parts, J₁, J₂, J₃. The relationship between τ_i+(m+1)(j-1) and move [i, j] is listed in Table 1.

Table 1
Relationship between τ_i+(m+1)(j-1) and move [i, j]

part P ₀ P ₁ P ₂ P ₃ P ₄

J ₁ [0, 1] →0 [1, 1] →1 [2, 1] →2 [3, 1] →3 [4, 1] →4

J ₂ [0, 2] →5 [1, 2] →6 [2, 2] →7 [3, 2] →8 [4, 2] →9

J ₃ [0, 3] →10 [1, 3] →11 [2, 3] →12 [3, 3] →13 [4, 4] →14

part	P ₀	P ₁	P ₂	P ₃	P ₄
J ₁	[0, 1] →0	[1, 1] →1	[2, 1] →2	[3, 1] →3	[4, 1] →4
J ₂	[0, 2] →5	[1, 2] →6	[2, 2] →7	[3, 2] →8	[4, 2] →9
J ₃	[0, 3] →10	[1, 3] →11	[2, 3] →12	[3, 3] →13	[4, 4] →14

Because robotic activity τ_i+(m+1)(j-1) corresponds to the move [i, j], and the number of robotic activities is n (m + 1). Finding robotic activity schedule means robotic move sequence and part input sequence are determined. So S = (τ₀, τ_σ(1), …, τ_σ(n(m+1)-1)) represents solution of the problem. How to check whether a solution is feasible or not, definition 2 is described.

Definition 2. A robotic activity schedule S is feasible if

Before one robotic activity τ_i is executed, job (i) must be loaded and finished its processing on P_Q(i)(0 ≤ i ≤ n (m + 1) -1) and

Forbid to load a part to an occupied tank and

Forbid to unload a part from an empty tank.

According to constraint (3), the processes to cross the cycle boundary is allowed. For avoiding violating problem constraints, some properties of feasible solution are developed.

Lemma 1. S = (τ₀, τ_σ(1), …, τ_σ(i), τ_σ(i+1), …, τ_σ(n(m+1)-1)) is a feasible robotic activity schedule. If job (σ (i)) ≠ job (σ (i + 1)) and |Q (σ (i)) - Q (σ (i + 1)) |>1 hold, S′ = (τ₀, τ_σ(1), …, τ_σ(i+1), τ_σ(i), …, τ_σ(n(m+1)-1)) is a feasible robotic activity schedule.

Proof. Because S is a feasible robotic activity schedule, S satisfies condition of lemma 2 [4]. That is to say, robotic activity in the right-most robotic activity on the left of τ_σ(i) is called τ_σ(r) and Q (σ (i)) = Q (σ (r)) +1 holds; robotic activity in the left-most robotic activity on the right of τ_σ(i) is called τ_σ(w) and Q (σ (i)) = Q (σ (w)) +1 holds. Because of |Q (σ (i)) - Q (σ (i + 1)) |>1, after τ_σ(i) and τ_σ(i+1) exchanges, there is only one Q (σ (i)) between Q (σ (r)) and Q (σ (w)). So lemma 1 holds.¨

Thereby, a corollary can result from lemma 1.□

Corollary. S = (τ₀, τ_σ(1), …, τ_σ(i-1), τ_σ(i), …, τ_σ(n(m+1)-1)) is a feasible robotic activity schedule. If job (σ (i)) ≠ job (σ (i - 1)) and |Q (σ (i)) - Q (σ (i - 1)) |>1 hold, S′ = (τ₀, τ_σ(1), …, τ_σ(i), τ_σ(i-1), …, τ_σ(n(m+1)-1)) is a feasible robotic activity sequence.

In lemma 1 and corollary, a new feasible robotic activity schedule is obtained by neighbourhood exchange. So lemma 1 and corollary are called neighbourhood exchange (NE).

Set S₁ = (τ₀, τ₁₂, τ₁₃, τ₁, τ₂, τ₅, τ₁₄, τ₆, τ₃, τ₄, τ₇, τ₁₀, τ₈, τ₉, τ₁₁) be a feasible robotic activity schedule. Figure 1 (a) and (b) show two new feasible robotic activity schedule are obtained, respectively, according to lemma 1 and corollary.

Fig.1

Neighbourhood exchange.

In lemma 1 and corollary, part input sequence doesn’t vary, and robotic move sequence changes. However, lemma 2 considers robotic move sequence fixes and part input sequence changes. So lemma 2 is named part exchange (PEx).

Lemma 2. S = (τ₀, τ_σ(1), …, τ_σ(n(m+1)-1)) is a feasible robotic activity schedule. (τ_σ(e₀), …, τ_{σ(e_m)}) and (τ_σ(g₀), …, τ_{σ(g_m)}) are all robotic activities of two d i fference parts, respectively, and Q (σ (e_i)) = Q (σ (g_i)) (0 ≤ i ≤ m). After τ_{σ(e_i)} and τ_{σ(g_i)} are exchange d in S, a new solution S′ is a feasible robotic activity schedule.

Proof. S satisfies condition of lemma 2 [4]. Because of Q (σ (e_i)) = Q (σ (g_i)), after τ_{σ(e_i)} and τ_{σ(g_i)} are exchanged in S, the part input sequence changes, and the robotic move sequence doesn’t change. Since S is a feasible robotic activity schedule, and S′ satisfies condition of lemma 2 [4], S′ is also a feasible robotic activity schedule.□

Set S = (τ₀, τ₁₂, τ₁₃, τ₁, τ₂, τ₅, τ₁₄, τ₆, τ₃, τ₄, τ₇, τ₁₀, τ₈, τ₉, τ₁₁) be a feasible robotic activity schedule. A new feasible robotic activity schedule is given based on PEx. The detailed procedure is shown in Fig. 2.

Fig.2

Part exchange.

4 ECRO

In CRO, each molecule (ω) which has several attributes represents a solution of the problem. One molecule turns another if any change among these attributes occurs. Each molecule possesses two kinds of energies: PE (potential energy) and KE (kinetic energy). The PE corresponds to the objective function of a molecule while the KE represents its ability of escaping from a local optimum.

ECRO is proposed based on CRO. In ECRO, a novel encoding, robotic activity encoding, is provided. A new rule, OI rule, is established for constructing feasible solution. Elementary reactions are realized based on properties of feasible solution.

To facilitate describing, a definition of parameter in ECRO is shown.

Popsize: Initial population size.

InitialKE: Initial kinetic energy.

buffer: Energy buffer.

KelossRate: Kinetic energy loss rate, 0 ≤ KELossRate ≤ 1

Molecoll: The threshold between single or more molecule(s) reaction.

α: The critical point between on-wall ineffective collision and decomposition.

β: The threshold between inter-molecular ineffective collision and synthesis.

4.1 Robotic activity encoding and decoding

In previous literatures, two encoding methods, robotic move sequence and part input sequence, were presented. These encoding methods are simple and evolutionary operators are easily realized, but it is hard to simultaneously find robotic move sequence and part input sequence. For amending the defect, a novel encoding method, robotic activity encoding, is proposed. The new encoding method can transfer a scheduling represented by a two-dimensional array into a sequence with one-dimensional array.

According to robotic activity encoding, robotic move sequence and input part sequence are obtained by the following steps.

Step 1. For each robotic activity τ_σ(i)(0 ≤ i ≤ n (m + 1) - 1) in robotic activity schedule, Let Q (σ (i)) ≡ τ_σ(i)mod (m + 1) be robotic move. So RM = (Q (0) , Q (σ (1)) , …, Q (σ (n (m + 1) -1))) is robotic move sequence.

Step 2. Along the length of R, if Q (σ (i)) =0, record μ_i′ = τ_σ(i)(1 ≤ i′ ≤ n). Let JS = (μ₁, μ₂, …, μ_n).

Step 3. For each μ_i′(1 ≤ i′ ≤ n) in JS, let J_δ(i′) = μ_i′/(m + 1) + 1. Thus Job = (J_δ(1), J_δ(2), J_δ(3), …, J_δ(n)) is the part input sequence.

Set S = (τ₀, τ₇, τ₈, τ₁, τ₂, τ₁₀, τ₉, τ₁₁, τ₃, τ₄, τ₁₂τ₅, τ₁₃, τ₁₄, τ₆) be a feasible robotic activity schedule. According to Step 1-Step 3, robotic move sequence is R = (0, 2, 3, 1, 2, 0, 4, 1, 3, 4, 2, 0, 3, 4, 1). Part input sequence is Job = (J_δ(1), J_δ(2), J_δ(3)) = (J₁, J₂, J₃). Figure 3 shows decoding diagram.

Fig.3

Decoding diagram.

A feasible schedule is listed in Table 2. The first column is robotic activity. The second column is robotic move, that is to say, the second column gives robotic move sequence. Columns “P₁”, “P₂”, “P₃”, “P₄” show the part that are currently loaded on the tanks. “– ” means the tank is empty. “*J_j(1 ≤ j ≤ 3)” means J_j is input robotic cells previous cycle. Column “P₁” shows part input sequence.

Table 2

Feasible schedule

robotic activity	robotic move	P ₁	P ₂	P ₃	P ₄
τ ₀	P₀ → P₁	J ₁	*J₃	–	–
τ ₇	P₂ → P₃	J ₁	–	*J₃	–
τ ₈	P₃ → P₄	J ₁	–	–	*J₃
τ ₁	P₁ → P₂	–	J ₁	–	*J₃
τ ₂	P₂ → P₃	–	–	J ₁	*J₃
τ ₁₀	P₀ → P₁	J ₂	–	J ₁	*J₃
τ ₉	P₄ → P₅	J ₂	–	J ₁	–
τ ₁₁	P₁ → P₂	–	J ₂	J ₁	–
τ ₃	P₃ → P₄	–	J ₂	–	J ₁
τ ₄	P₄ → P₅	–	J ₂	–	–
τ ₁₂	P₂ → P₃	–	–	J ₂	–
τ ₅	P₀ → P₁	J ₃	–	J ₂	–
τ ₁₃	P₃ → P₄	J ₃	–	–	J ₂
τ ₁₄	P₄ → P₅	J ₃	–	–	–
τ ₆	P₁ → P₂	–	J ₃	–	–

4.2 Initial population

Because ECRO is a multi-solution evolutionary algorithm, in this subsection, how to generate initial population of ECRO is presented. Firstly, for constructing feasible solution, a new rule, OI rule is proposed. Secondly, according to OI rule, IRAM that produces initial population is provided.

4.2.1 OI rule

OI rule contains six conditions. The first two conditions were proposed by Brucker, Burke and Groenemeyer [6]. Because of difference between job-shop and flow-shop, infeasible robotic activity schedule is produced if the first two conditions is applied in this paper. For example, if Rdone = {τ₀, τ₉, τ₁₄}. According to the first two conditions, Rdone = {τ₀, τ₉, τ₁₄} is partial feasible. However, Rdone = {τ₀, τ₉, τ₁₄} violates condition (3) of definition 2. So Rdone = {τ₀, τ₉, τ₁₄} isn’t partial feasible. To construct feasible robotic activity schedule, the remainder conditions is described. If one of the OI rule conditions occurs, Rdone is infeasible.

A robotic activity τ_i(τ_i ∈ Rtodo) is inserted in the end of Rdone, and a robotic activity τ_u ∈ Rdone. If Q (i) = Q (u) = m, but robotic activity τ_i - 1 ∈ Rtodo.

A robotic activity τ_i(τ_i ∈ Rtodo) is inserted in the end of Rdone, and a robotic activity τ_u ∈ Rdone, If Q (i) ≠ Q (u), Q (i) = m and job (i) = job (u), but robotic activity τ_i - 1 ∈ Rtodo.

A robotic activity τ_i(τ_i ∈ Rtodo) is inserted in the end of Rdone, and a robotic activity τ_u ∈ Rdone, If Q (i) ≠ Q (u), Q (u) = m and job (i) = job (u), but τ_u - τ_i < m.

The parts, J_δ(1), J_δ(2), …, J_δ(v)(1 ≤ v < n), are input in previous cycle and finish processing in current cycle. If the inputting sequence of J_δ(1), J_δ(2), …, J_δ(v) isn’t consistent of their outputting sequence in current cycle.

4.2.2 IRAM

To obtain effectively initial population, IRAM based on OI rule is presented. And low bound [6] is used in IRAM

Procedure 1. IRAM

Input: Rdone = {τ₀}, Rtodo = {τ_i|1 ≤ i ≤ n (m + 1) -1} A = n (m + 1) - 2.

Output: a feasible solution.

Step 1. The robotic activity which is inserted at the second place in Rdone is stochastically selected in Rtodo.

Step 2. According to OI rule, if Rdone is partial feasible, run Steps 3 to 7. Otherwise, go to Step 1.

Step 3. Add the selected robotic activity to Rdone and delete it from Rtodo. Set A = A - 1.

Step 4. For i = 1 to A.

Step 5. Based on OI rule, all robotic activities which is inserted at the ith place in Rdone is selected in Rtodo.

Step 6. The robotic activity which is inserted at the ith place in Rdone is selected if low bound of Rdone is the least.

Step 7. Add the robotic activity to Rdone and delete it from Rtodo. Set A = A - 1, i = 1.

After the Procedure 1 is implemented Popsize times, the initial population is produced.

4.3 Elementary reactions of ECRO

In ECRO, there are four elementary reactions. They can be categorized into intensification and diversification. The on-wall ineffective collision and inter-molecular ineffective collision implement intensification, while the decomposition and synthesis perform exploration.

4.3.1 On-wall ineffective collision

Since the obtained molecule can keep outstanding genes of the selected molecule after neighbourhood exchange (NE) is performed, on-wall ineffective collision reaction operator that can implement effectively intensification is designed based on NE in ECRO. For improving effectively intensification, low bound [6] is used in NE neighbourhood structure.

Procedure 2. NE

Input: a molecule ω.

Output: a new molecule ω′.

Step 1. A place(i) is stochastically selected in ω.

Step 2. If the conditions of NE is met, implement Steps 3 to 6.

Step 3. Low bound of ω₁ = (τ₀, τ_σ(1), …, τ_σ(i-1),τ_σ(i)) and ω₂ = (τ₀, τ_σ(1), …, τ_σ(i - 1), τ_σ(i+1)), denoted by LB1 and LB2, is computed, respectively.

Step 4. If LB2 < LB1 is right, τ_σ(i) and τ_σ(i+1) exchange.

Step 5. If LB2 = LB1 holds, low bound of $ω_{1}^{'} = (τ_{σ (i + 1)}, τ_{σ (i + 2)}, \dots, τ_{σ (n (m + 1) - 1)})$ and $ω_{2}^{'} = (τ_{σ (i)}, τ_{σ (i + 2)}, \dots, τ_{σ (n (m + 1) - 1)})$ , called GLB1 and GLB2, is obtained, respectively.

Step 6. If LB2 + GLB1 < LB1 + GLB2, τ_σ(i) and τ_σ(i+1) exchanges; Otherwise, go to Step 1.

Step 7. If LB2 > LB1, go to step 1.

The on-wall ineffective collision reaction operator based on NE is given in the Procedure 3.

Procedure 3. On-wall ineffective collision

Input: a molecule ω.

Output: ω with update state.

Step 1. Produce a new molecule ω′ by using the Procedure 2.

Step 2. Compute PE value of ω′, denoted as PE_ω′.

Step 3. If PE_ω′ ≤ PE_ω + KE_ω, perform Steps 4 to 7.

Step 4. A stochastic number p is got in [KELossRate, 1].

Step 5. Let KE_ω′ = (PE_ω + KE_ω - PE_ω′) × p be the KE value of ω′.

Step 6. Let buffer = buffer + (PE_ω + KE_ω - PE_ω′)×(1 - p)

Step 7. Substitute ω′ for ω.

4.3.2 Decomposition

In this study, to obtain decomposition reaction operator, lemma 2 [4] is applied. After decomposition reaction operator is performed, part input sequence doesn’t change, and robotic move sequence seriously changes. So decomposition reaction operator can maintain diversity solution. The neighbourhood structure of lemma 2 [4], denoted by VRMS (variable robotic move sequence), is presented in the Procedure 4. The decomposition reaction operator is provided in the Procedure 5.

Procedure 4. VRMS

Input: a molecule, ω.

Output: a new molecule, ω′.

Step 1. A position (i) is stochastically selected in ω.

Step 2. Find these robotic activities, τ_σ(i′), τ_σ(i″), $τ_{σ ({\bar{i}}^{'})}$ and $τ_{σ ({\bar{i}}^{″})}$ , in ω, and let $Q (σ (i^{'})) = Q (σ ({\bar{i}}^{'})) = Q (σ (i)) - 1$ and $Q (σ (i^{″})) = Q (σ ({\bar{i}}^{″})) = Q (σ (i)) + 1$ . There are τ_σ(i′) and τ_σ(i″) in the right-most robotic activities on the left of τ_σ(i), and there are $τ_{σ ({\bar{i}}^{'})}$ and $τ_{σ ({\bar{i}}^{″})}$ in the left-most robotic activities on the right of τ_σ(i).

Step 3. Let γ₁ = max(i′, i″) and $γ_{2} = \min ({\bar{i}}^{'}, {\bar{i}}^{″})$ . ρ is stochastically generated between γ₁ and γ₂.

Step 4. Insert τ_σ(i) at ρ in ω. A new molecular ω′ is produced.

Procedure 5. Decomposition

Input: a molecule ω.

Output: two new molecules ω′, ω″, and Boolean variable flag.

Step 1. Run Procedure 4 twice, then two new molecules ω′, ω″ are got.

Step 2. Evaluate PE values of ω′ and ω″, denoted by PE_ω′ and PE_ω″.

Step 3. Let temp1 = PE_ω + KE_ω - (PE_ω′ + PE_ω″). Set flag = false.

Step 4. If temp1 ≥ 0, implement Steps 5 to 8; Otherwise, go to Step 9.

Step 5. Set flag = true.

Step 6. p is stochastically got between 0 and 1.

Step 7. Let KE_ω″ = temp1 × (1 - p) and KE_ω′ = temp1 × p be KE values of ω″ and ω′, respectively.

Step 8. Go to Step 14.

Step 9. If temp1 + buffer ≥ 0, perform Steps 10 to 13.

Step 10. Set flag = true.

Step 11. Get four stochastic numbers, p₁, p₂, p₃ and p₄, in [0, 1].

Step 12. Let KE_ω′ = (temp1 + buffer) × p₁ × p₂ and KE_ω″ = (temp1 + buffer - KE_ω′) × p₃ × p₄ be KE values of ω′ and ω″, respectively. Let buffer = temp1 + buffer - KE_ω′ - KE_ω″.

Step 13. Go to Step 14.

Step 14. Delete ω from the population and add ω′ and ω″ to the population.

4.3.3 Inter-molecular ineffective collision

In this subsection, to gain inter-molecular ineffective collision reaction operator, PEx is used. After inter-molecular ineffective collision reaction operator is implemented, part input sequence of selected molecule changes, and robotic move sequence of selected molecule doesn’t change. So depth search is performed more effectively in ECRO. In the following, PEx neighbourhood structure and inter-molecular ineffective collision reaction operator are given, respectively.

Procedure 6. PEx

Input: two molecules ω₁ and ω₂.

Output: two new molecules $ω_{1}^{'}$ and $ω_{2}^{'}$ .

Step 1. The point (i) is stochastically selected in ω₁.

Step 2. Find these parts, denoted $J_{σ (i)}^{1}$ and $J_{σ (i)}^{2}$ , which represent the parts of τ_σ(i) in ω₁ and ω₂, respectively.

Step 3. If $J_{σ (i)}^{1}$ and $J_{σ (i)}^{2}$ are the same, go to Step 1; Otherwise, implement Step 4.

Step 4. The PEx is applied in ω₁ and ω₂, respectively. Two new molecules $ω_{1}^{'}$ and $ω_{2}^{'}$ are generated.

Procedure 7. Inter-molecular ineffective collision

Input: two molecules ω₁ and ω₂.

Output: two new molecules $ω_{1}^{'}$ and $ω_{2}^{'}$ .

Step 1. Run Procedure 6, then two new molecules $ω_{1}^{'}$ and $ω_{2}^{'}$ are obtained.

Step 2. Compute PE value of $ω_{1}^{'}$ and $ω_{2}^{'}$ , denoted by ${PE}_{ω_{1}^{'}}$ and ${PE}_{ω_{2}^{'}}$ .

Step 3. temp2 = PE_{ω
₁} + KE_{ω
₁} + PE_{ω
₂} + KE_{ω
₂} - $({PE}_{ω_{1}^{'}}$ + ${PE}_{ω_{2}^{'}})$

Step 4. If temp2 ≥ 0, perform Steps 5 to Step 7.

Step 5. Produce a stochastic number p in [0, 1].

Step 6. Let ${KE}_{ω_{2}^{'}} = temp 2 \times (1 - p)$ and ${KE}_{ω_{1}^{'}}$ = temp2 × p be KE value of ω_1′ and ω_2′, respectively.

Step 7. Delete ω₁ and ω₂ from the population and push $ω_{1}^{'}$ and $ω_{2}^{'}$ into the population.

4.3.4 Synthesis

In ECRO, since distance-preserving crossover operator [27] can maintain selected molecules outstanding genes. Synthesis operator is realized according to following two steps. Firstly, part input sequence is got applied distance-preserving crossover operator. Secondly, robotic move sequence is stochastic selected molecules. The detailed process is shown in Procedure 8 and Procedure 9.

Procedure 8. distance-preserving crossover

Input: two molecules ω₁ and ω₂.

Output: a molecule ω.

Step 1. Find part input sequence of ω₁ and ω₂, denoted as Job₁ and Job₂, respectively.

Step 2. A new part input sequence, denoted by Job, is produced based on Job₁ and Job₂ according to distance-preserving crossover operator.

Step 3. Find robotic move sequence of ω₁ and ω₂, denoted as RM₁ and RM₂, respectively.

Step 4. Get a stochastic number p in [0, 1].

Step 5. If p ≥ 0.5, robotic move sequence of ω, denoted as RM, is RM₁; Otherwise, the RM is RM₂.

Step 6. A new molecule ω is generated based on Job and RM.

Procedure 9. synthesis

Input: two molecules ω₁ and ω₂.

Output: a new molecule ω, and the Boolean variable flag.

Step 1. Implement Procedure 8. A new molecule ω is got.

Step 2. Evaluate PE value of ω, denoted as PE_ω. Set flag = false.

Step 3. Let temp3 = PE_{ω
₁} + KE_{ω
₁} + PE_{ω
₂} + KE_{ω
₂} - PE_ω

Step 4. If temp3 ≥ 0, perform Steps 5 to 7.

Step 5. Set flag = true.

Step 6. Let KE_ω = temp3 be KE value of ω.

Step 7. Delete ω₁ and ω₂, and push ω into the population.

4.4 Fitness function

Fitness function is index which the molecule is evaluated. In this study the fitness function is the same as the objective function. The smaller the fitness value is, the better the molecule is. The objective function value is calculated according to literature [3].

4.5 Selection operation

Tournament selection can keep diversity solution and avoid premature. In this paper, tournament selection is considered in selection operation. For improving convergence speed, after multiple tests are carried out, competition scale is one third the number of current population. In procedure 10 detailed process is elaborated.

Procedure 10. selection operation

Input: the population

Output: one or two molecules

Step 1. One third molecules of the population are stochastically selected.

Step 2. If single molecular reactions are triggered, the molecule that fitness value is the best is selected.

Step 3. If two molecular reactions occur, perform twice Step 1, the molecule of the best fitness value is selected every time.

As mentioned above, ECRO flowchart is shown in Fig. 4.

Fig.4

ECRO flowchart.

5 Computational results

This section shows the computational experiments to test the performance of ECRO for the studied problem. Extensive experiments are conducted on a set of problems. All experiments are implemented using Microsoft Visual Studio 2010 and are run on a Intel(R) Core(TM) i5-4460 CPU@ 3.20 GHz and RAM 8 GB PC.

To evaluate the performance of ECRO, 36 instances are generated according to literature [15]. a_i,j (1 ≤ i ≤ m,1 ≤ j ≤ n) is an integer and a_i,j ∼ U [20, 99]. n is an integer and n = 5, 6, 7, 8. m varies in [4, 20], and m is an even number. d_i,j = 6 for all 1 ≤ j ≤ n, 0 ≤ i ≤ m. Void move time c_i,l = 4|i - l| for all 0 ≤ i, l ≤ m + 1.

5.1 IRAM performance

To evaluate the performance of IRAM, the other method, stochastic generated solution method (SGSM), is proposed. When n = 5 and n = 8, thirty solutions of each instance are got by IRAM and SGSM, respectively. Figure 5 shows the result of IRAM and SGSM. Following conclusions can be gained: (1) When n is fixed, the bigger m is, the bigger the value of objective function is. (2) Compared with SGSM, the solutions which IRAM produces is more concentrated. (3) The maximum value (MAXV) that IRAM produces is smaller than the minimum value (MINV) that SGSM gets, and the distance between MAXV and MINV increases gradually when m varies from 4 to 20. So IRAM can produce much better solutions, and initial population is more effective.

Fig.5

Comparison of IRAM and SGSM.

5.2 Comparisons of algorithms

On the test the instances, ECRO compares with branch and bound (BB) method, beam search (BS). BB and BS are designed based on OI rule. But BB is an exact method, BS is a heuristic search algorithm.

ECRO performance is affected by parameters. After multiple tests are carried out, Table 3 lists the parameter values. Termination condition is the maximum computational time exceeds 600 seconds.

Table 3
Parameter values

KE KELossRate MoleColl α β buffer Popsize

1000 0.2 0.2 100 200 0 30

KE	KELossRate	MoleColl	α	β	buffer	Popsize
1000	0.2	0.2	100	200	0	30

For each given pair of (m, n), each instance is run 15 times, the average of each instance, called ${AVGE}_{i}^{r}$ (i ∈ {4, 6, 8, 10, 12, 14, 16, 18, 20}, r∈ { BB, BS, ECRO }), is recorded. The performance measures are defined by Equations (15), (16) and (17). $IR 1_{i} = \frac{{AVGE}_{i}^{BB} - {AVGE}_{i}^{BS}}{{AVGE}_{i}^{BB}} \times 100$ $IR 2_{i} = \frac{{AVGE}_{i}^{BB} - {AVGE}_{i}^{ECRO}}{{AVGE}_{i}^{BB}} \times 100$ (16) $IR 3_{i} = \frac{{AVGE}_{i}^{BS} - {AVGE}_{i}^{ECRO}}{{AVGE}_{i}^{BS}} \times 100$ (17)

For evaluating ECRO performance, the performance indices are defined by Equations (18) and (19). ${AVGIR}_{BS} = \sum_{i} IR 1_{i} / 9$ (18) ${AVGIR}_{CRO} = \sum_{i} IR 2_{i} / 9$ (19)

Figure 6 shows the advantages of ECRO and BS. Although ECRO advantage is going down when n changes from 5 to 8, ECRO is outstanding. For all n, ECRO is much better than BB. Compared to BS, when the number of parts in MPS varies from 5 to 7, ECRO is advantageous, but the advantage is reducing. Furthermore, when n = 8, ECRO is little worse than BS.

Fig.6

BS and ECRO performance.

Tables 4 and 5 displays comparative ECRO with BB and BS. The results indicate high quality solutions can be searched by ECRO. ECRO compares with the BB improvement rate of only six instances is less than zero. In the six instances, although the smallest IR2 is – 2.51%, the biggest distance of the objective function value is 18. In the remainder instances, the worst IR2 is 0.16%, the best IR2 is 20.14%, the average IR2 is 6.41%. Compared to BS, although 7 out of 36 instances aren’t improved, in the remainder instances the biggest IR3 is 10.81%, the average IR3 is 4.56%. So, ECRO is outstanding.

Table 4

Improvement rate of the algorithms for n = 5 and n = 6

m	n = 5					n = 6
	T			Improvement rate		T			Improvement rate
	BB	BS	ECRO	IR2	IR3	BB	BS	ECRO	IR2	IR3
4	490	491	498	– 1.71%	– 1.51%	566	602	580	– 2.51%	3.62%
6	618	603	582	5.79%	3.45%	805	713	683	15.20%	4.26%
8	859	877	826	3.84%	5.82%	948	971	929	1.98%	4.30%
10	1115	1122	1057	5.20%	5.79%	1193	1255	1148	3.81%	8.56%
12	1380	1469	1398	– 1.33%	4.81%	1568	1659	1515	3.39%	8.69%
14	1739	1656	1599	8.06%	3.45%	1952	1966	1865	4.45%	5.13%
16	1979	1949	1868	5.59%	4.14%	2265	2303	2097	7.43%	8.96%
18	2140	2231	2103	1.72%	5.73%	2575	2487	2404	6.64%	3.34%
20	2722	2669	2437	10.48%	8.71%	3059	2953	2634	13.90%	10.81%

Table 5

Improvement rate of the algorithms for n = 7 and n = 8

m	n = 7					n = 8
	T			Improvement rate		T			Improvement rate
	BB	BS	ECRO	IR2	IR3	BB	BS	ECRO	IR2	IR3
4	669	728	674	– 0.81%	7.36%	768	768	767	0.16%	0.16%
6	980	780	783	20.14%	– 0.33%	963	899	905	6.02%	– 0.67%
8	1060	1051	1044	1.55%	0.70%	1343	1200	1174	12.61%	2.20%
10	1484	1432	1394	6.04%	2.63%	1518	1518	1489	1.88%	1.88%
12	1667	1811	1669	– 0.11%	7.85%	2043	1781	1832	10.32%	– 2.87%
14	2119	2045	2024	4.46%	1.01%	2262	2286	2222	1.76%	2.79%
16	2484	2473	2433	2.05%	1.61%	2581	2573	2591	– 0.40%	– 0.72%
18	2840	2812	2713	4.49%	3.53%	3160	2934	3040	3.80%	– 3.61%
20	3260	2923	2899	11.09%	0.83%	3575	3190	3270	8.53%	– 2.51%

6 Conclusions

In this paper, the cyclic multi-type parts robotic cell scheduling problem with blocking is investigated, and an effective chemical reaction optimization is proposed for optimizing simultaneously robotic move sequence and part input sequence.

In ECRO, the robotic activity encoding is proposed, the encoding method can transfer a scheduling sequence represented by a two-dimensional array into a sequence with one-dimensional array. To construct feasible solution, OI rule is proposed. For generating effectively initial population, IRAM is presented based on OI rule. For improving search speed and enhancing performance of ECRO, elementary reaction operators are designed according to properties of feasible solutions that are found in this paper. Compared with BB and BS based on solving stochastic generating instances, the proposed algorithm is outstanding. Next, we will discuss how to design evolutionary operators and keep diversity solution for improving ECRO.

Footnotes

Acknowledgments

This work was partially supported by the National Nature Science Foundation of China under Grant Nos. 71471151 and 61573264; Fundamental Research Funds for the Central Universities under Grant No. 26816WCX04; and Science and Technology Research Program of Chongqing Municipal Education Commission under Grant No. KJ1711293.

References

Agnetis

, Scheduling no-wait robotic cells with two and three machines, European Journal of Operational Research 123(2) (2000), 303–314.

Amraoui

A.E.

and Elhafsi

, An efficient new heuristic for the hoist scheduling problem, Computers & Operations Research 67 (2016), 184–192.

Amraoui

A.E.

, Manier

M.A.

, Moudni

A.E.

and Benrejeb

, A genetic algorithm approach for a single hoist scheduling problem with time windows constraints, Engineering Applications of Artificial Intelligence 26(7) (2013a), 1761–1771.

Amraoui

A.E.

, Manier

M.A.

, Moudni

A.E.

and Benrejeb

, A linear optimization approach to the heterogeneous r-cyclic hoist scheduling problem, Computers & Industrial Engineering 65(3) (2013b), 360–369.

Aneja

Y.P.

and Kamoun

, Scheduling of parts and robot activities in a two machine robotic cell, Computer and Operations Research 26(4) (1999), 297–312.

Brucker

, Burke

E.K.

and Groenemeyer

, A branch and bound algorithm for the cyclic job-shop problem with transportation, Computer & Operations Research 39(12) (2012a), 3200–3214.

Carlier

, Haouari

, Kharbeche

and Moukrim

, An optimization-based heuristic for the robotic cell problem, European Journal of Operational Research 202(3) (2010), 626–635.

Che

, Chu

and Levner

, A polynomial algorithm for 2-degree cyclic robot scheduling, European Journal of Operational Research 145(14) (2003), 31–44.

Che

, Yan

, Yang

and Chu

, Optimal cyclic scheduling of a hoist and multi-type parts with fixed processing times, International Journal of Production Research 48(5) (2010), 1225–1243.

10.

Chen

, Chu

and Proth

, Cyclic scheduling with time window constraints, IEEE Transactions on Robotics and Automation 14(1) (1998), 144–152.

11.

Chen

, Chu

and Proth

J.M.

, Sequencing of parts in robotic cells, International Journal of Flexible Manufacturing Systems 9(1) (1997), 80–104.

12.

Duan

H.B.

and Gan

, Elitist chemical reaction optimization for contour-based target recognition in aerial images, IEEE Transactions on Geoscience & Remote Sensing 53(5) (2015), 2845–2859.

13.

Hall

N.G.

, Kamoun

and Sriskandarajah

, Scheduling in robotic cells: Classification, two and three machine cells, Operational Research 45(3) (1997), 421–439.

14.

Hall

N.G.

, Kamoun

and Sriskandarajah

, Scheduling in robotic cells: Complexity and steady state analysis, European Journal of Operational Research 109(1) (1998), 43–65.

15.

Kamoun

, Hall

N.G.

and Sriskandarajah

, Scheduling in robotic cells: Heuristics and cell design, Operational Research 47(6) (1999), 821–835.

16.

Kats

and Levner

, Cyclic scheduling in a robotic production line, Journal of Scheduling 5(1) (2002), 23–41.

17.

Kharbeche

, Carlier

, Haouari

and Moukrim

, Exact method for robotic cell problem, Electronic Notes in Discrete Mathematics 36(2) (2010), 858–865.

18.

Kim

, Lee

and Lee

, Noncyclic scheduling of cluster tools with a branch and bound algorithm, IEEE Transactions on Automation Science & Engineering 12(2) (2015), 690–700.

19.

Lam

A.Y.S.

and Li

V.O.K.

, Chemical-reaction-inspired metaheuristic for optimisation, IEEE Transactions Evolutionary Computation 14(3) (2010), 381–399.

20.

Lam

A.Y.S.

and Li

V.O.K.

, Chemical reaction optimization: A tutorial, Memetic Computing 4(3) (2012), 3–17.

21.

Lei

, Che

and Chu

, Optimal cyclic scheduling of a robotic flowshop with multiple part types and flexible processing times, European Journal of Industrial Engineering 8(2) (2014), 143–167.

22.

Levner

, Kats

and Levit

, An improved algorithm for cyclic flowshop scheduling in a robotic cell, European Journal of Operational Research 97(3) (1997), 500–508.

23.

J.Q.

, Pan

Q.K.

and Wang

F.T.

, A hybrid variable neighbourhood search for solving the hybrid flow shop scheduling problem, Applied Soft Computing 24 (2014), 63–77.

24.

Liu

S.Q.

and Kozan

, A hybrid metaheuristic algorithm to optimise a real-world robotic cell, Computers & Operations Research 84 (2017), 188–194.

25.

Majumder

and Laha

, A new cuckoo search algorithm for 2-machine robotic cell scheduling problem with sequence-dependent setup times, Swarm and Evolutionary Computation 28 (2016), 131–143.

26.

Marzouki

and Driss

O.B.

, Multi agent model based on chemical reaction optimization for flexible job shop problem, Computational Collective Intelligence 9329 (2015), 29–38.

27.

Merz

, Freisleben

, A genetic local search approach to the quadratic assignment problem. in Proc 7th Int Conf Genetic Algorithms. Bäck

, Ed. San Francisco, CA: Morgan Kaufmann, 1997, pp. 465–472 .

28.

Mogale

D.G.

, Kumar

S.K.

, Márquez

F.P.G.

and Tiwari

M.K.

, Bulk wheat transportation and storage problem of public distribution system, Computers and Industrial Engineering 104 (2017), 80–97.

29.

Paul

, Bierwirt

H.C.

and Kopfer

, A heuristic scheduling procedure for multi-item hoist production lines, International Journal of Production Economics 105(1) (2007), 54–69.

30.

Roy

P.K.

, Hybrid chemical reaction optimization approach for combined economic emission short-term hydrothermal scheduling, Electric Power Components and Systems 42(15) (2014), 1647–1660.

31.

Saifullah

and Rafiqul

, Chemical reaction optimization for solving shortest common supersequence problem, Computational Biology and Chemistry 64 (2016), 82–93.

32.

Sethi

, Sriskandarajah

, Sorger

, Blazewicz

and Kubiak

, Sequencing of parts and robot moves in a robotic cell, International Journal of Flexible Manufacturing Systems 4 (1992), 31–58.

33.

Truong

T.K.

, Li

K.L.

and Xu

Y.M.

, Chemical reaction optimization with greedy strategy for the 0–1 knapsack problem, Applied Soft Computing 13(4) (2013), 1774–1780.

34.

Zahrouni

and Kamoun

, Transforming part-sequencing problems in a robotic cell into a GTSP, Journal of the Operational Research Society 62(1) (2011), 114–123.

35.

Zahrouni

and Kamoun

, Sequencing and scheduling in a three-machine robotic cell, International Journal of Production Research 49(10) (2012), 2823–2835.

36.

Zarandi

M.H.F.

, Mosadegh

and Fattahi

, Two-machine robotic cell scheduling problem with sequence-dependent setup times, Computers & Operations Research 40(5) (2013), 1420–1434.

An effective chemical reaction optimization for cyclic multi-type parts robotic cell scheduling problem with blocking

Abstract

Keywords

1 Introduction

2 Problem description

Table 1 Relationship between τi+(m+1)(j-1) and move [i, j] part P 0 P 1 P 2 P 3 P 4 J 1 [0, 1] →0 [1, 1] →1 [2, 1] →2 [3, 1] →3 [4, 1] →4 J 2 [0, 2] →5 [1, 2] →6 [2, 2] →7 [3, 2] →8 [4, 2] →9 J 3 [0, 3] →10 [1, 3] →11 [2, 3] →12 [3, 3] →13 [4, 4] →14

4.1 Robotic activity encoding and decoding

4.2.1 OI rule

4.2.2 IRAM

4.3 Elementary reactions of ECRO

4.3.1 On-wall ineffective collision

4.3.2 Decomposition

4.3.3 Inter-molecular ineffective collision

4.3.4 Synthesis

4.4 Fitness function

4.5 Selection operation

5.1 IRAM performance

Table 3 Parameter values KE KELossRate MoleColl α β buffer Popsize 1000 0.2 0.2 100 200 0 30

Footnotes

Acknowledgments

References

Table 3
Parameter values

KE KELossRate MoleColl α β buffer Popsize

1000 0.2 0.2 100 200 0 30