An Improved Harris Hawk Optimization Algorithm for Flexible Job Shop Scheduling Problem

Zhaolin Lv ,Yuexia Zhao ,Hongyue Kang ,Zhenyu Gao and Yuhang Qin

1College of Systems Engineering,National University of Defense Technology,Changsha,410073,China

2College of Information Management,Nanjing Agricultural University,Nanjing,210031,China

3Department of Intelligent Supply Chain,JD Logistics,Beijing,100076,China

4College of Intelligent Science and Technology,National University of Defense Technology,Changsha,410073,China

ABSTRACT Flexible job shop scheduling problem (FJSP) is the core decision-making problem of intelligent manufacturing production management.The Harris hawk optimization(HHO)algorithm,as a typical metaheuristic algorithm,has been widely employed to solve scheduling problems.However,HHO suffers from premature convergence when solving NP-hard problems.Therefore,this paper proposes an improved HHO algorithm(GNHHO)to solve the FJSP.GNHHO introduces an elitism strategy,a chaotic mechanism,a nonlinear escaping energy update strategy,and a Gaussian random walk strategy to prevent premature convergence.A flexible job shop scheduling model is constructed,and the static and dynamic FJSP is investigated to minimize the makespan.This paper chooses a twosegment encoding mode based on the job and the machine of the FJSP.To verify the effectiveness of GNHHO,this study tests it in 23 benchmark functions,10 standard job shop scheduling problems(JSPs),and 5 standard FJSPs.Besides,this study collects data from an agricultural company and uses the GNHHO algorithm to optimize the company’s FJSP.The optimized scheduling scheme demonstrates significant improvements in makespan,with an advancement of 28.16%for static scheduling and 35.63%for dynamic scheduling.Moreover,it achieves an average increase of 21.50%in the on-time order delivery rate.The results demonstrate that the performance of the GNHHO algorithm in solving FJSP is superior to some existing algorithms.

KEYWORDS Flexible job shop scheduling;improved Harris hawk optimization algorithm(GNHHO);premature convergence;maximum completion time(makespan)

1 Introduction

Consumers’demand patterns are changing due to the rapid development of globalization and a shift in customer consumption consciousness.The demand of the whole market has gradually evolved from the previous state of few varieties and large quantities to a state where customers require small and medium-sized batches,more variety,high product quality,and short delivery time requirements[1].There is an urgent need for manufacturing enterprises to achieve high efficiency,high quality,and flexibility and enhance enterprise competitiveness with low-cost manufacturing.With the advancement of technology,information technology has brought new convenience to the development of companies[2,3].Intelligent manufacturing is the primary trend and key to the development of the manufacturing industry[4].Job shop scheduling problem(JSP)is a core decision-making problem of intelligent manufacturing production management.The flexible job shop scheduling problem(FJSP)is an extension of the classical JSP which comprises two sub-problems: machine assignment and operation sequencing.Machine assignment involves selecting a machine from a candidate set for each operation,while operation sequencing deals with scheduling all operations on all machines to create satisfactory schedules.The FJSP is a classical NP-hard problem whose application fields are extremely broad [5].The scheduling scheme optimization aims to reduce the maximum completion time (makespan) [6] or reduce the production cost.An efficient scheduling scheme can shorten the production cycle,reduce production costs,and facilitate adaptation to complex markets[7].

With the improvement of intelligence level,companies need to change their traditional ways of operating and implement smart manufacturing,including intelligent production processes and decision-making [8].Therefore,it is essential to use intelligent algorithms to solve the FJSP.Some studies have utilized intelligent algorithms to solve the FJSP and its variants.Zhang et al.[9]solved the reconfigurable distributed flowshop group scheduling problem using an iterated F-Race algorithm.Experimental results demonstrate significant advancement in solution accuracy and efficiency compared to other heuristics.Lu et al.[10] tackled the energy-efficient scheduling of distributed flow shops with heterogeneous factories,considering permutation and hybrid flow shops.A hybrid multi-objective optimization algorithm is proposed and it outperforms six advanced benchmark algorithms in a real-world example.The Harris hawk optimization (HHO) [11] algorithm is a novel bionic swarm intelligence optimization algorithm inspired by hawks’predatory behavior.Due to its fewer parameters,high efficiency,and ease of implementation,it has captured the attention of many researchers and has been used in several fields[12].Several literatures have used the HHO algorithm to solve the JSP.Liu [13] proposed an enhanced HHO algorithm (IHHO) for the shortcomings of HHO,which has blind search during the global search.Experimental results for the JSP showed that IHHO outperformed other compared algorithms.Choo et al.[14] proposed an integrated HHO (EN-HHO) to solve the multi-objective flexible job shop scheduling problem (MOFJSP).Jouhari et al.[15]used the modified HHO(MHHO)to solve the problem of unrelated parallel machine scheduling.Amer et al.[16]proposed an improved elite learning HHO(ELHHO)to address the multiobjective scheduling problem,and the experimental results demonstrated that the proposed ELHHO method could yield better results than other algorithms.Attiya et al.[17] proposed an improved HHO algorithm based on simulated annealing (SA) called HHOSA for job scheduling in a cloud environment.Experimental results showed that the proposed HHOSA can significantly reduce the makespan of job scheduling.However,these researchers do not apply the HHO algorithm to solve the classical FJSP and do not consider its application in the real manufacturing process.Furthermore,the current research on the HHO algorithm has found that it has the same dilemma as other intelligent algorithms,that is,it will appear a premature convergence problem when solving some more complex issues[18–20].Additionally,since global exploration is only conducted in the first half of the iteration,it is challenging to balance the capabilities of global exploration and local exploitation using the escaping energy of prey.Table 1 compares related work on job shop scheduling to highlight the differences between our work and the existing research.

Table 1:Comparison of related works on job shop scheduling

In this paper,we propose an improved Harris hawk optimization algorithm(GNHHO)to solve the FJSP,which introduces an elitism strategy,a chaotic mechanism,a nonlinear escaping energy update strategy,and a Gaussian random walk strategy to prevent premature convergence.Specifically,GNHHO prevents the algorithm from premature convergence by replacing the optimal solution,adding a perturbation to the parameterr,proposing a nonlinear method to update the escaping energyE,and using a Gaussian random walk strategy to generate new individuals.Furthermore,this paper utilizes the tent mapping mechanism to add perturbation for the parameterrand introduces a cosine function to adjust the step size of the Gaussian random walk.Our objective is to minimize the makespan and we choose a two-segment encoding mode based on the job and the machine of the FJSP.By comparing the proposed GNHHO algorithm with the HHO algorithm on 23 functions,we verify the effectiveness of the GNHHO algorithm.This study then uses the GNHHO algorithm to solve the 10 standard JSPs and 5 Brandimarte FJSP standard examples.The results demonstrate that the performance of the GNHHO algorithm in solving JSP and FJSP is superior to some existing algorithms.We then collect data from an agricultural company and use the GNHHO algorithm to optimize the company’s job shop scheduling whose objective is to minimize makespan.The company has the characteristics of multiple varieties,small batches,and flexible working.The production job shop of the company is a flexible job shop,which is in line with the FJSP that we aim to solve through the proposed method.In addition,the actual data of the company can be used to deal with some special cases of scheduling problems,and the change of order delivery rate can be further analyzed.The final results are expressed in the form of a Gantt chart[21].By comparing the scheduling schemes before and after optimization,the optimized scheduling scheme could advance the makespan by 28.16% and 35.63% for static and dynamic scheduling,respectively,with an average increase of 21.50% in the order delivery rate on time.

The main contributions of this paper are as follows:

(1)This paper addresses a real-world enterprise problem where static scheduling orders have low delivery rates and dynamic scheduling cannot respond to the change of customer demands in time.

(2) This paper proposes a GNHHO algorithm that introduces an elitism strategy,a chaotic mechanism,a nonlinear escaping energy update strategy,and a Gaussian random walk strategy to prevent premature convergence.

(3)The experimental results indicate that our proposed GNHHO algorithm is better than some existing algorithms.It can advance the makespan by 28.16% and 35.63% for static and dynamic scheduling,respectively while also increasing the order delivery rate by 21.50%.

The paper is organized as follows.Section 2 summarizes the research methodology.Section 3 demonstrates an improved HHO algorithm for FJSP.Section 4 shows the experiment and analysis.The paper is concluded in Section 5.

2 Research Methodology

This section describes the constructed flexible job shop scheduling model.Section 2.1 introduces the FJSP.Section 2.2 provides a detailed description of the model.

2.1 Problem Description

For a job shop in production job shops,there areNjobs{J1,J2,···Ji,···,JN}to be processed,and there areMmachines in a production workshop.Jobicontainsaioperations.The data information we can learn is the time of each production operation.We need to choose different machines for these operations and determine the start time of the processing to achieve the optimal goal,which means that it minimizes makespan.For the FJSP,some basic assumptions should be satisfied:

(1) Before the operation behind the same jobs starts,all the previous operations have been processed.

(2)There is no specific requirement for the processing sequence of different jobs.

The meanings of notations to be used in this paper are shown in Table 2.

2.2 Modeling

This study selects the model’s objective function to minimize the makespan,ensuring that a job shop can complete its task as quickly as possible.The objective function is defined by Eq.(1).

whereTis the corresponding time when the processing of jobiis completed.The constraints are as follows:

Eq.(2)represents the makespan of any job must be less than or equal to the makespan of all jobs.Eq.(3)is the constraint on processing operation.Specifically,Xijmis a 0–1 variable that is 1 if operationjof jobiis processed on machinem,and 0 otherwise.Eqs.(4)and(5)symbolize when processing jobs,only one operation can be performed simultaneously on the same equipment.Specifically,Yi(j+1)hlmis a 0–1 variable that is 1 if the operationjof jobiprecedes the operationlof jobhon machinem.Eq.(6)limits that an operation can only be processed once by a machine.Eq.(7)represents an operation that can only choose one machine to process.Eq.(8)represents the sequence constraint of the operations.Eqs.(9)and(10)indicate that the parameter variable must be no less than 0.

3 Improved HHO Algorithm for Flexible Job Shop Scheduling Problem

This section describes the improved HHO algorithm for the FJSP.The HHO algorithm is presented in Section 3.1,and an improved algorithm is proposed in Section 3.2.The proposed GNHHO algorithm is designed to solve the FJSP in Section 3.3.

3.1 HHO Algorithm

Harris hawks can switch various chasing modes according to the dynamic changes of the capture environment they face and the escape mode of the prey [22].Based on this,the HHO algorithm is developed by mathematically simulating this behavior and the raiding method.

1.Exploration stage

In the algorithm,the hawk’s position is determined by two different methods based on the locations of the other hawks and the rabbit at the time of the kill,with equal probability.It can be defined by Eq.(11):

whereX(t+1)is the position of the hawk after thetiterations andX(t)is the location of the hawk at the moment t.Xrabbit(t)represents the location of the rabbit,andr1,r2,r3,r4andqare random numbers whose ranges are(0,1).The variables’range is determined by the values oflbandub,andXrand(t)is the randomly chosen hawk position.Xm(t)=,whereXmis the average position of the current hawk group andXirepresents the position of each hawk.Qdenotes the total number of hawks.

2.The transition between exploration and exploitation

In the process of running away,the rabbit’s energy will be significantly reduced.We call it the escaping energy of the preyE.It can be defined by Eq.(12):

whereE0is the initial value of energy,which is a random number,and the range is (-1,1).Tis the maximum number of iterations.The exploration stage is carried out at|E|≥1.

3.Exploitation stage

At this stage,the Harris hawk has concluded the exploration stage and has detected the location of the target prey(rabbit).The HHO lists four possible scenarios depending on how the prey escapes and the hawk hunts.Assuming thatris the probability of determining whether the prey can escape,r<0.5 means the rabbit can avoid the hawk’s capture.Otherwise,the prey cannot escape.When|E|≥0.5 andr≥0.5,the Harris hawks only need to surround the rabbit to capture it softly.When|E|<0.5 butr≥0.5,the Harris hawks directly adopt a hard besiege raid on the rabbit.When|E|≥0.5 butr<0.5,the Harris hawks need to employ a wittier soft surrounding with progressive quick dives.When|E|<0.5 andr<0.5,the Harris hawks will take the hard besiege with a progressive rapid dive strategy.

3.2 Improved HHO Algorithm

As an intelligent algorithm,the HHO algorithm requires fewer parameters than other algorithms and possesses strong global exploration capabilities.However,it may also encounter the problem of premature convergence when dealing with more complex issues.Therefore,this paper takes some measures to improve the HHO algorithm to solve the problem of premature convergence.

1.Introducing an Elitism Strategy

In order to improve the global search ability of the algorithm and avoid the decrease of population diversity in the later stages of iteration,an elitism strategy (elitist preservation strategy) [23] is introduced.Considering enhanced communication between the optimal and suboptimal solutions during the iteration,we choose two optimal positions to replace the optimal solution which can better guide the hawks to prey.

whereXjbestandf(Xjbest)mean the dominant individual and its fitness value.

2.Introducing a Chaotic Mechanism

The tent mapping system[24]has the characteristics of randomness and regularity which makes the algorithm easy to jump out of local optima,so it is often used to increase the perturbation of the algorithm or generate the initial population.Fig.1 depicts the scatter plot and the sequence distribution histogram of the tent mapping,in which the maximum number of iterations is 500.From Fig.1,it can be seen that the tent mapping is random and evenly distributed.Therefore,this paper uses this tent mapping mechanism to add perturbation to the parameterrin HHO to make its change more volatile.

The formula for calculatingris as follows:

Figure 1:The scatter plot and the histogram of the tent mapping

3.Introducing a Nonlinear Escaping Energy Update Strategy

In the HHO algorithm,the transition of the algorithm from the exploration stage to the exploitation stage is controlled by theE.However,the update ofEchanges linearly,which means that if the algorithm enters the second half of the iteration,it will only perform local development and search.At this point,the algorithm easily falls into the local optimization.Therefore,a nonlinear method is proposed to update the escaping energyE.

wherekis related to the number of decreasing cycles of the escaping energy.In our study,it is determined by grid search,which is searched in the scope of[0,15].Experimental results demonstrate that the algorithm achieves optimal exploration and exploitation performance whenk=5.And when the value ofkwas set to 5,it generated the most optimal solutions and exhibited superior convergence speed when solving various benchmark functions.Therefore,it is concluded that the optimal value for the parameterkwould be 5.To provide a clearer visualization of the effect of the proposed nonlinear escaping energy update strategy,Fig.2 displays the relationship between the escaping energy and the number of iterations for HHO and GNHHO.Fig.2 shows that compared with the linear variation of the escaping energyE,the periodic trend ofE1 towards 0 reflects that the hawk is approaching and capturing the prey according to the probability.Therefore,this enables multiple rounds of global and local optimization searches.

4.Introducing a Gaussian Random Walk Strategy

During successive iterations of the algorithm,we consider that if the computation finds that the mean value of the dominant population has not changed twice,and this happens continuously,then we determine that the algorithm is stalled at this iteration.To overcome the issue of falling into stagnation and improve exploration abilities,we utilize the Gaussian random walk strategy [25] to generate new individuals.The random walk strategy introduces a probabilistic model that imitates the random movement of organisms in nature.It has been widely utilized in the design and enhancement of several optimization algorithms.It can efficiently address the challenge of falling into local optima by injecting randomness and diversifying the search process.

whereX?(t) is a randomly selected individual from the dominant population,and a cosine function continuously adjusts the random step size.In this way,it can be realized that relatively large disturbances can be generated in the population in the early stage,and the disturbances in the later stage will be reduced.

Figure 2:Comparison of escaping energy for HHO and GNHHO

In general,we adopt four strategies which introduce an elitism strategy,a chaotic mechanism,a nonlinear escaping energy update strategy,and a Gaussian random walk strategy to improve the HHO algorithm,and the pseudo-code of the improved HHO algorithm is displayed in the Algorithm 1.

3.3 GNHHO for the Flexible Job Shop Scheduling Problem

3.3.1 Encoding and Decoding of Algorithm

The original HHO algorithm was initially developed for tackling successional optimization problems,while the FJSP represents a discrete optimization problem.Therefore,it becomes crucial to establish a transitional mechanism between the HHO and the FJSP.In this paper,we introduce a two-segment encoding and decoding mechanism to solve this problem.The coding strategy adopted in this paper is a two-segment coding method that considers the operation and machine selection.It represents a set of feasible solutions with X=[Xg|Xj],where the vector Xgrepresents the selection method of the machine and the vector Xjrepresents the processing sequence of the operation.The position vector of the Harris hawks in the HHO algorithm is expressed by a 2l-dimensional vector of real numbers,X={x1,x2,···,xl,xl+1,···,x2l},wherelis the number of all operations in the FJSP to be solved,and the element X of the vector is the real number between[-N,N].The two-segment encoding method is shown in Table 3.

Table 3 Meaning of two-segment encoding mode

Suppose a job shop needs to process 3 jobs,each job has 2 operations,and there are 3 optional machines,then the total length of the position vector is 12,and the value range is between[-3,3].The first step is based on the selection of the machine,assuming that a set of codes that exist at this time is[2 1 2 3 1 3],then this corresponds to the operation sequence and is selected for processing on the corresponding machine.At this time,this group of codes means that the machine selection order is machine 2,machine 1···,and machine 3 for the operation sequence{O11O12O21O22O31O32}.Then,the encoding method is to encode at the operation level.For example,it can be assumed that a code is[1 2 3 2 1 3]based on the operation.The number represents the serial number of the job to be processed,and the number of digits in this group of codes represents the number of all operations in all the jobs.The sequence of the numbers represents the order in which the machine operations these operations,and the length of the code represents the total number of operations after the decomposition of the order.Taking this code as an example,it is 1,2,3,and means that there are 3 jobs,of which there are 6 numbers,representing 6 operations that need to be processed.That is,the processing sequence of the operation is operation 1 for job 1,operation 1 for job 2···,and operation 2 for job 3.This is a feasible set of operation scheduling schemes.

Then,we need to convert the given position vector X to the machine selection(MS)vector Xgand the operation sequence(OS)vector Xj.We adopted the method of[26]and used Eq.(18)to convert individual position vector X into corresponding numbers,which could be selected and assigned by machine sets.It can be defined by Eq.(18):

whereround(x) is the function that setsxto the nearest integer andyjrepresents the serial number of the machine assigned by operationjin the machine set of available machines for operationjand.Then,xjis the vector value ofjandsjrepresents the number of available machines for operationj.

In the conversion of the process sequence vector,first place the elements of the position vector Xjin the process order{Oi1Oi2,···,Oij}.Then sort in descending order by the size of the element value,and replace the number of each operation with the job number it belongs to.Fig.3 is an example of converting a position vector Xjinto an operation sequence vector.

Figure 3:The conversion from the position vector to the operation sequence vector

The decoding part can be understood as the inverse operation of encoding.The inversion of Eq.(18) can be used to calculate the transformation of position vectors to scheduling schemes.It means that the real value is converted into an integer value,and then calculate the objective function value for decoding.When the individual position vector is converted into a scheduling scheme,the Ranked Order Value (ROV) rule [27] is used to rank operations.First,each individual is sorted according to the ascending order of the position vector values.In this way,the ROV value is determined,and the sequence of operations is obtained according to the corresponding ROV value.Table 4 shows the correspondence between individual location information and operation sequence.

Table 4:The relationship between location information and operation sequence

3.3.2 Population Initialization

The effectiveness of the initial swarm directly impacts the optimization result of the metaheuristic algorithm.To enhance the algorithm’s capability,specific strategies can be employed to improve the original swarm.In this paper,a two-segment coding mechanism is applied,which involves separate swarm initialization for the machine selection and operation sequence segments.For the initialization of machine selection,two different machine selection rules are adopted,global selection [28] and random selection.Global selection can reduce the makespan and improve the load balance of machines.The specific method is to set an array of the same length as the number of machines,and each value of the array corresponds to the processing time of the corresponding machine.The proportion of using the two machine rules is 0.7 and 0.3.Next,randomly select a job,starting from the first operation,and add the processing time of the selected machine for the current operation to the corresponding position in the array.Then select the machine with the shortest processing time as the processing machine and keep the time at the corresponding position in the array.Repeat similar operations until the machine selection for all operations is complete.The purpose of random selection is to maintain the diversity of the initial solutions of the population.For the initialization of the operation sequence,a set of operation sequence schemes is generated randomly.Finally,these schemes are then combined with the machine selection segment to produce various scheduling schemes.

3.3.3 Local Search Strategy

In this paper,when a scheduling scheme is obtained,we can use the neighborhood structure as a local search strategy to seek a better one close to the optimal one to prevent local optima[29].This study performs the local search in the following four ways:

(1)For the neighborhood structure N1:randomly select two different operations in the existing scheduling scheme to exchange.

(2) For the neighborhood structure N2: randomly select two adjacent operations and exchange their sequences.Fig.4 illustrates the neighborhood structure of N2.

(3)For the neighborhood structure N3:randomly select two different operations in the preferred scheduling plan and then invert all the operations contained between these two operations.

(4)For the neighborhood structure N4:randomly select a contiguous sequence of operations as a block,similarly select another contiguous sequence of operations as a block,and then switch the operations of these two blocks.

The specific strategy is to use the first way to obtain a new solution.The objective function value is calculated after the exchange,and compared with the objective function values before the exchange,leaving the solution with the smaller objective function value and updating it.After that,continue to implement the first way,and set a critical value as the basis for judgment if there is no better solution when more than the critical value,the next local search way is performed.

Figure 4:The neighborhood structure of N2

3.3.4 Algorithm Design for the Flexible Job Shop Scheduling Problem

After describing the algorithm’s encoding and decoding approach and the local search strategy for the FJSP,we explained in detail how to use the proposed GNHHO algorithm to solve FJSP.In the GNHHO algorithm for the FJSP,the positions of the hawks denote the common candidate solutions,excluding the global optimum.The location of the prey represents the global optimal solution,which is the best scheduling scheme for FJSP.By employing the GNHHO algorithm,each candidate solution obtained represents a specific scheduling scheme.The objective is to obtain the optimal solution,which corresponds to the best flexible job shop scheduling scheme,by optimizing these candidate solutions using the GNHHO algorithm.The specific steps for solving FJSP using the proposed GNHHO algorithm are as follows:

Step 1.Set the parameters,including the number of jobsN,the number of machinesM,and the maximum number of iterationsT,and then generate a set of initial feasible solutions using the global selection and random selection.

Step 2.Generate the initial location of hawks and calculate the fitness value.Then decide the current best scheduling scheme by introduced elitism strategy.

Step 3.The value of the proposed nonlinear escaping energyE1 and introduced modifiedris calculated,and the nonlinear escaping energy update strategy proposed by GNHHO is utilized to regulate global exploration and local exploitation.

Step 4.Select the processing sequence of the optimal operation obtained in the exploration process,and then search for a better solution(processing sequence)by four local search strategies.

Step 5.Assess the algorithm’s stagnation and employ the introduced Gaussian random walk strategy to update the population.

Step 6.Determine whether the algorithm reaches the maximum number of iterationsT.If it does,output the optimal scheduling scheme.Otherwise,repeat steps 2–5.

The flowchart of the GNHHO algorithm is presented in Fig.5.

4 Experiment and Analysis

In this section,we use a set of benchmark datasets to evaluate the performance of the GNHHO.After that,we use GNHHO to solve the FJSP of companyA.Some famous FJSP benchmarks are employed to verify the effectiveness of GNHHO in Section 4.1.Section 4.2 utilizes the GNHHO algorithm to address the FJSP of companyA.

The experiments were run on a Windows 10 Ultimate 64-bit operating system PC and performed with MATLAB R2017a.To ensure the rationality and credibility of the experimental results,the population sizeQof 30 is uniformly adopted for all algorithms,while the maximum number of iterationsTis set to 200.Other parameter settings of the algorithm are shown in Table 5.

Figure 5:Flowchart of the GNHHO algorithm for FJSP

Table 5:Parameter settings

Table 7:Results for brandimarte examples

4.1 Tests of GNHHO Algorithm for Solving Scheduling Problems

This study uses HHO[30],GA[31],PSO[32],GWO[33],WOA[34]and GNHHO to solve the 10 examples from the standard test library JSPlib [35] and the 5 cases from the Brandimarte FJSP standard examples [36].The parameter settings of each algorithm are shown in Table 5.The other experimental parametersQandTare the same as in the previous experiment settings.We ran each algorithm 20 times independently.The results are shown in Tables 6 and 7,which list the example names,the problem sizes(NandM),the best-known solutions(BKS),the best results(Best),and the average results(Ave)obtained by existing algorithms and our proposed algorithm.

Based on the data presented in Tables 6 and 7,it can be observed that the GNHHO algorithm yields results closer to the actual value than other algorithms in 15 randomly selected computational examples.From Tables 6 and 7,we can see that the best and mean values of GNHHHO are better than those of other algorithms,which makes its optimization performance rank first.The value of the fitness in Fig.6 represents the makespan of the experimental examples.From Fig.6,we can see that the fitness of GNHHO is comparatively lower than other algorithms and has a faster convergence speed,indicating that GNHHO can quickly achieve a lower makespan.The reason is that the guidance of elite individuals can enhance the likelihood of GNHHO discovering superior candidate solutions.The nonlinear escaping energy updating strategy can effectively address the issue of transitioning into local search during the latter half of iterations.And the introduced Gaussian random walk strategy can mitigate the stagnation.The introduced four strategies can make the algorithm jump out of the local optimum and increase the ability of exploration and exploitation,which makes the algorithm faster to obtain better solutions.Also,the initial fitness value of GNHHO is 58,which is lower than other algorithms,showing that GNHHO is able to generate better initial solutions.This can be attributed to the incorporation of global selection and random selection methods for initialization in GNHHO,making it possible to find better initial solutions.However,the benchmark algorithms in our study have similar shortcomings,such as low convergence accuracy,falling into local optimization easily,and slow convergence speed leading to poor experimental results.

Figure 6:The convergence curves of FT06

Fig.7 compares the makespan of HHO and GNHHO,taking MK04 as an example.It can be seen from Fig.7 that GNHHO can find better solutions faster than HHO.In specific,the algorithm falls into a local optimum at the 6th and 13th iterations but is able to reach a lower makespan at the 12th and 16th.It demonstrates that the GNHHO algorithm can jump out of local optima compared with HHO because of the update strategy we introduced in HHO.

Fig.8 shows the Gantt charts of the scheduling results solved by HHO and GNHHO.The horizontal coordinates of the Gantt chart represent time,while the vertical coordinates represent the machine.From Fig.8,it is clear that GNHHO can produce better results than HHO.The makespan for this example has been reduced from 57 to 49.Therefore,it is clear that the GNHHO algorithm outperforms the HHO algorithm in handling the FJSP.This can reflect the better performance of the GNHHO algorithm in solving FJSP problems.

4.2 Solving Flexible Job Shop Scheduling Problems for Company A

4.2.1 Problem Analysis of Company A

CompanyAhas the characteristics of multiple varieties,small batches,and flexible working.It can be found that the order on-time delivery rate of companyAis at a relatively low level.Table 8 and Fig.9 show the order delivery rate of companyAfor each quarter of 2019–2021,where 19-1 is for the first quarter of 2019,and the other meanings are similar.

Figure 7:Comparison of HHO and GNHHO results

Figure 8:(Continued)

Table 8:Quarterly order delivery rate of company A in 2019–2021

Figure 9:Order delivery rate of company A in 2019–2021 Quarterly

From the data information shown in Table 8 and Fig.9,it can be found that,on average,only 69.92%of the orders can be delivered on time.The highest on-time submission rate for orders is only 76%.This will reduce profits and significantly reduce customer satisfaction due to delayed orders.It can be revealed that the scheduling plan of companyAis developed using manual preparation based on the staff’s experience,resulting in the long makespan,which ultimately led to low order delivery rates.Therefore,this paper uses the GNHHO algorithm to solve the FJSP of companyA.

4.2.2 Static Scheduling for Company A

In one order,a total of 11 jobs need to be processed by decomposing the order,and these jobs have a capacity of 96 operations for companyA.CompanyAuses the GNHHO algorithm to solve the FJSP.The solution result is shown in Fig.10.The makespan is 125 hours.

Figure 10:Gantt chart of static scheduling

Using the original manual scheduling scheme,the makespan is 174 hours.Therefore,the proposed GNHHO algorithm can shorten the makespan and help improve the order delivery rate.

4.2.3 Dynamic Scheduling for Company A

1.Dynamic adjustment strategy

Considering that companyAwill encounter various uncertain factors when carrying out production,particularly the uncertainty of the order.A dynamic event occurs att=37 hours.That is the demand for jobs increases.Under the influence of emergency order insertion,enterprises can adopt a rearranging strategy[37],which uses some intelligent algorithms to adjust the original scheduling when a new order is inserted.All the remaining orders and this inserted order are used as new production tasks to be re-formulated.This strategy allows most orders to be completed on time.When companyAfaces an urgent insertion order,the goal of dynamic adjustment is to minimize the makespan after adjustment.

2.Results of dynamic scheduling

When a dynamic event occurs at 37 h,we adopt a rearranging strategy to minimize the makespan after adjustment.Fig.11 shows the new Gantt chart,and the makespan is 141 h.It is clear that the rescheduling schedule obtained by the GNHHO algorithm requires a much lower makespan than the company’s original manual schedule,which required 203 h.The rearranging strategy is implemented to replace the initial strategy,which can respond to order changes more effectively.

Figure 11:Gantt chart of the optimal scheduling after dynamic adjustment

4.2.4 Results Analysis

1.Comparison of order completion time

Table 9 and Fig.12 show the specific data comparison of makespan.It shows that the optimized scheduling scheme can advance the makespan by 28.16% and 35.63% for static and dynamic scheduling,respectively.The reason is that the GNHHO algorithm introduces four strategies to jump out of the local optimum.This can demonstrate the effectiveness of the GNHHO algorithm in solving FJSP problems.The reduction of makespan is the basis for companyAto achieve on-time delivery of orders.

Figure 12:Comparison of makespan for static scheduling and dynamic scheduling

Table 9:Comparison of company A’s static and dynamic scheduling optimization

2.Comparison of order delivery rate

Based on the analysis that the optimized scheme can shorten the makespan of the order,this paper explores how the order delivery rate changes after optimization.We use the GNHHO algorithm to address the FJSP of companyAfor each quarter of 2021 and compare the new delivery time with the delivery time required by historical orders.The results are demonstrated in Table 10 and Fig.13.Table 10 shows that the optimization rates for the four quarters are 24.50%,20%,23%,and 18.50%,respectively,because the GNHHO algorithm can obtain better solutions for FJSP.The data show an average 21.5% improvement in order delivery rates,which means that the optimized scheduling scheme can better solve the problem of the low delivery rate of orders of companyA.Overall,the proposed GNHHO algorithm exhibits remarkable robustness,excellent optimization performance,and rapid convergence speed,which can effectively address the FJSP.Consequently,this can further promote the improvement of order delivery rates.

Figure 13:Comparison of the order delivery rate of the company A

5 Conclusion and Future Work

In this paper,we construct a flexible job shop scheduling model and propose a GNHHO algorithm to solve it.After verifying the effectiveness of the GNHHO algorithm by using benchmark test functions and standard JSP and FJSP examples,we use the algorithm to solve the FJSP of companyA.According to the experimental results,the optimized scheduling scheme demonstrates significant improvements in makespan,with an advancement of 28.16% for static scheduling and 35.63% for dynamic scheduling.Moreover,it achieves an average increase of 21.50% in the on-time order delivery rate.By comparing with previous studies,the GNHHO prevents the algorithm from premature convergence by replacing the optimal solution,adding a perturbation to the parameterr,proposing a nonlinear method to update the escaping energyE,and using a Gaussian random walk strategy to generate new individuals.The proposed GNHHO algorithm can solve FJSP efficiently.

In future research,we will focus on two aspects:Firstly,we aim to achieve a better balance between exploration and exploitation in the HHO algorithm by introducing four strategies,which increase the algorithm’s complexity.Additionally,we plan to study other parameter tuning methods for further enhancement.Moreover,exploring alternative search strategies is expected to improve the overall effectiveness of the HHO algorithm.Secondly,our current paper on the FJSP problem has certain limitations as it does not consider uncertainties such as machine failures.For future work,we propose investigating and incorporating these uncertainties into the problem formulation to provide a more comprehensive and realistic analysis.

Acknowledgement:This research did not receive any specific grant from funding agencies in the public,commercial,or not-for-profit sectors.

Funding Statement:The authors received no specific funding for this study.

Author Contributions:The authors confirm contribution to the paper as follows: conceptualization:Zhaolin Lv and Yuexia Zhao;methodology: Zhaolin Lv;software: Zhaolin Lv;resources: Yuexia Zhao;writing—original draft preparation:Zhaolin Lv and Yuhang Qin;writing—review and editing:Zhaolin Lv and Hongyue Kang;supervision:Zhenyu Gao;project administration:Yuexia Zhao.All authors reviewed the results and approved the final version of the manuscript.

Availability of Data and Materials:The datasets used in the paper are benchmark and public datasets,which can be easily downloaded from the Internet.Other enterprise data was obtained from the company Bodeau Agricultural Company and are available from the authors with the permission of the company Bodeau Agricultural Company.

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