A shuffled frog-leaping algorithm with Q-learning for unrelated parallel machine scheduling with additional resource and learning effect

Abstract

Unrelated parallel machine scheduling problem (UPMSP) with additional resources and UPMSP with learning effect have attracted some attention; however, UPMSP with additional resources and learning effect is seldom studied and meta-heuristics for UPMSP hardly possess reinforcement learning as new optimization mechanism. In this study, a shuffled frog-leaping algorithm with Q-learning (QSFLA) is presented to solve UPMSP with one additional resource and learning effect. A new solution presentation is presented. Two populations are obtained by division. A Q-learning algorithm is constructed to dynamically decide search operator and search times. It has 12 states depicted by population quality evaluation, four actions defined as search operators, a new reward function and a new action selection. Extensive experiments are conducted. Computational results demonstrate that QSFLA has promising advantages for the considered UPMSP.

Keywords

parallel machine scheduling additional resource learning effect shuffled frog-leaping algorithm reinforcement learning

1 Introduction

Scheduling problems and algorithms have been widely applied in manufacturing industries for efficient production. Parallel machine scheduling problem (PMSP) is a typical scheduling one which is among the most studied area in scheduling literature and has been extensively investigated [1 –24]. In most of the related works on PMSP, machine is the only considered resource; however, additional resources including automated guided vehicles, machine operators, tools, pallets, dies and industrial robots are often required in many real-world parallel machine manufacturing process. PMSP with additional resources has become a significant area of scheduling research [3 –24].

Edis et al. [3] presented notation and classification on PMSP with additional resources according to types of additional resources, which may be renewable or non-renewable, discrete or continuous and exist in processing or during setup etc. Unrelated parallel machine scheduling problem with additional resources (UPMSPR) is an extended version of unrelated parallel machine scheduling problem (UPMSP) and has been extensively considered in the past decades. With respect to UPMSPR with one additional resource, Ventura and Kim [6] dealt with two UPMSPR, one of which possesses one single type additional resource and is shown to be equivalent to the asymmetric assignment problem. Zheng and Wang [7] reported a two-stage adaptive fruit fly optimization algorithm (FOA) for the problem with renewable resource. Fanjul-Peyro et al. [8] constructed two integer linear programming model and proposed three matheuristics. Fleszar and Hindi [9] presented an efficient mixed-integer linear programming (MILP) model to calculated a lower bound and a constraint programming model to schedule jobs on machines. Zheng and Wang [10] reported a collaborative multi-objective FOA for the problem with carbon emission minimization. Villa et al. [11] developed several heuristics based on resource constraint and assignment rule. Vallada et al. [12] applied an enriched scatter search and an enriched iterated greedy and adopted a best known heuristic and a repair mechanism in two algorithms.

Regarding UPMSP with multiple additional resources, Chen [13] proposed a heuristic with a capability relative to a runtime and solution quality for UPMSP with some types of dies as second resources. Bitar and Dauzère-Pérès [14] dealt with UPMSP with auxiliary resources in a photolithography workshop of a semiconductor plant, analyzed properties of the problem and provided a memetic algorithm. Afzalirad and Shafipour [15] developed an integer mathematical programming model and two genetic algorithms (GA) for UPMSPR with eligibility restrictions. Al-Harkan and Qamhan [16] solved UPMSP with non-zero arbitrary release dates, additional resources and sequence-dependent setup times (SDST) by a two-stage hybrid meta-heuristic based on variable neighborhood search and simulated annealing. Fanjul-Peyro [17] focused on UPMSP with processing resources, setup resources and shared resources and presented a MILP model and a three phase algorithm. Yepes-Borrero et al. [18] presented three heuristics and GRASP algorithm for UPMSP with setup times and additional limited resources in setup. Pinar and Seyda [19] considered multi-resource constrained UPMSP with sequence-dependent setup times (SDST), precedence relation, machine eligibility and release dates and proposed a constraint programming model and two branching strategies for the model.

Learning effect means that processing time is subject to change due to learning of operators. UPMSP with learning effect has been investigated in the past decade. Kuo et al. [20] discussed the polynomial solvability of UPMSP with setup times and learning effect. Wang and Wang [21] handled UPMSP with learning effect and deteriorating jobs and proved that the problem can be solved in polynomial time when the number of machines is given. Lu et al. [22] analyzed unrelated parallel-machine resource allocation scheduling problem with learning effect and deteriorating jobs and proved that the problem is polynomial time solvable if the number of machines is fixed. Soleimani et al. [23] considered UPMSP with start-time-related deterioration, position-based learning and SDST and presented GA, cat swarm optimization and interactive artificial bee colony to minimize mean weighted tardiness and power consumption. Zhang et al. [24] proposed a combinatorial evolutionary algorithm for UPMSP with setup times, limited worker resources and learning effect.

As stated above, UPMSPR is frequently investigated and UPMSP with learning effect also attracts some attention; however, the existing works seldom combine additional resources and learning effect together. In fact, additional resources and learning effect often exist simultaneously in parallel machine production process and optimization results of UPMSPR with learning effect can effectively reflect real-life situation, so it is necessary to considered UPMSPR with learning effect. On the other hand, as the main approaches to production scheduling problem, meta-heuristics are not applied to solve UPMSPR fully, the optimization ability and advantages of some meta-heuristics including shuffled frog-leaping algorithm (SFLA) are hardly tested to find more competitive methods; moreover, new optimization mechanisms including reinforcement learning (RL) are seldom added into meta-heuristics for the above UPMSP.

RL algorithms including Q-learning algorithm have been applied to service meta-heuristics for production scheduling problem in recent years. Cao et al. [25] presented a cuckoo search with RL and surrogate modelling for semiconductor final testing scheduling problem with multiresource constraints. Chen et al. [26] proposed a self-learning genetic algorithm with Q-learning algorithm for flexible job shop scheduling. Cao et al. [27] developed a knowledge-based cuckoo search with knowledge base based on RL algorithm named SARSA for flexible job shop scheduling with sequencing flexibility. In these works, RL is used to adjust adaptively parameters settings and results proved that the performance of meta-heuristic can be improved effectively. The integration of RL and meta-heuristic also can dynamically select search operator [28]; however, search operator of meta-heuristic is seldom decided dynamically by RL, so it is necessary to discuss fully the integration of RL and meta-heuristic.

SFLA is a meta-heuristic by observing, imitating and modelling the behavior of a group of frogs when searching for the location that has maximum amount of available food [29]. Owing to fast convergence speed and effective algorithm structure containing local search and global information exchanges, it has been widely applied to solve various scheduling problems in single factory [30 –38], and multiple factories [39 –42]; however, SFLA is hardly applied to solve UPMSPR and UPMSPR with learning effect. SFLA has some good features and extensive applications to scheduling; moreover, RL can be integrated easily with SFLA because of its algorithm structure, so SFLA may be effective path to solve UPMSPR with learning effect and its search efficiency can be improved effectively by RL algorithm.

In this study, UPMSPR with learning effect is considered and a novel shuffled frog-leaping algorithm with Q-learning (QSFLA) is proposed to minimize makespan. In QSFLA, a new coding and decoding are proposed and the whole population is divided into two sub-populations, then Q-learning algorithm is constructed to dynamically select search operator and search times. It consists of 12 states depicted by population quality evaluation, four actions defined as search operators, a new reward function and a novel action selection. A number of experiments are conducted and computational results show that QSFLA can solve effectively UPMSPR with learning effect.

The remainder of the paper is organized as follows. The problem is described in Section 2. QSFLA for the considered problem is reported in Section 3. Numerical experiments on QSFLA are reported in Section 4 and the conclusions are summarized in the final section and some topics of the future research are provided.

2 Problem description

UPMSPR with learning effect is described as follows. There are n jobs J₁, J₂, ⋯ , J_n and m unrelated parallel machines M₁, M₂, ⋯ , M_m. Each job can be processed on any one of m machines. p_kjv indicates processing time of job J_j processed on position v on machine M_k by a given schedule, p_kjv = p_kj (W + (1 - W) v^δ) [43], where p_kj indicates initial processing time, δ ≤ 0 is learning factor, W is incompressibility factor, v denotes the position of J_j on M_k in a given schedule.

An additional renewable resource is considered. When job J_j is processed on M_k, it needs re_kj units of the additional resource. At most R_max units of the additional resource can be used at any time.

There have following constraints on jobs and machines.

All jobs and machines are available at time zero.

Each job can be processed on only one machine at a time.

Operations cannot be interrupted.

Preemption is not allowed.

The problem is composed of scheduling sub-problem and machine assignment sub-problem. The goal of the problem is to minimize makespan. $min C_{max} = max {C_{j} | j = 1, 2, \dots, n}$ (1) where C_j and C_max indicate the completion time of job J_j and maximum completion time of all jobs. $p_{kj} = (\begin{matrix} 49 & 51 & 9 & 98 & 63 & 80 & 12 & 41 \\ 88 & 64 & 75 & 47 & 29 & 50 & 59 & 85 \end{matrix}); {re}_{kj} = (\begin{matrix} 4 & 3 & 7 & 5 & 6 & 3 & 5 & 3 \\ 6 & 4 & 8 & 1 & 7 & 2 & 6 & 6 \end{matrix})$

An illustrative example is provided. W = 0, δ = -0.1, R_max = 10. A schedule of the example is shown in Fig. 1.

Fig. 1

A schedule of the example.

3 QSFLA for UPMSPR with learning effect

The integration of RL and meta-heuristic for combinatorial optimization has been extensively studied [28]. In this study, a typical RL algorithm named Q-learning algorithm is integrated with SFLA to dynamically select search operator and search times. Q-learning algorithm is constructed by 12 states based on population evaluation, four actions used as search operators, a new reward function and a action selection method. The detailed steps of QSFLA are described in the following sections.

3.1 Solution representation and population division

A new two-string representation is adopted. For UPMSPR with n jobs, m machines, R_max units of additional resource and learning effect, its solution is composed of a machine assignment string [M_{h
₁}, M_{h
₂}, ⋯ , M_{h
_n}] and a scheduling string [π₁, π₂, ⋯ , π_n], where M_{h
_i} is the assigned machine for job J_i and π_i∈ { 1, 2, ⋯ , n }.

The decoding procedure is shown below. For scheduling string, start with π₁, for each π_i, first check each idle period of the processing machine M_k of job J_{π_i} decided by the first string, if J_{π_i} can be inserted into some idle periods when processing time and resource constraint are met, then choose an idle period with the smallest beginning time and insert J_{π_i} into the chosen period according to processing time and resource constraint; otherwise, J_{π_i} is processed after the current last processed job of M_k.

All constraints are handled in decoding procedure as done in papers [1 –24] and each solution is feasible, solutions can be improved continuously in the search process of QSFLA.

The beginning time B_{π_ik} is decided as follows: B_{π_ik} = max{ η_k, θ_{π_ik} }, η_k is the best available time of M_k and θ_{π_ik} is the earliest time of J_{π_i} on M_k that resource constraint is met. When a job J_{π_i} is inserted into an idle period of a machine, the position of other jobs after the inserted job J_{π_i} will increase and the corresponding processing time will diminish, in this case, beginning times of these jobs are kept invariant and completion time will become smaller.

For the example in Section 2, a solution is composed of a machine assignment string [M₂, M₁, M₂, M₁, M₂, M₂, M₁, M₁] and a scheduling string [1, 6, 4, 7, 5, 8, 2, 3]. In the decoding process, when job J₇ is handled and processed on M₁, there is an idle period [0,88] and J₇ cannot be processed in the idle period because of resource constraint, so J₇ is processed after job J₄. For job J₈, it can be inserted into idle period [0,81] on M₁, after J₈ is inserted, completion times of J₄, J₇ diminish, so an idle period between J₄ and J₇. If there is no insertion on M₁, no idle period between J₄, J₇ exists. Fig. 1 shows the obtained schedule by decoding the above two strings.

An initial population P with N solutions is randomly produced. N/2 randomly chosen solutions are added into sub-population P₁ and the remained N/2 solutions are included into sub-population P₂. P = P₁ ∪ P₂.

In sub-population P₁, there are S/2 solutions with smaller makespan than other solutions of P₁, suppose $C_{\max}^{x_{1}} \leq C_{\max}^{x_{2}} \leq \dots C_{\max}^{x_{S / 2}}$ , where $C_{\max}^{x_{i}}$ indicates makespan of solution x_i. P₁ is divided into s/2 memeplexes: allocate x_l to memeplex $M_{l}$ sequentially, l = 1, 2, ⋯ , s/2; let g = s/2 +1, l = 1, repeat the following steps until g > N/2: randomly choose two solutions from $P_{1} ∖ ⋃_{i = 1}^{s / 2} M_{i}$ , add the better one of two solution into memeplex $M_{l}$ , l = l + 1, let l = 1 if l = s/2 +1, g = g + 1.

The remained s/2 memeplexes are constructed by using P₂ in the same way of P₁. Finally, s memeplexes are obtained.

3.2 Global search and neighborhood search

In each memeplex $M_{i}$ , $x_{b} \in M_{i}$ is selected as optimization object. Global search of $x_{b} \in M_{i}$ is used and shown below. Execute two-point crossover between machine assignment strings of x_b and a randomly selection $x \in M_{i}$ , obtain a new solution y, if y is better than x_b, then update x_b with y and renew elite solution x^* if y is also better than x^*; otherwise, execute partially mapping crossover (PMX [44]) between scheduling string of x_b and x and update x_b and x^* with the newly generated solution y according to the above conditions.

Five neighborhood structures are used. $N_{1}$ is shown below. Randomly select two machines M_k, M_l and exchange a randomly chosen job J_i on M_k and a stochastically selected job J_j on M_l. $N_{2}$ is described as follows. Decide a machine M_k with the biggest completion time and a randomly chosen machine M_l, l ≠ k, remove a randomly chosen job on M_k to M_l. $N_{3}$ is swap operator on scheduling string, $N_{4}$ is insertion on scheduling string and $N_{5}$ is invert operator on scheduling string.

Multiple neighborhood search on x_b is described as follows. $N_{1}, N_{2}, N_{3}, N_{4}, N_{5}$ are executed sequentially, for each $N_{u}, u = 1, 2, 3, 4, 5$ , produce $y \in N_{u} (x_{b})$ , if y is better than x_b, then x_b is replaced with y and x^* is updated with y if possible. where $N_{u} (x)$ indicates the set of neighborhood solutions produced by $N_{u}$ .

3.3 Q-learning algorithm

Q-learning algorithm is the most commonly used model-free RL algorithm [45]. It has successfully applied to solve scheduling problem [25 –27]. $\begin{matrix} Q ({st}_{t}, a_{t}) \leftarrow Q ({st}_{t}, a_{t}) + α (r_{t + 1} + \\ γ max_{a} Q ({st}_{t + 1}, a) - Q ({st}_{t}, a_{t})) \end{matrix}$ (2) where α is the learning rate and often set to be 0.1, γ indicates the discount factor, r_t+1 is the reward received from the environment by taking action a_t in state st_t, $\max_{a} Q ({st}_{t + 1}, a)$ represents the biggest Q value in Q-table at state st_t+1.

In Q-learning algorithm, there are state st_t, action a_t, reward r_t and action selection strategy. In this study, environmental state is depicted as population evaluation result and action is described as a combination of global search and neighborhood search.

12 states are defined based on evaluation on population P. Two performance indices are used. trial^* describes the improvement of elite solution x^*. trial^* = 0 indicates that x^* is improved on the current generation t. trial^* > 0 implies that x^* cannot be improved in trial^* generations. Diversity index on generation t is defined by ${DI}_{t} = \sqrt{\frac{1}{N} \sum_{x_{i} \in P} {(C_{max, t}^{x_{i}} - {\bar{C}}_{max, t})}^{2}}$ (3) where $C_{\max, t}^{x_{i}}$ and ${\bar{C}}_{\max, t}$ indicate makespan of x_i and the average makespan of all solutions in P on generation t.

Table 1 describes 12 states defined by trial^* and ΔDI_t, which is equal to DI_t - DI_t-1. where μ_i is integer, μ₁ < μ₂.

Table 1

State set

state	state description
1	0 < trial^* < μ₁ and ΔDI_t = 0
2	0 < trial^* < μ₁ and ΔDI_t > 0
3	0 < trial^* < μ₁ and ΔDI_t < 0
4	μ₁ ≤ trial^* < μ₂ and ΔDI_t = 0
5	μ₁ ≤ trial^* < μ₂ and ΔDI_t > 0
6	μ₁ < trial^* ≤ μ₂ and ΔDI_t < 0
7	trial^* ≥ μ₂ and ΔDI_t = 0
8	trial^* ≥ μ₂ and ΔDI_t > 0
9	trial^* ≥ μ₂ and ΔDI_t < 0
10	trial^* = 0 and ΔDI_t = 0
11	trial^* = 0 and ΔDI_t > 0
12	trial^* = 0 and ΔDI_t < 0

Four actions are adopted, which are search operators of P₁, P₂. Each search operator consists on a combination of global search and neighborhood search on P₁ and another combination of global search and neighborhood search on P₂.

When action is defined, sub-populations P₁, P₂ are first evaluated, then they are sorted in ascending order of ${Eva}_{P_{i}}^{t}$ , suppose that ${Eva}_{P_{1}}^{t} \leq {Eva}_{P_{2}}^{t}$ , that is, the sub-population with smaller ${Eva}_{P_{i}}^{t}$ is P₁ and another sub-population is P₂. ${Eva}_{P_{i}}^{t} = C_{\max, t}^{x_{1}} + C_{\max, t}^{x_{2}} + λ \sum_{x \in P_{i} ∖ {x_{1}, x_{2}}} C_{\max, t}^{x}$ (4) where x₁, x₂ are two solutions of P_i with smallest makespan, λ is a real number and set to be 0.1 by experiments.

Action a (1) is described as follows. For each $M_{i} \subset P_{1}$ , global search is performed on $x_{b} \in M_{i}$ in the first β iterations, then multiple neighborhood search of $x_{b} \in M_{i}$ is executed in the remained R - β iterations; For each $M_{i} \subset P_{2}$ , global search on $x_{b} \in M_{i}$ is first done in the first R - β iterations and multiple neighborhood search of $x_{b} \in M_{i}$ is executed in the remaining β iterations, where R is the number of iterations, β is an integer.

The differences between a (2) and a (1) lie in that no global search is done for each $M_{i} \subset P_{2}$ and neighborhood search is executed in R iterations. a (3) differs from a (1) in the following steps: no neighborhood search is applied for each $M_{i} \subset P_{1}$ and global search is done in R iterations.

Action a (4) is shown below. Global search on $x_{b} \in M_{i}$ is performed in R iterations for each $M_{i} \subset P_{1}$ and multiple neighborhood search on $x_{b} \in M_{i}$ is done in R iterations for each $M_{i} \subset P_{2}$ .

A new reward function r_t+1 is defined by $r_{t + 1} = {\begin{matrix} \frac{- | {eq}_{t + 1} - {eq}_{t} | {eq}_{t + 1}}{{eq}_{t}} & if {eq}_{t + 1} \geq {eq}_{t} \\ \frac{| {eq}_{t + 1} - {eq}_{t} | {eq}_{t}}{{eq}_{t + 1}} & else \end{matrix}$ (5) where ${eq}_{t} = w_{1} \frac{C_{max, t}^{*}}{C_{max, 1}^{*}} + w_{2} \frac{{DI}_{t}}{{DI}_{1}}$ (6)

In Equ. (6), w₁, w₂ are weight, w₁ + w₂ = 1, $C_{\max, t}^{*}$ is makespan of elite solution x^* on generation t. We set w₂ < 0.5 to guarantee that eq_t is mainly decided by the first part.

Action selection is done based on Q values. Initially, all Q values are zero, which means that the agent does not have any learning experience to use. ɛ-greedy is often used and expressed as follows. If a random number rand < ɛ, then randomly select an action a; otherwise, select the action a which maximizes Q values, that is, $a = arg max_{a^{'}} Q (s_{t}, a^{'})$ .

In this study, a novel action selection method is proposed. For the current state st_t, one of four actions a (1) , a (2) , a (3) , a (4) is chosen as a_t by roulette selection based on probability Pr (st_t, a (l)) , l = 1, 2, 3, 4.

$\Pr ({st}_{t}, a (l)) = e^{ω_{l}} / \sum_{g = 1}^{4} e^{ω_{g}}$ (7) $ω_{g} = Q ({st}_{t}, a (g)) / \sum_{b = 1}^{4} Q ({st}_{t}, a (b))$ (8)

In this way, each action can be selected in an appropriate probability for each state st_t and it is unnecessary to decide parameter ɛ.

Unlike the previous works [25 –27], Q-learning algorithm is used to provide search operator and search times for memeplex. 12 states are used to depict evolution quality of population P and four actions are applied to decide search operators for P₁, P₂ and search iterations for each operator; action selection is done without using ɛ and a reward function is defined.

3.4 Algorithm description

In QSFLA, a new solution representation and decoding process are first introduced; then population P is divided into sub-populations P₁, P₂; Q-learning algorithm is used to dynamically select search operator for all memeplexes on each generation; moreover, memeplex $M_{i} \subset P_{1}$ has different search operators from memeplex $M_{j} \subset P_{2}$ , as a result, differentiated search is implemented.

The detailed steps of QSFLA are shown below.

(1) Randomly produce an initial population P with N solutions, set initial Q-table, t = 1.

(2) Divide P into P₁, P₂ and obtain s/2 memeplexes for each P_i, i = 1, 2.

(3) Evaluate sub-populations P₁, P₂ and sort them according to ${Eva}_{P_{i}}^{t}$ .

(4) Select an action according to Equ. (7) and execute memeplex search in each memeplex by using the chosen action.

(5) Execute population shuffling and update Q-table, t = t + 1.

(6) If the stopping condition is not met, go to step (2); otherwise, terminate the search.

Q-table is updated once on a generation, so t indicates generation of population evolution and times of Q-learning. Time complexity of QSFLA is N × (n + snum × anum) × max _ t, where snum, aunm, max _ t are total number of states, total number of actions and maximum generation.

4 Computational experiments

Extensive experiments are conducted to test the performance of QSFLA for UPMSPR with learning effect. All experiments are implemented by using Microsoft Visual C++ 2019 and run on 8.0G RAM 2.30GHz CPU PC.

4.1 Test instances and comparative algorithms

300 instances are used and their basic data are directly from Fanjul-Peyro et al. [8]. On learning effect, W = 0 and δ = -0.1. R_max = 5m. Each instance is denoted as n × m × No. There are five ways to produce processing time and two ways to generate additional resource. There are 10 combinations of processing time and additional resource. No is defined as a combination of the a-th way of processing time and the b-th way of additional resource. b = 1 for No ≤ 5 and b = 2 for No > 5.

Zheng and Wang [7] proposed a two-stage adaptive fruit fly optimization algorithm (TAFOA) and Villa et al. [11] developed a multi-pass heuristic (MPH) for UPMSPR. TAFOA and MPH have promising advantages on solving UPMSPR and can be directly used to solve UPMSPR with learning effect, so they are chosen as comparative algorithms. Salehi Mir and Rezaeian [46] presented a hybrid particle swarm optimization and genetic algorithm (HPSOGA). HPSOGA can be directly applied to handle our UPMSPR after the decoding procedure of QSFLA is adopted, so we use it as comparative algorithm. TAFOA and HPSOGA have the same complexity N × n × max _ t.

We construct SFLA by deleting Q-learning algorithm from QSFLA and no population division to show the effect of Q-learning. In the search process of each memeplex, for optimization object x_b, global search is first performed, if the new solution cannot substitute for x_b as described in QSFLA, then multiple neighborhood search of x_b is executed.

4.2 Parameter settings

QSFLA has main parameters: N, s, R, β, γ, w₁ and stopping condition. We first tested stopping condition and found that QSFLA can converge well when 0.3n seconds CPU times reaches. We also found that each comparative algorithm also converges fully when 0.3n seconds CPU times is used, so stopping condition of comparative algorithms is set to 0.3n seconds CPU times.

Taguchi method [47] is used to decide the settings for other parameters. We select instance 150 × 20 × 7. The levels of each parameter are shown in Table 2. The orthogonal array L₂₇ (3⁶) is tested. QSFLA with each combination runs 10 times independently for the chosen instance.

Table 2
Parameters and their levels

Parameter Factor level

1 2 3

N 48 64 96

s 4 8 16

R 30 50 70

β R/ 4 R/ 3 R/ 2

γ 0.85 0.9 0.95

w ₁ 0.6 0.7 0.8

Parameter	Factor level
N	48	64	96
s	4	8	16
R	30	50	70
β	R/ 4	R/ 3	R/ 2
γ	0.85	0.9	0.95
w ₁	0.6	0.7	0.8

The results of MIN and S/N ratio are shown in Fig.2, in which S/N ratio is defined as -10 × log ₁₀ (MIN²) and MIN is the best solution found in 10 runs. It can be found from Fig. 2 that QSFLA with following combination N = 64, s = 8, R = 50, β = R/3, γ = 0.9 and w₁ = 0.7 can obtain better results than QSFLA with other combinations, so the above combination is adopted.

Fig. 2

The mean MIN and the mean S/N ratio of MIN

SFLA has following parameters: N = 64, s = 8 and R = 50.

Parameter settings of three comparative algorithms are directly selected from references [7 , 46] except that the stopping condition. We also test these settings for each comparative algorithm. The computational results show that these settings of each comparative algorithm are still effective and comparative algorithms with these settings can produce better results than MPH, HPSOGA and TAFOA with other settings.

4.3 Results and analyses

QSFLA is compared with SFLA, MPH, HPSOGA and TAFOA. Each algorithm randomly runs 10 times for each instance. The corresponding results of all algorithms are shown in Tables 3 –11, where AVG indicates average value of 10 elite solutions obtained in 10 runs and SD is standard deviation among 10 elite solutions in 10 runs. Fig. 3 describes box plot of all algorithms and Fig. 4 shows convergence curves of all algorithms.

Table 3
Computational results of five algorithms on metric MIN

Instance QSFLA SFLA TAFOA HPSOGA MPH Instance QSFLA SFLA TAFOA HPSOGA MPH

8×2×1 210.5 292.7 237.9 290.8 210.5 12×6×1 139.2 143.0 149.3 217.6 152.3

8×2×2 246.2 246.2 246.3 253.5 246.2 12×6×2 139.3 141.1 155.5 212.6 153.3

8×2×3 150.6 150.6 150.7 158.0 150.7 12×6×3 56.9 56.9 58.0 59.5 57.2

8×2×4 221.0 221.0 221.0 221.0 221.0 12×6×4 60.0 62.5 63.0 183.1 62.6

8×2×5 140.3 140.3 182.6 162.7 177.8 12×6×5 47.7 47.7 47.7 72.6 48.7

8×2×6 103.9 103.9 127.5 171.1 174.7 12×6×6 57.0 57.0 60.2 93.4 59.0

8×2×7 152.5 152.5 192.1 189.1 183.4 12×6×7 54.7 60.7 57.9 150.0 70.5

8×2×8 132.5 132.5 164.4 218.8 150.0 12×6×8 61.0 66.4 80.2 114.8 65.7

8×2×9 493.4 494.7 494.7 560.5 511.5 12×6×9 240.0 432.0 266.0 284.8 268.6

8×2×10 496.9 572.8 527.9 573.4 496.9 12×6×10 252.5 426.4 270.6 262.8 285.8

8×4×1 114.3 114.3 120.3 129.1 126.0 16×2×1 387.5 493.7 391.8 503.7 407.5

8×4×2 114.8 114.8 133.4 146.1 135.7 16×2×2 422.2 451.4 422.4 507.9 432.9

8×4×3 163.9 168.4 171.1 167.9 164.2 16×2×3 356.3 356.8 356.9 379.2 373.8

8×4×4 115.5 129.3 117.4 126.6 115.5 16×2×4 486.9 493.8 509.6 548.5 487.5

8×4×5 76.6 76.6 83.4 87.1 94.5 16×2×5 234.0 353.4 335.6 332.4 234.1

8×4×6 63.1 88.6 72.9 72.9 63.1 16×2×6 204.5 275.4 269.3 314.2 209.0

8×4×7 87.3 87.3 103.4 97.0 87.9 16×2×7 276.0 371.6 331.8 398.9 280.9

8×4×8 74.7 74.7 84.8 110.0 76.1 16×2×8 254.2 339.6 262.1 361.6 288.8

8×4×9 269.0 269.0 263.5 331.9 319.8 16×2×9 929.5 1058.6 937.3 983.9 979.9

8×4×10 265.3 265.3 266.4 265.3 265.3 16×2×10 935.3 1093.9 995.8 1166.0 1064.2

8×6×1 103.0 103.0 103.0 103.0 103.0 16×4×1 264.9 337.8 274.1 339.1 318.2

8×6×2 106.0 106.0 106.0 106.0 106.0 16×4×2 195.3 210.5 198.2 221.1 196.8

8×6×3 43.0 43.0 43.0 43.0 43.0 16×4×3 170.0 178.3 172.8 183.2 182.2

8×6×4 66.9 66.9 70.6 69.1 68.7 16×4×4 129.5 144.6 145.9 142.3 135.0

8×6×5 36.0 36.0 36.0 54.0 36.0 16×4×5 71.2 75.5 116.4 106.6 104.7

8×6×6 58.0 58.0 58.0 58.0 58.0 16×4×6 80.6 80.6 135.0 129.9 127.2

8×6×7 42.0 42.0 65.6 49.0 49.0 16×4×7 101.7 124.0 107.1 157.5 130.1

8×6×8 62.0 62.0 62.0 62.0 62.0 16×4×8 111.8 184.5 126.6 162.3 104.8

8×6×9 206.5 206.5 211.1 221.1 219.1 16×4×9 449.2 526.0 474.3 513.1 518.2

8×6×10 210.7 217.2 219.8 217.2 217.2 16×4×10 466.8 576.6 493.6 527.4 531.6

12×2×1 228.2 228.2 257.4 288.6 241.6 16×6×1 131.8 154.4 147.7 159.7 140.1

12×2×2 401.9 478.5 428.0 443.5 402.1 16×6×2 141.9 163.3 159.4 165.8 147.5

12×2×3 296.0 296.0 297.2 325.5 297.3 16×6×3 111.4 113.1 120.6 124.2 117.8

12×2×4 247.8 247.8 253.0 275.3 257.0 16×6×4 111.1 111.1 115.8 117.7 111.1

12×2×5 147.2 147.2 153.9 147.2 147.2 16×6×5 61.9 72.2 71.5 128.9 69.7

12×2×6 218.1 251.2 219.1 255.2 253.2 16×6×6 58.5 93.1 64.9 131.4 86.9

12×2×7 177.9 177.9 192.4 177.9 177.9 16×6×7 80.2 90.0 90.3 100.4 88.2

12×2×8 247.5 248.9 279.3 261.5 286.2 16×6×8 79.7 106.2 85.1 136.0 106.8

12×2×9 687.2 687.2 691.2 712.9 687.7 16×6×9 336.6 351.8 355.1 360.2 343.4

12×2×10 758.4 801.1 765.6 838.1 797.7 16×6×10 339.5 406.2 378.8 395.4 364.4

12×4×1 209.6 252.2 215.5 231.8 236.5 20×2×1 449.7 547.9 502.2 500.4 453.2

12×4×2 185.5 209.0 195.2 204.6 185.5 20×2×2 463.4 496.5 465.7 539.1 529.7

12×4×3 206.5 235.6 209.5 253.1 247.5 20×2×3 548.5 619.1 602.5 722.3 561.6

12×4×4 211.4 212.3 219.1 217.7 218.2 20×2×4 471.6 569.1 472.7 540.6 485.3

12×4×5 85.3 85.3 106.4 164.6 135.0 20×2×5 309.9 461.6 316.3 456.0 454.4

12×4×6 68.0 94.9 68.4 162.5 107.9 20×2×6 267.1 358.2 303.1 380.7 271.4

12×4×7 103.1 103.1 101.5 179.3 103.1 20×2×7 358.2 435.6 400.4 523.5 360.9

12×4×8 88.8 99.0 116.5 162.2 114.6 20×2×8 324.9 425.8 361.6 406.7 335.3

12×4×9 379.2 391.5 401.5 516.0 412.2 20×2×9 1179.0 1337.1 1285.3 1317.3 1334.1

12×4×10 362.9 436.2 364.6 435.8 379.3 20×2×10 1156.1 1180.8 1175.6 1417.5 1364.3

Instance	QSFLA	SFLA	TAFOA	HPSOGA	MPH	Instance	QSFLA	SFLA	TAFOA	HPSOGA	MPH
8×2×1	210.5	292.7	237.9	290.8	210.5	12×6×1	139.2	143.0	149.3	217.6	152.3
8×2×2	246.2	246.2	246.3	253.5	246.2	12×6×2	139.3	141.1	155.5	212.6	153.3
8×2×3	150.6	150.6	150.7	158.0	150.7	12×6×3	56.9	56.9	58.0	59.5	57.2
8×2×4	221.0	221.0	221.0	221.0	221.0	12×6×4	60.0	62.5	63.0	183.1	62.6
8×2×5	140.3	140.3	182.6	162.7	177.8	12×6×5	47.7	47.7	47.7	72.6	48.7
8×2×6	103.9	103.9	127.5	171.1	174.7	12×6×6	57.0	57.0	60.2	93.4	59.0
8×2×7	152.5	152.5	192.1	189.1	183.4	12×6×7	54.7	60.7	57.9	150.0	70.5
8×2×8	132.5	132.5	164.4	218.8	150.0	12×6×8	61.0	66.4	80.2	114.8	65.7
8×2×9	493.4	494.7	494.7	560.5	511.5	12×6×9	240.0	432.0	266.0	284.8	268.6
8×2×10	496.9	572.8	527.9	573.4	496.9	12×6×10	252.5	426.4	270.6	262.8	285.8
8×4×1	114.3	114.3	120.3	129.1	126.0	16×2×1	387.5	493.7	391.8	503.7	407.5
8×4×2	114.8	114.8	133.4	146.1	135.7	16×2×2	422.2	451.4	422.4	507.9	432.9
8×4×3	163.9	168.4	171.1	167.9	164.2	16×2×3	356.3	356.8	356.9	379.2	373.8
8×4×4	115.5	129.3	117.4	126.6	115.5	16×2×4	486.9	493.8	509.6	548.5	487.5
8×4×5	76.6	76.6	83.4	87.1	94.5	16×2×5	234.0	353.4	335.6	332.4	234.1
8×4×6	63.1	88.6	72.9	72.9	63.1	16×2×6	204.5	275.4	269.3	314.2	209.0
8×4×7	87.3	87.3	103.4	97.0	87.9	16×2×7	276.0	371.6	331.8	398.9	280.9
8×4×8	74.7	74.7	84.8	110.0	76.1	16×2×8	254.2	339.6	262.1	361.6	288.8
8×4×9	269.0	269.0	263.5	331.9	319.8	16×2×9	929.5	1058.6	937.3	983.9	979.9
8×4×10	265.3	265.3	266.4	265.3	265.3	16×2×10	935.3	1093.9	995.8	1166.0	1064.2
8×6×1	103.0	103.0	103.0	103.0	103.0	16×4×1	264.9	337.8	274.1	339.1	318.2
8×6×2	106.0	106.0	106.0	106.0	106.0	16×4×2	195.3	210.5	198.2	221.1	196.8
8×6×3	43.0	43.0	43.0	43.0	43.0	16×4×3	170.0	178.3	172.8	183.2	182.2
8×6×4	66.9	66.9	70.6	69.1	68.7	16×4×4	129.5	144.6	145.9	142.3	135.0
8×6×5	36.0	36.0	36.0	54.0	36.0	16×4×5	71.2	75.5	116.4	106.6	104.7
8×6×6	58.0	58.0	58.0	58.0	58.0	16×4×6	80.6	80.6	135.0	129.9	127.2
8×6×7	42.0	42.0	65.6	49.0	49.0	16×4×7	101.7	124.0	107.1	157.5	130.1
8×6×8	62.0	62.0	62.0	62.0	62.0	16×4×8	111.8	184.5	126.6	162.3	104.8
8×6×9	206.5	206.5	211.1	221.1	219.1	16×4×9	449.2	526.0	474.3	513.1	518.2
8×6×10	210.7	217.2	219.8	217.2	217.2	16×4×10	466.8	576.6	493.6	527.4	531.6
12×2×1	228.2	228.2	257.4	288.6	241.6	16×6×1	131.8	154.4	147.7	159.7	140.1
12×2×2	401.9	478.5	428.0	443.5	402.1	16×6×2	141.9	163.3	159.4	165.8	147.5
12×2×3	296.0	296.0	297.2	325.5	297.3	16×6×3	111.4	113.1	120.6	124.2	117.8
12×2×4	247.8	247.8	253.0	275.3	257.0	16×6×4	111.1	111.1	115.8	117.7	111.1
12×2×5	147.2	147.2	153.9	147.2	147.2	16×6×5	61.9	72.2	71.5	128.9	69.7
12×2×6	218.1	251.2	219.1	255.2	253.2	16×6×6	58.5	93.1	64.9	131.4	86.9
12×2×7	177.9	177.9	192.4	177.9	177.9	16×6×7	80.2	90.0	90.3	100.4	88.2
12×2×8	247.5	248.9	279.3	261.5	286.2	16×6×8	79.7	106.2	85.1	136.0	106.8
12×2×9	687.2	687.2	691.2	712.9	687.7	16×6×9	336.6	351.8	355.1	360.2	343.4
12×2×10	758.4	801.1	765.6	838.1	797.7	16×6×10	339.5	406.2	378.8	395.4	364.4
12×4×1	209.6	252.2	215.5	231.8	236.5	20×2×1	449.7	547.9	502.2	500.4	453.2
12×4×2	185.5	209.0	195.2	204.6	185.5	20×2×2	463.4	496.5	465.7	539.1	529.7
12×4×3	206.5	235.6	209.5	253.1	247.5	20×2×3	548.5	619.1	602.5	722.3	561.6
12×4×4	211.4	212.3	219.1	217.7	218.2	20×2×4	471.6	569.1	472.7	540.6	485.3
12×4×5	85.3	85.3	106.4	164.6	135.0	20×2×5	309.9	461.6	316.3	456.0	454.4
12×4×6	68.0	94.9	68.4	162.5	107.9	20×2×6	267.1	358.2	303.1	380.7	271.4
12×4×7	103.1	103.1	101.5	179.3	103.1	20×2×7	358.2	435.6	400.4	523.5	360.9
12×4×8	88.8	99.0	116.5	162.2	114.6	20×2×8	324.9	425.8	361.6	406.7	335.3
12×4×9	379.2	391.5	401.5	516.0	412.2	20×2×9	1179.0	1337.1	1285.3	1317.3	1334.1
12×4×10	362.9	436.2	364.6	435.8	379.3	20×2×10	1156.1	1180.8	1175.6	1417.5	1364.3

Table 4

Computational results of five algorithms on metric MIN

Instance	QSFLA	SFLA	TAFOA	HPSOGA	MPH	Instance	QSFLA	SFLA	TAFOA	HPSOGA	MPH
20×4×1	320.6	422.3	334.7	399.7	386.7	30×2×1	798.2	854.1	845.8	1012.6	876.1
20×4×2	263.3	290.3	276.6	290.3	287.8	30×2×2	643.2	668.5	656.1	713.0	663.4
20×4×3	144.8	160.7	158.5	151.7	154.0	30×2×3	268.7	268.9	283.5	275.7	279.4
20×4×4	134.3	142.8	139.0	148.8	145.9	30×2×4	687.2	703.8	690.3	707.4	752.9
20×4×5	97.1	153.8	126.3	192.9	110.0	30×2×5	497.9	525.0	517.4	565.7	543.5
20×4×6	102.1	159.6	102.6	134.7	125.8	30×2×6	511.7	550.3	534.4	556.5	537.1
20×4×7	133.8	198.0	147.1	258.9	198.5	30×2×7	567.1	598.2	601.1	610.2	841.5
20×4×8	132.2	184.1	146.0	167.2	147.3	30×2×8	589.0	632.7	617.9	642.7	630.4
20×4×9	561.6	668.4	652.3	585.4	591.8	30×2×9	1743.8	2218.7	1800.7	1836.6	2144.8
20×4×10	568.8	671.5	668.5	673.9	599.5	30×2×10	1812.5	1965.0	1850.8	2209.0	2063.7
20×6×1	197.0	209.2	210.1	239.3	207.9	30×4×1	354.2	380.0	375.5	410.1	416.1
20×6×2	185.8	197.7	178.2	198.1	194.3	30×4×2	326.6	370.2	348.5	363.4	316.7
20×6×3	163.2	167.3	202.0	177.5	171.7	30×4×3	256.4	269.2	278.3	284.2	272.1
20×6×4	53.2	66.0	63.7	67.7	59.2	30×4×4	274.9	309.4	268.0	309.1	293.4
20×6×5	69.6	146.8	84.7	116.0	83.8	30×4×5	137.3	210.9	161.2	225.6	168.9
20×6×6	53.0	104.8	68.9	111.4	74.2	30×4×6	111.0	264.5	165.6	269.0	140.2
20×6×7	95.1	136.1	110.5	170.8	109.3	30×4×7	189.5	214.5	224.8	337.9	283.0
20×6×8	77.6	133.6	100.9	139.4	93.1	30×4×8	157.5	227.7	213.5	245.6	228.2
20×6×9	410.2	510.2	442.2	482.5	443.5	30×4×9	824.8	892.7	867.0	1028.9	971.1
20×6×10	399.5	488.6	441.9	490.6	439.4	30×4×10	786.0	863.0	763.7	891.1	876.0
25×2×1	570.9	720.2	593.1	685.6	592.1	30×6×1	292.1	319.2	317.8	341.3	343.9
25×2×2	580.9	589.6	587.0	600.7	624.5	30×6×2	246.5	260.7	261.4	285.4	267.0
25×2×3	1006.0	1425.3	1083.3	1346.5	1103.9	30×6×3	186.9	204.9	202.2	217.5	203.4
25×2×4	207.9	238.1	210.8	257.1	213.0	30×6×4	235.6	244.4	249.3	248.0	234.2
25×2×5	445.2	659.6	470.6	714.9	539.2	30×6×5	70.0	155.5	99.0	208.7	114.9
25×2×6	345.3	483.8	362.1	410.5	489.2	30×6×6	75.2	180.9	128.1	154.6	132.5
25×2×7	503.7	561.9	518.0	781.3	512.3	30×6×7	108.7	148.1	151.7	229.8	164.7
25×2×8	418.7	427.2	429.5	508.1	485.9	30×6×8	114.8	198.0	172.0	262.7	176.1
25×2×9	1491.4	1628.5	1547.1	1972.2	1544.2	30×6×9	526.4	632.8	529.7	619.9	585.6
25×2×10	1422.2	1581.7	1467.9	1661.9	1448.5	30×6×10	564.6	682.6	580.9	707.8	665.0
25×4×1	303.3	430.1	369.7	363.8	352.9	50×10×1	266.8	306.4	296.6	339.8	289.4
25×4×2	362.2	398.6	389.5	374.3	378.3	50×10×2	260.2	287.6	281.1	311.5	287.8
25×4×3	247.9	264.8	260.1	379.7	272.4	50×10×3	251.8	288.8	275.1	284.9	276.6
25×4×4	126.5	151.5	139.1	156.8	143.3	50×10×4	228.0	248.1	235.7	235.2	237.3
25×4×5	113.3	270.4	135.6	148.9	133.3	50×10×5	82.7	172.5	84.3	261.3	101.1
25×4×6	147.4	274.4	253.5	250.7	203.3	50×10×6	101.2	174.6	145.6	234.5	190.0
25×4×7	151.2	301.1	185.1	274.4	268.6	50×10×7	115.4	214.6	130.3	269.9	220.5
25×4×8	183.3	234.3	203.9	292.6	261.1	50×10×8	141.2	207.5	167.5	270.4	201.1
25×4×9	670.0	787.1	731.7	766.4	721.6	50×10×9	572.3	789.8	583.4	805.2	698.3
25×4×10	720.3	835.0	813.9	846.3	843.8	50×10×10	592.9	752.7	635.7	784.8	706.3
25×6×1	210.6	241.3	221.3	260.3	246.8	50×20×1	191.0	222.6	213.5	249.8	222.6
25×6×2	194.0	208.0	215.0	237.3	216.9	50×20×2	149.8	177.7	163.5	202.3	170.6
25×6×3	144.0	155.7	159.7	150.9	154.2	50×20×3	130.4	140.0	134.2	187.4	146.6
25×6×4	80.9	95.2	94.6	103.5	106.6	50×20×4	129.4	137.8	118.8	114.0	131.7
25×6×5	67.5	100.7	111.4	153.2	102.1	50×20×5	33.1	115.3	34.6	164.3	50.9
25×6×6	69.3	107.2	90.0	147.0	103.2	50×20×6	36.9	107.5	50.7	140.5	114.0
25×6×7	96.4	227.5	173.8	240.0	169.9	50×20×7	63.9	136.5	68.4	177.6	66.2
25×6×8	99.2	177.3	130.4	150.7	137.7	50×20×8	54.4	128.3	69.5	150.6	146.7
25×6×9	484.7	522.7	512.7	564.6	546.5	50×20×9	351.2	416.7	374.3	479.4	365.2
25×6×10	496.4	567.4	536.0	641.6	601.5	50×20×10	340.4	403.8	382.8	427.7	477.8

Table 5

Computational results of five algorithms on metric MIN

Instance	QSFLA	SFLA	TAFOA	HPSOGA	MPH	Instance	QSFLA	SFLA	TAFOA	HPSOGA	MPH
50×30×1	122.0	144.5	133.9	194.8	142.8	250×20×1	746.4	835.2	725.8	860.0	945.1
50×30×2	115.2	143.8	140.1	208.6	143.4	250×20×2	728.7	884.2	863.4	868.6	743.3
50×30×3	92.5	131.4	100.0	183.6	97.8	250×20×3	663.4	821.9	931.1	1172.2	739.1
50×30×4	96.0	153.9	99.0	100.0	104.4	250×20×4	757.1	1153.6	1086.3	1253.3	864.8
50×30×5	36.1	169.7	46.0	150.4	89.6	250×20×5	612.0	805.8	723.1	732.2	625.4
50×30×6	40.1	89.7	49.3	163.7	88.6	250×20×6	553.6	710.2	662.5	811.6	758.0
50×30×7	52.3	99.7	67.9	179.9	94.4	250×20×7	662.8	994.8	757.5	1040.4	848.2
50×30×8	58.9	97.5	79.7	165.7	171.7	250×20×8	620.1	820.7	889.9	1335.9	738.8
50×30×9	286.5	469.5	290.1	312.3	290.1	250×20×9	1814.4	2541.0	2001.1	2184.0	1971.3
50×30×10	286.6	305.3	285.6	524.7	318.4	250×20×10	1772.1	2249.5	2068.8	2304.9	2065.8
150×10×1	822.1	901.2	882.7	1047.2	1000.5	250×30×1	592.8	784.3	648.5	801.7	614.6
150×10×2	721.9	775.4	730.6	869.8	730.7	250×30×2	561.3	642.6	581.2	721.8	745.7
150×10×3	832.1	859.4	845.6	924.6	850.2	250×30×3	386.1	741.3	550.0	621.2	632.8
150×10×4	568.6	820.6	746.0	814.1	863.5	250×30×4	404.2	873.0	651.0	1102.0	773.3
150×10×5	411.5	756.4	480.4	729.9	550.1	250×30×5	249.0	533.8	441.6	779.7	548.0
150×10×6	430.4	562.0	490.0	873.3	669.8	250×30×6	270.4	691.1	546.4	569.8	434.0
150×10×7	536.5	632.4	580.8	824.5	773.8	250×30×7	489.8	593.2	736.4	644.4	434.0
150×10×8	539.4	626.2	601.0	724.3	716.4	250×30×8	576.7	841.3	677.1	977.0	604.2
150×10×9	1721.1	1957.6	1813.7	2262.6	2008.1	250×30×9	975.5	2006.7	1361.5	1521.8	1531.2
150×10×10	1529.6	1951.1	1773.8	2131.5	1877.9	250×30×10	977.3	1972.0	1306.0	2028.8	1492.7
150×20×1	484.7	494.1	446.8	587.3	502.9	350×10×1	1923.2	2263.8	2031.1	2334.9	2139.3
150×20×2	424.9	446.9	440.1	523.2	553.0	350×10×2	1786.0	1980.5	1874.2	2257.2	1854.7
150×20×3	435.5	713.0	533.0	882.7	508.4	350×10×3	1539.5	2243.1	1673.0	2451.2	2072.7
150×20×4	442.3	533.7	447.0	662.9	448.3	350×10×4	1408.2	2334.5	1857.9	3051.6	1787.9
150×20×5	304.3	368.4	394.8	478.5	486.3	350×10×5	645.1	957.9	750.3	871.4	761.6
150×20×6	263.0	334.6	291.2	413.4	344.5	350×10×6	475.9	628.6	526.2	669.8	516.4
150×20×7	313.3	409.7	340.6	543.7	529.2	350×10×7	1561.5	1857.0	1569.6	2028.7	1605.3
150×20×8	297.8	380.0	327.3	652.3	464.5	350×10×8	1486.4	1711.7	1583.3	1723.7	1556.3
150×20×9	911.9	1143.0	1029.8	1571.3	1354.2	350×10×9	3283.9	5173.4	4447.2	5276.0	4752.1
150×20×10	830.5	1110.9	976.2	1267.6	1017.5	350×10×10	3374.1	4739.3	4300.0	4608.9	4337.1
150×30×1	331.2	347.8	334.5	482.9	470.8	350×20×1	1078.8	1305.3	1154.1	1341.6	1052.0
150×30×2	275.1	352.8	307.0	427.4	515.4	350×20×2	947.1	1156.1	1013.2	1083.2	1337.1
150×30×3	321.3	545.3	348.5	393.0	440.4	350×20×3	751.1	946.7	851.9	1152.2	906.0
150×30×4	383.5	514.3	424.9	523.5	471.3	350×20×4	1049.1	1275.1	1362.6	1600.3	1253.7
150×30×5	220.5	398.6	256.5	656.4	355.0	350×20×5	310.7	726.8	558.9	856.8	665.5
150×30×6	180.9	252.3	262.2	423.4	374.3	350×20×6	217.2	478.4	328.4	513.9	417.3
150×30×7	231.1	290.5	290.9	431.3	457.9	350×20×7	643.6	1024.4	886.3	1132.5	991.6
150×30×8	208.2	273.1	271.6	417.5	302.3	350×20×8	752.0	965.2	1042.8	1026.4	836.0
150×30×9	719.0	844.1	746.6	1232.6	1124.4	350×20×9	1778.3	2678.4	2145.5	3044.2	2445.2
150×30×10	639.1	940.7	731.6	1142.4	803.7	350×20×10	1843.2	2739.2	2671.2	2846.7	2344.8
250×10×1	1282.6	1521.3	1373.1	1615.2	1400.2	350×30×1	782.4	1266.5	866.7	1038.7	899.4
250×10×2	1171.1	1263.1	1248.3	1420.5	1561.5	350×30×2	675.8	914.6	780.1	861.6	834.0
250×10×3	1034.5	1443.3	1279.9	1364.5	1376.8	350×30×3	804.3	1081.7	753.6	1053.4	948.1
250×10×4	1061.5	1330.1	1224.3	1461.0	1313.9	350×30×4	941.7	1216.2	958.9	1158.5	980.4
250×10×5	866.1	1432.8	891.8	1224.3	1146.3	350×30×5	262.1	496.8	427.3	499.6	376.3
250×10×6	900.3	1281.1	956.3	1139.3	1015.5	350×30×6	163.9	281.7	292.4	360.5	256.8
250×10×7	1032.6	1417.4	1121.9	1363.3	1164.1	350×30×7	641.4	866.7	849.6	782.2	763.7
250×10×8	959.1	1467.3	1086.8	1460.0	1254.6	350×30×8	365.4	550.7	495.0	539.6	598.0
250×10×9	2267.5	3571.5	3048.0	3715.3	3247.7	350×30×9	1772.4	2517.7	1826.5	2249.3	1994.1
250×10×10	3074.5	3834.2	3172.8	4076.4	3428.9	350×30×10	1319.5	1872.8	1757.1	2005.6	1352.2

Table 6

Computational results of five algorithms on metric AVG

Instance	QSFLA	SFLA	TAFOA	HPSOGA	MPH	Instance	QSFLA	SFLA	TAFOA	HPSOGA	MPH
8×2×1	211.6	298.5	239.8	300.9	216.2	12×6×1	142.1	145.5	158.1	229.0	159.4
8×2×2	246.2	246.2	248.2	261.5	246.2	12×6×2	141.9	147.8	164.0	217.0	161.7
8×2×3	150.6	150.6	150.7	170.1	156.2	12×6×3	59.6	64.8	61.3	63.6	60.5
8×2×4	221.0	221.0	224.0	227.7	223.5	12×6×4	61.0	64.5	65.9	184.2	65.9
8×2×5	140.3	141.1	182.6	175.8	179.5	12×6×5	47.7	48.9	57.2	84.3	58.7
8×2×6	104.7	109.9	139.6	204.8	177.0	12×6×6	57.0	57.3	69.3	103.2	74.1
8×2×7	157.8	158.1	192.1	202.0	184.2	12×6×7	56.2	64.9	72.7	168.5	72.7
8×2×8	133.4	138.0	166.0	232.8	151.5	12×6×8	61.3	73.3	92.7	123.5	76.2
8×2×9	494.1	494.7	494.7	569.1	515.2	12×6×9	241.0	434.8	271.2	288.7	274.0
8×2×10	499.3	574.1	530.3	590.8	503.8	12×6×10	255.7	437.3	276.7	284.9	302.9
8×4×1	114.8	117.3	132.3	131.1	126.0	16×2×1	394.8	498.3	397.3	516.5	421.6
8×4×2	114.8	117.3	148.1	148.0	144.9	16×2×2	424.2	455.1	428.5	512.1	438.4
8×4×3	164.5	168.7	174.6	169.4	167.3	16×2×3	356.3	361.5	363.6	386.7	381.6
8×4×4	115.5	140.7	119.0	139.1	116.3	16×2×4	487.6	501.0	516.9	566.0	491.3
8×4×5	76.6	78.3	99.4	93.4	94.5	16×2×5	240.1	364.7	348.3	344.0	242.4
8×4×6	63.1	108.2	75.2	74.3	66.2	16×2×6	214.8	280.4	274.8	352.4	210.7
8×4×7	87.3	88.3	109.7	97.0	96.1	16×2×7	279.9	382.7	340.0	422.4	288.6
8×4×8	74.8	79.7	84.8	116.4	85.2	16×2×8	260.9	358.8	268.9	368.1	298.8
8×4×9	269.0	274.6	265.2	336.3	338.3	16×2×9	932.9	1063.2	954.0	991.7	984.8
8×4×10	265.3	266.5	270.9	265.7	265.3	16×2×10	946.9	1100.4	1000.4	1170.3	1069.7
8×6×1	103.0	103.0	108.2	104.8	104.2	16×4×1	273.1	347.9	287.8	347.0	335.6
8×6×2	106.0	106.0	106.2	106.5	106.3	16×4×2	198.1	222.8	205.4	231.5	205.4
8×6×3	43.3	44.8	45.3	44.2	44.6	16×4×3	170.5	188.0	175.4	186.6	185.0
8×6×4	66.9	69.4	82.6	69.1	69.0	16×4×4	130.6	152.2	153.9	153.3	138.0
8×6×5	36.0	36.0	40.0	54.0	36.0	16×4×5	71.9	82.1	135.3	112.1	108.1
8×6×6	58.0	58.0	70.3	60.7	61.3	16×4×6	85.7	96.2	152.8	144.4	135.1
8×6×7	42.0	44.4	65.6	51.5	52.0	16×4×7	102.7	149.6	114.4	168.2	136.7
8×6×8	62.0	62.0	71.4	64.8	72.3	16×4×8	112.0	190.8	143.2	180.1	111.4
8×6×9	206.5	207.0	241.9	221.1	220.9	16×4×9	449.2	534.0	488.1	523.3	524.8
8×6×10	212.7	217.5	225.2	217.6	217.7	16×4×10	468.6	579.4	508.4	556.7	540.0
12×2×1	228.6	232.8	264.8	295.7	260.3	16×6×1	139.1	165.2	162.9	168.7	150.2
12×2×2	408.4	481.2	431.8	452.3	404.8	16×6×2	143.7	170.0	169.3	173.2	151.6
12×2×3	296.0	296.6	298.3	329.6	298.4	16×6×3	111.4	119.7	126.7	127.6	124.6
12×2×4	247.8	248.5	263.6	286.5	275.3	16×6×4	111.7	114.5	120.6	120.3	117.2
12×2×5	147.2	148.9	157.6	147.2	149.1	16×6×5	64.9	81.5	87.7	136.5	87.1
12×2×6	220.6	256.8	224.3	267.7	256.3	16×6×6	63.3	106.5	76.3	140.1	92.5
12×2×7	177.9	177.9	196.7	177.9	177.9	16×6×7	82.3	100.1	109.8	102.9	93.4
12×2×8	249.7	255.6	282.7	270.0	291.3	16×6×8	84.3	132.3	97.6	142.8	124.5
12×2×9	687.2	687.2	701.5	741.0	708.9	16×6×9	338.9	362.4	364.3	363.4	356.1
12×2×10	768.6	805.5	783.4	845.5	804.8	16×6×10	345.5	407.3	390.4	411.7	375.5
12×4×1	215.3	264.2	222.4	246.3	243.9	20×2×1	455.0	551.6	517.4	503.3	463.6
12×4×2	187.9	216.2	207.4	209.4	191.0	20×2×2	467.4	510.8	477.8	544.2	538.3
12×4×3	212.4	256.9	216.6	255.8	253.4	20×2×3	560.3	625.6	610.7	737.2	574.2
12×4×4	211.4	216.4	233.6	218.4	219.9	20×2×4	472.6	574.3	480.5	550.0	490.5
12×4×5	86.1	88.6	111.1	172.1	163.8	20×2×5	317.1	473.1	328.1	468.3	466.3
12×4×6	72.1	103.8	80.2	163.9	117.7	20×2×6	273.4	369.3	316.7	394.7	280.7
12×4×7	103.4	108.3	119.1	190.6	106.8	20×2×7	365.2	444.5	415.5	536.2	381.0
12×4×8	91.6	104.3	123.7	170.0	141.0	20×2×8	332.4	434.0	378.1	411.6	341.0
12×4×9	379.2	402.1	409.0	526.8	418.1	20×2×9	1185.8	1340.2	1298.0	1323.5	1339.7
12×4×10	363.5	441.4	392.1	442.7	385.9	20×2×10	1160.7	1196.7	1187.3	1423.0	1379.6

Table 7

Computational results of five algorithms on metric AVG

Instance	QSFLA	SFLA	TAFOA	HPSOGA	MPH	Instance	QSFLA	SFLA	TAFOA	HPSOGA	MPH
20×4×1	330.7	429.1	345.7	421.0	388.1	30×2×1	813.3	893.6	858.6	1020.1	879.5
20×4×2	266.6	309.1	280.1	299.3	310.9	30×2×2	652.6	681.6	664.2	720.2	680.7
20×4×3	145.7	162.8	162.8	155.8	157.9	30×2×3	269.7	269.9	293.9	280.8	283.3
20×4×4	141.3	150.4	143.3	151.5	154.2	30×2×4	689.3	714.0	697.9	715.5	757.7
20×4×5	105.8	159.2	135.4	214.2	120.4	30×2×5	510.1	543.4	525.5	574.2	566.9
20×4×6	102.5	186.5	123.6	142.8	138.0	30×2×6	522.4	565.5	543.4	568.5	544.5
20×4×7	137.5	207.3	156.5	274.6	211.6	30×2×7	579.5	604.3	611.0	633.6	855.7
20×4×8	139.2	203.7	161.8	177.1	156.2	30×2×8	599.5	640.2	622.8	649.3	638.2
20×4×9	567.5	676.3	665.2	613.4	601.7	30×2×9	1757.0	2230.6	1807.5	1855.7	2151.1
20×4×10	570.7	674.3	671.1	674.9	608.6	30×2×10	1821.0	1972.5	1863.1	2212.8	2069.1
20×6×1	201.3	216.9	240.5	259.2	217.4	30×4×1	362.1	390.3	388.9	430.9	439.1
20×6×2	189.4	202.5	183.1	204.0	202.8	30×4×2	331.9	377.6	353.5	370.9	329.0
20×6×3	164.4	174.2	217.1	183.0	175.3	30×4×3	258.1	273.2	300.0	286.9	277.2
20×6×4	57.9	72.6	67.7	71.9	67.7	30×4×4	277.7	319.6	276.5	328.8	299.4
20×6×5	73.6	154.2	101.6	126.2	94.7	30×4×5	142.1	221.6	186.1	245.0	184.9
20×6×6	55.9	110.7	80.2	114.4	80.7	30×4×6	113.8	270.9	174.2	274.5	161.2
20×6×7	98.5	164.8	121.3	183.8	125.8	30×4×7	192.1	233.3	230.0	342.4	289.1
20×6×8	86.1	142.6	111.0	160.1	108.7	30×4×8	165.0	230.1	225.3	250.6	236.2
20×6×9	415.2	515.4	451.4	492.6	457.9	30×4×9	827.3	898.9	879.0	1039.8	976.4
20×6×10	410.1	498.8	448.6	494.9	446.6	30×4×10	794.9	878.7	778.4	894.8	883.4
25×2×1	582.2	740.0	600.7	693.3	601.7	30×6×1	299.0	335.2	327.8	359.2	368.7
25×2×2	584.6	596.2	593.7	608.9	649.2	30×6×2	248.7	271.8	281.7	288.2	284.9
25×2×3	1027.5	1436.4	1094.8	1372.3	1112.1	30×6×3	198.9	212.1	209.7	222.1	211.7
25×2×4	209.8	252.8	215.3	262.9	218.7	30×6×4	241.6	254.9	264.5	268.0	249.0
25×2×5	456.5	676.0	482.2	721.4	545.4	30×6×5	73.5	163.9	116.1	212.9	130.1
25×2×6	353.7	492.2	371.6	414.3	497.9	30×6×6	86.2	205.5	147.6	171.0	143.3
25×2×7	511.6	583.6	529.3	786.8	525.8	30×6×7	113.6	156.7	171.3	234.9	169.8
25×2×8	424.9	443.1	439.3	545.5	491.5	30×6×8	122.7	218.3	183.2	265.1	183.0
25×2×9	1505.2	1632.6	1577.1	1981.1	1552.6	30×6×9	537.7	639.9	535.8	622.1	592.5
25×2×10	1428.1	1588.5	1472.8	1668.9	1463.7	30×6×10	573.0	685.2	589.2	715.0	672.9
25×4×1	310.6	440.5	391.3	376.1	363.6	50×10×1	286.8	320.3	308.0	361.9	306.3
25×4×2	369.1	405.5	398.4	383.2	389.9	50×10×2	265.3	295.3	290.0	313.3	293.8
25×4×3	250.8	269.0	278.6	384.4	285.8	50×10×3	268.8	294.5	291.9	294.2	288.5
25×4×4	128.2	162.0	144.4	164.3	145.1	50×10×4	254.4	255.1	243.2	243.6	243.0
25×4×5	117.1	280.4	150.8	166.3	147.9	50×10×5	89.0	191.6	102.9	283.5	108.7
25×4×6	152.0	291.6	274.5	260.8	214.7	50×10×6	112.4	190.7	166.0	240.0	194.9
25×4×7	157.4	304.9	192.6	287.8	272.9	50×10×7	125.0	228.9	136.3	273.7	226.2
25×4×8	193.0	238.6	217.3	313.0	264.5	50×10×8	151.7	226.2	184.5	273.0	207.0
25×4×9	674.2	793.4	738.6	773.1	728.3	50×10×9	592.5	797.2	599.2	807.8	709.0
25×4×10	731.8	849.3	819.4	861.8	845.6	50×10×10	617.4	757.2	644.2	795.2	710.5
25×6×1	216.9	252.9	230.7	266.0	253.9	50×20×1	199.6	230.0	222.5	262.2	228.8
25×6×2	198.1	211.9	227.7	244.6	229.8	50×20×2	159.2	187.4	178.2	216.9	180.0
25×6×3	145.0	160.0	166.0	156.3	159.8	50×20×3	141.2	150.8	139.0	215.4	149.9
25×6×4	87.0	101.6	101.2	112.1	113.4	50×20×4	141.6	144.6	136.1	122.0	149.3
25×6×5	73.6	112.1	114.5	167.3	113.8	50×20×5	42.5	126.4	46.2	175.4	55.4
25×6×6	71.6	117.4	103.5	163.4	111.7	50×20×6	53.4	119.0	54.5	152.3	121.0
25×6×7	101.4	239.5	199.7	244.1	177.2	50×20×7	73.5	145.6	77.5	182.8	73.3
25×6×8	107.0	184.3	145.7	162.6	150.0	50×20×8	58.3	140.5	76.3	162.7	163.4
25×6×9	489.3	541.3	520.1	567.3	560.8	50×20×9	373.7	438.2	382.2	484.5	378.7
25×6×10	501.3	576.9	560.1	646.0	606.1	50×20×10	345.5	434.1	386.1	456.2	483.9

Table 8

Computational results of five algorithms on metric AVG

Instance	QSFLA	SFLA	TAFOA	HPSOGA	MPH	Instance	QSFLA	SFLA	TAFOA	HPSOGA	MPH
50×30×1	125.7	150.3	145.0	211.1	148.6	250×20×1	755.0	841.0	739.5	863.5	952.8
50×30×2	121.1	148.6	146.8	222.9	150.2	250×20×2	735.7	888.6	867.6	874.7	752.9
50×30×3	97.6	136.7	101.4	186.0	105.1	250×20×3	689.3	826.7	940.9	1175.5	751.7
50×30×4	106.1	157.8	103.4	111.1	113.8	250×20×4	763.3	1157.8	1088.1	1270.0	867.7
50×30×5	43.1	185.3	48.8	175.0	96.5	250×20×5	615.8	807.3	731.6	741.4	635.4
50×30×6	45.0	94.6	52.9	176.0	93.5	250×20×6	562.7	715.9	671.0	815.7	760.1
50×30×7	61.0	108.1	73.7	188.3	108.1	250×20×7	665.4	1003.5	762.1	1048.0	852.8
50×30×8	64.2	106.8	84.4	186.3	187.4	250×20×8	624.8	821.7	905.3	1349.9	747.5
50×30×9	293.3	479.8	290.4	328.2	290.3	250×20×9	1823.1	2544.3	2004.1	2190.9	1978.5
50×30×10	294.9	319.2	288.1	531.7	333.9	250×20×10	1779.7	2253.9	2074.0	2309.5	2072.7
150×10×1	829.9	918.5	901.9	1055.7	1004.1	250×30×1	597.2	790.4	651.3	808.8	620.4
150×10×2	737.7	788.8	746.0	875.2	754.4	250×30×2	565.2	649.8	591.4	745.3	757.7
150×10×3	857.3	866.3	848.4	928.5	868.1	250×30×3	389.0	744.8	554.3	634.5	645.3
150×10×4	573.2	828.9	750.9	819.2	871.3	250×30×4	409.1	874.7	658.3	1108.4	784.1
150×10×5	417.9	760.6	488.8	737.8	559.0	250×30×5	252.8	541.8	445.0	788.3	554.5
150×10×6	436.4	565.2	515.1	883.8	673.6	250×30×6	280.3	704.0	551.2	580.8	438.0
150×10×7	542.2	644.0	589.0	836.6	789.9	250×30×7	493.4	597.2	745.2	676.0	439.7
150×10×8	543.6	653.1	615.6	737.9	725.6	250×30×8	581.4	846.3	680.2	996.6	612.6
150×10×9	1727.0	1974.0	1818.4	2266.7	2016.4	250×30×9	978.2	2040.1	1375.3	1532.6	1538.4
150×10×10	1534.5	1964.4	1779.8	2137.3	1884.8	250×30×10	982.6	1978.8	1312.3	2035.9	1497.0
150×20×1	495.0	507.3	455.5	591.2	507.5	350×10×1	1929.7	2275.8	2052.2	2340.9	2144.7
150×20×2	426.9	470.0	441.8	544.0	561.5	350×10×2	1819.3	1985.2	1882.6	2264.8	1861.6
150×20×3	441.9	717.5	537.4	890.3	513.5	350×10×3	1546.2	2254.2	1675.6	2453.5	2080.6
150×20×4	447.8	542.5	467.0	665.9	472.4	350×10×4	1416.6	2350.2	1866.5	3062.3	1790.6
150×20×5	308.6	381.6	396.9	481.7	493.8	350×10×5	660.3	963.0	760.7	878.7	769.9
150×20×6	267.9	361.2	295.6	427.7	354.8	350×10×6	478.1	638.5	533.7	677.9	540.0
150×20×7	327.3	419.3	345.7	547.1	534.2	350×10×7	1569.0	1863.2	1581.8	2034.8	1611.3
150×20×8	307.2	398.1	339.0	662.4	471.6	350×10×8	1491.1	1717.5	1594.8	1730.6	1561.2
150×20×9	918.4	1154.6	1038.1	1582.6	1363.8	350×10×9	3298.8	5183.7	4458.1	5286.4	4755.3
150×20×10	837.7	1116.1	979.9	1271.7	1020.3	350×10×10	3389.0	4748.5	4310.2	4614.1	4342.2
150×30×1	337.9	364.0	345.8	487.2	485.2	350×20×1	1084.5	1310.9	1158.2	1346.7	1055.7
150×30×2	285.3	357.3	322.8	437.3	524.8	350×20×2	959.8	1167.3	1022.0	1089.2	1346.9
150×30×3	324.5	549.5	353.9	402.5	448.6	350×20×3	758.7	954.5	855.8	1165.6	912.2
150×30×4	386.7	521.7	429.8	554.5	480.5	350×20×4	1058.1	1282.8	1374.1	1609.9	1258.9
150×30×5	222.8	401.0	273.8	663.6	359.7	350×20×5	317.0	737.9	561.4	859.3	678.0
150×30×6	186.8	263.5	267.0	426.5	388.2	350×20×6	223.3	483.1	334.5	518.6	423.3
150×30×7	239.4	310.4	293.1	436.6	469.2	350×20×7	653.9	1031.7	893.9	1137.9	994.2
150×30×8	216.8	285.4	288.6	422.1	310.9	350×20×8	757.4	971.8	1047.0	1031.1	850.1
150×30×9	722.7	864.9	754.5	1239.6	1132.6	350×20×9	1782.1	2685.4	2158.1	3054.3	2452.8
150×30×10	644.0	948.4	739.1	1146.5	826.0	350×20×10	1852.9	2744.2	2681.9	2859.7	2352.5
250×10×1	1288.9	1552.1	1397.5	1624.8	1406.5	350×30×1	790.6	1271.7	870.3	1048.9	908.4
250×10×2	1178.6	1267.9	1252.2	1427.2	1569.3	350×30×2	683.4	919.6	792.2	870.2	839.4
250×10×3	1037.0	1449.2	1285.7	1371.9	1387.1	350×30×3	811.6	1086.3	760.3	1062.9	954.8
250×10×4	1070.1	1337.4	1230.4	1466.5	1314.8	350×30×4	948.6	1223.9	967.9	1167.7	986.2
250×10×5	880.9	1436.4	897.8	1227.6	1157.9	350×30×5	274.5	507.7	430.8	508.3	383.2
250×10×6	904.2	1289.2	970.4	1147.1	1019.5	350×30×6	170.1	288.5	300.7	366.1	266.1
250×10×7	1039.3	1428.8	1129.4	1371.6	1177.5	350×30×7	651.6	868.6	856.7	787.8	771.1
250×10×8	968.0	1473.9	1094.0	1468.5	1262.7	350×30×8	373.8	559.5	523.8	543.4	616.8
250×10×9	2272.8	3582.0	3053.1	3724.2	3252.5	350×30×9	1779.3	2522.0	1835.4	2257.3	2001.2
250×10×10	3077.7	3840.7	3182.1	4082.6	3438.1	350×30×10	1354.0	1885.3	1768.6	2010.4	1357.1

Table 9

Computational results of five algorithms on metric SD

Instance	QSFLA	SFLA	TAFOA	HPSOGA	MPH	Instance	QSFLA	SFLA	TAFOA	HPSOGA	MPH
8×2×1	1.5	4.8	2.7	6.5	4.6	12×6×1	2.3	2.5	5.2	5.7	4.8
8×2×2	0.0	0.0	1.5	3.0	0.0	12×6×2	2.8	4.1	5.0	3.9	5.8
8×2×3	0.0	0.0	0.0	4.4	6.5	12×6×3	2.4	3.1	1.6	1.5	2.0
8×2×4	0.0	0.0	1.6	3.0	3.6	12×6×4	1.3	1.0	1.7	1.1	3.1
8×2×5	0.0	1.3	0.0	4.3	1.2	12×6×5	0.0	0.9	7.1	7.6	7.0
8×2×6	1.5	6.4	4.8	11.4	2.0	12×6×6	0.0	0.9	7.3	6.0	10.5
8×2×7	4.8	6.5	0.1	6.8	1.1	12×6×7	1.3	5.6	6.1	10.5	2.5
8×2×8	2.3	3.3	1.3	7.4	1.2	12×6×8	0.9	3.6	10.2	9.1	7.2
8×2×9	0.9	0.0	0.0	5.3	2.1	12×6×9	2.3	3.3	4.5	4.5	6.5
8×2×10	3.0	1.4	2.4	13.4	10.2	12×6×10	3.0	7.3	6.5	10.4	11.6
8×4×1	1.4	3.1	8.6	2.7	0.0	16×2×1	6.7	3.2	6.2	8.4	8.8
8×4×2	0.0	2.5	7.0	0.7	4.2	16×2×2	2.0	3.7	5.0	4.8	3.2
8×4×3	1.3	0.6	2.9	1.0	1.4	16×2×3	0.1	3.8	4.7	8.7	7.8
8×4×4	0.0	4.0	2.0	4.3	0.4	16×2×4	0.4	5.7	6.0	11.5	4.5
8×4×5	0.0	2.8	5.6	2.4	0.0	16×2×5	4.0	7.7	11.0	9.6	6.9
8×4×6	0.0	8.0	2.6	1.2	4.4	16×2×6	4.1	3.0	4.7	13.3	1.6
8×4×7	0.0	1.4	6.3	0.0	2.7	16×2×7	2.4	6.3	8.1	11.6	7.1
8×4×8	0.2	4.8	0.0	4.0	4.1	16×2×8	4.6	12.3	5.0	4.5	4.7
8×4×9	0.0	6.6	2.3	4.4	9.1	16×2×9	2.8	4.2	8.5	6.4	2.8
8×4×10	0.0	0.9	3.7	0.6	0.0	16×2×10	13.7	5.7	3.3	4.6	3.0
8×6×1	0.0	0.0	4.1	2.7	2.5	16×4×1	4.9	4.9	8.9	3.0	11.7
8×6×2	0.0	0.0	0.7	1.0	0.7	16×4×2	1.7	8.5	3.4	7.1	3.7
8×6×3	0.9	1.8	1.1	1.9	2.1	16×4×3	0.9	5.0	1.3	3.0	2.2
8×6×4	0.0	2.0	7.9	0.0	0.1	16×4×4	1.3	3.7	4.9	5.5	1.8
8×6×5	0.0	0.0	4.0	0.0	0.0	16×4×5	1.4	3.1	10.1	5.0	2.7
8×6×6	0.0	0.0	4.9	0.9	2.1	16×4×6	3.9	8.5	11.2	8.6	5.7
8×6×7	0.0	3.5	0.0	1.7	1.6	16×4×7	1.3	15.9	4.4	8.4	4.2
8×6×8	0.0	0.0	8.4	3.3	3.9	16×4×8	0.6	6.2	9.7	8.6	5.2
8×6×9	0.0	0.9	10.3	0.0	0.6	16×4×9	0.0	7.8	10.7	7.5	4.0
8×6×10	3.0	0.3	6.4	0.3	0.3	16×4×10	4.2	3.3	9.1	16.8	5.5
12×2×1	0.7	2.7	12.4	4.8	12.6	16×6×1	5.4	6.2	8.0	5.4	4.1
12×2×2	4.2	3.3	2.8	4.3	2.8	16×6×2	1.5	6.1	6.9	4.6	2.7
12×2×3	0.0	0.9	0.4	3.7	0.7	16×6×3	0.0	3.7	3.8	1.4	5.2
12×2×4	0.0	1.3	7.6	12.4	7.4	16×6×4	1.1	1.6	3.0	2.7	3.0
12×2×5	0.0	1.5	3.4	0.0	2.0	16×6×5	2.8	4.7	8.6	4.4	9.7
12×2×6	2.3	2.5	5.8	7.8	3.3	16×6×6	3.8	7.8	6.4	4.9	4.9
12×2×7	0.0	0.0	3.5	0.0	0.0	16×6×7	1.6	5.2	10.0	2.2	3.8
12×2×8	2.4	5.5	2.1	3.1	3.1	16×6×8	3.7	10.3	6.4	6.4	8.0
12×2×9	0.0	0.0	8.4	13.8	10.6	16×6×9	1.0	7.7	7.5	3.5	9.5
12×2×10	3.4	4.3	8.7	7.2	4.2	16×6×10	4.5	1.1	9.7	7.4	8.0
12×4×1	3.3	8.5	4.0	9.4	3.4	20×2×1	3.7	3.6	8.6	3.3	4.2
12×4×2	1.9	5.0	7.5	3.6	4.1	20×2×2	2.8	7.8	5.7	3.2	5.2
12×4×3	2.9	13.6	4.5	1.5	2.4	20×2×3	6.3	4.6	5.0	11.0	9.6
12×4×4	0.0	2.0	9.4	0.5	4.6	20×2×4	0.8	5.0	5.4	6.3	3.5
12×4×5	1.2	2.6	4.1	6.2	12.2	20×2×5	4.6	8.9	6.6	9.9	7.8
12×4×6	5.5	8.0	6.5	1.1	5.9	20×2×6	3.5	6.5	11.0	9.7	8.3
12×4×7	0.5	5.0	13.4	5.0	3.8	20×2×7	5.6	4.6	8.9	8.7	9.4
12×4×8	4.3	4.2	6.7	3.3	12.1	20×2×8	4.7	7.3	12.3	3.9	4.5
12×4×9	0.0	6.9	6.8	6.4	7.3	20×2×9	2.9	3.2	9.3	3.5	4.6
12×4×10	0.6	8.2	16.4	5.1	4.6	20×2×10	4.6	11.9	8.8	5.6	9.7

Table 10

Computational results of five algorithms on metric SD

Instance	QSFLA	SFLA	TAFOA	HPSOGA	MPH	Instance	QSFLA	SFLA	TAFOA	HPSOGA	MPH
20×4×1	5.9	3.8	8.9	9.9	1.2	30×2×1	10.3	15.3	7.8	6.3	4.3
20×4×2	1.7	7.7	3.1	6.9	11.2	30×2×2	4.5	6.7	7.0	7.1	6.5
20×4×3	0.9	1.5	2.7	3.7	2.8	30×2×3	2.6	0.7	5.0	3.4	2.3
20×4×4	6.4	5.6	2.3	1.1	4.7	30×2×4	1.5	6.5	6.6	5.0	5.5
20×4×5	5.3	6.2	6.7	11.8	6.6	30×2×5	5.9	9.6	7.5	5.5	8.5
20×4×6	0.5	14.1	12.3	4.6	8.6	30×2×6	5.4	12.5	6.2	8.2	3.8
20×4×7	2.5	6.2	7.5	11.7	7.0	30×2×7	6.3	6.6	5.3	10.6	10.2
20×4×8	3.9	9.1	6.8	9.3	4.5	30×2×8	6.5	5.2	4.6	5.8	5.8
20×4×9	6.3	6.1	8.6	12.3	9.9	30×2×9	8.2	7.9	6.5	10.7	5.9
20×4×10	1.2	2.4	4.9	0.7	5.7	30×2×10	6.2	4.1	7.8	3.9	5.0
20×6×1	2.6	4.5	12.9	7.5	4.9	30×4×1	4.8	8.0	8.6	10.0	12.5
20×6×2	2.0	2.9	3.2	4.9	4.4	30×4×2	3.0	5.3	4.0	4.9	7.5
20×6×3	0.9	3.3	7.2	3.7	1.9	30×4×3	1.5	2.6	11.9	2.3	4.3
20×6×4	5.4	3.3	2.3	2.6	3.3	30×4×4	3.0	5.8	5.3	14.1	4.5
20×6×5	2.6	5.0	8.1	6.8	9.2	30×4×5	3.0	6.6	12.6	13.0	10.1
20×6×6	2.5	6.2	7.1	2.6	4.5	30×4×6	2.4	5.1	4.8	5.2	10.5
20×6×7	1.7	15.5	5.8	8.9	7.3	30×4×7	2.4	10.6	3.5	5.6	4.6
20×6×8	5.0	7.9	6.6	8.9	7.8	30×4×8	3.6	1.8	6.6	3.5	5.8
20×6×9	4.0	3.8	8.6	8.2	9.2	30×4×9	2.9	4.2	8.2	7.7	5.7
20×6×10	5.8	8.3	6.3	2.8	5.9	30×4×10	5.2	9.5	9.3	3.3	5.4
25×2×1	8.5	13.5	6.6	5.0	7.0	30×6×1	5.2	7.6	4.8	10.4	11.0
25×2×2	2.2	3.4	3.8	7.2	13.8	30×6×2	1.8	5.2	13.0	2.6	9.5
25×2×3	14.4	7.6	5.8	13.9	6.1	30×6×3	8.1	4.3	5.3	3.5	4.2
25×2×4	1.2	9.4	3.0	5.6	2.3	30×6×4	4.5	7.1	7.1	8.8	8.9
25×2×5	7.0	10.8	7.9	6.1	5.0	30×6×5	2.2	5.7	9.0	4.1	7.2
25×2×6	4.6	6.9	7.2	2.7	6.6	30×6×6	6.1	14.0	14.1	8.3	7.0
25×2×7	5.8	11.5	9.1	4.4	8.1	30×6×7	2.9	7.8	11.1	4.3	4.0
25×2×8	3.3	8.7	5.0	17.0	5.2	30×6×8	4.7	9.7	7.1	2.1	6.1
25×2×9	10.7	3.7	12.1	5.9	7.7	30×6×9	11.8	5.4	5.2	1.4	4.7
25×2×10	4.5	4.8	5.0	5.5	15.2	30×6×10	4.3	2.6	6.9	7.1	7.5
25×4×1	5.1	5.8	16.6	8.5	7.8	50×10×1	10.3	6.1	7.9	9.8	9.1
25×4×2	3.3	6.6	6.3	4.8	6.3	50×10×2	4.2	4.9	4.7	2.3	3.1
25×4×3	1.5	3.1	10.7	4.8	6.0	50×10×3	10.8	4.8	12.3	5.1	7.3
25×4×4	1.8	5.9	3.4	3.7	1.3	50×10×4	14.4	4.9	6.0	5.1	4.1
25×4×5	3.4	6.0	8.2	10.9	11.1	50×10×5	5.8	11.9	11.4	11.8	6.4
25×4×6	4.6	10.8	13.4	6.6	5.7	50×10×6	5.1	9.1	14.3	4.9	3.2
25×4×7	4.9	3.4	8.5	8.1	3.4	50×10×7	7.2	7.9	4.2	3.0	4.5
25×4×8	5.6	5.6	8.9	15.7	2.9	50×10×8	5.6	11.5	11.6	2.5	4.3
25×4×9	5.6	4.0	4.0	5.7	4.0	50×10×9	11.6	7.2	9.0	2.4	7.7
25×4×10	7.0	9.9	4.0	9.5	1.4	50×10×10	13.3	4.9	5.3	7.3	4.1
25×6×1	3.4	7.3	4.8	3.8	7.7	50×20×1	5.0	4.5	7.7	8.7	4.7
25×6×2	2.2	3.1	8.5	6.3	6.9	50×20×2	3.5	5.4	8.5	8.0	7.0
25×6×3	0.9	3.2	3.0	3.5	2.6	50×20×3	7.1	7.2	4.1	15.3	3.3
25×6×4	5.4	2.9	4.7	4.3	4.9	50×20×4	8.3	4.4	10.3	8.3	7.4
25×6×5	3.0	8.5	2.8	9.2	8.3	50×20×5	5.0	6.5	8.1	7.3	3.1
25×6×6	1.7	5.7	7.6	10.5	5.2	50×20×6	8.9	5.3	3.6	6.8	5.3
25×6×7	3.4	8.2	13.6	2.8	5.0	50×20×7	8.1	7.4	4.7	3.3	6.8
25×6×8	4.6	6.9	9.6	9.7	7.6	50×20×8	2.9	7.1	3.8	8.4	9.4
25×6×9	3.4	11.2	5.0	2.8	9.2	50×20×9	11.0	10.2	5.4	3.8	5.5
25×6×10	3.0	7.5	15.0	4.5	3.6	50×20×10	2.9	13.2	3.9	14.6	4.5

Table 11

Computational results of five algorithms on metric SD

Instance	QSFLA	SFLA	TAFOA	HPSOGA	MPH	Instance	QSFLA	SFLA	TAFOA	HPSOGA	MPH
50×30×1	3.0	4.0	6.0	8.1	3.9	250×20×1	8.2	4.8	12.8	3.5	10.4
50×30×2	3.5	2.4	4.3	9.2	4.1	250×20×2	6.1	4.7	2.9	4.4	6.1
50×30×3	3.1	4.2	2.1	2.5	4.9	250×20×3	13.9	3.5	9.7	3.9	9.6
50×30×4	5.6	3.6	4.0	6.9	5.3	250×20×4	3.8	4.4	2.7	11.1	2.7
50×30×5	5.1	7.2	3.0	11.1	3.6	250×20×5	2.4	1.6	7.8	6.7	9.7
50×30×6	3.6	2.7	3.0	7.1	3.0	250×20×6	4.9	6.9	4.5	3.4	3.2
50×30×7	3.9	5.5	2.7	4.4	7.4	250×20×7	2.9	5.1	2.6	8.0	4.2
50×30×8	2.6	5.6	3.8	11.6	9.6	250×20×8	3.7	1.6	7.8	8.3	8.1
50×30×9	3.8	8.7	0.3	10.4	0.1	250×20×9	6.3	3.8	2.1	4.7	6.8
50×30×10	4.8	6.9	3.5	4.2	6.7	250×20×10	4.9	3.0	2.6	4.2	5.4
150×10×1	5.0	8.1	10.4	7.9	3.8	250×30×1	2.6	5.1	3.5	5.8	4.8
150×10×2	9.7	9.6	10.6	5.6	10.8	250×30×2	2.7	8.4	5.6	17.1	11.0
150×10×3	10.8	7.9	3.2	3.4	14.0	250×30×3	2.0	4.7	3.6	8.1	8.1
150×10×4	2.6	6.5	3.7	3.6	6.5	250×30×4	4.8	1.7	6.8	4.4	6.0
150×10×5	5.4	4.5	6.3	5.1	6.1	250×30×5	2.5	5.4	4.3	7.2	5.4
150×10×6	4.9	2.7	13.8	6.2	4.1	250×30×6	6.5	10.7	5.8	7.3	4.0
150×10×7	4.0	7.8	7.1	7.3	9.6	250×30×7	2.6	2.2	4.9	14.8	4.7
150×10×8	4.8	12.8	9.8	8.0	6.9	250×30×8	3.7	2.6	3.3	9.8	5.8
150×10×9	3.7	8.2	4.6	4.7	6.0	250×30×9	1.5	14.5	8.3	9.2	6.4
150×10×10	4.4	7.6	3.9	3.9	6.5	250×30×10	2.8	4.4	7.1	6.0	5.3
150×20×1	8.2	6.7	6.4	4.0	3.9	350×10×1	6.3	7.9	14.5	5.6	4.0
150×20×2	1.8	12.5	1.3	13.2	8.1	350×10×2	15.9	4.7	5.4	4.7	7.1
150×20×3	4.3	3.7	3.1	5.5	3.2	350×10×3	7.4	8.4	3.9	3.1	5.8
150×20×4	4.7	5.2	10.3	2.4	10.9	350×10×4	6.3	10.4	5.1	8.4	3.2
150×20×5	3.1	10.1	1.8	2.7	6.2	350×10×5	8.3	6.1	7.0	6.1	8.7
150×20×6	3.8	11.6	2.3	8.4	6.3	350×10×6	2.5	6.4	7.8	6.2	12.5
150×20×7	9.7	6.8	3.4	3.7	3.8	350×10×7	6.5	3.4	7.6	4.9	4.9
150×20×8	4.8	8.7	6.6	6.4	5.5	350×10×8	5.3	4.7	6.9	6.5	3.9
150×20×9	3.6	10.8	6.1	6.9	5.2	350×10×9	9.5	6.0	8.1	6.3	2.9
150×20×10	4.4	4.3	2.9	4.4	2.1	350×10×10	8.9	7.8	6.9	5.8	4.4
150×30×1	5.1	7.3	9.9	5.9	12.2	350×20×1	5.3	5.3	3.8	4.3	5.6
150×30×2	5.0	3.7	9.7	8.9	5.8	350×20×2	8.7	7.3	6.6	4.5	7.7
150×30×3	3.4	3.2	4.2	7.6	4.3	350×20×3	7.2	6.7	5.7	9.5	5.3
150×30×4	4.1	4.6	4.3	13.2	6.4	350×20×4	5.1	7.0	5.8	6.1	5.3
150×30×5	1.7	2.5	9.8	5.4	4.1	350×20×5	5.7	8.0	1.7	3.0	6.8
150×30×6	4.2	5.0	4.3	4.0	9.2	350×20×6	4.6	7.2	4.3	4.8	3.6
150×30×7	6.8	9.8	1.0	5.6	8.3	350×20×7	5.2	5.4	6.4	4.2	2.7
150×30×8	6.2	8.0	10.2	4.9	5.5	350×20×8	3.4	8.3	3.8	6.0	11.6
150×30×9	2.2	13.9	4.4	5.2	6.3	350×20×9	5.5	5.6	8.2	8.2	4.7
150×30×10	3.5	6.7	5.8	4.6	15.0	350×20×10	7.2	4.5	6.9	11.6	7.7
250×10×1	4.3	14.7	11.8	6.8	3.7	350×30×1	6.7	3.5	3.5	8.4	7.8
250×10×2	5.8	4.8	3.4	6.3	7.4	350×30×2	5.6	3.6	8.2	6.9	5.6
250×10×3	2.9	4.9	5.2	5.5	7.9	350×30×3	4.8	4.1	5.2	6.4	6.5
250×10×4	5.7	5.0	5.9	5.3	1.3	350×30×4	4.2	6.7	7.4	6.2	5.0
250×10×5	7.8	3.7	6.6	2.2	8.4	350×30×5	9.6	7.2	3.0	7.6	5.6
250×10×6	4.9	7.0	10.1	6.6	2.8	350×30×6	5.9	6.2	6.4	4.3	5.9
250×10×7	5.7	6.6	5.7	8.6	9.0	350×30×7	7.4	1.3	8.3	4.8	6.3
250×10×8	5.6	4.7	4.7	6.0	5.1	350×30×8	5.0	4.7	14.2	3.3	12.3
250×10×9	4.2	6.1	3.2	7.1	3.5	350×30×9	4.5	3.6	6.9	6.0	4.2
250×10×10	2.7	4.4	8.9	6.4	5.3	350×30×10	12.2	7.2	7.5	4.5	3.9

As stated in Tables 3 –11, QSFLA has better SD than SFLA on most of instances and obtains better MIN and AVG than SFLA on nearly all instances; moreover, MIN and AVG of SFLA is notably worse than those of QSFLA on all instances. There are significant performance differences between QSFLA and SFLA on convergence and average performance. This conclusion also can be obtained from Fig. 3 and Fig. 4. The difference between QSFLA and SFLA is the usage of Q-learning. The notable performance differences between QSFLA and SFLA show that Q-learning algorithm really has positive impact on the performance of QSFLA, so it is effective and efficient to introduce Q-learning algorithm into QSFLA.

It can be found from Tables 3 –5 that QSFLA performs better than its comparative algorithms on metric MIN. QSFLA produces smaller MIN than three comparative algorithms on 266 of 300 instances; moreover, MIN of QSFLA is less than that of TAFOA by at least 30 on 142 instances, that of MPH by at least 30 on 178 instances and that of HPSOGA by at least 30 on 245 instances. QSFLA has better convergence than MPH, HSPOGA and TAFOA. This conclusion also can be drawn from Figs. 3 and 4.

As shown in Tables 6 –8, QSFLA obtains smaller AVG than MPH, TAFOA and HPSOGA on 273 instances; moreover, AVG of QSFLA is better than that of its all comparative algorithms by at least 10 on 226 instances. QSFLA possesses better average performance than MPH, TAFOA and HPSOGA. Figure 3 also depicts the average performance difference.

It can be seen from Tables 9 –11 that QSFLA produces better SD than its comparative algorithms on 88 of 120 instances with n ≤ 20, obtains smaller SD than TAFOA on 108 instances with n > 20, than HPSOGA on 101 instances with n > 20 and than MPH on 107 instances with n > 20. Fig. 3 also shows that QSFLA can provide better results on metric SD than comparative algorithms.

The above analyses validate the good performances of QSFLA on UPMSPR with learning effect. The good performance mainly results from the dynamical selection of search operators and the differentiated search of sub-populations P₁, P₂. These two strategies lead to good exploration ability and low possibility of falling local optima, thus, it can be concluded that QSFLA is a very competitive method for UPMSPR with learning effect.

5 Conclusions

UPMSP with additional resources and other real-life constraints like learning effect is seldom considered. In this study, UPMSPR with learning effect is handled and a new algorithm named QSFLA is proposed by combining Q-learning algorithm and SFLA together. A new solution presentation and decoding process are presented. The whole population is divided into two sub-populations. A Q-learning algorithm is applied to implement the dynamical selection of search operator and search times. It possesses 12 states, four actions, a new action selection and a reward function. Extensive experiments are conducted. Computational results demonstrate that QSFLA has promising advantages for the considered UPMSPR.

UPMSPR with other processing constraints is still our future research topic because additional resources, learning effect or deteriorating jobs etc often exist in an unrelated parallel machines manufacturing process. We will try to solve the above problem using meta-heuristics like imperialist competitive algorithm etc. The previous works proved that RL is an effective path to enhance search ability of meta-heuristics. We will focus on the integration of RL and meta-heuristics for various production scheduling problems including distributed scheduling and energy-efficient scheduling.

References

Cheng

T.C.E.

and Sin

C.C.S.

, A state-of-the-art review ofparallel-machine scheduling research, Euro. J. Oper. Res 47 (1990), 271–292.

Pan

Z.X.

, Lei

D.M.

and Wang

, A knowledge-based two-population optimization algorithm for distributed energy-efficient parallel machines scheduling, IEEE Trans. Cyber. 52(6) (2022), 5051–5063.

Edis

E.B.

, Oguz

and Ozkarahan

, Parallel machine scheduling with additional resources: notation, classification, models and solution methods, Euro. J. Oper. Res 230 (2013), 449–463.

Blazewicz

, Kubiak

, Rck

and Szwarcfiter

, Minimizing mean flow-time with parallel processors and resource-constraints, Acta Infor 24(5) (1987), 513–524.

Edis

E.B.

and Oguz

, Parallel machine scheduling with flexible resources, Comput. Ind. Eng 63(2) (2012), 433–447.

Ventura

J.A.

and Kim

, Parallel machine scheduling withearliness-tardiness penalties and additional resource constraints, Comput. Oper. Res 30 (2003), 1945–1958.

Zheng

X.L.

and Wang

, A two-stage adaptive fruit fly optimization algorithm for unrelated parallel machine scheduling problem with additional resource constraint, Expert Syst. Appl 65(2016), 28–39.

Fanjul-Peyro

, Perea

and Ruiz

, Models and matheuristics forthe unrelated parallel machine scheduling problem with additional resources, Euro. J. Oper. Res 260 (2017), 482–493.

Fleszar

and Hindi

K.S.

, Algorithms for the unrelated parallelmachine scheduling problem with a resource constraint, Euro. J.Oper. Res 271 (2018), 839–848.

10.

Zheng

X.L.

and Wang

, A collaborative multiobjective fruit fly optimization algorithm for the resource constrained unrelated parallel machine green scheduling problem, IEEE Trans. Syst,Man, Cyber: Syst 48(5) (2018), 790–800.

11.

Villa

, Vallada

and Fanjul-Peyro

, Heuristic algorithms forthe unrelated parallel machine scheduling problem with one scarceadditional resource, Expert Syst. Appl 93 (2018), 28–38.

12.

Vallada

, Villa

and Fanjul-Peyro

, Enriched metaheuristicsfor the resource unrelated parallel machine scheduling problem, Comput. Oper. Res 111 (2019), 415–424.

13.

Chen

J.F.

, Unrelated parallel machine scheduling with second resource constraints, Int. J. Adv. Manuf. Techno 26(2005), 285–292.

14.

Bitar

and Dauzère-Pérès

, A memetic algorithm to solve an unrelated parallel machine scheduling problem with auxiliary resources in semiconductor manufacturing, J. Sched 19(4) (2016), 1094–6136.

15.

Afzalirad

and Shafipour

, Design of an efficient genetical gorithm for resource-constrained unrelated parallel machinescheduling with machine eligibility restrictions, J. Intel.Manuf 29(2) (2018), 422–437.

16.

Al-Harkan

I.M.

and Qamhan

A.A.

, Optimize unrelated paralllel machine scheduling problems with multiple limited additional resources, sequence-dependent setup times and release date constraints, IEEE Acc. 7 (2019), 171533–171547.

17.

Fanjul-Peyro

, Models and an exact method for the unrelatedparallel machine scheduling problem with setups and resources, Expert Syst. Appl 5 (2020), 100022.

18.

Yepes-Borrero

J.C.

, Villa

, Perea

and Caballero-Villalobos

J.P.

, GRASP algorithm for the unrelated parallelmachine scheduling problem with setup times and additionalresources, Expert Syst. Appl 141 (2020), 112959.

19.

Pinar

and Seyda

T.Y.

, Constraint programming approach for multi-resource-constrained unrelated parallel machine scheduling problem with sequence-dependent setup times, Int. J. Prod. Res (2021), 1–18.

20.

Kuo

W.H.

, Hsu

C.J.

and Yang

D.L.

, Some unrelated parallel machine scheduling problems with past-sequence-dependent setup time and learning effects, Comput. Ind. Eng 61(1) (2011), 179–183.

21.

Wang

X.Y.

and Wang

J.J.

, Scheduling deteriorating jobs with alearning effect on unrelated parallel machines, Appl. Mathe.Model 38(21–22) (2014), 5231–5238.

22.

Y.Y.

, Jin

, Ji

and Wang

J.B.

, Resource-dependent scheduling with deteriorating jobs and learning effects on unrelated parallel machine, Neural Comput. Appl 27(7) (2016), 1993–2000.

23.

Soleimani

, Ghaderi

, Tsai

P.W.

, Zarbakhshnia

and Maleki

, Scheduling of unrelated parallel machines considering sequence-related setup time, start time-dependent deterioration, position-dependeent learning and power consumption minimization, J. Clean. Prod 249 (2020), 119428.

24.

Zhang

L.K.

, Deng

Q.W.

, Lin

R.H.

, Gong

G.L.

and Han

W.W.

, A combinatorial evolutionary algorithm for unrelated parallel machine scheduling problem with sequence and machine-dependent setup times, limited worker resources and learning effect, Expert Syst.Appl 175 (2021), 114843.

25.

Cao

Z.C.

, Lin

, Zhou

and Huang

, Scheduling semi-conductortesting facility by using cuckoo search algorithm with reinforcement learning and surrogate modeling, IEEE Trans. Auto. Sci. Eng 16 (2019), 825–837.

26.

Chen

, Yang

, Li

and Wang

, A self-learning genetic algorithm based on reinforcement learning for flexible job-shop scheduling problem, Comput. Ind. Eng 149 (2020), 106778.

27.

Cao

Z.C.

, Lin

and Zhou

, A knowledge-based cuckoo search algorithm to schedule a flexible job shop with sequencing flexibility, IEEE Trans. Auto. Sci. Eng 18 (2021), 56–69.

28.

Karimi-Mamaghan

, Mohammadi

, Meyer

, Karimi-Mamaghan

A.M.

and Talbi

E.G.

, Machine learning at service of meta-heuristics for solving combinatorial optimization problems: a state-of-the-art, Euro. J. Oper. Res, (2021) in press.

29.

Eusuff

M.M.

, Lansey

K.E.

and Pasha

, Shuffled frog-leaping algorithm: a memetic meta-heuristic for discrete optimization, Eng. Optim 38(2) (2006), 129–154.

30.

Rahimi-Vahed

and Mirzaei

A.H.

, Solving a bi-criteria permutation flow-shop problem using shuffled frog-leaping algorithm, SoftComput. 12 (2008), 435–452.

31.

Pan

Q.K.

, Wang

, Gao

and Li

J.Q.

, An effective shuffled frog-leaping algorithm for lot-streaming flow shop scheduling problem, Int. J. Adv. Manuf. Techno 52 (2011), 699–713.

32.

, Wang

, Liu

and Wang

S.Y.

, An effective shuffled frog-leaping algorithm for hybrid flow-shop scheduling with multiprocessor tasks, Int. J. Adv. Manuf. Techno 68(2013) (2013), 1529–1537.

33.

Lei

D.M.

and Guo

X.P.

, A shuffled frog-leaping algorithm for hybrid flow shop scheduling with two agents, Expert Syst. Appl 42 (2015), 9333–9339.

34.

J.Q.

, Pan

Q.K.

and Xie

S.X.

, An effective shuffled frog-leaping algorithm for multi-objective flexible job shop scheduling problems, Appl. Mathe. Comput 218(18) (2012), 9353–9371.

35.

Lei

D.M.

and Guo

X.P.

, A shuffled frog-leaping algorithm for jobshop scheduling with outsourcing options, Int. J. Prod. Res 54(16) (2016), 4793–4804.

36.

Lei

D.M.

, Zheng

Y.L.

and Guo

X.P.

, A shuffled frog-leaping algorithmfor flexible job shop scheduling with the consideration of energy consumption, Int. J. Prod. Res 55(11) (2017), 3126–3140.

37.

Kong

, Liu

X.B.

, Pei

, Pardalos

P.M.

and Mladenovic

, Parallel-batching scheduling with nonlinear processing times on asingle and unrelated parallel machines, J. Global Optim. 78(4) (2020), 693–715.

38.

Lei

D.M.

and Yi

, A novel shuffled frog-leaping algorithm for unrelated parallel machine scheduling with deteriorating maintenance and setup time, Symmetry 13(9) (2021), 1574.

39.

Lei

D.M.

and Wang

, Solving distributed two-stage hybrid flowshopscheduling using a shuffled frog-leaping algorithm with memeplexgrouping, Eng. Optim 52(9) (2020), 1461–1474.

40.

Cai

J.C.

and Lei

D.M.

, A cooperated shuffled frog-leaping algorithmfor distributed energy-efficient hybrid flow shop scheduling with fuzzy processing time, Comp. Intel. Syst. 7(5) (2021), 2235–2253.

41.

Cai

J.C.

, Zhou

and Lei

D.M.

, Dynamic shuffled frog-leaping algorithm for distributed hybrid flow shop scheduling with multiprocessor tasks, Eng. Appl. Artif. Intell. 90(2020), 103540.

42.

Cai

J.C.

, Lei

D.M.

and Li

, A shuffled frog-leaping algorithm with memeplex quality for bi-objective distributed scheduling in hybridflow shop, Int. J. Prod. Res. 59(18) (2021), 5404–5421.

43.

Okolowski

and Gawiejnowicz

, Exact and heuristic algorithms for parallel-machine scheduling with Dejong’s learning effect, Comput. Ind. Eng. 59 (2010), 272–279.

44.

Potvin

J.Y.

, Genetic algorithms for the traveling salesman problem, Ann. Oper. Res 63(3) (1996), 339–370.

45.

Watkins

C.J.C.H.

and Dayan

, Q-learning. Mach. Learn. 8 (1992), 279–292.

46.

Salehi Mir

M.S.

and Rezaeian

, A robust hybrid approach based onparticle swarm optimization and genetic algorithm to minimize thetotal machine laod on unrelated parallel machines, Appl. Soft Comput. 41 (2016), 488–504.

47.

Taguchi

, Introduction to quality engineering. Asian Productivity Organization. Tokyo: Asian Productivity Organization (1986).

A shuffled frog-leaping algorithm with Q-learning for unrelated parallel machine scheduling with additional resource and learning effect

Abstract

Keywords

1 Introduction

2 Problem description

3.1 Solution representation and population division

3.2 Global search and neighborhood search

3.3 Q-learning algorithm

4 Computational experiments

4.1 Test instances and comparative algorithms

4.2 Parameter settings

Table 2 Parameters and their levels Parameter Factor level 1 2 3 N 48 64 96 s 4 8 16 R 30 50 70 β R/ 4 R/ 3 R/ 2 γ 0.85 0.9 0.95 w 1 0.6 0.7 0.8

References

Table 2
Parameters and their levels

Parameter Factor level

1 2 3

N 48 64 96

s 4 8 16

R 30 50 70

β R/ 4 R/ 3 R/ 2

γ 0.85 0.9 0.95

w ₁ 0.6 0.7 0.8