An Elite-Class Teaching-Learning-Based Optimization for Reentrant Hybrid Flow Shop Scheduling with Bottleneck Stage

Deming Lei,Surui Duan,Mingbo Liand Jing Wang

College of Automation,Wuhan University of Technology,Wuhan,430070,China

ABSTRACT Bottleneck stage and reentrance often exist in real-life manufacturing processes;however,the previous research rarely addresses these two processing conditions in a scheduling problem.In this study,a reentrant hybrid flow shop scheduling problem(RHFSP)with a bottleneck stage is considered,and an elite-class teaching-learning-based optimization(ETLBO)algorithm is proposed to minimize maximum completion time.To produce high-quality solutions,teachers are divided into formal ones and substitute ones,and multiple classes are formed.The teacher phase is composed of teacher competition and teacher teaching.The learner phase is replaced with a reinforcement search of the elite class.Adaptive adjustment on teachers and classes is established based on class quality,which is determined by the number of elite solutions in class.Numerous experimental results demonstrate the effectiveness of new strategies,and ETLBO has a significant advantage in solving the considered RHFSP.

KEYWORDS Hybrid flow shop scheduling;reentrant;bottleneck stage;teaching-learning-based optimization

1 Introduction

A hybrid flow shop scheduling problem(HFSP)is a typical scheduling problem that exists widely in many industries such as petrochemicals,chemical engineering,and semiconductor manufacturing[1,2].The term ‘reentrant’means a job may be processed multiple times on the same machine or stage [3].A typical reentrant is a cyclic reentrant [4,5],which means that each job is cycled through the manufacturing process.As an extension of HFSP,RHFSP is extensively used in electronic manufacturing industries,including printed circuit board production [6] and semiconductor wafer manufacturing[7],etc.

RHFSP has been fully investigated and many results have been obtained in the past decade.Xu et al.[8]applied an improved moth-flame optimization algorithm to minimize maximum completion time and reduce the comprehensive impact of resources and environment.Zhou et al.[9]proposed a hybrid differential evolution algorithm with an estimation of distribution algorithm to minimize total weighted completion time.Cho et al.[10] employed a Pareto genetic algorithm with a local search strategy and Minkowski distance-based crossover operator to minimize maximum completion time and total tardiness.Shen et al.[11]designed a modified teaching-learning-based optimization(TLBO)algorithm to minimize maximum completion time and total tardiness,where Pareto-based ranking method and training phase are adopted.

In recent years,RHFSP with real-life constraints has attracted much attention.Lin et al.[12]proposed a hybrid harmony search and genetic algorithm(HHSGA)for RHFSP with limited buffer to minimize weighted values of maximum completion time and mean flowtime.For RHFSP with missing operations,Tang et al.[13]designed an improved dual-population genetic algorithm(IDPGA)to minimize maximum completion time and energy consumption.Zhang et al.[14]considered machine eligibility constraints and applied a discrete differential evolution algorithm(DDE)with a modified crossover operator to minimize total tardiness.Chamnanlor et al.[15] adopted a genetic algorithm hybridized ant colony optimization for the problem with time window constraints.Wu et al.[16]applied an improved multi-objective evolutionary algorithm based on decomposition to solve the problem with bottleneck stage and batch processing machines.

In HFSP withHstages,each job is processed in the following sequence:Stage 1,stage 2,···,stageH.If processing time of each job at a stage is significantly longer than its processing time at other stages,then that stage is the bottleneck stage.The bottleneck stages often occur in real-life manufacturing processes when certain stages of the process are slower than others,limiting the overall efficiency of the process[16–21].These stages may arise due to resource constraints,process complexity or other factors.Bottleneck stage is a common occurrence in real-life manufacturing processes,such as seamless steel tube cold drawing production[16],engine hot-test production[20]and casting process[21].More processing resources or times are needed at the bottleneck stage,and the production capacity of the whole shop will be limited because of bottleneck stage.There are some works about HFSP with the bottleneck stage.Costa et al.[17]considered HFSP with bottleneck stage and limited human resource constraint and applied a novel discrete backtracking search algorithm.Shao et al.[18] designed an iterated local search algorithm for HFSP with the bottleneck stage and lot-streaming.Liao et al.[19]developed a new approach hybridizing particle swarm optimization with bottleneck heuristic to fully exploit the bottleneck stage in HFSP.Zhang et al.[20] studied a HFSP with limited buffers and a bottleneck stage on the second process routes and proposed a discrete whale swarm algorithm to minimize maximum completion time.Wang et al.[21] adopted an adaptive artificial bee colony algorithm for HFSP with batch processing machines and bottleneck stage.

As stated above,RHFSP with real-life constraints such as machine eligibility and limited buffer has been investigated;however,RHFSP with bottleneck stage is seldom considered,which exists in real-life manufacturing processes such as seamless steel tube cold drawing production [16].The modelling and optimization on reentrance and bottleneck stage can lead to optimization results with high application value,so it is necessary to deal with RHFSP with the bottleneck stage.

TLBO [22–26] is a population-based algorithm inspired by passing on knowledge within a classroom environment and consists of the teacher phase and learner phase.TLBO[27–31]has become a main approach to production scheduling[32–35]due to its simple structure and fewer parameters.TLBO has been successfully applied to solve RHFSP [11] and its searchability and advantages on RHFSP are tested;however,it is rarely used to solve RHFSP with the bottleneck stage,which is an extension of RHFSP.The successful applications of TLBO to RHFSP show that TLBO has potential advantages to address RHFSP with bottleneck stage,so TLBO is chosen.

In this study,the reentrance and bottleneck stages are simultaneously investigated in a hybrid flow shop,and an elite-class teaching-learning-based optimization(ETLBO)is developed.The main contributions can be summarized as follows: (1) RHFSP with bottleneck stage is solved and a new algorithm called ETLBO is proposed to minimize maximum completion time.(2)In ETLBO,teachers are divided into formal ones and substitute ones.The teacher phase consists of teacher competition and teacher teaching,the learner phase is replaced by reinforcement research of elite class;adaptive adjustment on teachers and classes is applied based on class quality,and class quality is determined by the number of elite solutions in class.(3)Extensive experiments are conducted to test the performances of ETLBO by comparing it with other existing algorithms from the literature.The computational results demonstrate that new strategies are effective and ETLBO has promising advantages in solving RHFSP with bottleneck stage.

The remainder of the paper is organized as follows.The problem description is described in Section 2.Section 3 shows the proposed ETLBO for RHFSP with the bottleneck stage.Numerical test experiments on ETLBO are reported in Section 4.Conclusions and some topics of future research are given in the final section.

2 Problem Description

RHFSP with bottleneck stage is described as follows.There arenjobsJ1,J2,···,Jnand a hybrid flow shop withHstages.StagekhasSk≥1 machinesMk1,Mk2,···,MkSk,and at least one stage exists two or more identical parallel machines.Each job is processedL(L>1)times in the following sequence:Stage 1,stage 2,···,stageH,which means each job is reenteredL-1 times.Each job must be processed in the lastHstages before next processing can begin until itsLprocessings are finished.pikrepresents the processing time of jobJiat stagek.There is a bottleneck stageb,b∈(1,H).pibis often more than about 10×piksuch as casting process[21],k/=b.

There are the following constraints on jobs and machines:

All jobs and machines are available at time 0.

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.

The problem can be divided into two sub-problems:scheduling and machine assignment.Scheduling is applied to determine processing sequence for all jobs on each machine.Machine assignment is used for selecting appropriate machine at each stage for each job.There are strong coupled relationships between these two sub-problems.The optimization contents of scheduling are directly determined by the machine assignment.To obtain an optimal solution,it is necessary to efficiently combine the two sub-problems.

The goal of the problem is to minimize maximum completion time when all constraints are met.

whereCiis the completion time of jobJi,andCmaxdenotes maximum completion time.

An example is shown in Table 1,wheren=5,H=3,L=2,b=2,S1=2,S2=4,S3=3.A schedule of the example withCmax=749 is displayed in Fig.1.denotes the operation in which jobJiis processed for thel-thtime at stagek.

Figure 1: A schedule of the example

Table 1: An example of RHFSP

3 ETLBO for RHFSP with Bottleneck Stage

Some works are obtained on TLBO with multiple classes;however,in the existing TLBO[36–39],competition among teachers is not used,reinforcement search of some elite solutions and adaptive adjustment on classes and teachers are rarely considered.To effectively solve RHFSP with bottleneck stage,ETLBO is constructed based on reinforcement search of elite class and adaptive adjustment.

3.1 Initialization and Formation of Multiple Classes

To solve the considered RHFSP with reentrant feature,a two-string representation is used[12].For RHFSP withnjobs,Hstages andLprocessing,its solution is represented by a machine assignment string [q11,q12,···,q1H×L|q21,q22,···,q2H×L|···|qn1,qn2,···,qnH×L] and a scheduling string[π1,π2,···,πn×H×L],whereπi∈[1,2,···,n],qi((l-1)×H+k)is the machine for thel-thprocessing at stagekfor jobJi.

In scheduling string,the frequency of occurrence isH×Lfor each jobJi.Take jobJ1as an example,wheng

The decoding procedure to deal with reentrant feature is shown below.Start with jobπ1,for each jobπi,decide its corresponding operation,which is processed on a assigned machine forby machine assignment string.

For the example in Section 2,the solution is shown in Fig.2.For jobJ4,a segment of[1,3,2,1,2,2]is obtained from machine assignment string,in the segment,1,3,2 means that operationare processed on machinesM11,M23,M32respectively in the first processing,completion times of three operations are 28,470,482;1,2,2 indicates thatare processed on machinesM11,M22,M32in the second processing,their corresponding completion times are 494,737,749,respectively.A schedule of the decoding as shown in Fig.1.

Figure 2: A coding of the example

Initial populationPwithNsolutions are randomly produced.

The formation of multiple classes is described as follows:

1.Sort all solutions ofPin ascending order ofCmax,suppose thatCmax(x1) ≤Cmax(x2) ≤··· ≤Cmax(xN),first(α+β)solutions are chosen as teachers and formed as a set Ω,and remaining solutions are learners.

2.Divide all learners intoαclasses by assigning each learnerxito classCls(i-1)(modα)+1.

3.Each classClsris assigned a formal teacher in the following way,r=1,repeat the following steps untilr>α:Randomly select a teacher from Ω as the formal teacherofClsr,Ω=,r=r+1.

whereCmax(x)denotes the maximum completion time of solutionx.

The remainingβsolutions in Ω are regarded as substitute teachers,Ω=Teachers are not assigned to classes,and each class consists only of learners.

3.2 Search Operators

Global searchGS(x,y) is described as follows.Ifrand≤0.5,then order-based crossover [12]is done on scheduling string ofxand y;otherwise,two-point crossover [40] is executed on machine assignment string ofxand y,a new solutionzis obtained,ifCmax(z)

Ten neighborhood structuresN1-N10are designed,N1-N5are about scheduling string andN6-N10are related to machine assignment string.N7,N9are the strategies for the bottleneck stage.N1is the swapping of two randomly chosenπiandπj. N2is used to generate solutions by insertingπiinto the position ofπj. N3is shown below.Stochastically chooseJi,Jj,a,b∈[1,L],c,d∈[1,H],determineand their corresponding genesπe,πf,πg,πh,respectively,then swapπe,πfand exchangeπg,πhon scheduling string.Taking Fig.2 as an example,randomly selectJ1,J5,a=1,b=2,c=2,d=3,determineand their corresponding genesπ2=1,π27=1,π7=5,π30=5,then swapπ2=1 andπ7=5,and exchangeπ27=1 andπ30=5.

N4is show below.Stochastically select two genesπjandπkofJi,and invert genes between them.N5is described below.Randomly choose a jobJi,determine its correspondingH×Lgenes and delete them from scheduling string,then for each gene ofJi,insert the gene into a new randomly decided positionkin scheduling string.For the example in Fig.2,randomly select jobJ3and delete its all genesπ8,π11,π14,π20,π23,π26from scheduling string,which becomes[1,1,1,5,2,2,5,5,4,2,2,4,2,4,1,1,2,4,4,4,1,5,5,5],start withπ8,for each gene,insert it into a randomly chosen position on scheduling string,scheduling string finally becomes[3,1,3,1,1,5,3,2,2,5,5,4,2,2,3,4,3,2,4,1,1,2,3,4,4,4,1,5,5,5].

N6is shown as follows.Randomly select a machineqig,determine the processing stagekfor this machine,qig=h,wherehis stochastically chosen from{1,2,···,Sk}qig.N7is similar toN6expect thatqigis the machine at bottleneck stageb.WhenN8is executed,JiandJjare randomly selected,thenqi1,qi2,···,qiH×LofJiandqj1,qj2,···,qjH×LofJjare swapped,respectively.N9has the same steps asN8expect that only swap machines at bottleneck stagebofJiandJj.N10is shown as follows.Stochastically decided a jobJi,w=1,repeat the following steps untilw>H×L:PerformN6forqiw,w=w+1.

N7,N9are proposed for the bottleneck stage due to the following feature of the problem:The new machine of a jobJiat the bottleneck stagebor the swap between machines at bottleneck stagebofJiandJjcan significantly optimize the corresponding objective values with a high probability.

Multiple neighborhood search is executed in the following way.Lett=1,repeat the following steps untilt>10:For solutionx,produce a new solutionz∈Nt(x),ifCmax(z)

3.3 Class Evolution

Class evolution is composed of teacher competition,teacher’s teaching and reinforcement search of elite class.Let Λ=

Teacher competition is described as follows:

Unlike the previous TLBO [40–43],ETLBO has reinforcement search of elite class used to substitute for learner phase.Since elite solutions are mostly composed of teachers and good learners,better solutions are more likely generated by global search and multiple neighborhood search on these elite solutions,and the waste of computational resources can be avoided on interactive learning between those worse learners with bigger

3.4 Adaptive Adjustment on Teachers and Classes

Class quality is determined by the number of elite solutions in class.The qualityCqurof classClsris defined as follows:

Adaptive adjustment on teachers and classes is shown below:

(1) Sort all classes in descending order ofCqur,suppose thatCqu1≥Cqu2≥···≥Cquα,r=1,repeat the following steps untilr>(α-1),swap the best learner inClsrand the worst learner inClsr+1.

In step(1),communication between classesClsrandClsr+1is done to avoid excessive differences among classes in solution quality.In step (2),the best learner can become teacher.In step (3),the formal teacher of each class is adjusted adaptively.Substitute teachers are updated in step (4).The above adaptive adjustment on learners and teachers can maintain high population diversity and make global search ability be effectively enhanced.

3.5 Algorithm Description

The search procedure of ETLBO is shown below:

1.Randomly produce an initial populationPwithNsolutions and divide population intoαclasses.

2.Execute teacher competition.

3.Perform teacher’s teaching.

4.Implement reinforcement search of elite class.

5.Apply adaptive adjustment on teachers and classes.

6.If the termination condition is not met,go to step(2);otherwise,stop search and output the optimum solution.

Fig.3 describes flow chart of ETLBO.

Figure 3: Flow chart of ETLBO

ETLBO has the following new features.Teachers are divided into formal ones and substitute ones.Teacher competition is applied between formal and substitute teachers.Teacher’s teaching is performed and reinforcement search of elite class is used to replace learner phase.Adaptive adjustment on teachers and classes is conducted based on class quality assessment.These features promote a balance between exploration and exploitation,then good results can finally be obtained.

4 Computational Experiments

Extensive experiments are conducted to test the performance of ETLBO for RHFSP with bottleneck stage.All experiments are implemented by using Microsoft Visual C++2022 and run on i7-8750H CPU(2.20 GHz)and 24 GB RAM.

4.1 Test Instance and Comparative Algorithms

60 instances are randomly produced.For each instance depicted byn×H×L,whereL∈{2,3},n∈[10,100],H∈{3,4,5}.IfH=3,thenb=2,Sb=4;ifH=4,thenb=3,Sb=5;ifH=5,thenb=4,Sb=6;ifk/=b,Sk∈[2,4],pik∈[10,20];otherwise,pik∈[200,300].Skandpikare integer and follow uniform distribution within their intervals.

For the considered RHFSP with maximum completion time minimization,there are no existing methods.To demonstrate the advantages of ETLBO for the RHFSP with bottleneck stage,hybrid harmony search and genetic algorithm(HHSGA,[12]),improved dual-population genetic algorithm(IDPGA,[13])and discrete differential evolution algorithm(DDE,[14])are selected as comparative algorithms.

Lin et al.[12] proposed an algorithm named HHSGA for RHFSP with limited buffer to minimize weighted values of maximum completion time and mean flowtime.Tang et al.[13]designed IDPGA to solve RHFSP with missing operations to minimize maximum completion time and energy consumption.Zhang et al.[14]applied DDE to address RHFSP with machine eligibility to minimize total tardiness.These algorithms have been successfully applied to deal with RHFSP,so they can be directly used to handle the considered RHFSP by incorporating bottleneck formation into the decoding process;moreover,missing judgment vector and related operators of IDPGA are removed.

A TLBO is constructed,it consists of a class in which the best solution be seen as a teacher and remaining solutions are students,and it includes a teacher phase and a learner phase.Teacher phase is implemented by each learner learning from the teacher and learner phase is done by interactive learning between a learner and another randomly selected learner.These activities are the same as global search in ETLBO.The comparisons between ETLBO and TLBO are applied to show the effect of new strategies of ETLBO.

4.2 Parameter Settings

It can be found that ETLBO can converge well when 0.5×n×H×Lseconds CPU time reaches;moreover,when 0.5×n×H×Lseconds CPU time is applied,HHSGA,IDPGA,DDE,and TLBO also converge fully within this CPU time,so this time is chosen as stopping condition.

Other parameters of ETLBO,namelyN,α,β,γ,andw,are tested by using Taguchi method[44]on instance 50×4×2.Table 2 shows the levels of each parameter.ETLBO with each combination runs 10 times independently for the chosen instance.

Table 2: Level of the parameters

Fig.4 shows the results of MIN and S/N ratio,which is defined as-10×log10and MIN is the best solution in 10 runs.It can be found in Fig.4 that ETLBO with following combinationN=50,α=3,β=2,γ=0.2,w=2 can obtain better results than ETLBO with other combinations,so above combination is adopted.

TLBO haveNand stopping condition are given with the same settings as ETLBO.All parameters of HHSGA,IDPGA and DDE except stopping condition are obtained directly from [12–14].The experimental results show that those settings of each comparative algorithm are still effective and comparative algorithms with those settings can produce better results than HHSGA,IDPGA and DDE with other settings.

Figure 4: Main effect plot for mean MIN and S/N ratio

4.3 Result and Discussions

ETLBO is compared with HHSGA,IDPGA,DDE and TLBO.Each algorithm randomly runs 10 times for each instance.AVG,STD denotes the average and standard deviation of solutions in 10 run times.Tables 3–5 describe the corresponding results of five algorithms.Figs.5 and 6 show box plots of all algorithms and convergence curves of instance 50×3×3 and 70×5×2.The relative percentage deviation(RPD)between the best performs algorithm and other four algorithms is used in Fig.5.RPDMIN,RPDAVG,RPDSTDare defined:where MIN∗(MAX∗,STD∗)is the smallest MIN(MAX,STD)obtained by all algorithms,when MIN and MIN∗are replaced with STD(AVG)and STD∗(AVG∗),respectively,RPDSTD(RPDAVG)is obtained in the same way.

Table 6 describes the results of a pair-sample t-test,in which t-test(A1,A2)means that a paired ttest is performed to judge whether algorithm A1 gives a better sample mean than A2.If the significance level is set at 0.05,a statistically significant difference between A1 and A2 is indicated by ap-value less than 0.05.

As shown in Tables 3–5,ETLBO obtains smaller MIN than TLBO on all instances and MIN of ETLBO is lower than that of TLBO by at least 50 on 46 instances.It can be found from Table 4 that AVG of ETLBO is better than that of TLBO on 59 of 60 instances and SFLA is worse AVG than ETLBO by at least 50 on 45 instances.Table 5 shows that ETLBO obtains smaller STD than TLBO on 58 instances.Table 6 shows that there are notable performance differences between ETLBO and TLBO in a statistical sense.Fig.5 depicts the notable differences between STD of the two algorithms,and Fig.6 reveals that ETLBO significantly converges better than TLBO.It can be concluded that teacher competition,reinforcement search of elite class and adaptive adjustment on teachers and classes have a positive impact on the performance of ETLBO.

Figure 5: Box plots for all algorithms

Figure 6: Convergence curves of instance 50×3×3 and 70×5×2

Table 3 describes that ETLBO performs better than HHSGA and IDPGA on MIN for all instances.As can be seen from Table 4,ETLBO produces smaller AVG than with the two comparative algorithms on 57 of 60 instances;moreover,AVG of ETLBO is less than that of HHSGA by at least 50 on 26 instances and IDPGA by at least 50 on 48 instances.Table 5 also shows that ETLBO obtains smaller STD than the two comparative algorithms on 49 instances.ETLBO converges better than HHSGA and IDPGA.The results in Table 6,Figs.5 and 6 also demonstrate the convergence advantage of ETLBO.

Table 3: Computational results of five algorithms on MIN

Table 4: Computational results of five algorithms on AVG

Table 5: Computational results of five algorithms on STD

Table 6: t-test result of the algorithm

It can be concluded from Tables 3–5 that ETLBO performs significantly better than DDE.ETLBO produces smaller MIN than DDE in all instances,also generates better AVG than DDE by at least 50 on 45 instances and obtains better STD than or the same STD as DDE on nearly all instances.ETLBO performs notably better than DDE,and the same conclusion can be found in Table 6.Fig.5 illustrates the significant difference in STD,and Fig.6 demonstrates the notable convergence advantage of ETLBO.

As analyzed above,ETLBO outperforms its comparative algorithms.The good performance of ETLBO mainly results from its teacher competition,reinforcement search of elite class and adaptive adjustment on teachers and classes.Teacher competition is proposed to make full use of teacher solutions,reinforcement search of elite class performs more searches for better solutions to avoid wasting computational resources,adaptive adjustment on teachers and classes dynamically adjusts class composition according to class quality,as a result,which can effectively prevent the algorithm from falling into local optima.Thus,it can be concluded that ETLBO is a promising method for RHFSP with bottleneck stage.

5 Conclusions and Future Work

This study considers RHFSP with bottleneck stage,and a new algorithm named ETLBO is presented to minimize maximum completion time.In ETLBO,teachers are divided into formal teachers and substitute teachers.A new teacher phase is implemented,which includes two types of teachers’competition and teaching phases.Reinforcement search of the elite class is used to replace the learner phase.Based on class quality,adaptive adjustment is made for classes and teachers to change the composition of them.The experimental results show that ETLBO is a very competitive algorithm for the considered RHFSP.

In the near future,we will continue to focus on RHFSP and use other meta-heuristics such as artificial bee colony algorithm and imperialist competitive algorithm to solve it.Some new optimization mechanisms,such as cooperation and reinforcement learning,are added into metaheuristics are our future research topics.Fuzzy RHFSP and distributed RHFSP are another of our directions.Furthermore,the application of ETLBO to deal with other scheduling problems is also worthy of further investigation.

Acknowledgement:The author would like to thank the editors and reviewers for their valuable work,as well as the supervisor and family for their valuable support during the research process.

Funding Statement:This research was funded by the National Natural Science Foundation of China(Grant Number 61573264).

Author Contributions:The authors confirm contribution to the paper as follows:study conception and design:Deming Lei,Surui Duan;data collection:Surui Duan;analysis and interpretation of results:Deming Lei,Surui Duan,Mingbo Li,Jing Wang;draft manuscript preparation:Deming Lei,Surui Duan,Mingbo Li,Jing Wang.All authors reviewed the results and approved the final version of the manuscript.

Availability of Data and Materials:Data supporting this study are described in the first paragraph of Section 4.1.

Conflicts of Interest:The authors declare that they have no conflicts of interest to report regarding the present study.