Keywords

1 Introduction

In recent years, to break through the bottleneck limitation of traditional optimization algorithms, various intelligent optimization algorithms based on animal foraging or other learning behaviors, such as Artificial Bee Colony, Shuffled Frog Leaping Algorithm and Firefly Algorithm, have emerged. Compared with other animals in nature, human has evolved a higher level of intelligence and learning ability and is able to solve complex problems that other animals are unable to solve. Inspired by a simple yet general human learning mechanism, Wang et al. proposed Human Learning Optimization (HLO) [1], in which the random learning operator, individual learning operator and social learning operator were designed through simulating the learning mechanism of humans to search out the optimal solution of problems.

To further improve the optimization performance of HLO, Wang et al. proposed an adaptive simplified human learning optimization algorithm (ASHLO), which set the linearly increasing and linearly decreasing adaptive strategy for the parameters pr and pi, respectively, to maintain the balance between algorithmic exploration and exploitation [2]. Based on the phenomenon that human IQ follows normal distribution on the whole and shows an upward trend, a diverse human learning optimization algorithm (DHLO) was proposed, where the social learning capability of all individuals was subject to normal distribution and tuned dynamically [3]. The simulation results indicate that DHLO possesses better global optimization performance. Yang et al. adopted an adaptive strategy based on cosine and sine functions to propose a sine-cosine adaptive human learning optimization algorithm (SCHLO) [4]. Later, An improved adaptive human learning optimization algorithm (IAHLO) [5] which used a two-stage adaptive strategy to dynamically adjust the execution probability of random learning operators is proposed, so that the algorithm focused on exploration to diversify the population at the beginning of iterations, and focused on local search at the later phase of iterations to enhance the mining ability of the algorithm. Nowadays, many various practical problems, such as extraction of text abstracts [6], financial market forecasts [4], image processing [7], mixed variable engineering optimization problems [8], and intelligent control [9,10,11], have been successfully solved by HLO.

As a binary algorithm, HLO is capable of solving discrete optimization problems directly. Fan W et al. adopted the ASHLO to take place local search in standard VNS to solve scheduling problems with multiple constraints [12]. Li et al. took advantage of HLO to solve the actual production scheduling problem of a dairy plant [13]. Ding et al. combined an improved PSO and some scheduling strategies to solve the flexible job shop scheduling problem under the algorithm architecture of HLO [14]. A. Shoja et al. combined ASHLO with GA and PSO, respectively, to solve the two-stage supply chain network design problem aiming at minimizing cost [15].

However, with the scale of the problem grows, the size of the feasible solution set grows exponentially, and the phenomenon of “combinatorial explosion” inevitably occurs, which results in a significant decrease in the optimization efficiency of binary HLO for discrete problems. Therefore, this paper extends HLO and proposes an enhanced discrete HLO (EDHLO) algorithm for the PFSSP, which is a classical discrete problem and plays an essential part in ensuring the steady progress of production and improving resource utilization. To solve PFSSP more efficiently, the learning operators of EDHLO are improved and the efficient heuristic algorithm NEH [16] is combined with random initialization to improve the quality of the initial solutions. Besides, a local search strategy is utilized to help EDHLO algorithm get rid of the local optima.

The structure of this paper is as follows: Sect. 2 is a description of the PFSSP and the related definitions. Section 3 describes the proposed algorithm EDHLO. The experimental results of EDHLO and other metaheuristics are given in Sect. 4. Section 5 summarizes this paper.

2 Permutation Flow Shop Scheduling Problem

PFSSP which is a simplified model of assembly-line production in many manufacturing enterprises, one of the most well-known classes of scheduling problems, has been investigated extensively and intensively due to its importance in the aspect of academy and engineering applications [17].

The current approaches for solving PFSSP mainly can be divided into 3 classifications, i.e., precision methods, heuristic rule-based methods and meta-heuristic algorithms [18]. PFSSP, as an NP-hard combinatorial optimization problem, grows exponentially in computational complexity as the problem scale increases. Although the precision methods can find the exact solution to the problem, they are only suitable for solving small-scale PFSSP considering the computational resources. Constructive heuristics are methods for solving specific problems by inductive reasoning and experimental analysis according to experience, which can obtain nearly optimal solutions. However, some of them are difficult to obtain satisfactory solutions. Compared with the other two categories, meta-heuristic algorithms are more advantageous in terms of stability, convergence speed and computational efficiency. Thus, currently, meta-heuristic algorithms have become the most effective and efficient method to solve scheduling problems, and the main hotspots of research are also concentrated on the improvement of the meta-heuristics and the development of new algorithms.

The description of PFSSP is as following: n jobs require m processes on different machines sequentially, and the processing sequence of n jobs on all machines is the same, with the goal to find the best permutation to minimize the makespan. It should be noted that each machine at the same time only one job is allowed to be machined, accordingly, each job can be handled on only one machine at a time. The processing time H(pj,k) is the time for job pj to be processed on the k-th machine. C(pj,k) represents the processing completion time of job pjon the k-th machine. PFSSP can be mathematically formulated as follows Eq. (1) [19]:

$$\left\{ \begin{gathered} C\left( {p_{1} ,1} \right) = H\left( {1,1} \right) \hfill \\ C\left( {p_{j} ,1} \right) = H\left( {j,1} \right) + C\left( {p_{j - 1} ,1} \right) \, j = 2,3, \ldots ,n \hfill \\ C(p_{1} ,k) = H(1,k) + C\left( {p_{1} ,k - 1} \right) \, k = 2,3, \ldots ,m \hfill \\ C(p_{j} ,k) = H(j,k) + \max (C(p_{j - 1} ,k),C(p_{j} ,k - 1)) \, j = 2,3, \ldots ,n; \, k = 2,3, \ldots ,m \hfill \\ C_{\max } = C\left( {p_{n} ,m} \right) \hfill \\ \end{gathered} \right..$$
(1)

The optimal permutation p* can be found by the optimization in Eq. (2):

$$p^{*} = \arg \, \min \, C\left( {p_{n} ,m} \right), \, \forall p \in \Omega .$$
(2)

3 Enhanced Discrete Human Learning Optimization for PFSSP

3.1 Initialization

The solution of PFSSP is a single linked list, which focuses on the position of each element in the whole permutation. Therefore, different from the standard HLO, EDHLO uses the integer encoding framework, where the individual solution in EDHLO is represented by an integer array as Eq. (3),

$$x_{i} = [x_{i1} \, x_{i2} \, \cdots \, x_{ij} \, \cdots \, x_{iM} ], \, x_{ij} \in \left\{ {1,2, \cdots ,M} \right\},{ 1} \le i \le N,1 \le j \le M$$
(3)

where xi is the i-th individual, xij is the j-th element of the i-th individual, N is the size of population and M denotes the length of solutions, i.e. the number of jobs. Under the assumption that the prior knowledge of problems does not exist at first, each variable of an individual in EDHLO is initialized with an integer between 1 and M stochastically to present the number of jobs.

Aiming at solving PFSSP efficiently, the NEH algorithm, an efficient heuristic algorithm, is used to generate 10% of the individuals, so as to enhance the quality of the initial population and maintain the diversity of the population.

3.2 Learning Operators

The standard HLO generates new candidates to search out the optimal solution by the random learning operator, the individual learning operator and the social learning operator, but these three learning operators are not applicable to PFSSP. Thus, EDHLO redesigns and introduces the learning operators to solve PFSSP more efficiently.

3.2.1 Random Learning Operator for PFSSP-Like Problems

In reality, humans usually have to solve a problem by using the random learning strategy at the beginning due to a lack of prior knowledge. Moreover, since a person is easy to be affected by various factors like interference and forgetting, the human cannot fully replicate the previous experiences. And consequently, learning processes are always accompanied by randomness [20]. To imitate the random learning behavior for the PFSSP, the random learning operator is designed in EDHLO as Eq. (4),

$$x_{ij} = R(M)$$
(4)

where R(M) represents the random learning operator which randomly chooses a job not scheduled yet.

3.2.2 Individual Learning Operators for PFSSP-Like Problems

Individual learning refers to the ability of an individual to construct his own knowledge by reflecting on the extrinsic stimuli and sources [21]. Drawing on previous experience is conducive to efficient learning of humans. Set up an Individual Knowledge Database (IKD) to store individual optimum solutions to simulate the individual learning mechanism described above, as shown in Eqs. (5–6),

$$IKD = \left[ {\begin{array}{*{20}c} {ikd_{1} } \\ {ikd_{2} } \\ \vdots \\ {ikd_{i} } \\ \vdots \\ {ikd_{N} } \\ \end{array} } \right], \, 1 \le i \le N$$
(5)
$$ikd_{i} = \left[ {\begin{array}{*{20}c} {ikd_{i1} } \\ {ikd_{i2} } \\ \vdots \\ {ikd_{ip} } \\ \vdots \\ {ikd_{iK} } \\ \end{array} } \right] = \left[ {\begin{array}{*{20}c} {ik_{i11} } & {ik_{i12} } & \cdots & {ik_{i1j} } & \cdots & {ik_{i1M} } \\ {ik_{i21} } & {ik_{i22} } & \cdots & {ik_{i2j} } & \cdots & {ik_{i2M} } \\ \vdots & \vdots & {} & \vdots & {} & \vdots \\ {ik_{ip1} } & {ik_{ip2} } & \cdots & {ik_{ipj} } & \cdots & {ik_{ipM} } \\ \vdots & \vdots & {} & \vdots & {} & \vdots \\ {ik_{iK1} } & {ik_{iK2} } & \cdots & {ik_{iKj} } & \cdots & {ik_{iKM} } \\ \end{array} } \right],{ 1} \le p \le K.$$
(6)

where ikdi represents the IKD of individual i, K is the size of IKD, ikdip is the p-th best solution of individual i, and each ikipj is an integer between 1 and M.

EDHLO uses its previous knowledge in the IKD to generate a high-quality candidate by conducting the individual imitation learning operator (IILO) as Eq. (7).

$$x_{ij} = ik_{ipj}$$
(7)

Besides, to diversify the population and further enhance the quality of the solution, the individual swap learning operator (ISLO) and the individual reversal-insertion learning operator (IRLO), inspired and borrowed from two cross operators, i.e. the swap exploration operator and reversal-insertion operator, are introduced in the individual learning process. The swap exploration operator and reversal-insertion operator are successful ways of solving PFSSP in the previous studies, and their effectiveness has been verified in [22] and [23] respectively.

As shown in Fig. 1, the individual swap learning operator refers to exchanging the positions of two random jobs. The number of executions of the individual swap learning operator is thirty percent of the number of jobs. The individual reversal-insertion learning operation is described in Fig. 2 where it exchanges the position of two adjacent jobs, removes them from the original permutation and then inserts them in any other (n-2) positions. These two operators only need individual knowledge and therefore they are designed as individual learning operators. The newly generated permutation will replace the original one if and only if it has a better fitness.

Fig. 1.
figure 1

The individual swap learning operator

Full size image
Fig. 2.
figure 2

The individual reversal-insertion learning operator

Full size image

3.2.3 Social Learning Operator for PFSSP-Like Problems

The process of tackling complicated problems through individual learning alone can be quite slow and inefficient. Therefore, as social animals, human beings naturally learn from others in the collective to gain experience and expand their knowledge [24]. By directly or indirectly transferring experiences, humans can improve their competence and learning efficiency. To utilize the social experience productively, Social Knowledge Database (SKD) which stores the optimal solution found by the whole population in the search process is established in EDHLO as Eq. (8),

$$SKD = \left[ {\begin{array}{*{20}c} {skd_{1} } \\ {skd_{2} } \\ \vdots \\ {skd_{q} } \\ \vdots \\ {skd_{H} } \\ \end{array} } \right] = \left[ {\begin{array}{*{20}c} {sk_{11} } & {sk_{12} } & \cdots & {sk_{1j} } & \cdots & {sk_{1M} } \\ {sk_{21} } & {sk_{22} } & \cdots & {sk_{2j} } & \cdots & {sk_{2M} } \\ \vdots & \vdots & {} & \vdots & {} & \vdots \\ {sk_{q1} } & {sk_{q2} } & \cdots & {sk_{qj} } & \cdots & {sk_{qM} } \\ \vdots & \vdots & {} & \vdots & {} & \vdots \\ {sk_{H1} } & {sk_{H2} } & \cdots & {sk_{Hj} } & \cdots & {sk_{HM} } \\ \end{array} } \right],1 \le q \le H$$
(8)

where skdq denotes the q-th optima solution in the SKD and H is the size of the SKD. When an individual performs social learning, it operates as Eq. (9).

$$x_{ij} = sk_{qj}$$
(9)

3.3 Updating of IKD and SKD

Although the individual learning operators and the social learning operator can learn the order of jobs scheduled for processing from the better solutions efficiently, they may produce duplicate job numbers and yield infeasible solutions. Therefore, after the new population is generated, EDHLO will find the duplicate job numbers from the random position of the individual sequence and replace them randomly with the job numbers that have not been assigned. Then the new candidates are substituted into the fitness function to calculate the fitness values. Only when the number of candidates stored in IKD is fewer than the set value K or the new candidate solution is superior to the worst in IKD, the new candidate solution will be saved in the IKD directly, otherwise, it will be discarded. For the SKD, the same updating strategy is applied. Moreover, to obtain a superior SKD and help the EDHLO escape from the local minimum, a local search approach is applied in EDHLO.

The local search method operates as follows: move each job in the optimal permutation with dimension M to the remaining (M-1) positions sequentially except the current position, and keep the rest of the permutation unchanged. After every movement, calculate the fitness of the new permutation. If the fitness is better, update the SKD. To avoid redundant computations, the local search is activated every 50 iterations.

3.4 Implementation of EDHLO

In summary, EDHLO performs the random learning operator, individual learning operators, and social learning operator with specified probabilities to search for the optimal solution. The implementation of EDHLO can be described as below:

  • Step 1: set the parameters of EDHLO, such as the population size, maximum number of iterations, pr, pi;

  • Step 2: initialize 10% of individuals by NEH and randomly yield the rest initial population;

  • Step 3: evaluate the fitness of the whole population and generate the initial IKDs and SKD;

  • Step 4: yield new candidates by executing the learning operators of EDHLO as Eq. (4), Eq. (7) and Eq. (9) with the probabilities of pr, (pi-pr) and (1-pi), respectively;

  • Step 5: fix the infeasible solutions and execute the ISLO and the IRLO for 20% of individuals;

  • Step 6: update the IKDs and SKD according to the calculated fitness of new individuals.

  • Step 7: perform the local search on the SKD every 50 iterations;

  • Step 8: Determine whether the termination condition is satisfied, if so, output the optimal solution found, otherwise go to step 4.

4 Experimental Results and Discussion

To estimate the performance, the proposed EDHLO, together with six meta-heuristic algorithms, i.e. the particle swarm optimization based memetic algorithm (PSOMA) [25], hybrid genetic algorithm (HGA) [26], discrete bat algorithm (DBA) [27], hybrid differential evolution algorithm with local search (L-HDE) [22], hybrid backtracking search algorithm (HBSA) [19] and chaotic whale algorithm (CWA) [23], are adopted to solve 21 benchmark problems proposed by Reeves. Referring to the literature [1], the IKD and SKD sizes of EDHLO are 1, and the remaining parameters of EDHLO are specified as given below: population size popsize = 60, maximum iterations Gmax = 2000, pr = 0.1, pi = 0.45. Run each instance 30 times independently to compare. The computations were carried out using a PC with AMD Ryzen 5 2600 Six-Core Processor CPU and 32GB RAM on Windows 10, 64-bit operating system.

The best relative error (BRE), the average relative error (ARE) and the worst relative error (WRE) of the optimal solution are selected as the evaluation metrics, which are defined as Eqs. (10–12),

$$BRE = \frac{{S_{Best} - BKS}}{BKS} \times 100\% .$$
(10)
$$ARE = \frac{{S_{Average} - BKS}}{BKS} \times 100\% .$$
(11)
$$WRE = \frac{{S_{Worst} - BKS}}{BKS} \times 100\% .$$
(12)

where SBest, SAverage and SWorst represent the best solution, the average solution and the worst solution found by the algorithm respectively, and BKS represents the optimal solution value known so far of the benchmark problem.

Table 1 lists the experimental data of EDHLO. The corresponding data of compared algorithms are obtained from the original literature and the experimental results not given in the original literature are indicated by “–”.

Table 1. Comparison of EDHLO and other algorithms on Reeves benchmarks
Full size table

Figures 3 and 4 show the average values of the three evaluation metrics on the Reeves benchmark problems. Since the original literature of CWA contains results for only 19 Reeves benchmarks, for the sake of fairness, CWA is compared with EDHLO separately. It can be seen in Figs. 3 and 4 that EDHLO achieves the best results. Compared with PSOMA, HGA, DBA, L-HDE and HBSA, EDHLO ranks first in terms of the mean of BRE, ARE and WRE, with the lowest values of 0.258, 0.564 and 0.628, respectively. According to the values of the mean of BRE, ARE and WRE, EDHLO is also superior to CWA. The above experimental outcomes prove the effectiveness and stability of EDHLO.

Fig. 3.
figure 3

The comparison of PSOMA, HGA, DBA, L-HDE, HBSA and EDHLO on Reeves benchmarks

Full size image
Fig. 4.
figure 4

The comparison of CWA and EDHLO on Reeves benchmarks

Full size image

5 Conclusions

To further study HLO and extend it to solve discrete problems more efficiently, this paper proposed an enhanced discrete human learning optimization (EDHLO) algorithm for solving PFSSP. EDHLO is based on the standard learning mechanisms of HLO, but it redesigns and introduces the learning operators to solve PFSSP efficiently. In the proposed EDHLO, the efficient heuristic algorithm NEH is integrated with random initialization to improve the original population quality and maintain the diversity of the original population, two cross operators are introduced into the individual learning of EDHLO to upgrade the local exploitation capacity, and a local search method is used to facilitate EDHLO to get rid of the local optimum. The experimental results on 21 benchmark problems and the comparisons with other meta-heuristics verify the effectiveness and stability of the EDHLO.