Diversified teaching-learning-based optimization for fuzzy two-stage hybrid flow shop scheduling with setup time

Abstract

Distributed scheduling has attracted much attention in recent years; however, distributed scheduling problem with uncertainty is seldom considered. In this study, fuzzy distributed two-stage hybrid flow shop scheduling problem (FDTHFSP) with sequence-dependent setup time is addressed and a diversified teaching-learning-based optimization (DTLBO) algorithm is applied to optimize fuzzy makespan and total agreement index. In DTLBO, multiple classes are constructed and categorized into two types according to class quality. Different combinations of global search and neighborhood search are used in two kind of classes. A temporary class with multiple teachers is built based on Pareto rank and difference index and evolved in a new way. Computational experiments are conducted and results demonstrate that the main strategies of DTLBO are effective and DTLBO has promising advantages on solving the considered problem.

Keywords

Two-stage hybrid flow shop scheduling distributed scheduling fuzzy scheduling teaching-learning-based optimization

1 Introduction

Two-stage hybrid flow shop scheduling problem (THFSP) is a special case of hybrid flow shop scheduling and possesses parallel machines at one stage or two stages. It is NP-hard because its simplest version with two machines at one stage and single machine at another stage is proved to be NP-hard [1]. In the past decades, THFSP has been extensively considered in single factory and multiple factories and a number of results have been obtained.

Regarding THFSP in single factory, many methods including exact algorithm, heuristic and meta-heuristic have been applied. Allaoui and Artiba [2] investigated THFSP with availability constraint by using an exact method and several heuristics to minimize makespan. Yang [3] developed some heuristics for some special cases of the problem with dedicated machines. Wang and Liu [4] presented a heuristic based on branch-and-bound for the problem with dedicated machines. Wang et al. [5] proposed a problem-tailored constructive heuristic with local search strategy to solve a bi-criteria energy-efficient THFSP.

Meta-heuristic is a group of various algorithms [6 –23] and the main path to solve THFSP. Wang and Liu [6] proposed a genetic algorithm for no-wait THFSP. Tan et al. [7] presented a hybrid decomposition approach with variable neighborhood search for the problem with batch processing machines. Fan et al. [8] provided a mutant firefly algorithm to optimize the simultaneous rate for the arrival and the on-time delivery rate. Except these works, THFSP with batching and scheduling [9], interval processing times [10], assembly [11], renewable resources [12], preventive maintenance [13] and deteriorating effect [14] are studied and other meta-heuristics including tabu search [13, 15], artificial bee colony [16], estimation of distribution algorithm [14] and imperialist competitive algorithm [17] are used.

Production has transferred from single factory to multiple factories with the development of globalisation. Distributed scheduling problems in multiple factories have attracted much attention in recent years. As the extended version of THFSP in multiple factories, distributed two-stage hybrid flow shop scheduling problem (DTHFSP) is also considered. Lei and Wang [24] developed a shuffled frog-leaping algorithm with memeplex grouping for DTHFSP with makespan minimization. Cai et al. [25] investigated FDTHFSP with sequence-dependent setup time (SDST) and presented a collaborative variable search (CVS) to optimize total agreement index and fuzzy makespan simultaneously.

As stated above, the previous works are mainly about THFSP in single factory and the results on DTHFSP are very limited. With the applications of multi-factory production in many manufacturing situations like semi-conductor manufacturing, it is important to pay attention to DTHFSP to quickly respond to rapid changes in market requirements and customer demands in the global market. On the other hand, uncertainty extensively exists in real-life production process, for example, processing time, setup time and due date are not fixed in advance and often described by fuzzy number etc. In the past decade, scheduling problems with uncertainty have been extensively considered in single factory.

Uncertainty cannot neglected intentionally because the obtained schedule is hard to meet the requirements of real-life production after uncertainty is neglected; moreover, the neglecting of uncertainty in multiple factories will lead to greater loss than the neglecting in single factory, so it is necessary to consider distributed scheduling problems with uncertainty such as FDTHFSP.

Fuzzy theory is often used to describe uncertainty and fuzzy scheduling problems have been extensively considered in single factory [26 –37]. In recent years, there are some works on fuzzy distributed scheduling in multiple factories. Shao et al. [36] focused on distributed fuzzy blocking flow shop scheduling problem in multiple homogeneous factories and presented two constructive heuristics and two iterated greedy to minimize fuzzy makespan. Zheng et al. [37] handled multi-objective fuzzy distributed hybrid flow shop scheduling problem and proposed a cooperative coevolution algorithm with iterated greedy and estimation of distribution algorithm. Cai et al. [25] solved FDTHFSP by using CVS. Obviously, fuzzy distributed scheduling does not attract sufficient attention and FDTHFSP is seldom investigated, thus, it is necessary to focus on fuzzy distributed scheduling problems and especially on FDTHFSP.

As mentioned above, TLBO is seldom used to solve FDTHFSP. It is is a population-based algorithm inspired by passing on knowledge within a classroom environment, which has simple structure and fewer parameters and is easily understood and implemented [39]. In recent years, it has been successfully used to solve various production scheduling problems in single factory and multiple factories. Lin et al. [40] proposed a multi-objective TLBO with three carbon-footprint-reduction strategies for processing parameter optimization and flow shop scheduling. Li et al. [41] developed discrete TLBO with a modified iterated greedy for flow shop rescheduling problems. Lei et al. [42] presented a teachers’ TLBO for energy-efficient hybrid flow shop scheduling. Xu et al. [43] solved fuzzy flexible job shop scheduling by using an effective TLBO. Shao et al. [44] provided a hybrid discrete TLBO to solve no-idle flow shop scheduling. Mishra and Shrivastava [45] presented a TLBO and a jaya heuristic for permutation flow shop scheduling with cost minimization. Buddala and Mahapatra [46] applied two-stage TLBO for scheduling in flexible job shop with machine breakdown. Lei et al. [47] proposed a cooperated TLBO for distributed two-stage assembly flow shop scheduling. The competitive performances of TLBO are verified and tested in the above works, so TLBO may be an useful path to solve FDTHFSP.

In this study, FDTHFSP with SDST, fuzzy makespan and maximize total agreement index is considered, which is DTHFSP with fuzzy processing data and studied by Cai et al. [25]. A diversified teaching-learning-based optimization (DTLBO) algorithm is presented, in which multiple classes are constructed and categorized into two types according to class quality. Different combinations of global search and neighborhood search are used in two kind of classes. A temporary class with multiple teachers is constructed and evolved in a new way. A number of experiments are conducted on many instances. The computational results show the effectiveness of the main strategies of DTLBO and its promising advantages in solving FDTHFSP with SDST.

The remainder of the paper is organized as follows. Problem description is given in Section 2 followed by operators of fuzzy number. DTLBO for the considered problem is reported in Section 4. Numerical experiments on DTLBO are reported in Section 5 and the conclusions are summarized in the final section and some topics of the future research are provided.

2 Problem description

FDTHFSP with SDST is described as follows. There are n jobs J₁, J₂, ⋯ , J_n processed by F factories located in different sites. Each factory f possesses a two-stage hybrid flow shop, where there are m_f identical parallel machines at the first stage and a single machine at the second stage. All jobs are available at time zero. Machines M_{1,S_f+1}, ⋯ , M_{1,S_f+m_f} exist at the first stage of factory f, where $S_{f} = \sum_{l = 1}^{f - 1} m_{l}, f > 1$ , S₁ = 0. $W = \sum_{f = 1}^{F} m_{f}$ is the total number of parallel machines. M_2,f indicates the single machine at the second stage of factory f.

Triangular fuzzy number (TFN) is used to depict processing time and setup time. $p_{iSf} = (p_{iSf}^{1}, p_{iSf}^{2}, p_{iSf}^{3})$ is the processing time of job J_i at stage S of factory f. SDST are considered. $u_{jiSf} = (u_{jiSf}^{1}, u_{jiSf}^{2}, u_{jiSf}^{3})$ denotes setup time for job J_i on each machine of stage S in factory f when job J_j is processed directly before it on the same machine. $u_{0 iSf} = (u_{0 iSf}^{1}, u_{0 iSf}^{2}, u_{0 iSf}^{3})$ represents initial fuzzy setup time of the first job J_i processed on machine at stage S of factory f. Fuzzy due date of J_iis often indicated as $d_{i} = (d_{i}^{1}, d_{i}^{2})$ [25, 33].

FDTHFSP has some constraints on jobs and machines: each machine can process at most one operation at a time; no jobs may be processed on more than one machine at a time; operations cannot be interrupted; all machines are available at all times, that is, maintenance, failure and breakdown are not considered.

FDTHFSP consists of three sub-problems, (1) factory assignment used to decide which jobs are allocated into each factory; (2) machine assignment; (3) scheduling. Cai et al. [25] analyzed the relationships among these sub-problems and pointed out that two assignment sub-problems can be combined into machine assignment of the first stage.

The goal of the problem is to optimize the following two objectives under all constraints are met. $C_{max} = max_{i = 1, 2, \dots, n} C_{i}$ (1) ${AI}_{tot} = \sum_{i = 1}^{n} A I_{i}$ (2) where $C_{max} = (C_{max}^{1}, C_{max}^{2}, C_{max}^{3})$ is fuzzy makespan, C_i indicates fuzzy completion time of job J_i, AI_tot is the total agreement index and AI_i denotes the agreement index of job J_i.

${AI}_{i} = area (C_{i} \cap d_{i}) / area (C_{i})$ (3)

Obviously, FDTHFSP is NP-hard because THFSP is the special case of FDTHFSP and NP-hard.

3 Operators of TFN

When TFN is used to represent processing data of scheduling problem, three operators are often used to build a schedule, which are addition operator, max operator and ranking operator.

Addition operator is used to compute completion time and defined for TFNs A = (a₁, a₂, a₃) and B = (b₁, b₂, b₃) by $A + B = (a_{1} + b_{1}, a_{2} + b_{2}, a_{3} + b_{3})$ (4)

Ranking operator is used to compare fuzzy completion time. To compare A and B, criteria c₁, c₂ and c₃ are defined for TFN A, c₁ (A) = (a₁ + 2a₂ + a₃)/4, c₂ (A) = a₂, c₃ (A) = a₃ - a₁. If c₁ (A) > c₁ (B), then A > B. If c₁ (A) = c₁ (B) and c₂ (A) > c₂ (B), then A > B. If c₁ and c₂ of A and B are both equal, c₃ is used to compare A and B.

Max operator is applied to decide fuzzy beginning time and given by $if A > B, then A \lor B = s; else A \lor B = B$ (5)

4 DTLBO for FDTHFSP with SDST

In TLBO [39], its search process acts on a population considered as a class of learners and has a teacher phase and a learner phase. In teacher phase, a teacher x_teacher which is the best solution obtained so far passes its knowledge to learners and a solution x is modified by $x_{new} = x + rand \times (x_{teacher} - (T \times x_{mean}))$ (6) where T is a teaching factor and can be either 1 or 2, x_mean is the current mean value of all solutions and rand is a random number following uniform distribution in [0,1].

In learner phase, a learner x increases its knowledge by interaction with its classmate x_j. $x_{new} = {\begin{matrix} x + rand \times (x - x_{j}) & iff (x) < f (x_{j}) \\ x + rand \times (x_{j} - x) & otherwise \end{matrix}$ (7)

In the above phases, x_new is accepted if x_new gives a better objective value than x.

Equations (6,7) are hard to directly generate feasible solutions of scheduling problem because of its combinatorial feature. TLBO is often discrete when it is used to solve scheduling problems [41 –47]. In this study, DTLBO is also discrete.

In DTLBO, multiple classes are constructed and divided into good classes and common classes and different combinations of global search and neighborhood search are adopted in two kind of classes; a temporary class with multiple teachers is constructed and evolved in a new way, as a result, diversification is implemented.

4.1 Initialization and construction of s classes

Cai et al. [25] pointed out that FDTHFSP is composed of scheduling and machine assignment of the first stage and provided a two-string representation, in which a machine assignment string and a random key string are used. In this study, this representation is adopted. For FDTHFSP with n jobs and W parallel machines at stage 1, a solution is denoted by a machine assignment string [M_1,h₁, M_1,h₂, ⋯ , M_{1,h_n}] and a random key string [r₁, r₂, ⋯ , r_n], where machine M_{1,h_i} is allocated for job J_i, r_i is real number of job J_i. The second string is for scheduling sub-problem.

The decoding procedure is shown as follows. In each factory f, for each parallel machine M_1,q, decide its all allocated jobs according to machine assignment string and obtain a permutation of these jobs by sort these jobs in the ascending order of their r_i, then start with the first job of the permutation, process all jobs of the permutation on M_1,q sequentially, finally, deal with the processing of each job on M_2,f after the processing at stage is finished.

Cai et al. [25] provided an example of FDTHFSP with 10 jobs and 2 factories. m₁ = m₂ = 2. A possible solution is composed of [M_1,1, M_1,3, M_1,4, M_1,1, M_1,2, M_1,2, M_1,1, M_1,1, M_1,3, M_1,4] and [0.12, 0.43, 0.89, 0.77, 0.40, 0.25, 0.89, 0.91, 0.17, 0.36.

An initial population P with N solutions is randomly produced. Then N solutions are compared according to Pareto dominance and a rank_x is computed for solution x ∈ P. ${rank}_{x} = | {y \in P | y ≻ x} |$ (8) where y ≻ x means y dominates x, y ≻ x if C_max (y) ≤ C_max (x), AI_tot (y) ≤ AI_tot (x), at least one objective, for example, C_max meets C_max (y) < C_max (x).

When multiple classes are used, it is easy to apply different search strategies in different classes, exploration ability of TLBO can be extended and falling local optima can be avoided effectively. In this study, s classes are constructed as follows. Let g = 1, repeat the following steps until all solutions are added into classes: randomly select a solution x ∈ P and remove it from P to class L_g(mod s)+1, g = g + 1, where g (mod s) indicates the remainder of g/ s.

There are s classes L₁, L₂, ⋯ , L_s and these classes have the same size θ, obviously, N = s × θ.

The division of s classes is done as follows. Q_i = ∑_{x∈L_i}rank_x is computed for each class L_i, i = 1, 2, ⋯ , s and all classes are sorted in the ascending order of Q_i, suppose that Q₁ ≤ Q₂ ≤ ⋯ ≤ Q_s, where Q_i denotes the quality of class L_i. We define the first s/2 classes as good ones and other classes as common ones.

4.2 The diversified search in multiple classes

Algorithm 1 describes the diversified search procedure in multiple classes, where R₁, R₂ are integer. Solutions of good class are better than those of common class, we set R₁ < R₂ to assign more neighborhood search to solutions of good class and make them be used fully. Ω is used to store non-dominated solutions by DTLBO. When y is utilized to update Ω, y is included into Ω, all solutions in Ω are compared each other and the dominated ones are removed.

Seven neighborhood structures are used, four of which are for machine assignment and three of which are for scheduling. Neighborhood structure $N_{1}$ is described below. Randomly decide a job J_i on M_1,u of factory f, repeat the following steps until f = g and u ≠ l: stochastically select a l ∈ [1, W], suppose that S_g + 1 ≤ l ≤ S_g + m_g; then insert the job into M_1,l, that is, M_{1,h_i} = M_1,l. $N_{2}$ is shown as follows. Randomly select a job J_i allocated on M_1,u of factory f and stochastically choose a job J_j on M_1,l, l ≠ u of factory f, then swap these two jobs, that is, M_{1,h_i} = M_1,l and M_{1,h_j} = M_1,u. $N_{3}$ is done in the following way. Stochastically select a job J_i on M_1,u of factory f, repeat the following step until g ≠ f: randomly decide a machine M_1,l, S_g + 1 ≤ l ≤ S_g + m_g; then insert J_i into M_1,l. $N_{4}$ is shown below. Randomly choose a job J_i on M_1,u of factory f, repeat the following steps until g ≠ f: randomly decide a job J_j on machine M_1,l of factory g; then swap jobs J_i and J_j like $N_{2}$ .

$N_{5}$ produces new solutions by swapping two randomly chosen jobs on scheduling string. $N_{6}$ is depicted as follows. Randomly decide two positions k₁, k₂ on scheduling string, then insert the job on position k₁ into position k₂ - 1 if k₂ > 1 or into position k₂ if k₂ = 1. $N_{7}$ is done in the following way. Randomly choose three positions k₁, k₂, k₃, suppose jobs on position k₁, k₂, k₃ are J_i, J_j and J_v, then remove jobs from scheduling string, insert J_i into position k₃, J_j into position k₁ and J_v into position k₂.

Algorithm 1 Diversified search

1: for i = 1 to s do

2: if L_i is good class then

3: for t = 1 to R₁ do

4: decide a teacher $x_{teacher}^{i} \in L_{i}$ with the smallest ${rank}_{x_{teacher}^{i}}$

5: for each solution x ∈ L_i, $x \neq x_{teacher}^{i}$ do

6: select two-point crossover of machine assignment string or

7: two-point crossover of scheduling string in the same probability

8: perform the chosen crossover between x and its teacher $x_{teacher}^{i}$ and obtain a solution y, update x and archive Ω with y if y ≻ x

9: execute NS₃ on x

10: end for

11: end for

12: else

13: for t = 1 to R₂ do

14: determine a teacher $x_{teacher}^{i} \in L_{i}$ as done in good class

15: for each solution x ∈ L_i, $x \neq x_{teacher}^{i}$ do

16: perform crossover between x and $x_{teacher}^{i} \in L_{i}$ as done in good class

17: execute NS₁ and NS₂ on x sequentially

18: end for

19: end for

20: end if

21: end for

Three neighborhood searches NS₁, NS₂, NS₃ are constructed by using above neighborhood structures. NS₁ is shown below. For solution x, let g = 1, z = 0, repeat the following steps until z = 1 or g > 4: produce a solution $y \in N_{g} (x)$ , if one objective of y is better than that of x, then z = 1 and stop the search; otherwise, g = g + 1. If z = 1 and y ≻ x, then replace x and update Ω with y, where $N_{g} (x)$ indicates the set of neighborhood solutions of x generated by $N_{g}$ . NS₂ is similar with NS₁. When NS₂ is performed, let g = 5, $N_{5}$ , $N_{6}$ and $N_{7}$ are used and g > 4 is replaced with g > 7.

NS₃ is described as follows. For solution x, let g = 1, z = 0, repeat the following steps until z = 1 or g > 4: produce a solution $y \in N_{g} (x)$ , if all objectives of y are not better than those of x, then g = g + 1; otherwise, apply NS₂ on y, obtain a solution y′, and if all objectives of y′ are not better than those of x, then g = g + 1; else z = 1. If z = 1 and y′ ≻ x, then replace x and update Ω with y′.

As stated above, the diversified searches in two kind of classes are implemented by the different combination of global search and NS₁, NS₂, NS₃ and the usage of the parameters R₁ > R₂, as a result, the possibility of falling local optima reduces and the good balance between exploration and exploitation can be made.

Algorithm 2 Search in temporary class

1: decide rank_x for each solution x ∈ P and sort all solutions in the ascending order of rank_x

2: directly add the first α₁ × N solutions of P into TCL and choose (α₂ - α₁) × N solutions with biggest DI_x from the next α₂ × N solutions of P and include them into TCL

3: determine δ teachers with the smallest rank_x for TCL and let other solutions be learners

4: for each learner x ∈ TCL do

5: randomly select a teacher, execute two-point crossover of machine assignment string between x and the chosen teacher, obtain a solution y

6: if y ≻ x then

7: update x and Ω with y

8: else

9: perform two-point crossover of scheduling string between x and the chosen teacher and update x and Ω with the obtained y if y ≻ x

10: end if

11: end for

12: for each solution x ∈ TCL do

13: for t = 1 to R₃ do

14: execute NS₄ and NS₅ sequentially on x

15: randomly select a member y ∈ Ω, perform a randomly chosen neighborhood structure on y, if y ≻ x, then replace x and update Ω with y when t can be exactly divided by β

16: end for

17: end for

4.3 Search in temporary class

Algorithm 2 describes the search procedure in temporary class TCL, where δ ≥ 2, β and R₃ are integer, α_i is real number, i = 1, 2, difference index DI_x is computed by

${DI}_{x} = \sum_{y \in H} {MDI}_{x, y} + {SDI}_{x, y}$ (9) where H is the set of the first α₁ × N solutions of P after all solutions of population P are sorted in the ascending order of rank_x, MDI_x,y (SDI_x,y) indicates the difference between machine assignment strings (job permutations) of x, y. ${MDI}_{x, y} = \sum_{i = 1}^{n} η_{ixy}, {SDI}_{x, y} = \sum_{i = 1}^{n} λ_{ixy}$ , η_ixy (λ_ixy) is 1 if the ith genes of machine assignment strings (job permutations) of x and y are not identical and 0 otherwise.

When SDI_x,y is computed, job permutation is obtained by sorting all jobs in the ascending order of their r_i in scheduling string. We set δ = 3 and β = 10 by experiments.

The diversified searches in s classes L₁, L₂, ⋯ , L_s are implemented independently. In TCL, α₁ solutions with the smallest rank_x is first chosen and then α₂ - α₁ solutions with the biggest DI_x are decided. The search in TCL is applied to perform the intensified communications among classes to keep high diversity of class and low possibility falling local optima.

Obviously, it is unreasonable to set α₂ to be greater than 0.5 because TCL consists of good solutions of population P. We obtain α₂ = 0.25 by experiments independently.

NS₄ is depicted as follows. For solution x, let g = 5, z = 0, repeat the following steps until z = 1 or g > 8: produce a solution $y \in N_{g} (x)$ if g ≤ 7 or execute two-point crossover of scheduling string between x and a randomly selected solution from Ω if g = 8, if one objective of y is better than that of x, then z = 1 and stop the search; otherwise, g = g + 1. If z = 1 and y ≻ x, then replace x with y and update Ω with y.

NS₅ is similar with NS₁ and described below. For solution x, let g = 1, z = 0, repeat the following steps until z = 1 or g > 5: produce a solution $y \in N_{g} (x)$ if g ≤ 4 or execute two-point crossover of machine assignment string between x and a randomly chosen member of Ω if g = 5, if one objective of y is better than that of x, then z = 1 and stop the search; otherwise, g = g + 1. If z = 1 and y ≻ x, then replace x with y and update Ω with y.

Temporary class is composed of solution with good quality in convergence and diversity, the reinforced search in TCL can effectively implement the communication among classes and produce new solutions with good quality, as a result, high diversity of population P can be kept.

Algorithm 3 DTLBO

1: randomly produce initial population P and construct s classes

2: while stopping condition is not met do

3: apply classes division

4: perform search in s classes sequentially

5: execute search in temporary class

6: end while

4.4 Algorithm description

The search procedure of DTLBO is shown in Algorithm 3. Fig.1 shows flow chart of DTLBO.

Fig. 1

Algorithm flowchart.

DTLBO has the following features. s classes are constructed and divided into two types. The diversified searches based on the different combinations of neighborhood search and its parameter are implemented. A temporary class is built by using some solutions with best rank_x and DI_x and the reinforced search in TCL is applied to perform communications among classes, thus, the diversified searches and the intensified communications are the main strategies of DTLBO. DTLBO has more complicated structure than the general TLBO; however, the above features can result in the great improvements in search efficiency.

5 Computational experiments

Extensive experiments are conducted to test the performance of DTLBO for FDTHFSP with SDST. All experiments are implemented by using Microsoft Visual C++ 2019 and run on 8.0G RAM 2.4GHz CPU PC.

5.1 Instance, metrics and comparative algorithms

95 instances provided by Cai et al. [25] are directly adopted for FDTHFSP with SDST and six instances with n = 200 are added. The processing data of these added instances are produced as done in [25]. Table 1 shows information on these instances.

Table 1
Information on 100 instances

Instances F mf Instances n

1-10 2 3,3 1,11,22,32,43,53,64 30

11-21 2 2,4 2,12,23,33,44,54,65 40

22-31 3 3,3,3 3,13,24,34,45,55,66,75,83,92 50

32-42 3 2,3,4 4,14,25,35,46,56,67,76,84,93 60

43-52 4 2,2,2,2 5,15,26,36,47,57,68,77,85,94 70

53-63 4 2,2,3,3 6,16,27,37,48,58,69,78,86,95 80

64-74 4 2,3,4,5 7,17,28,38,49,59,70,79,87,96 90

75-82 5 3,3,3,3,3 8,18,29,39,50,60,71,80,88,97 100

83-91 5 2,3,3,3,4 9,19,30,40,51,61,72,81,89,98 120

92-100 5 2,3,4,5,6 10,20,31,41,52,62,73,82,90,99 150

21,42,63,74,91,100 200

Instances	F	mf	Instances	n
1-10	2	3,3	1,11,22,32,43,53,64	30
11-21	2	2,4	2,12,23,33,44,54,65	40
22-31	3	3,3,3	3,13,24,34,45,55,66,75,83,92	50
32-42	3	2,3,4	4,14,25,35,46,56,67,76,84,93	60
43-52	4	2,2,2,2	5,15,26,36,47,57,68,77,85,94	70
53-63	4	2,2,3,3	6,16,27,37,48,58,69,78,86,95	80
64-74	4	2,3,4,5	7,17,28,38,49,59,70,79,87,96	90
75-82	5	3,3,3,3,3	8,18,29,39,50,60,71,80,88,97	100
83-91	5	2,3,3,3,4	9,19,30,40,51,61,72,81,89,98	120
92-100	5	2,3,4,5,6	10,20,31,41,52,62,73,82,90,99	150
			21,42,63,74,91,100	200

Metrics $C$ [48], inverted generational distance (IGD) [49] and ρ_l [50] are used to evaluate the results of DTLBO and its comparative algorithms.

Metric $C$ is applied to compare the approximate Pareto optimal set respectively obtained by algorithms. $C (L, B)$ measures the fraction of members of B that are dominated by members of L.

$C (L, B) = \frac{| {b \in B : \exists h \in L, h ≻ b} |}{| B |}$ (10)

Let Ω^* represent the set of non-dominated solutions along the Pareto front and |Ω^*| denote the size of Ω^*. d (x, y) is defined as the Euclidean distance computed by using vectors of the normalized objectives of x and y, ρ_l and IGD are then defined.

Metric ρ_l indicates the ratio of number of the elements in the set {x∈ Ω_l|x ∈ Ω^* } to |Ω^*|. The larger the value of ρ_l, the more members that Ω_l provides for Ω^*. ρ_l = 1 indicates that all solutions of Ω^* are provided by Ω_l. ρ_l can be calculated as follow: $ρ_{l} = \frac{| {x \in Ω_{l} | x \in Ω^{*}} |}{| Ω^{*} |}$ (11)

IGD is a quality indicator for evaluating all quality aspects of multi-objective optimization results and obtained by $IGD (A, Ω^{*}) = \frac{1}{| Ω^{*} |} \sum_{x \in Ω^{*}} min_{y \in A} d (x, y)$ (12) The smaller IGD (A, Ω^*) is, the closer A is to the Pareto front. In this paper, when the normalized value of C_max is computed, c₁ (C_max) is used, Ω^* consists of non-dominated solutions in the union set of all archives of all algorithms in all runs.

Three comparative algorithms are applied, which are competitive memetic algorithm (CMA [51]), multi-objective tabu search (MOTS [13]) and CVS [25]. CMA is used to solve multi-objective distributed permutation flow-shop scheduling problem with makespan and total tardiness. After the encoding and decoding of DTLBO are used directly, CMA can directly handle FDTHFSP because the objectives of optimization are similar, search operators for makepan and total tardiness can be used directly without any changes. MOTS is proposed to solve THFSP with preventive maintenance and it can be applied to deal with FDTHFSP after the repair related encoding string is deleted. CVS itself is presented for FDTHFSP with SDST, C_max and AI_tot.

We also compare DTLBO with TLBO to show the effect of the main strategies of DTLBO. In TLBO, there is only one class, teacher phase and learner phase are implemented as done in common class of Algorithm 1.

5.2 Parameter settings

The stopping condition is set to be 0.15 × n × K CPU time, where K is the number of stages in hybrid flow shop, in this study, K = 2. It can be found that archive Ω cannot be updated by new solutions when running time of DTLBO is 0.15 × n × K for each instance, so we think DTLBO converge well. it is also found that the above time is also appropriate for all comparative algorithms, so the above condition is adopted. Other parameters of DTLBO are R₁, R₂, R₃, s, N, α₁. We conduct Taguchi method [52], which is often used to decide settings of algorithm parameters.

We select instance 71 for parameters tuning. The levels of each parameter are shown in Table 2. There are 27 parameter combinations according to the orthogonal array L₂₇ (3⁶).

Table 2
Parameters and their levels

Parameter Factor level

1 2 3

N 40 60 80

s 4 6 8

R ₁ 4 8 12

R ₂ 2 4 6

R ₃ 50 100 150

α ₁ 0.10 0.15 0.20

Parameter	Factor level
N	40	60	80
s	4	6	8
R ₁	4	8	12
R ₂	2	4	6
R ₃	50	100	150
α ₁	0.10	0.15	0.20

DTLBO with each combination runs 10 times independently for the chosen instance. The results of IGD and S/N ratio are shown in Fig.2, in which S/N ratio is defined as -10 log ₁₀ (IGD²). It can be found from Fig. 2 that DTLBO with following combination N = 60, s = 6, R₁ = 8, R₂ = 4, R₃ = 100 and α₁ = 0.15 can obtain better results than DTLBO with other combination, so the above settings are adopted.

Fig. 2

Results on IGD and S/N ratio.

5.3 Results and analyses

DTLBO is compared with TLBO, CMA, MOTS and CVS. All parameters except stopping condition of CVS, CMA and MOTS are directly adopted from papers [13 , 51]. For TLBO, there are no R₁, R₃, α_i, i = 1, 2, 3 and δ, other parameters are given the same settings as DTLBO. Each algorithm randomly runs 10 times for each instance. Tables 5-8 show the computational results of all algorithms, in which symbols D, CV, CM, M, T indicate DTLBO, CVS, CMA, MOTS and TLBO, respectively. Fig.3 gives box plot of all algorithms and Fig. 4 reveals the distribution of non-dominated solutions of four instances.

Table 3
The orthogonal array L₂₇ (3⁶)

Ins Factor level IGD

N s R ₁ R ₂ R ₃ α ₁

1 1 1 1 1 1 1 0.316

2 1 1 1 1 2 2 0.158

3 1 1 1 1 3 3 0.221

4 1 2 2 2 1 1 0.122

5 1 2 2 2 2 2 0.103

6 1 2 2 2 3 3 0.181

7 1 3 3 3 1 1 0.220

8 1 3 3 3 2 2 0.070

9 1 3 3 3 3 3 0.211

10 2 1 2 3 1 2 0.158

11 2 1 2 3 2 3 0.104

12 2 1 2 3 3 1 0.184

13 2 2 3 1 1 2 0.110

14 2 2 3 1 2 3 0.236

15 2 2 3 1 3 1 0.187

16 2 3 1 2 1 2 0.270

17 2 3 1 2 2 3 0.105

18 2 3 1 2 3 1 0.138

19 3 1 3 2 1 3 0.126

20 3 1 3 2 2 1 0.231

21 3 1 3 2 3 2 0.179

22 3 2 1 3 1 3 0.191

23 3 2 1 3 2 1 0.148

24 3 2 1 3 3 2 0.221

25 3 3 2 1 1 3 0.245

26 3 3 2 1 2 1 0.172

27 3 3 2 1 3 2 0.175

Ins	Factor level	IGD
1	1	1	1	1	1	1	0.316
2	1	1	1	1	2	2	0.158
3	1	1	1	1	3	3	0.221
4	1	2	2	2	1	1	0.122
5	1	2	2	2	2	2	0.103
6	1	2	2	2	3	3	0.181
7	1	3	3	3	1	1	0.220
8	1	3	3	3	2	2	0.070
9	1	3	3	3	3	3	0.211
10	2	1	2	3	1	2	0.158
11	2	1	2	3	2	3	0.104
12	2	1	2	3	3	1	0.184
13	2	2	3	1	1	2	0.110
14	2	2	3	1	2	3	0.236
15	2	2	3	1	3	1	0.187
16	2	3	1	2	1	2	0.270
17	2	3	1	2	2	3	0.105
18	2	3	1	2	3	1	0.138
19	3	1	3	2	1	3	0.126
20	3	1	3	2	2	1	0.231
21	3	1	3	2	3	2	0.179
22	3	2	1	3	1	3	0.191
23	3	2	1	3	2	1	0.148
24	3	2	1	3	3	2	0.221
25	3	3	2	1	1	3	0.245
26	3	3	2	1	2	1	0.172
27	3	3	2	1	3	2	0.175

Table 4

Response table for means

Level	N	s	R ₁	R ₂	R ₃	α ₁
1	0.1779	0.1865	0.1966	0.2022	0.1954	0.1907
2	0.1658	0.1664	0.1604	0.1616	0.1473	0.1606
3	0.1876	0.1784	0.1743	0.1674	0.1886	0.1799
Delta	0.0218	0.0201	0.0362	0.0405	0.0481	0.0301
Rank	5	6	3	2	1	4

Table 5

Computational results of all algorithms on $C$ of the first 50 instances

Ins	$C$ (D,CV)	$C$ (CV,D)	$C$ (D,CM)	$C$ (CM,D)	$C$ (D,M)	$C$ (M,D)	$C$ (D,T)	$C$ (T,D)
1	1.00	0.00	0.63	0.20	1.00	0.00	1.00	0.00
2	1.00	0.00	0.73	0.06	1.00	0.00	1.00	0.00
3	1.00	0.00	0.10	0.44	1.00	0.00	1.00	0.00
4	1.00	0.00	0.00	0.18	1.00	0.00	1.00	0.00
5	1.00	0.00	0.00	0.19	1.00	0.00	1.00	0.00
6	1.00	0.00	0.00	0.00	1.00	0.00	1.00	0.00
7	1.00	0.00	0.20	0.00	1.00	0.00	1.00	0.00
8	1.00	0.00	0.05	0.00	1.00	0.00	1.00	0.00
9	1.00	0.00	0.12	0.06	1.00	0.00	1.00	0.00
10	1.00	0.00	0.00	0.04	1.00	0.00	1.00	0.00
11	1.00	0.00	0.63	0.33	1.00	0.00	1.00	0.00
12	1.00	0.00	0.44	0.07	1.00	0.00	1.00	0.00
13	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
14	1.00	0.00	0.30	0.05	1.00	0.00	1.00	0.00
15	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
16	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
17	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
18	1.00	0.00	0.00	0.14	1.00	0.00	1.00	0.00
19	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
20	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
21	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
22	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
23	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
24	1.00	0.00	0.93	0.08	1.00	0.00	1.00	0.00
25	0.64	0.05	0.00	0.19	1.00	0.00	1.00	0.00
26	1.00	0.00	0.00	0.11	1.00	0.00	1.00	0.00
27	1.00	0.00	0.14	0.11	1.00	0.00	1.00	0.00
28	1.00	0.00	0.11	0.10	1.00	0.00	1.00	0.00
29	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
30	1.00	0.00	0.05	0.00	1.00	0.00	1.00	0.00
31	1.00	0.00	0.60	0.28	1.00	0.00	1.00	0.00
32	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
33	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
34	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
35	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
36	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
37	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
38	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
39	1.00	0.00	0.86	0.00	1.00	0.00	1.00	0.00
40	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
41	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
42	0.83	0.00	1.00	0.00	1.00	0.00	1.00	0.00
43	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
44	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
45	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
46	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
47	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
48	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
49	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
50	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00

Table 6

Computational results of all algorithms on $C$ of instances 51-100

Ins	$C$ (D,CV)	$C$ (CV,D)	$C$ (D,CM)	$C$ (CM,D)	$C$ (D,M)	$C$ (M,D)	$C$ (D,T)	$C$ (T,D)
51	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
52	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
53	0.40	0.06	1.00	0.00	1.00	0.00	1.00	0.00
54	0.86	0.00	1.00	0.00	1.00	0.00	1.00	0.00
55	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
56	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
57	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
58	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
59	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
60	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
61	1.00	0.00	0.50	0.00	1.00	0.00	1.00	0.00
62	1.00	0.00	0.00	0.25	1.00	0.00	1.00	0.00
63	0.93	0.00	1.00	0.00	1.00	0.00	1.00	0.00
64	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
65	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
66	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
67	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
68	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
69	0.65	0.11	1.00	0.00	1.00	0.00	1.00	0.00
70	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
71	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
72	1.00	0.00	0.88	0.00	1.00	0.00	1.00	0.00
73	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
74	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
75	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
76	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
77	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
78	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
79	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
80	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
81	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
82	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
83	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
84	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
85	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
86	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
87	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
88	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
89	1.00	0.00	0.50	0.22	1.00	0.00	1.00	0.00
90	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
91	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
92	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
93	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
94	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
95	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
96	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
97	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
98	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
99	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00
100	1.00	0.00	1.00	0.00	1.00	0.00	1.00	0.00

Table 7

Computational results of all algorithms on metric ρ_l

Ins	DTLBO	CVS	CMA	MOTS	TLBO	Ins	DTLBO	CVS	CMA	MOTS	TLBO
1	0.57	0.00	0.43	0.00	0.00	51	1.00	0.00	0.00	0.00	0.00
2	0.83	0.00	0.17	0.00	0.00	52	1.00	0.00	0.00	0.00	0.00
3	0.50	0.00	0.50	0.00	0.00	53	0.84	0.16	0.00	0.00	0.00
4	0.64	0.00	0.36	0.00	0.00	54	0.89	0.11	0.00	0.00	0.00
5	0.65	0.00	0.35	0.00	0.00	55	1.00	0.00	0.00	0.00	0.00
6	0.11	0.00	0.89	0.00	0.00	56	1.00	0.00	0.00	0.00	0.00
7	0.45	0.00	0.55	0.00	0.00	57	1.00	0.00	0.00	0.00	0.00
8	0.44	0.00	0.56	0.00	0.00	58	1.00	0.00	0.00	0.00	0.00
9	0.29	0.00	0.71	0.00	0.00	59	1.00	0.00	0.00	0.00	0.00
10	0.48	0.00	0.52	0.00	0.00	60	1.00	0.00	0.00	0.00	0.00
11	0.36	0.00	0.64	0.00	0.00	61	0.62	0.00	0.38	0.00	0.00
12	0.57	0.00	0.43	0.00	0.00	62	0.41	0.00	0.59	0.00	0.00
13	1.00	0.00	0.00	0.00	0.00	63	0.88	0.13	0.00	0.00	0.00
14	0.44	0.00	0.56	0.00	0.00	64	1.00	0.00	0.00	0.00	0.00
15	1.00	0.00	0.00	0.00	0.00	65	1.00	0.00	0.00	0.00	0.00
16	1.00	0.00	0.00	0.00	0.00	66	1.00	0.00	0.00	0.00	0.00
17	1.00	0.00	0.00	0.00	0.00	67	1.00	0.00	0.00	0.00	0.00
18	0.72	0.00	0.28	0.00	0.00	68	1.00	0.00	0.00	0.00	0.00
19	1.00	0.00	0.00	0.00	0.00	69	0.71	0.29	0.00	0.00	0.00
20	1.00	0.00	0.00	0.00	0.00	70	1.00	0.00	0.00	0.00	0.00
21	1.00	0.00	0.00	0.00	0.00	71	1.00	0.00	0.00	0.00	0.00
22	1.00	0.00	0.00	0.00	0.00	72	0.92	0.00	0.08	0.00	0.00
23	1.00	0.00	0.00	0.00	0.00	73	1.00	0.00	0.00	0.00	0.00
24	0.96	0.00	0.04	0.00	0.00	74	1.00	0.00	0.00	0.00	0.00
25	0.48	0.15	0.36	0.00	0.00	75	1.00	0.00	0.00	0.00	0.00
26	0.42	0.00	0.58	0.00	0.00	76	1.00	0.00	0.00	0.00	0.00
27	0.73	0.00	0.27	0.00	0.00	77	1.00	0.00	0.00	0.00	0.00
28	0.51	0.00	0.49	0.00	0.00	78	1.00	0.00	0.00	0.00	0.00
29	1.00	0.00	0.00	0.00	0.00	79	1.00	0.00	0.00	0.00	0.00
30	0.29	0.00	0.71	0.00	0.00	80	1.00	0.00	0.00	0.00	0.00
31	0.52	0.00	0.48	0.00	0.00	81	1.00	0.00	0.00	0.00	0.00
32	1.00	0.00	0.00	0.00	0.00	82	1.00	0.00	0.00	0.00	0.00
33	1.00	0.00	0.00	0.00	0.00	83	1.00	0.00	0.00	0.00	0.00
34	1.00	0.00	0.00	0.00	0.00	84	1.00	0.00	0.00	0.00	0.00
35	1.00	0.00	0.00	0.00	0.00	85	1.00	0.00	0.00	0.00	0.00
36	1.00	0.00	0.00	0.00	0.00	86	1.00	0.00	0.00	0.00	0.00
37	1.00	0.00	0.00	0.00	0.00	87	1.00	0.00	0.00	0.00	0.00
38	1.00	0.00	0.00	0.00	0.00	88	1.00	0.00	0.00	0.00	0.00
39	0.78	0.00	0.22	0.00	0.00	89	0.93	0.00	0.07	0.00	0.00
40	1.00	0.00	0.00	0.00	0.00	90	1.00	0.00	0.00	0.00	0.00
41	1.00	0.00	0.00	0.00	0.00	91	1.00	0.00	0.00	0.00	0.00
42	0.71	0.29	0.00	0.00	0.00	92	1.00	0.00	0.00	0.00	0.00
43	1.00	0.00	0.00	0.00	0.00	93	1.00	0.00	0.00	0.00	0.00
44	1.00	0.00	0.00	0.00	0.00	94	1.00	0.00	0.00	0.00	0.00
45	1.00	0.00	0.00	0.00	0.00	95	1.00	0.00	0.00	0.00	0.00
46	1.00	0.00	0.00	0.00	0.00	96	1.00	0.00	0.00	0.00	0.00
47	1.00	0.00	0.00	0.00	0.00	97	1.00	0.00	0.00	0.00	0.00
48	1.00	0.00	0.00	0.00	0.00	98	1.00	0.00	0.00	0.00	0.00
49	1.00	0.00	0.00	0.00	0.00	99	1.00	0.00	0.00	0.00	0.00
50	1.00	0.00	0.00	0.00	0.00	100	1.00	0.00	0.00	0.00	0.00

Table 8

Computational results of all algorithms on IGD

Ins	DTLBO	CVS	CMA	MOTS	TLBO	Ins	DTLBO	CVS	CMA	MOTS	TLBO
1	0.00	0.10	0.02	0.23	0.27	51	0.00	0.25	0.14	0.67	0.53
2	0.01	0.10	0.05	0.21	0.23	52	0.00	0.07	0.15	0.50	0.36
3	0.07	0.13	0.00	0.35	0.28	53	0.00	0.03	0.10	0.10	0.17
4	0.06	0.11	0.00	0.35	0.22	54	0.00	0.04	0.24	0.37	0.33
5	0.01	0.05	0.00	0.38	0.24	55	0.00	0.10	0.11	0.31	0.21
6	0.00	0.23	0.00	0.41	0.34	56	0.00	0.16	0.63	0.26	0.24
7	0.00	0.13	0.01	0.50	0.41	57	0.00	0.29	0.29	0.61	0.50
8	0.00	0.12	0.00	0.33	0.21	58	0.00	0.11	0.24	0.28	0.38
9	0.02	0.14	0.01	0.39	0.37	59	0.00	0.09	0.23	0.44	0.28
10	0.00	0.05	0.00	0.47	0.33	60	0.00	0.07	0.10	0.35	0.24
11	0.04	0.10	0.03	0.25	0.24	61	0.00	0.09	0.04	0.50	0.39
12	0.01	0.08	0.02	0.25	0.45	62	0.02	0.15	0.00	0.45	0.36
13	0.00	0.15	0.17	0.43	0.32	63	0.00	0.08	0.29	0.22	0.18
14	0.00	0.15	0.02	0.38	0.24	64	0.00	0.10	0.26	0.23	0.26
15	0.00	0.05	0.40	0.52	0.25	65	0.00	0.07	0.19	0.26	0.30
16	0.00	0.05	0.36	0.31	0.18	66	0.00	0.18	0.25	0.53	0.39
17	0.00	0.09	0.29	0.55	0.23	67	0.00	0.09	0.20	0.38	0.28
18	0.01	0.09	0.00	0.41	0.26	68	0.00	0.24	0.15	0.55	0.44
19	0.00	0.11	0.40	0.65	0.26	69	0.00	0.06	0.29	0.23	0.13
20	0.00	0.04	0.57	0.66	0.34	70	0.00	0.08	0.25	0.57	0.29
21	0.00	0.04	0.45	0.58	0.32	71	0.00	0.08	0.52	0.42	0.28
22	0.00	0.06	0.05	0.13	0.16	72	0.00	0.06	0.07	0.63	0.13
23	0.00	0.05	0.15	0.25	0.22	73	0.00	0.06	0.27	0.77	0.37
24	0.01	0.11	0.05	0.24	0.21	74	0.00	0.06	0.51	0.59	0.24
25	0.01	0.04	0.00	0.34	0.24	75	0.00	0.11	0.52	0.22	0.26
26	0.02	0.25	0.00	0.43	0.42	76	0.00	0.11	0.16	0.30	0.18
27	0.01	0.12	0.00	0.25	0.20	77	0.00	0.17	0.12	0.33	0.31
28	0.01	0.08	0.00	0.21	0.22	78	0.00	0.17	0.35	0.44	0.27
29	0.00	0.20	0.31	0.57	0.60	79	0.00	0.10	0.15	0.28	0.28
30	0.00	0.19	0.00	0.48	0.38	80	0.00	0.11	0.14	0.41	0.35
31	0.03	0.14	0.14	0.47	0.37	81	0.00	0.15	0.22	0.37	0.31
32	0.00	0.17	0.04	0.13	0.19	82	0.00	0.11	0.19	0.44	0.30
33	0.00	0.27	0.10	0.53	0.35	83	0.00	0.11	0.21	0.29	0.23
34	0.00	0.13	0.10	0.26	0.21	84	0.00	0.10	0.26	0.43	0.34
35	0.00	0.16	0.15	0.41	0.48	85	0.00	0.12	0.35	0.33	0.30
36	0.00	0.10	0.23	0.40	0.20	86	0.00	0.13	0.13	0.27	0.44
37	0.00	0.03	0.24	0.36	0.23	87	0.00	0.18	0.17	0.40	0.24
38	0.00	0.08	0.27	0.26	0.25	88	0.00	0.10	0.28	0.44	0.28
39	0.00	0.04	0.08	0.22	0.14	89	0.01	0.22	0.03	0.51	0.47
40	0.00	0.20	0.34	0.68	0.38	90	0.00	0.08	0.51	0.61	0.43
41	0.00	0.09	0.39	0.44	0.34	91	0.00	0.10	0.22	0.33	0.23
42	0.00	0.09	0.40	0.35	0.13	92	0.00	0.24	0.34	0.44	0.40
43	0.00	0.10	0.18	0.18	0.19	93	0.00	0.13	0.21	0.35	0.25
44	0.00	0.16	0.09	0.39	0.24	94	0.00	0.07	0.24	0.21	0.11
45	0.00	0.07	0.16	0.25	0.24	95	0.00	0.16	0.62	0.55	0.22
46	0.00	0.09	0.15	0.27	0.31	96	0.00	0.23	0.43	0.71	0.47
47	0.00	0.08	0.08	0.26	0.24	97	0.00	0.20	0.33	0.47	0.25
48	0.00	0.26	0.17	0.53	0.45	98	0.00	0.11	0.28	0.56	0.23
49	0.00	0.08	0.24	0.35	0.25	99	0.00	0.05	0.39	0.41	0.17
50	0.00	0.14	0.21	0.54	0.42	100	0.00	0.07	0.53	0.53	0.15

As shown in Tables 5-8 and Fig.3, DTLBO performs better than TLBO and the performance differences between DTLBO and TLBO are notable in statistical sense. All solutions of TLBO are dominated by non-dominated ones of DTLBO on all instances; ρ_l of DTLBO is 1 or very close to 1 on more than 70 instances and DTLBO obtains IGD of 0 on at least 80 instances.

Fig. 3

Box plot of all algorithms.

Fig. 4

Distribution of non-dominated solutions.

The notable performance differences between two TLBOs show that the main strategies such as the diversified search in s classes and the reinforced search in TCL really have positive impact on performances of DTLBO, so the new strategies are reasonable and effective.

It can be found that DTLBO performs better than its three comparative algorithms. DTLBO produces smaller $C (CV, D)$ than $C (D, CV)$ on all instances and obtains $C (D, CV)$ of 1 on 94 instances, that is, CVS cannot generate any solutions dominating one non-dominated solutions of DTLBO on these instances. ρ_l of CVS is 0 on 94 instances and IGD of CVS is greater than that of DTLBO on all instances. Figs. 2 and 3 also reveal the significant performance advantages of DTLBO when DTLBO is compared with CVS. It also can be seen from Tables 5-8 and Figs.2-3 that DTLBO can produce better results than MOTS and CMA on more than 80 instances.

As stated in section 4.4, the diversified search in s classes and the intensified communications by the search in TCL are two main strategies of DTLBO. These strategies can effectively improve search efficiency by keeping high diversity of population and low possibility falling local optima, as a result, DTLBO can provide promising results, thus, DTLBO is a very competitive method for solving FDTHFSP with SDST.

6 Conclusions

Distributed scheduling problem with uncertainty is seldom investigated. In this study, FDTHFSP with SDST is studied and a new algorithm named DTLBO is proposed to minimize fuzzy makespan and total agreement index simultaneously. Multiple classes are constructed and categorized into two types according to class quality in DTLBO. Different combinations of global search and neighborhood search are used in two kind of classes. A temporary class with multiple teachers is built based on Pareto rank and difference index and evolved in a new way. Many experiments are conducted and the computational results reveal that DTLBO can solve FDTHFSP with SDST well and provide promising results.

THFSP has very important applications in many real world scenarios such as the electronics, paper and textile industries. FDTHFSP is an extended version of THFSP by considerations on two important managerial things: uncertainty and multiple factories production, and this work provides an effective path to deal with these two things; moreover, DTLBO can be extended to handle other distributed scheduling with uncertainty.

It is important to combine uncertainty and multiple factories production into a scheduling problem and distributed scheduling problem with uncertainty should be considered fully in the near future. We will investigate the application advantages of newly proposed meta-heuristics such as whale optimization algorithm [20] and crow search algorithm [21] etc. and the application possibility of reinforcement learning into meta-heuristic to solve the above problem. Distributed scheduling problem with uncertainty and energy-related objective is also our future topic. We will try to solve the problem by using heuristics and learning-based meta-heuristics.

References

Gupta

J.N.D.

, Two-stage hybrid flow shop scheduling problem, J Oper Res Soc 39(4) (1988), 359–364.

Allaoui

and Artiba

, Scheduling two-stage hybrid flow shop with availability constraints, Comput Oper Res 33 (2006), 1399–1419.

Yang

, Minimizing total completion time in two-stage hybrid flow shop with dedicated machines, Comput Oper Res 38(7) (2011), 1045–1053.

Wang

and Liu

, A heuristic method for two-stage hybrid flow shop with dedicated machines, Comput Oper Res 40(1) (2013), 438–450.

Wang

, Wang

X.D.

, Chu

and Yu

J.B.

, An energy-efficient twostage hybrid flow shop scheduling problem in a glass production, Int J Prod Res 58(8) (2020), 2283–2314.

Wang

and Liu

, A genetic algorithm for two-stage no-wait hybrid flow shop scheduling problem, Comput Oper Res 40(4) (2013), 1064–1075.

Tan

, Mönch

and Fowler

J.W.

, A hybrid scheduling approach for a two-stage flexible flow shop with batch processing machines, J Scheduling 21(1) (2017), 1–18.

Fan

, Yang

and Zhang

, Solving the two-stage hybrid flow shop scheduling problem based on mutant firefly algorithm, J Amb Intel Hum Comp 10(3) (2019), 979–990.

J.M.

, Huang

and Lee

D.H.

, Iterative algorithms for batching and scheduling to minimise the total job tardiness in two-stage hybrid flow shops, Int J Prod Res 55(11) (2017), 3266–3282.

10.

Feng

, Zheng

and Xu

, Robust scheduling of a two-stage hybrid flow shop with uncertain interval processing times, Int J Prod Res 54(12) (2016), 3706–3717.

11.

Komaki

G.M.

, Teymourian

and Kayvanfar

, Minimising makespan in the two-stage assembly hybrid flow shop scheduling problem using artificial immunne systems, Int J Prod Res 54(4) (2016), 963–983.

12.

Figielska

, A heuristic for scheduling in a two-stage hybrid flowshop with renewable resources shared among the stages, Eur J Oper Res 236(2) (2014), 433–444.

13.

Wang

and Liu

, Two-stage hybrid flow shop scheduling with preventive maintenance using multi-objective tabu search method, Int J Prod Res 52(5) (2014), 1495–1508.

14.

Liu

S.W.

, Pei

, Cheng

, Liu

X.B.

and Pardalos

P.M.

, Twostage hybrid flow shop scheduling on parallel batching machines considering a job-dependent deteriorating effect and noidentical job sizes, Appl Soft Comput 84 (2019), 105701.

15.

Wang

S.J.

, Wang

X.D.

, Chu

and Yu

J.B.

, An energy-efficient two-stage hybrid flow shop scheduling problem in a glass production, Int J Prod Res (2019).

16.

Kheirandish

, Tavakkoli-Moghaddam

and Karimi-Nasab

, An artificial bee colony algorithm for a two-stage hybrid flowshop scheduling problem with multilevel product structures and requirement operations, Int J Comput Integ M 28(5) (2015), 437–450.

17.

Rabiee

, Sadeghi Rad

, Mazinani

and Shafaei

, An intelligent hybrid meta-heuristic for solving a case of no-wait two-stage flexible flow shop scheduling problem with unrelated parallel machines, Int J Adv Manuf Tech 71(5–8) (2014), 1229–1245.

18.

Assiri

A.S.

, Hussien

A.G.

and Amin

, Ant lion optimization: variants, hybrids, and applications, IEEE Access 8 (2020), 77746–77764.

19.

Hussien

A.G.

, Amin

and Aziz

M.E.A.E.

, A comprehensive review of moth-flame optimisation: variants, hybrids, and applications, J Exp Theor Artif Intel (2020), 1–21.

20.

Hussien

A.G.

, Oliva

, Houssein

E.H.

, Juan

A.A.

and Yu

, Binary whale optimization algorithm for dimensionality reduction, Mathe 8(10) (2020), 1821.

21.

Hussien

A.G.

, Amin

, Wang

, Liang

, Alsanad

, Gumaei

and Chen

, Crow search algorithm: theory, recent advances, and applications, IEEE Access 8 (2020), 173548–173565.

22.

Abualigah

, Elaziz

M.A.

and Hussien

A.G.

, Lightning search algorithm: a comprehensive survey, Appl Intell (2020)

23.

Abualigah

, Gandomi

A.H.

, Elaziz

M.A.

, Hussien

A.G.

, Khasawneh

A.M.

, Alshinwan

and Houssein

E.H.

, Nature-Inspired Optimization Algorithms for Text Document ClusteringąłA Comprehensive Analysis, Algorithms (13) (2020), 345.

24.

Lei

D.M.

and Wang

, Solving distributed two-stage hybrid flow shop scheduling using a shuffled frog-leaping algorithm with memeplex grouping, Eng Optimiz 52(9) (2020), 1461–1474.

25.

Cai

J.C.

, Zhou

and Lei

D.M.

, Fuzzy distributed twostage hybrid flow shop scheduling problem with setup time: collabortive variable search, J Intell Fuzzy Syst 38(3) (2020), 3189–3199.

26.

Vela

C.R.

, Afsar

and Jose Palacios

, Evolutionary tabu search for flexible due-date statisfaction in fuzzy job shop scheduling, Comput Oper Res 119 (2020), 104931.

27.

Dorfeshan

, Tavakkoli-Moghaddam

, Mousavi

S.M.

and Vahedi-Nouri

, A new weighted distance-based approximation methodology for flow shop scheduling group decisions under the interval-valued fuzzy processsing time, Appl Soft Comput 91 (2020), 106248.

28.

Sun

, Lin

, Gen

M.S.

and Li

H.J.

, A hybrid cooperative coevolution algorithm for fuzzy flexible job shop scheduling, IEEE T Fuzzy Syst 27(5) (2019), 1008–1022.

29.

Lin

, Backtracking search based hyper-heuristic for the flexible job-shop scheduling problem with fuzzy processing time, Eng Appl Artif Intel 77 (2020), 186–196.

30.

Liu

G.S.

, Zhou

and Yang

H.D.

, Minimizing energy consumption and tardiness penalty for fuzzy flow shop scheduling with state-dependent setup time, J Clean Prod 147 (2017), 470–484.

31.

Gao

K.Z.

, Suganthan

P.N.

, Pan

Q.K.

and Tasgetiren

M.F.

, An effective discrete harmony search algorithm for flexible job shop scheduling problem with fuzzy processing time, Int J Prod Res 53(19) (2015), 5896–5911.

32.

J.Q.

and Pan

Q.K.

, Chemical-reaction optimization for solving fuzzy job-shop scheduling problem with flexible maintenance activities, Int J Prod Econ 145(1) (2013), 4–17.

33.

Wang

, Zhou

, Xu

and Liu

, A hybrid artificial bee colony algorithm for the fuzzy flexible job-shop scheduling problem, Int J Prod Res 51(12) (2013), 3593–3608.

34.

Lei

D.M.

, Co-evolutionary genetic algorithm for fuzzy flexible job shop scheduling, Appl Soft Comput 12(8) (2012), 2237–2245.

35.

, Chen

J.F.

, Fu

, Jia

Z.H.

and Fu

W.Z.

, Uniform parallel machine scheduling with fuzzy processing times under resource consumption constraint, Appl Soft Comput 82 (2019), 105585.

36.

Shao

Z.S.

, Shao

W.S.

and Pi

D.C.

, Effective heuristics and metaheuristics for the distributed fuzzy blocking flow-shop scheduling problem, Swarm Evol Comput 59 (2020), 100747.

37.

Zheng

, Wang

and Wang

J.J.

, A cooperative coevolution algorithm for multi-objective fuzzy distributed hybrid flow shop, Knowl-based Syst 194 (2020), 105536.

38.

Wang

W.X.

, Ge

X.L.

, Li

L.C.

and Su

J.F.

, Proactive and reactive multi-project scheduling in uncertain environment, IEEE Access 7 (2019), 88986–88997.

39.

Rao

R.V.

, Savsani

V.J.

and Vakharia

D.P.

, Teaching-learningbased optimization: a novel method for constrained mechanical design optimization problems, Comput Aided Design 43(3) (2011), 303–315.

40.

Lin

W.W.

, Yu

D.Y.

, Zhang

C.Y.

and Liu

, A multi-objective teaching-learning-based optimization algorithm to scheduling in turning process for minimizing makespan and carbon footprint, J Clean Prod 101 (2015), 337–347.

41.

J.Q.

, Pan

Q.K.

and Mao

, A discrete teaching-learning-based optimisation algorithm for realistic flowshop scheduling problems, Eng Appl Artif Intel 37 (2015), 279–292.

42.

Lei

D.M.

, Gao

and Zheng

Y.L.

, A novel teaching-learningbased optimization algorithm for energy-efficient scheduling in hybrid flow shop, IEEE T Eng Manage 65(2) (2018), 330–340.

43.

, Wang

S.Y.

and Liu

, An effective teachinglearning-based optimization algorithm for the flexible job-shop scheduling problem with fuzzy processing time, Neurocomputing 148 (2015), 260–268.

44.

Shao

W.S.

, Pi

D.C.

and Shao

Z.S.

, A hybrid discrete teachinglearning based meta-heuristic for solving no-idle flow shop scheduling problem with total tardiness criterion, Comput Oper Res 94 (2018), 89–105.

45.

Mishra

and Shrivastava

, A TLBO and a Jaya heuristics for permutation flow shop scheduling to minimize the sum of inventory holding and batch delay costs, Comput Ind Eng 124 (2018), 509–522.

46.

Buddala

and Mahapatra

S.S.

, Two-stage teaching-learningbased optimization method for flexible job-shop scheduling under machine breakdown, Int J Adv Manuf Tech 100(5–8) (2019), 1419–1432.

47.

Lei

D.M.

, Su

and Li

, Cooperated teaching-learning-based optimisation for distributed two-stage assembly flow shop scheduling, Int J Prod Res (2020) in press.

48.

Zitzler

and Thiele

, Multi-objective evolutionary algorithms: a comparative case study and the strength Pareto approach, IEEE T Evolut Comput 3(4) (1999), 257–271.

49.

Lei

D.M.

, Pareto archive particle swarm optimization for multi-objective fuzzy job shop scheduling problems, Int J Adv Manuf Tech 37 (2008), 157–165.

50.

Luong

N.H.

, Poutre

H.L.

and Bosman

P.A.

, Multi-objective genepool optimal mixing evolutionary algorithm with the interleaved multi-start scheme, Swarm Evol Comput 40 (2018), 238–254.

51.

Deng

and Wang

, A competitive memetic algorithm for multiobjective distributed permutation flow shop scheduling problem, Swarm Evol Comput 32 (2017), 121–131.

52.

Taguchi

, Introduction to quality engineering: designing quality into products and processes, Asian Productivity Organization (1986).

Diversified teaching-learning-based optimization for fuzzy two-stage hybrid flow shop scheduling with setup time

Abstract

Keywords

1 Introduction

2 Problem description

4.3 Search in temporary class

5.1 Instance, metrics and comparative algorithms

Table 2 Parameters and their levels Parameter Factor level 1 2 3 N 40 60 80 s 4 6 8 R 1 4 8 12 R 2 2 4 6 R 3 50 100 150 α 1 0.10 0.15 0.20

References

Table 2
Parameters and their levels

Parameter Factor level

1 2 3

N 40 60 80

s 4 6 8

R ₁ 4 8 12

R ₂ 2 4 6

R ₃ 50 100 150

α ₁ 0.10 0.15 0.20