Abstract
Combining the harmony search algorithm (HS) with the local search algorithm (LS) can prevent the HS from falling into a local optimum. However, how LS affects the performance of HS has not yet been studied systematically. Therefore, in this paper, it is first proposed to combine four frequently used LS with HS to obtain several search algorithms (HSLSs). Then, by taking the flexible job-shop scheduling problem (FJSP) as an example and considering decoding times, study how the parameters of HSLSs affect their performance, where the performance is evaluated by the difference rate based on the decoding times. The simulation results mainly show that (I) as the harmony memory size (HMS) gradually increases, the performance of HSLSs first increases rapidly and then tends to remain unchanged, and HMS is not the larger the better; (II) as harmony memory considering rate increases, the performance continues to improve, while the performance of pitch adjusting rate on HSLSs goes to the opposite; Finally, more benchmark instances are also used to verify the effectiveness of the proposed algorithms. The results of this paper have a certain guiding significance on how to choose LS and other parameters to improve HS for solving FJSP.
Introduction
It is generally known that scheduling plays a crucial role in production and manufacturing [2]. Among them, the flexible job-shop scheduling problem (FJSP), due to its generality and complexity, has been extensively studied [16]. In an FJSP, an operation of a job can be processed on several machines. Therefore, FJSP is more in line with the actual production situation, and is more complex than the job-shop scheduling problem (where an operation can only be processed on a given machine) which is already an NP-hard problem [12].
Traditionally, researchers proposed numerous exact algorithms to solve FJSP [5], including branch and bound [3], Lagrange relaxation [24], mixed-integer linear programming [26], and so on. These exact algorithms can find optimal solutions within acceptable time bounds for small-scale FJSPs, but may be prohibitive for large-scale ones. Heuristic algorithms can find suboptimal solutions within acceptable time bounds for large-scale FJSPs, but not necessarily optimal ones.
Recently, numerous researchers have used meta-heuristic algorithms to solve FJSP [17], such as genetic algorithm [31], ant colony optimization algorithm [45], grey wolf optimization algorithm [38], etc. Among them, the harmony search algorithm (HS), a relatively new meta-heuristic algorithm, has begun to be used to solve FJSP and performs well [19, 46]. It is found that combining HS with some local searches can improve the performance of HS when solving FJSPs [41]. Actually, there are many local search algorithms adapted to solve FJSP, such as tabu search (TB) [36], simulated annealing (SA) [6], etc. Unfortunately, how different local search algorithms and the related parameters affect the performance of HS and hence how to choose a suitable local search algorithm (or other parameters) to improve HS in the context of solving FJSP are not yet studied systematically.
Therefore, in this paper, we first use the frequently used local search algorithms to improve HS, obtaining several HSs, i.e., harmony search with local search algorithms (HSLSs). Then, with the goal of minimizing makespan and under a certain number of evaluation times (i.e., decoding times [9]), study how different parameters (e.g., harmony memory size (HMS), harmony memory considering rate (HMCR), pith adjusting rate (PAR), different local search algorithms, local search frequency (L r ), and local search intensity (L i ), etc.) affect the performance of HSLSs, giving some insights into choosing a suitable local search algorithm to improve HS for solving FJSP.
The remainder of this paper is organized as follows. Section 2 gives a related literature review. Section 3 describes FJSP. Section 4 describes HS and the four frequently used local search algorithms, obtaining different HSLSs. In Section 5, how different parameters affect the performance of HSLSs is addressed. And Section 6 gives a conclusion and some future directions.
Literature review
Since Brucker and Schile [29] first proposed a polynomial algorithm to solve FJSP, an increasing number of algorithms have been proposed to solve it, mainly including exact algorithms, heuristic algorithms, and meta-heuristic algorithms [13]. Exact algorithms perform very well when solving small-scale FJSPs because they can find optimal solutions. Lloyd et al. [35] proposed an algorithm based on Petri net and improved branch and bound search, which uses the Pertri net model to generate and search partial feasible solutions, and combines the improved branch and bound method to obtain the optimal makespan. Hoitomt et al. [4] proposed to solve FJSP using Lagrangian relaxation method, which decomposes the scheduling problem into two subproblems and can obtain the lower bound of the optimal cost. Gomes et al. [27] proposed a mixed-integer linear programming model to solve multi-objective FJSP. This model takes into account both the re-entrant process and the final assembly stage, and optimizes the three objectives of order earliness, order tardiness, and in-process inventory. Elazeem et al. [5] presented the mathematical model of FJSP and its dual problem (i.e., Abdou’s problem), where the objective is to minimize the makespan, and shown that the optimal value of Abdou’s problem is a lower bound of the objective value of the primal problem. However, exact algorithms may be prohibitive for large-scale FJSPs, which encourages researchers to seek other algorithms.
Therefore, numerous meta-heuristic algorithms have been used to solve FJSP recently. Zhang et al. [7] proposed genetic algorithm to solve FJSP, and designed three initial population strategies using global selection, local selection, and random selection to improve the quality of initial individuals. Wang et al. [21] proposed an improved ant colony optimization algorithm to solve the FJSP with the goal of minimizing the makespan, which improves the selection of machine, the uniform distribution mechanism of initializing ants and the guidance mechanism of pheromone, and hence can provide better solutions in a reasonable amount of computing time. The FJSP with makespan minimization was solved by Caldeira and Gnanavelbabu [33] using the modified Jaya algorithm which is featured as using an efficient local search algorithm and an acceptance criterion that can effectively balance the exploration and exploitation. Ge et al. [10] proposed an efficient artificial fish swarm distribution estimation model to solve FJSP, which has improved the diversity of the population and the performance of their algorithm by adjusting the pre-principle and post-principle arrangement mechanisms of machine assignment and operation sequence in different orders. Gao et al. [18] proposed a pareto-based discrete harmony search algorithm to solve multi-objective FJSP. The discrete machine permutation method is used for machine assignment and the job permutation is used for operation sequence. However, these aforementioned algorithms have the drawback of choosing parameters through trial and error. Wang et al. [22] proposed an improved adaptive binary search algorithm with adaptively changing parameters, which can improve the flexibility and robustness of their algorithm. Aiming at minimizing the makespan, Huang et al. [25] designed adaptive mutation and crossover probabilities based on genetic algorithm to improve the robustness and convergence speed of their proposed algorithm. However, none of these papers have considered the impact of algorithm parameters on algorithm performance.
There is no single algorithm that works well for every problem, and each algorithm has its own suitable situations. Therefore, the combination of multiple optimization algorithms has become an effective means to improve the performance of some algorithms. So far, algorithms that have achieved good results on standard test problems are mostly hybrid algorithms. Li and Gao [39] proposed a combination of genetic algorithm and tabu search to solve the FJSP with makespan minimization, where genetic algorithm is used for global search and tabu search is used to improve its local search ability. Xu et al. [23] proposed to add a variable neighborhood search (VNS) to genetic algorithm to minimize the makespan of FJSP, and proposed two-layer coding based on process and machine in the initial population, which effectively improves the optimization ability of their proposed algorithm. Zhang et al. [8] combined genetic algorithm and variable neighborhood algorithm, and proposed three kinds of improved neighborhood structures to effectively improve the search ability of their algorithm. Zhang and Wu [32] designed a hybrid optimization algorithm by adding the immune process to the simulated annealing algorithm, which effectively improves the convergence speed of the algorithm for solving FJSP. Li et al. [14] proposed a hybrid Pareto-based discrete artificial bee colony algorithm for solving the multi-objective FJSP. The algorithm introduced fast Pareto set and several local search algorithms, which effectively balances the exploration and exploitation capability of their algorithm. However, none of these papers explain why this local search method was chosen. Yuan et al. [46] proposed a hybrid harmony search algorithm, which introduces heuristic and random strategies to improve the quality and diversity of initial solutions, and embeds local search to enhance the local search ability. Gao et al. [20] proposed a Pareto-based grouping discrete harmony search algorithm, which embeds two local searches based on critical path and due date to enhance the exploitation ability of the algorithm. The computational results demonstrated the efficiency and effectiveness of the proposed algorithm for solving FJSP. Li et al. [15] proposed the combination of genetic algorithm and variable neighborhood search algorithm, and effectively solved the multi-objective flexible job-shop scheduling problem under the same number of iterations. Shi et al. [40] studied how the sub-population number and size and the propagation rate of advantageous genes affect the performance of MPGA-ER under a certain number of total individuals. For large-scale problems, hybrid algorithms can show obvious advantages in search efficiency and solution quality. However, these papers do not compare and explain the parameter selection and selected local search of HS.
Therefore, this study will investigate the effect of local search frequency and local search intensity on the performance of HSLSs by combining local search with HS to solve FJSP. At the same time, how the parameters of HS affect the performance of HSLSs is also studied. Finally, more FJSP instances are solved by using the HSLSs with optimized parameters. Compared with the algorithms proposed in other research, the effectiveness of the combination of local search and HS is proved experimentally. In solving FJSP, investigating how to choose a suitable local search algorithm to improve HS provides some guidance.
Flexible job-shop scheduling problem
FJSP is mainly divided into total FJSP (T-FJSP) and partial FJSP (P-FJSP) [11]. In a T-FJSP, an operation can be processed on every machine, while in a P-FJSP an operation cannot be processed on at least one machine. Table 1 shows an example of P-FJSP with 3 jobs, 5 machines, and 7 operations. Each integer in the table represents the processing time of an operation on that machine, and the symbol ‘–‘ indicates that the corresponding operation cannot be processed on that machine. Generally speaking, FJSP can be described as follows.
An instance of P-FJSP
An instance of P-FJSP
There are n jobs (J1, J2, …, J
n
) to be processed on m machines (M1, M2, …, M
m
). The j
th
operation of the i
th
job (denoted by Q
ij
) is processed on a machine M
k
of its candidate machine set. The processing order of the operations of the same job is known and unchangeable. Finally, the mathematical model and constraints of FJSP are as follows [42, 43].
Equation (1) is an objective function, where C J i represents the completion time of the last operation of J i . “min ()” and “max ()” represent the functions that set the minimum and maximum values, respectively. Equation (2) represents the processing constraint of each job, where S Q ij represents the start time of Q ij , and P Q ij K represents the processing time of Q ij on M k (k ∈ { 1, 2, …, m }). X Q ij k represents whether Q ij is processed on machine M k or not. X Q ij k = 1 when Q ij is processed on M k , and X Q ij k = 0 otherwise. Equation (3) means that the same machine can only process one operation at a time. Z represents a large positive number. If Q ij starts earlier than Q ab on machine M k , then Y Q ijab k = 1, and Y Q ijab k = 0 otherwise. Equation (4) represents the machine constraint, that is, the same operation can only be processed by one machine at a time. m Q ij represents the number of machines available for Q ij . Equation (5) indicates that both the start machining time of the workpiece and the machining time on the machine should be greater than 0.
Harmony search is a relatively new meta-heuristic algorithm, which simulates the music creation process. The algorithm first initializes the harmony memory (HM) and then generates new harmony in the HM randomly. If the new harmony is better than the worst harmony in the HM, it is replaced. The loop continues until the termination condition is met. HM is a solution set composed of randomly generated solution, and its size (harmony memory size) directly affects the global search ability. The harmony memory considering rate is another major parameter. Its value is in the closed interval [0, 1], which determines the generation mode of new solutions in each iteration. In order to make the objective function value escape the local optimum, the pitch adjusting rate is used to control the local search. However, when a single harmony search is used to solve a certain problem, it is easy to fall into local optimum, so it is necessary to add local search to make the solution escape from local optimum. The frequently used local search algorithms (i.e., insertion, swap and reverse operators (ISR), TB, SA and VNS) and HS are combined to obtain HSLSs to improve the performance of the original HS.
The details of the HSLSs are as follows.
HSLS for solving FJSP
The main operators for solving FJSP using HSLS are coding, decoding, variables selection, and local search. The flowchart of HSLS is shown in Fig. 1.

The flow chart of HSLS.
FJSP encode consists of machine coding and operation coding. The FJSP coding can be represented as a feasible solution using integer coding. The machine coding consists of integers of length l equal to the total number of operations, with each integer representing the number of machines on which the corresponding operation is processed. For example, in the P-FJSP example in Table 1, the job has seven operations, so the machine coding consists of integers of length seven [3 2 2 1 3 1 1]. The first integer 3 means that job 1 picks the fifth machine from the candidate machine set m∈ { m1, m2, m5 } to be processed instead of m3, and so on. The operation coding also consists of integer of length l, each representing the corresponding job number. For example, the operation coding of the P-FJSP example in Table 1 [2 3 1 2 1 3 1]. Job 1 has three operations so it happens exactly three times. The first integer 2 means that the first operation of job 2 is processed first, and the second integer 2 means the second operation of job 2 is processed. And so on. Finally, machine coding and operation coding are combined to represent a solution, such as [3 2 2 1 3 1 1 2 3 1 2 1 3 1].
Decoding
For ease of computation and understanding, the evolved individual encodings need to be decoded into practically feasible scheduling schemes. Using the decoding algorithm proposed in the paper by Shi et al [42] paper, the previously mentioned encodings are decoded as (2 1 2 2 0 2; 3 1 3 4 0 4; 1 1 5 5 0 5; 2 2 4 5 2 7; 1 2 3 2 5 7; 3 2 1 7 4 11; 1 3 4 9 7 16). The decoding method will not be described repeatedly here. The reader is referred to [40, 42] for a detailed description.
Variables chosen
The initial harmony vector generates a new harmony vector based on three rules: HMCR, PAR and random selection
If,
a) Insertion, swap and reverse operators [14]
These three operators are frequently used in local search. Insertion is the random insertion of an operation from its current location to other locations in a sequence of operations. If the insertion is backward, the operation between the start points and the insertion point moves forward; otherwise, it moves backward. Swap is used to randomly swap the locations of two operations. Reverse is to reverse the order of operations between two randomly selected points.
b) Tabu search [36]
TB is a global stepwise optimization algorithm. Tabu table is used to label the researched neighborhood and local optimal point, and the repeated search of the searched area in tabu table is avoided in the next search, which is beneficial to expand the search space to find the global optimal solution.
TB mainly considers tabu object, tabu length, number of candidate solution set, amnesty condition and termination rule. Tabu length is a very important parameter, which directly affects the search process and behavior of the whole algorithm. The size of candidate solution set refers to the number of candidate neighborhood solution. Termination iteration size refers to the number of tabu searches.
c) Simulated annealing [6]
SA is a global optimization algorithm that converges to the global optimal solution with probability, which is derived from the solid annealing principle. SA mainly includes two parts, metropolis criterion and annealing process. When the particle is at temperature T, with time, the temperature is continuously reduced according to the attenuation factor until the critical value is reached. According to the metropolis criterion, a new solution with a certain probability of exp(- Δt′/T) is accepted. Where Δt′ represents the difference between the new objective value and the previous one.
d) Variable neighborhood search [34]
VNS is a general framework to solve optimization problems. The basic idea is to use different neighborhood structures to search. First, search in the smallest neighborhood. When the optimal solution cannot be improved, search in a slightly larger neighborhood. If the optimal solution is improved, it will return to the smallest neighborhood structure to continue the search, otherwise, it will continue to replace the larger neighborhood structure to search. And so on until the termination condition is met.
The first level of the neighborhood structure operates only on machine codes. A process is randomly selected and the processing machine of the process is replaced by the machine with the shortest processing time. The second level of neighborhood structure operates only on job codes. A process is randomly selected and the process is interchanged with the head or tail of the process. The third level of neighborhood structure operates on both machine and job codes. Two processes are randomly selected to be interchanged and the machine is changed accordingly.
Evaluation index
It proposes for solving the FJSP with the criterion to deviation rate (D
r
). Deviation rate can be expressed by the following formula.
Firstly, how the HMS, HMCR and PAR affect the performance of HSLSs with a given number of decodes is investigated. Secondly, the effect of L r and L i on the performance of HSLSs is discussed. Finally, the optimal parameter and local search combinations are chosen to solve more FJSP examples to verify the effectiveness of HSLS in solving FJSP.
Effect of harmony memory size on HSLSs
The MK01 instance (10 × 10 FJSP) mentioned in Brandimart [28] was used to study the effect of the harmony memory size on HSLSs. This instance, which has a reasonable number of machines and jobs and moderate difficulty, has been extensively studied in several studies (Yuan et al. [46]; Gao et al. [19]; Kong et al. [38]). The tabu search length (TB) was set to 13 and the number of candidate solution sets was set to 20. The initial temperature of SA was set equal to the total number of processes and the decay factor was set to 0.3. To ensure that the four local searches were investigated with the same number of decodes, the number of decodes was set to a larger number of 500,000. The other parameters were set as follows: HMCR = 0.9, PAR = 0.05, L r = 0.2, L i = 1000, HMS varies from 5 to 50 with a step size of 5. Each algorithm is run 50 times independently and the performance of the HSLSs is measured by D r . The simulation results are shown in Fig. 2.

Effect of harmony memory size on HSLSs.
In Fig. 2, the X-axis and Y-axis represent HMS and D r respectively. When HMS is 5, the D r of the four local searches is the largest, and the performance of the HSLSs is extremely poor. No optimal value of 40 can be found (the optimal value of MK01 FJSP is 40, and Fig. 3 shows its Gantt chart). As the HMS increases to 15, the performance of the HSLSs improves rapidly. However, as the HMS continues to increase, the performance of the HSLSs slowly decreases and levels off. When HMS = 40, the minimum D r of HSLS-TB is 1.18. When HMS = 50, HSLS-SA has a minimum D r of 1.16. If HMS = 45, the minimum D r of HSLS-VNS is 0.7. When HMS = 40, the minimum D r of HSLS-ISR is 0.6. HSLS-ISR and HSLS-VNS perform significantly better than HSLS-TB and HSLS-SA. The best performance is achieved with HSLS-ISR. To obtain HSLSs with good performance, the value of HMS should be large, but not too large. In general, values should be in the range of 15 to 40.

Gantt chart of a solution to MK01.
The MK01 example is used again. First, the effect of HMCR on HSLS performance was investigated. The HMCR varies from 0.5 to 1 in steps of 0.05. Based on the study in Section 5.1, HM = 40 is used in the following study. The other parameters are the same as those chosen in Section 5.1. The simulation results are shown in Fig. 4.

Effect of harmony memory considering rate on HSLSs.
In Fig. 4. When HMCR = 0.5, the D r values of the four local searches are the largest, and HSLSs also has the worst performance. Can’t find the optimal solution 40. As the HMCR increases, the performance of HSLSs improves. When HMCR = 0.95, the D r of HSLS-ISR and HSLS-SA are 0.58 and 1.16 respectively. When HMCR = 1, the D r of HSLS-TB and HSLS-VNS are 1.2 and 0.5 respectively. The minimum D r of HSLS-VNS is lower than that of HSLS-ISR, but the overall performance of HSLS-ISR is better than the other three. Therefore, for a given number of decoding times, the performance of HSLSs increases as the HMCR increases. To obtain HSLSs with good performance, the value of HMCR should be as close to 1 as possible rather than equal to 1. In general, the range of values should be [0.9, 0.95].
The MK01 FJSP instance mentioned above is used again. The effect of PAR on HSLS performance was investigated. The PAR was varied from 0 to 0.5 in steps of 0.05. Based on the study in Section 5.2, HMCR = 0.95 is used in the following study. The other parameters are the same as those selected in Section 5.2. The simulation results are shown in Fig. 5.

Effect of pith adjusting rate on HSLSs.
When PAR = 0.05, HSLS-ISR, HSLS-SA and HSLS-VNS achieve the best performance with D r values of 0.64, 1.22 and 0.48 respectively. The best performance of HSLS-TB is achieved with PAR = 0.1 and D r = 1.12. As PAR increases, the D r of the four local searches also increases, and the performance of the HSLSs deteriorates slowly and then rapidly. When PAR = 0.5, the D r of HSLS-TB and HSLS-SA are 6.9 and 6.98 respectively, at which point it is difficult for both to find the optimal solution. When PAR is between 0.05 and 0.25, the performance of the HSLSs is almost the same, but when PAR is greater than 0.25, HSLS-ISR performs significantly better than the other three. In general, the performance of HSLSs is better when the value of PAR is smaller, but the value of PAR should not be 0. In general, the value range should be [0.05, 0.1].
The MK01 FJSP example was used again to investigate the effect of local search frequency L r on HSLSs performance. L r was varied between 0.1 and 1 in steps of 0.1. Based on the study in Section 5.3, PAR = 0.05 is used in the following study. The remaining parameters are the same as those selected in Section 5.3. The simulation results are shown in Fig. 6.

Effect of local search frequency on HSLSs.
When L r is 0.2 and 1, the D r of HSLS-ISR is 0.56 and 1.04 respectively. And the performance of HSLS-ISR is best and worst, respectively. When L r is 0.1 and 0.7, the D r of HSLS-TB and HSLS-SA are 1.2 and 1.24 respectively, which is the best performance of the two, but the optimal solution is still not found 40. The performance of HSLS-ISR and HSLS-VNS is significantly better than that of HSLS-TB and HSLS-SA. Only when L r = 0.2 the performance of HSLS-ISR better than that of HSLS-VNS, with D r of 0.56 and 0.64 respectively. However, the overall performance of HSLS-VNS is better than that of HSLS-ISR, not the reverse. As L r increases, D r first becomes small, then flattens out and then becomes large. In general, the value of L r should be between 0.2 and 0.7 for the same number of decoding times.
The MK01 FJSP example was used again to investigated the effect of the local search intensity L i on HSLSs performance. The L i was varied between 500 and 1,500 in steps of 100. Based on the study in Section 5.4, the following study takes L r = 0.2. The remaining parameters are the same as those selected in Section 5.4. The simulation results are show in Fig. 7.

Effect of local search intensity on HSLSs.
When L i is 500 and 600, the D r of both HSLS-TB and HSLS-ISR is 0.36, at which point the HSLSs perform best and both can find the optimum value of 40. As L i increases, the performance of HSLSs decreases continuously, after which the performance fluctuates continuously up and down, HSLS-TB and HSLS-SA have the best performance at L i = 500, with D r of 1.04 and 0.36 respectively. At L i = 1000 and 1400, HSLS-ISR and HSLS-VNS have the same performance and D r is the same 0.46 and 0.56. HSLS-TB has the worst performance of the three, followed by HSLS-SA. In general, the higher the L i , the worse the performance of the HSLSs. In general, the range of values should be [500, 1000].
Comparison results of local search algorithms
Comparison results of local search algorithms
To further prove the correctness of the parameters of the proposed algorithm. In this study FJSPs were solved and compared with other algorithms (Kacem et al. [11]; Xia and Wu [37]; Bagheri et al. [1]; Demir and İşleyen [44]; Xie et al. [13]; Yuan et al. [46]). The FJSP instance data are Kacem data [11] and F-data [30]. Local search selects ISR. The algorithm parameters are: HM = 40, HMCR = 0.95, PAR = 0.05, L r = 0.2 and L i = 600. Tables 3 and 4 show the results, with the symbol “N/A” indicating that the author of the original text did not provide the corresponding data.
Results of comparison with other algorithms on K-data
Results of comparison with other algorithms on K-data
Results of comparison with other algorithms on F-data
As shown in Table 3, when 8 × 8 is solved by HSLS-ISR, the optimal solution is 14, which is better than 15 of the “AL+CGA” algorithm. When 15 × 10 is solved, it is better than 12 of “PSO+SA”. When solving MFJS05 with HSLS-ISR, the optimal value is 514, which is better than 527 of AIA algorithm. When solving MFJS07 with HSLS-ISR, the optimal solution is 879, which is better than 928 of M2 algorithm. Figure 8 is a Gantt chart of the solution of the 15 × 10 problems.

Gantt chart of a solution to 15 × 10.
As mentioned in Section 5.1, for a certain number of decoding times, the performance of HSLSs increases with HMS, and the ability to find the global optimal solution becomes stronger. However, as the HMS increases, so does the amount of computation, which affects the speed of the final search for the optimal solution, and performance is reduced. So bigger is not always better.
As mentioned in Sections 5.2 and 5.3. As HMCR increases, the overall trend of D r is downward, and the performance of HSLSs is constantly improving. In generally, the performance of HSLSs is optimal when HMCR is 0.95 rather than 1. PAR and HMCR have the opposite trend. As PAR increases, the performance of HSLS-TB, HSLS-SA and HSLS-VNS decreases slowly and then rapidly. However, the performance of HSLS-ISR decreases slowly. The optimum performance of the HSLSs is all concentrated at PAR = 0.05 instead of 0. The values of HMCR and PAR can be set to sum to 1.
As mentioned in Sections 5.4 and 5.5, the performance of the HSLSs varies continuously with different L r . The overall performance of HSLS-ISR and HSLS-VNS is better than that of HSLS-TB and HSLS-SA. The performance of HSLS-ISR is better than that of HSLS-VNS only when L r is 0.2, but the overall performance of HSLS-VNS is better than that of HSLS-ISR. HSLS-VNS can find the optimal value 40 for L r values between 0 and 1. As the local search intensity increases, the performance of HSLSs first improves and then deteriorates towards continuous variation. The smallest D r of HSLS-TB is 1.04 for L i = 500, and none of the optimal solutions can be found at 40. The largest D r of HSLS-VNS is 0.7 for L i = 4000 and the optimal solution can be found in almost all cases 40. HSLS-SA, HSLS-ISR and HSLS-VNS have similar overall performance, but are better than HSLS-TB.
Conclusion and future work
In this study, four commonly used local search algorithms were combined with HS to obtain HSLSs. At a certain number of decoding times, HSLSs were used to solve the MK01 FJSP instance, and the influence of parameters such as HMS, HMCR, PAR, L r and L i on HSLSs was systematically investigated. The simulation results showed that the combination of harmony search and local search can significantly improve the performance compared with the standard HS, and the performance of different local searches is also different. For HMS, the parameter should be larger, but the performance will degrade if it is too large, and the expectation interval is [15, 40]. The opposite is true for HMCR and PAR. HMCR should be as close to 1 as possible, but it cannot be 1. PAR should be as close to 0 as possible. The best value is 0.05 and the sum of these two values is 1. For L r the expected value is in [0.2, 0.7]. The expected value of L i is in the range [500, 1,000]. Overall, HSLS-ISR and HSLS-VNS perform better than HSLS-TB and HSLS-SA, with HSLS-ISR performing best. The results of the study can help researchers understand how to achieve better HSLSs using local search.
In this study, multiple local search algorithms combined with standard harmony search algorithms were used to obtain HSLSs. However, this may limit its performance and only solves small FJSPs. In the future, adaptive parameters and improvements to the local search structure will be considered to better address larger scale FJSPs.
Conflicts of interest
The authors declare no conflicts of interest regarding the publication of this paper.
Footnotes
Acknowledgments
This research is partially supported by the Natural Science Foundation of Sichuan Province (Grant No. 2023NSFSC0507), the Program for HUST State Key Laboratory of Intelligent Manufacturing Equipment and Technology (Grant No. IMETKF2023026), the Key Laboratory of Icing and Anti/De-icing of CARDC (Grant No. IADL20220405), and the Natural Science Foundation of Southwest University of Science and Technology (Grant No. 20zx7117).
