Quantum-inspired African vultures optimization algorithm with elite mutation strategy for production scheduling problems

Abstract

Graphical Abstract

Open in new tabDownload slide

1. Introduction

In engineering sciences, sustainability in manufacturing is becoming an urgent need for today’s manufacturing companies. In the context of Industry 4.0, the organizational model of production systems has undergone significant changes, leading to a transformation in the approach to production scheduling (PS). As a result, PS has been a topic of extensive research in the literature and is recognized as one of the key challenges in manufacturing systems (Jiang et al., 2022). PS involves the efficient allocation of resources to activities over time to meet all time and resource capacity constraints and optimize different objectives (Fazel Zarandi et al., 2020). PS can provide optimal resourcing for different issues (Bhosale & Pawar, 2020). The two most well-known PS problems are the parallel machine scheduling (PMS) and the flexible job shop scheduling problem (FJSP).

The problem of planning a sequence of tasks that are independent of each other on a polymorphic parallel machine is called the PMS problem. PMS is a famous NP-hard combinatorial optimization issue whose time complexity for finding a workable solution rises exponentially with the size of the issue. Based on the complexity of this problem, heuristic algorithms provide new ideas for finding suitable solutions. Before this work, a considerable body of literature demonstrated the effectiveness of metaheuristic algorithms in solving PMS problems within given time constraints (Al-qaness et al., 2021; Arık et al., 2022; Ewees et al., 2021; Fang et al., 2022; Lei & Yang, 2022; Lei et al., 2021; Zhang et al., 2021). In these studies, the irrelevant PMS problem with setup time is dealt with. The NP-hard problem of reducing the manufacturing span based on the machine environment, task characteristics, and optimality requirements is the irrelevant PMS problem (Graham et al., 1979). Due to the complexity of this problem and the inadequacy of exact algorithms when dealing with problems of medium to large size, quantum-inspired African vultures optimization algorithm with an elite mutation strategy (QEMAVOA) is offered in this study to identify high-quality PMS solutions.

The FJSP has evolved from the job shop scheduling problem (JSP), which is comprised of two sub-problems: operation sequencing and machine assignment. The operation sequencing problem is responsible for scheduling all operations on all machines, while machine assignment involves selecting machines for each job from a list of machine candidates (Boyer et al., 2021; Li et al., 2022). FJSP finds widespread use in specific industries such as semiconductor manufacturing, flow scheduling, automotive assembly, agent processing systems, and shipbuilding system (Boyer et al., 2021; Cho et al., 2022; Li et al., 2022; Pal et al., 2023; Sun et al., 2023; Vali et al., 2022). Due to its complexity, FJSP has been shown to be NP-hard, and traditional mathematical optimization methods have been proven to be difficult to solve in a timely manner (Li et al., 2022). In recent years, population intelligence and evolutionary algorithms have increasingly been used to solve the FJSP problem (Boyer et al., 2021; Oh et al., 2022). Given the complexity of FJSP, this study proposes QEMAVOA to determine a high-quality solution to the FJSP problem.

The African vulture optimization algorithm (AVOA) was proposed by Abdollahzadeh et al. (2021). Wang et al. (2022) developed the adaptive AVOA and applied it to the optimization of solid oxide fuel cell stacks. Kumar and Mary (2021) introduced an AVOA (i.e., I-AVO) based on orthogonal and opposition learning and applied it to photovoltaic systems. Bagal et al. (2021) introduced an AVOA (i.e., MAVO) based on the collective orientation factor and applied it to oxide fuel cell stack optimization. Chen and Zhang (2022) introduced an AVOA (i.e., IAVO) based on orthogonal learning and Lévy flight and applied it to fuel cell models. Fan et al. (2021) introduced an upgraded AVOA with time-varying mechanisms and chaotic mapping (i.e., TAVOA), contrasted it with the original algorithm in the benchmark function, and proved its superiority over the original AVOA using an engineering example. Diab et al. (2022) applied AVOA to a photovoltaic system by comparing it with the honey badger algorithm. Soliman et al. (2022) offer a novel hybrid African vulture-gray wolf optimizer (i.e., AV-GWO) technique for accurately predicting the electrical characteristics of the photovoltaic three-diode model. Gharehchopogh et al. (2022) propose a new algorithm created by a hybrid of harmony search (HA) and AVOA that is proposed and applied to the data clustering problem. Zheng et al. (2023) propose a multi-strategy enhanced AVOA for global optimization problems, applying it to classify multilayer perceptions using XOR and cancer datasets.

Combining ideas from quantum physics, computer science, and classical information theory, quantum computing (QC) represents an exciting new field (Steane, 1998). Recently, an increasing number of academics are combining QC techniques with heuristic algorithms and attempting to exploit them in a variety of sectors. Yu et al. (2021) incorporate the water circulation mechanism and quantum rotating gate (QRG) strategy into the slime mould algorithm (SMA). Deng et al. (2021) enhanced the differential evolution (DE) algorithm with a quantum double-chain encoding (QDCE) scheme and QRG. They used it in conjunction with a mutation method to solve large-scale, difficult issues (Deng et al., 2021). Cai et al. (2021) proposed an improved quantum-inspired cooperative co-evolutionary algorithm (MSQCCEA) and applied MSQCCEA to the airport gate optimization problem to verify the superiority of MSQCCEA in airport management decisions. Dias et al. (2021) proposed a quantum-inspired neural co-evolution (QNCo) model for the agent coordination problem, and tested the adapted model on prey-predator and multi-robot tasks and cell phone coverage, verifying that QNCo has superior performance. Dahi and Alba (2022) introduced a quantum heuristic metaheuristic for the mobility management problem and integrated it with a complete investigation of quantum hardware to give a new perspective on quantum heuristic metaheuristics. Cui et al. (2022) analyzed the shortcomings of the K-means algorithm and proposed a quantum-inspired moth-flame optimizer with an enhanced local search strategy (QLSMFO) and verified the superiority of QLSMFO in terms of accuracy, convergence speed, and stability on the cluster analysis problem. Zhang et al. (2022) proposed a novel adaptive mutation quantum-inspired squirrel search algorithm (AM-QSSA) and applied it to the image registration problem to verify the efficiency and stability of AM-QSSA. Houssein et al. (2022) proposed a hybrid quantum classical convolutional neural network (i.e., HQ-CNN) model based on stochastic quantum circuits for the detection of COVID-19 patients by chest X-ray images. Wang et al. (2023) proposed a quantum behavioral particle swarm optimization (PSO) algorithm applied to optimize neural networks and predict cross-sectional deformation of metal bends formed by a novel variable-diameter mold.

In the aforementioned studies, numerous researchers have explored the integration of QC concepts with metaheuristic algorithms. Specifically, QC has been successfully combined with algorithms such as SMA, DE, and moth-flame optimization algorithm (MFO). Through various experimental studies, it has been established that the incorporation of QC enhances the performance of the original algorithms. This finding presents a novel avenue for algorithmic improvement, encouraging researchers to explore the fusion of QC with diverse metaheuristic algorithms and assess the resultant improvements in algorithm performance. Furthermore, the amalgamation of QC with metaheuristic algorithms has proven to yield novel solutions for a wide range of problems, including airport gate optimization, cluster analysis, and agent coordination. Nevertheless, the application of QC in conjunction with metaheuristic algorithms for addressing PS problems remains inadequately explored within the current research landscape. Based on the aforementioned analysis, the introduction of QC can enhance the performance of metaheuristic algorithms, which will provide a new solution for solving PS problems by combining QC with metaheuristic algorithms to make them useful for solving PS problems. In light of these gaps, our study introduces three strategies, namely QDCE, QRG, and elite mutation (EM) strategy, into the AVOA. The objective is to enhance the performance of AVOA when applied to the PS domain, specifically the PMS and FJSP. Subsequently, the proposed algorithm’s superiority in tackling PS problems is empirically verified through extensive experiments.

This paper presents QEMAVOA, which combines QC and an AVOA. Firstly, QDCE is incorporated into QEMAVOA’s initialization step to boost population diversity and QEMAVOA’s exploration capabilities. Secondly, an EM strategy is applied to exploit QEMAVOA’s capabilities. Finally, the notion of QRG is added to balance QEMAVOA’s exploration and exploitation abilities and avoid QEMAVOA falling into local optimums. The incorporation of the aforementioned three strategies in QEMAVOA has augmented its ability to evade local optima while simultaneously enhancing its exploration and exploitation capabilities. Further, upon conducting a computational complexity analysis, it has been observed that the computational complexity of QEMAVOA and AVOA is analogous. The following are the study’s primary contributions:

• The incorporation of QDCE during the initialization phase of QEMAVOA has conferred enhanced exploratory process on QEMAVOA.

• The introduction of QRG within the iterative process of QEMAVOA has significantly bolstered the escape from local optima capacity of QEMAVOA.

• The introduction of EM within the iterative process of QEMAVOA has significantly bolstered the exploitation capabilities of QEMAVOA.

• The simulation experiment results show that the proposed QEMAVOA has good effect in solving PS problems.

This paper’s remaining sections are structured as follows: Section 2 gives an overview of the AVOA; Section 3 describes QEMAVOA’s specific improvement strategies for the AVOA; Section 4 provides a comprehensive description of PMS and FJSP; Section 5 performs simulation experiments and results analysis; and Section 6 describes the summary and future prospects.

2. African Vultures Optimization Algorithm

The AVOA in general is a novel metaheuristic algorithm that was suggested by Abdollahzadeh et al. (2021). AVOA is proposed by simulating African vulture foraging behavior and habits. The following model is used in AVOA to simulate African vulture activities and foraging behaviors.

Phase 1: population grouping

Initialize the vulture population, compute the fitness value for each vulture, and group the vultures according to their fitness value. The best value is the first group of vultures, the next best value is the second group of vultures, and all the other remaining vultures are in the third group of vultures. The grouping was done as shown in Equation (1):

where |$p_i^t$| is determined using the roulette wheel approach, the value is given in Equation (2), |${L}_1$| and |${L}_2$| are random values from |$[ {0,1} ]$|⁠, and the total of both |${L}_1$| and |${L}_2$| is 1.

where |$f_i^t$| indicates the likelihood of selecting this vulture.

In AVOA, if the parameter value of |${L}_1$| is near 1 and the parameter value of |${L}_2$| is near 0, the convergence will be faster. In contrast, it will increase the diversity of AVOA.

Phase 2: hunger rate of vultures

Vultures frequently seek food, and they will fly long distances to find it. When hungry, vultures become aggressive, circling stronger vultures in quest of food. Equation (3) describes the hunger rate of vultures:

where |$Iteratio{n}_i$| indicates the current iteration count, |$\max iterations$| indicates maximum iterations, |$rand_{i1}^t$| denotes a random value from |$[ {0,1} ]$|⁠, |${z}^t$| is a random value from |$[ { - 1,1} ]$|⁠, whenever the |${z}^t$| value falls below zero, this vulture was hungry, and whenever the |${z}^t$| value rises to one, the vulture was full, and t is determined using Equation (4):

where |$t$| represents a random variable between −2 and 2, and |$\omega $| is the probability that the AVOA will perform the exploitation phase.

Phase 3: exploration stage

This stage corresponds to the exploration stage of AVOA. In AVOA, the authors designed two distinct exploration patterns. They used one parameter |${p}_1$| to choose which exploration behavior the vulture takes, giving the parameter |${p}_1$| a range of |$[ {0,1} ]$|⁠. The behavior of the exploration phase of vultures can be simulated by Equation (5):

where |$X_i^{t + 1}$| indicates the vulture’s location; |$rand_{p1}^t$|⁠, |$rand_{i2}^t$|⁠, and |$rand_{i3}^t$| are four random numbers between 0 and 1; |$ub$| and |$lb$| indicate upper and lower solution bounds, respectively; and |$D_i^t$| is determined using Equation (6) and indicates the gap from vulture to optimal vulture.

where |$C$| is a random value from |$[ {0,2} ]$|⁠.

Phase 4: first exploitation stage

The vulture starts the first phase of exploitation whenever the value |$| {F_i^t} |$| is between 0.5 and 1. To detect whether the vultures are fighting for food or taking rotational flight, a random parameter |${p}_2$| inside the range |$[ {0,1} ]$| is defined in the initial exploitation phase. When |$rand_{p2}^t \ge {p}_2$|⁠, the vulture competes for food. When |$rand_{p2}^t < {p}_2$| is reached, the vulture begins to rotate in flight. Equation (7) depicts the mathematical model of vulture behavior for this process:

where |$rand_{i4}^t$| and |$rand_{p2}^t$| are random values ranging from |$[ {0,1} ]$|⁠, |$S_{i1}^t$| and |$S_{i2}^t$| are derived from Equations (8) and (9), accordingly.

where |$rand_{i5}^t$| and |$rand_{i6}^t$| are random values ranging from |$[ {0,1} ]$|⁠.

Phase 5: second exploitation stage

The vulture starts the second phase of exploitation whenever the value of |$| {F_i^t} |$| is less than 0.5. To detect whether the vultures are aggregating or attacking, a random parameter |${p}_3$| in the range |$[ {0,1} ]$| is defined in the initial exploitation phase. When |$rand_{p3}^t \ge {p}_3$|⁠, the vultures perform aggregation behavior. When |$rand_{p3}^t < {p}_3$|⁠, the vulture performs attack behavior. Equation (10) depicts the mathematical model of vulture behavior for this process:

where |$rand_{p3}^t$| is a random value ranging from |$[ {0,1} ]$|⁠, |$A_{i1}^t$| and |$A_{i2}^t$| are derived from Equations (11) and (12), accordingly, |$Levy( \bullet )$| denote the Lévy flight (Mirjalili, 2016), and it is calculated as shown in Equation (13).

where |$\delta $| is just a number that is frequently set at 1.5, |${r}_1$| and |${r}_2$| are random values ranging from |$[ {0,1} ]$|⁠. The AVOA flowchart is shown in Fig. 1 according to the above analysis.

Figure 1:

Flowchart of the AVOA.

Open in new tabDownload slide

3. The Proposed Algorithm

The description of AVOA is in Section 2. Because of its ease of use, good optimization performance, and simple parameter settings, AVOA is often used in some practical application problems, and the results obtained are usually competitive. However, AVOA tends to converge to the local optimum and exhibits a phenomenon known as premature convergence in the optimization process (Chen & Zhang, 2022). Three enhancement strategies are incorporated into the original AVOA to address these issues: (i) QDCE, (ii) QRG, and (iii) EM strategy. This section describes these three enhancement strategies in detail.

3.1. Quantum-inspired AVOA

QEMAVOA introduces QC into the standard AVOA algorithm and improves the performance of AVOA by exploiting the properties of quanta. In QEMAVOA, the vulture population is transformed into a quantum vulture population, and the change in the quantum population is used to find the optimal solution of the objective function. In prior research (Cui et al., 2022), the DE was augmented through the incorporation of QDCE and QRG techniques, which enabled it to effectively solve large-scale optimization problems. In light of these findings, we aim to introduce QDCE and QRG from QC into the AVOA. In the subsequent sections, we provide a detailed description of the newly incorporated QDCE and QRG methods.

3.1.1. Introduction of QDCE

The tiniest unit of stored data in QC devices is referred to as a quantum bit. A quantum bit, unlike a classical computer’s storage unit (bit), can be a combination of a “1” and a “0” state. A quantum bit is defined as follows:

where |${\alpha }^2$| and |${\beta }^2$| denote the probability amplitudes of the “0” and “1” states, respectively, and satisfy. Therefore, the definition of a quantum bit can be in accordance with Equation (15):

The idea of quantum encoding is introduced in the AVOA, and the position of a single quantum vulture is defined as shown in Equation (16):

where |$Q{X}_i$| indicate the position of the |$i\mathrm{th}$| vulture, the number of vultures is denoted by |$n$|⁠, the dimensionality of the problem is represented by |$d$|⁠, and every quantum vulture covers two locations in solution space, with each position representing a proposed solution to the issue, whose two positions are defined as shown in Equations (17) and (18):

In order to obtain individuals that can perform fitness calculations, we need to map the quantum position of the vulture to the solution space, assuming that the described issue’s solution space is |$\Omega = [ {lb,ub} ]$|⁠. The position transformation is shown in Equations (19) and (20):

After analysis, the original solution initialization process of real number coding is transformed into the solution initialization process of QDCE. The solution initialization process of quantum encoding is divided into following three steps.

Step1: establish angle matrix

The vulture population is composed of |$N$| vultures, and the issue dimension is |$\dim $|⁠. Probability amplitudes are generated from the angle matrices and used to represent the state of the quantum bits. For quantum initialization, the angle matrix |$N \times \dim $| with angles spanning from 0 to |$2\pi $| should be generated. The generation formula is shown in Equation (21):

where |$l{b}_{ij}$| and |$u{b}_{ij}$| denote minimum and maximum angle values, respectively, |$rand( {0,1} )$| denoting the randomly generated numbers between 0 and 1. The angle matrix generated by Equation (22) is shown below:

Step 2: establish quantum population

|$QX$| denotes one quantum population with |$N$| quantum vultures, each of which takes up two places in the search space. The quantum population is depicted in the following way:

Step 3: solution space transformation

The candidate solutions satisfying the constraints are obtained by mapping the quantum population into the problem’s solution space via Equations (19) and (20).

3.1.2. QRG ’s introduction

In QC, the change in the relative phase of quanta is achieved by quantum operators. The balance of exploration and mining capacity is achieved by modifying the QRG’s rotation angle. In QEMAVOA, the QRG formula is provided in Equation (24):

where |$\Delta \theta $| is the QRG’s rotation angle.

By updating the quantum gate using a QRG, the expression for updating the quantum bits using a QRG is provided in Equation (25).

In QEMAVOA, instead of employing a fixed angle as the QRG’s rotation angle, the rotation angle is dynamically updated by comparing DE (DE/rand/1), DE (DE/rand/2), and PSO algorithms. The comparison process is detailed in Section 5.1. Through comparison experiments, it was decided to use the PSO algorithm to dynamically update the rotation angle. Equation (26) shows the adjustment of the rotation angle by the PSO algorithm:

where |${r}_1$| and |${r}_2$| denoting the randomly generated numbers between 0 and 1, |${c}_1$| and |${c}_2$| are predefined learning factors, |${\theta }_{gj}$| is the angle of the |$j\mathrm{th}$| dimension corresponding to the optimal particle, and |${\theta }_{ilj}$| is the angle of the |$j\mathrm{th}$| dimension corresponding to the historical optimal particle of the |$i\mathrm{th}$| particle.

3.2. EM strategy

The EM strategy is introduced to avoid the drawback that the standard AVOA tends toward the local optimum. In this strategy, the optimal vulture searches for an optimal position in one of its neighborhoods and replaces the original position with this position if it is better than the original position. This increases the likelihood of reaching the best answer and improves EMAVOA’s ability to jump out of the local optimum. The expression of the elite variation strategy is shown in Equation (27):

where |$Mutation{\rm{ }}( \bullet )$| is an arbitrary selection of two–three dimensions and a full ranking of them, then the relevant dimensions of the optimal vulture position are exchanged according to the full ranking results. Suppose a dimension appears to be out of bounds. In that case, new values are randomly generated in that dimension, after which the individual with the best adaptation is retained as the new optimal vulture.

3.3. Pseudo-code and flowchart of QEMAVOA

The QEMAVOA pseudo-code is shown in Algorithm 1. Figure 2 depicts the flowchart of the QEMAVOA.

Figure 2:

Flowchart of the QEMAVOA.

Open in new tabDownload slide

Open in new tab

Algorithm 1: Pseudo-code of QEMAVOA.

Open in new tab

Algorithm 1: Pseudo-code of QEMAVOA.

3.4. QEMAVOA performance analysis

In this section, we analyze the computational complexity and memory efficiency of QEMAVOA, which denote the time complexity and space complexity of the algorithm, respectively.

3.4.1. Computational complexity of the QEMAVOA

Computational complexity is a fundamental measure in computer science that quantifies the difficulty of an algorithm by assessing the computational resources required to evaluate its efficiency and practical availability. In general, computational complexity increases as the size of the problem increases, although the same algorithm may produce different computational complexities for different problem sizes. The complexity of an algorithm is a crucial metric to consider when selecting an appropriate algorithm or problem solution. Therefore, it is essential to conduct a computational complexity analysis on an algorithm to determine its feasibility and practicality for a given problem.

QEMAVOA’s computational complexity consists of six main components: initialize quantum populations, calculation of the fitness value, generation of vulture populations, QRG, vulture location renewal, and optimal vulture EM strategy. Set N as the population size, |$D$| is the issue dimension, and |$T$| denotes maximum iterations. In the quantum initialization phase, a random initialization generates an angle matrix. The time required for this operation is |$O( {ND} )$|⁠. Second, the quantum population is generated and converted to a vulture population, with a time complexity of |$O( {ND} )$|⁠. When starting the iteration, the time complexity is proportional to |$T$|⁠. In this phase, the temporal complexity of the fitness value calculation, vulture position update, and QRG are all |$O( {ND} )$|⁠. Furthermore, the best vulture EM strategy has a computational required of |$O( {LTN} )$|⁠, and |$L$| is the number of total permutations of two or three with a maximum of 6.

QEMAVOA’s time complexity is the total of the time complexity of the six components listed above, and the computation procedure is described in Equation (28):

The basic AVOA has a temporal complexity of |$O( {AVOA} ) = O( {N( {T + TD} )} )$| (Abdollahzadeh et al., 2021). The comparison demonstrates that the temporal complexity of QEMAVOA is comparable to that of AVOA.

3.4.2. Memory efficiency of the QEMAVOA

Space complexity, as a metric, quantifies the memory resources utilized by an algorithm. It captures the supplementary memory space needed during the algorithm’s execution and its propensity to scale with input size. Space complexity analysis primarily considers the memory space occupied by data structures, variables, pointers, and recursive calls, among others, to assess the memory requirements. Analyzing space complexity is crucial for evaluating resource consumption, selecting suitable data structures, and optimizing memory utilization in algorithm design and analysis.

The space complexity analysis of QEMAVOA encompasses several key components: the rotation angle matrix, the real vulture population, the quantum vulture population, and the required parameter settings. Each of these elements contributes to the overall space complexity. It is worth noting that the space complexity of the parameter setting is constant, denoted as |$O(1)$|⁠, signifying that it remains unaffected by the problem size. The spatial complexity of QEMAVOA is determined to be |$O(N)$|⁠, where |$N$| represents the problem size. This complexity arises due to the rotation angle matrix, real vulture population, and quantum vulture population, all of which dynamically adjust as the problem size and parameter settings change. The time complexity associated with the vulture population is |$O(N)$|⁠, which consequently leads to the spatial complexity of AVOA being |$O(N)$|⁠.

In summary, based on the analysis, it can be concluded that both QEMAVOA and AVOA exhibit similar space complexity characteristics, namely linear space complexity. This implies that the amount of additional memory space required by these algorithms grows proportionally with the problem size.

4. PS Problem

PS problems represent a major challenge in manufacturing systems, as they involve the complex task of allocating available manufacturing resources to specific jobs and determining the optimal sequence of operations while satisfying all necessary constraints. Two widely studied PS problems are the PMS problem and the FJSP problem. Both of these problems are known to be NP-hard, indicating their high degree of computational complexity. In this section, a brief introduction to PMS and FJSP issues is provided.

4.1. PMS problem

In this section, we present the mathematical model of the PMS problem along with a detailed description of the coding approach used in applying QEMAVOA to solve this problem.

4.1.1. Mathematical model of PMS

When multiple machines with similar performance can process multiple jobs simultaneously, it is called the PMS problem (McNaughton, 1959). Figure 3 depicts an example with three machines and seven jobs.

Figure 3:

Examples of PMS.

Open in new tabDownload slide

With the primary goal of decreasing the finish time, the PMS problem involves scheduling |$n$| jobs that are waiting in the queue and running on |$m$| computers. The following is the fundamental mathematical model of PMS (Rabadi et al., 2006):

where |${C}_{\mathrm{max}}$| is the maximum termination time, |${C}_j$| is the time required to complete job |$j$|⁠, |${p}_{j,k}$| is the time required to process job |$j$| on machine |$k$|⁠, |${S}_{i,j,k}$| is the order related to processing job |$j$| after job |$i$| on machine |$k$| setup time, |${x}_{i,j,k}$| means that when job |$j$| is processed immediately after job |$i$| on machine |$k$|⁠, then the value of |${x}_{i,j,k}$| is 1, otherwise the value of |${x}_{i,j,k}$| is 0, |$M$| is a large integer.

In Equation (29), the decision variables represent the scheduling order of the jobs, and the maximum completion time under the current scheduling order is calculated by transforming it into the matrix x in the equation. The six constraints are as follows: The first constraint guarantees that each job is processed only once. The second constraint ensures that only one job is assigned to a machine when it starts working on that machine. The third constraint ensures that the job assigned to a machine is accurate. The fourth constraint specifies how the completion time is calculated, while the last two constraints define the range of values for the parameters.

4.1.2. Encoding process of PMS

In this research, the suggested QEMAVOA is used to resolve the PMS issue. For solving the PMS issue, QEMAVOA is applied to the PMS issue using the coding approach from the literature (Kılıç & Yüzgeç, 2019). The encoding process is shown below:

First, the problem dimension is determined using Equation (30):

where |$N$| is jobs, |$M$| is machines.

Finally, based on the dimension |$D$| of the problem derived above, |$D$| random numbers between |$[ {0,1} ]$| are generated to represent the locations of the vultures, the dimensions of the locations are sorted, and the sorted location index vector is used as a candidate solution of PMS. If the index value of any dimension is greater than |$N$|⁠, this is used to indicate the divider’s position. The sub-section character indicates switching to the next machine to run.

Taking two machines with three jobs as an example, the dimension of the problem is determined as 4 by Equation (30), and the problem is encoded in the process as Fig. 4.

Figure 4:

Encoding process for PMS with two machines and three jobs.

Open in new tabDownload slide

4.2. FJSP problem

This section presents the mathematical model of the FJSP problem and details the coding approach used by QEMAVOA to solve it.

4.2.1. Mathematical model of FJSP

JSP is a classical basic model for real-world applications. FJSP, as an extended version of JSP, has greater flexibility, which signifies those jobs in the FJSP problem do not need to process operations on only one machine (Boyer et al., 2021). FJSP is described as |$n$| pieces of workpiece are processed on |$m$| machines. |${n}_i$| represents the overall process for workpiece |$i$|⁠, the order of each process is determined, and each workpiece process has its own processing equipment set. Any equipment in the set can be selected to process that process, but the production time varies depending on the equipment. The purpose of scheduling is to select the most appropriate equipment for each process in the overall production plan and to determine the best production sequence for each machine to ensure the minimum and maximum completion times. Process sequencing and machine selection are two sub-problems of FJSP. Assume |$M = \{ {{M}_k| {1 \le k \le m} } \}$| indicate the machine set. |$J = \{ {{J}_i| {1 \le i \le N} } \}$| indicate the workpiece set. |${O}_i = \{ {{O}_{ij}| {1 \le j \le {n}_i} } \}$| indicate the process set of workpieces |${J}_i$|⁠. The basic mathematical model of FJSP is shown below (Chen et al., 2020):

where |${C}_{\mathrm{max}}$| is the maximum completion time of all operations, |${s}_{i,j,k}$| denotes the start time of operation |${O}_{i,j}$| in machine |${M}_k$|⁠, and |${t}_{i,j,k}$| denotes the processing time of operation |${O}_{i,j}$| in machine |${M}_k$|⁠. The first constraint indicates that the processing times of all operations are greater than 0. The second constraint indicates the priority order in which operations must be executed among themselves. The third constraint indicates that each operation |${O}_{i,j}$| has at least one processable machine. The fourth constraint ensures that each machine can process only one operation at any given time. The fifth constraint specifies the range of values for |${X}_{i,j,k}$|⁠.

4.2.2. Encoding process of FJSP

In this study, the proposed QEMAVOA is applied to solve the FJSP. In order to solve the FJSP, the encoding process of QEMAVOA is required as a way to apply QEMAVOA to the FJSP problem (Yuan et al., 2013). The encoding process is shown below:

Firstly, the problem dimension is determined using Equation (32):

where |$n$| indicate the number of workpieces and |$S{J}_i$| indicate the number of processes of workpiece |${J}_i$|⁠. The dimension |${N}_\mathrm{p}$| of the problem is derived from Equation (32), and |${N}_\mathrm{p}$| random numbers between |$[ { - 1,1} ]$| are generated to represent the vulture’s position |$P = [{p}_1,{p}_2,{\rm{ }}{\rm{. }}{\rm{. }}{\rm{. }},{p}_{Np}]$|⁠. The first |$0.5 \times {N}_\mathrm{p}$| dimensions correspond to the candidate solutions of the process ordering sub-problem; the second |$0.5 \times {N}_\mathrm{p}$| dimensions correspond to the candidate solutions of the machine selection sub-problem, and a vulture position corresponds to a complete candidate solution.

Secondly, a fixed ID is assigned to each operation based on the part number and the process order within. Figure 5 shows this numbering scheme, which is suitable for an instance of three machines, three parts, and two processes per part. After numbering, the order of operations will be determined by the fixed ID. The first |$0.5 \times {N}_\mathrm{p}$| dimensions of the generated candidate solutions are sorted in the inverse order, and the sorted position index vector is corresponding to the ID to get the process order.

Figure 5:

Operations numbering scheme.

Open in new tabDownload slide

Finally, the latter |$0.5 \times {N}_\mathrm{p}$| dimension of the candidate solution is converted to an integer according to Equation (33) as a way to represent the machine selected for the process in the first |$0.5 \times {N}_\mathrm{p}$| dimension:

where |$x(j)$| denotes the random number between |$[ { - 1,1} ]$| originally generated, |$s(j)$| denotes the number of optional operating machines of the process corresponding to |${P}_{j - 0.5 \times Np}$|⁠, |$round()$| denotes the rounding function, and |$u(j)$| denotes the index of the operating machines selected by the process corresponding to |${P}_{j - 0.5 \times Np}$|⁠, so as to obtain the machines selected by the process.

Take three machines, three workpieces, and two processes for each workpiece and each process can be processed on any of the three machines. Determine the dimension of the problem NP as 12 by Equation (33), and the problem is coded in the way shown in Fig. 6. The solutions marked in gray are the solutions for the process operation sequence, and those not marked in gray are the solutions selected by the machine.

Figure 6:

Encoding process for FJSP.

Open in new tabDownload slide

5. Experimental Process and Analysis

In this section, every experiment has been performed on MATLAB R2021(a) with the Windows 10 operating system, a CPU of the Inter(R) Core(TM) i7-9700 at 3.00 GHz, and 16 GB of running memory.

5.1. Experimental proof that QEMAVOA works

In order to test the validity of the QEMAVOA improvement, seven problems from the FJSP were selected: Kacem5, MK10, 13a, Edata_la35, Rdata_la34, Vdata_la33, and VL01, and the problems are described specifically in Section 5.3.

The algorithms involved in the experiments are the AVOA, African vultures optimization algorithm with elite mutation strategy (EMAVOA), quantum-inspired African vultures optimization algorithm with elite mutation strategy (QEMAVOA-DE), quantum-inspired African vultures optimization algorithm with elite mutation strategy (QEMAVOA-DE2), and QEMAVOA. Where EMAVOA is the standard AVOA introducing the elite mutation strategy, QEMAVOA-DE is the quantum-inspired idea based on EMAVOA and uses the DE algorithm (DE/rand/1) to calculate the rotation angle, and QEMAVOA-DE2 is the quantum-inspired idea based on EMAVOA and uses the DE algorithm (DE/rand/2) to determine the rotation angle.

To ensure the fairness and validity of the experiments, we set the population size to 50, the maximum number of iterations to 500, and 10 independent runs. The parameter settings used by the different algorithms are shown in Table 1. The parameter settings for AVOA were taken from previous studies in the literature (Abdollahzadeh et al., 2021), while the parameters specific to each algorithm were determined empirically as well as after experimental discussions.

Table 2 shows the mean values of 10 runs obtained by each algorithm, where the bolded font indicates the optimal value for each problem, and the problem size denotes the number of jobs and machines. Figure 7a and b show the mean convergence zone lines for the Rdata_la34 and VL01 problems, respectively. Figure 8a and b show the box plots for the Rdata_la34 and VL01 problems, respectively.

Figure 7:

Mean convergence curve of Rdata_la34 and VL01.

Open in new tabDownload slide

Figure 8:

Box plot of Rdata_la34 and VL01.

Open in new tabDownload slide

Table 3 shows the combined Friedman ranking of the following algorithms: AVOA, EMAVOA, QEMAVOA-DE, QEMAVOA-DE2, and the proposed QEMAVOA algorithm. The rankings are determined based on the optimal results, average results, and standard deviations of 10 independent runs of each algorithm. The final ranking is obtained by the Friedman test, which calculates the Friedman value based on the optimal result, the average result, and the standard deviation, and takes the average of the three different Friedman values. Finally, the algorithms are ranked using Friedman’s means. The results show that QEMAVOA obtained the best ranking. Figure 9 shows the overall ranking results.

Figure 9:

Comprehensive ranking of algorithms.

Open in new tabDownload slide

The effectiveness of the algorithm improvements was verified through a series of experiments aimed at evaluating its performance. The experiments encompassed comprehensive assessments of the algorithm’s capabilities, including the application of the Friedman test to determine the algorithm’s overall performance in comparison to other algorithms. The results indicated that QEMAVOA ranked first among the compared algorithms, affirming the superiority of the introduced enhancements. Notably, the incorporation of three strategies, namely QDCE, QRG, and EM, significantly improved the algorithm’s performance, surpassing that of AVOA specifically for the FJSP problem.

5.2. PMS test results

The PMS case in this study is drawn from the literature (Kılıç & Yüzgeç, 2019). In this application, four parallel machines have a total of 20 jobs, and the runtime of each job is given by a matrix |$p[ {20 \times 4} ]$|⁠, and the setup time for each job to finish processing before processing another job is represented using a matrix |$s[ {20 \times 20 \times 4} ]$|⁠.

The QEMAVOA has solved the PMS problem. Its performance has been compared to the algorithms evaluated in the literature (Kılıç & Yüzgeç, 2019). The comparison algorithms are shown below: improved antlion optimization algorithm via tournament selection (IALOT), antlion optimization algorithm (ALO), firefly algorithm (FA), MFO, genetic algorithm (GA), grasshopper optimization algorithm (GOA), dragonfly optimization algorithm (DA), gray wolf optimization algorithm (GWO), biogeography-based optimization algorithm (BBO), and PSO.

In the comparison experiments, QEMAVOA was run 10 times with an overall size of 20 and a maximum number of 1000 iterations. The parameters of the algorithm used in this study are listed in Table 4, which were set based on previous studies (Abdollahzadeh et al., 2021; Kılıç & Yüzgeç, 2019). Simulation experiments were performed using the proposed QEMAVOA algorithm, and the results are presented in Table 5. The experimental results obtained by QEMAVOA were compared with those reported in the literature (Kılıç & Yüzgeç, 2019).

The results of 10 independent runs of QEMAVOA to solve the PMS are presented in Table 5. The table includes the average value, best value, worst value, and standard deviation of the results obtained in 10 independent runs of all algorithms and the ranking of each metric obtained by QEMAVOA. When average cost and best cost are chosen as evaluation indicators, it can be seen that QEMAVOA achieves the best results in both indicators (mean cost = 115, best cost = 111), and Fig. 10 shows the best results obtained by QEMAVOA. When the worst cost and standard deviation are chosen as evaluation metrics, the GOA algorithm obtains optimal results (worst cost = 119, standard dev = 1.636).

Figure 10:

Results obtained by QEMAVOA for PMS problem.

Open in new tabDownload slide

The effectiveness of QEMAVOA in solving the PMS problem is evaluated by comparing its performance with other metaheuristic algorithms. However, the runtime of the algorithm is also a crucial factor to consider when solving the PMS problem. Therefore, the runtime of QEMAVOA is compared to that of AVOA. Figure 11 shows the comparison results. The experimental results indicate that QEMAVOA shows superior performance in solving the PMS problem while having a runtime comparable to that of AVOA.

Figure 11:

QEMAVOA and AVOA runtime comparison in PMS.

Open in new tabDownload slide

The algorithm’s superiority in solving the PMS problem was confirmed through dedicated experiments involving QEMAVOA. These experiments encompassed 10 independent runs, each producing optimal values, mean values, worst values, and standard deviations, enabling a comprehensive comparative analysis. The experimental results demonstrated that QEMAVOA outperformed the other algorithms considered for solving the PMS problem. Furthermore, runtime experiments were conducted, comparing QEMAVOA against AVOA in 10 independent trials. The results revealed that QEMAVOA exhibited slightly slower runtime performance compared to AVOA. In summary, the analysis concluded that QEMAVOA showcased exceptional performance in solving the PMS problem, albeit with a slightly longer runtime.

5.3. FJSP test results

In this section, the performance of the proposed QEMAVOA in solving the FJSP problem is evaluated. For this purpose, a series of simulation experiments are performed to apply QEMAVOA to the FJSP problem. To verify the effectiveness of QEMAVOA, the results of previously published studies have been chosen as a basis for comparison.

5.3.1. Experimental setup

To verify the performance of QEMAVOA in solving FJSP, the following problem datasets were considered in the experiments:

• Kacem dataset: This dataset is derived from a set of five problems proposed by Kacem et al. (2002). The jobs range from 4 to 15, and the machines range from 5 to 10. These five problems are fully flexible.

• Brandimarte dataset: This dataset is derived from a set of 10 problems proposed by Brandimarte (1993). The number of operations ranged from 10 to 20, and the number of machines ranged from 4 to 15. These 10 problems are partially flexible, with flexibility between 1.43 and 4.10 per operation and the number of operations between 55 and 240 for all operations.

• Dauzere dataset: This dataset is derived from a set of 18 problems proposed by Dauzère & Paulli (1997). The jobs range from 10 to 20, and the machines range from 5 to 10. These 18 problems are partially flexible, with flexibility between 1.13 and 5.02 for each operation and several operations between 196 and 387 for all operations.

• Hurink dataset: This dataset is derived from three sets of 129 problems proposed by Hurink et al. (1994). These problems are divided into Edata, Rdata, and Vdata (Behnke & Geiger, 2012; Hurink et al., 1994; Kasapidis et al., 2021), each containing 66 problems and differing in the flexibility of each operation. In this dataset, the number of jobs ranges from 6 to 30, the number of machines ranges from 5 to 15, and the flexibility of each job ranges from 1.15 to 7.5, with an average flexibility of 1.15 for Edata, 2 for Rdata, and 5 for Vdata. The number of operations for all operations ranges from 36 to 300.

• Large dataset: This dataset comes with a large-scale dataset generated based on Brandimarte’s rules, which contains three large-scale problems named VL01, VL02, and VL03 (Brandimarte, 1993; Escamilla-Serna et al., 2022; Sun et al., 2019). In the dataset, there are 50 to 80 jobs and 20 to 50 machines. These three problems are partially flexible, with an average flexibility rate of 0.75 per operation.

Due to the uncertainty of the algorithm, 10 independent experiments were conducted for each dataset. The parameter settings of QEMAVOA proposed in this paper are referred to in Table 4. The present study evaluates the performance of QEMAVOA in solving the FJSP problem by comparing its makespan with those obtained by the participating comparison algorithms, which all take the optimal makespan from their respective papers. At the same time, the n × m in the result statistics table represents the number of jobs and machines.

5.3.2. Kacem dataset

For the experiments with the Kacem dataset, the size of the QEMAVOA populations was 100 and the number of maximum iterations was 300. Table 6 shows the results of the comparison of QEMAVOA with other algorithms containing the following: BBO, artificial immune algorithm (AIA), hybrid tabu search algorithm (HTSA), teaching learning based optimization algorithm (TLBO), improved Jaya algorithm (IJA), hybrid artificial bee colony algorithm (HABC), and genetic algorithms and random-restart hill-climbing (GA-RRHC). For the algorithms to be compared, the best values from the respective papers have been used. With three solutions to the problem in the AIA literature and four solutions to the problem in the BBO literature.

As demonstrated in Table 6, BBO and AVOA algorithms obtained two optimal solutions each, AIA and BBO algorithms obtained three optimal solutions each, TLBO and QEMAVOA algorithms obtained four optimal solutions each, while HTSA, IJA, HABC, and GA-RRHC algorithms obtained all optimal solutions. When compared with other algorithms on the Kacem dataset, QEMAVOA’s performance was not outstanding, but it exhibited better performance than AVOA.

5.3.3. Brandimarte dataset

For the experiments with the Brandimarte dataset, the size of the QEMAVOA populations was 100 and the number of maximum iterations was 500. Table 7 shows the results of the comparison of QEMAVOA with other algorithms. The compared algorithms contain the following: deep reinforcement learning (Deep RL), DA, human learning optimization algorithm and particle swarm optimization algorithm (HLO-PSO), improved particle swarm optimization algorithm (IPSO), self-learning genetic algorithm (SLGA), hybrid whale optimization algorithm (HWOA), and hybrid gray wolf weed algorithm (GIWO). For the algorithms to be compared, the best values from the respective papers have been used. There are six solutions to the problem in the DA literature.

Table 7 shows the results of the comparison among different algorithms on the Brandimarte dataset. DA was unable to obtain an optimal solution, while Deep RL obtained an optimal solution. HLO-PSO, IPSO, GIWO, and AVOA obtained three optimal solutions. In contrast, SLGA and HWOA obtained six optimal solutions, and QEMAVOA obtained eight optimal solutions. Notably, QEMAVOA outperformed other algorithms on this dataset.

5.3.4. Dauzere dataset

For the experiments with the Dauzere dataset, the size of the QEMAVOA populations was 100 and the number of maximum iterations was 1000. Table 8 shows the results of the comparison of QEMAVOA with other algorithms. The compared algorithms contain the following: integrated approach based on tabu search (IATS), TS, general particle swarm optimization (GPSO), discrepancy search (DS), and multi-swarm collaborative genetic algorithm (MSCGA).

Table 8 presents the results obtained by different algorithms on the Dauzere dataset. IATS and GPSO failed to find optimal solutions, while AVOA obtained three, TS and DS obtained five, and MSCGA obtained six optimal solutions. In contrast, QEMAVOA outperformed other algorithms by finding 12 optimal solutions. The experimental results demonstrate the superior performance of QEMAVOA in solving FJSP problems on the Dauzere dataset.

5.3.5. Hurink dataset

The Hurink dataset contains three sub-sets: Edata, Rdata, and Vdata, each containing 66 problems. The three sub-sets differ in the average flexibility of their operations, with the Hurink Edata dataset having an average flexibility of 1.15, the Hurink Rdata dataset having an average flexibility of 2, and the Hurink Vdata dataset having an average flexibility of 5.

For the experiments with the Hurink dataset, the size of the QEMAVOA populations was 100 and the number of maximum iterations was 1000. The results of QEMAVOA compared to other algorithms on the Hurink Edata dataset are shown in Table 9. The results of QEMAVOA compared to other algorithms on the Hurink Rdata dataset are shown in Table 10. The results of QEMAVOA compared to other algorithms on the Hurink Vdata dataset are shown in Table 11. The compared algorithms contain the following: TS, constraint programming (CP), PSO, two-level metaheuristic of the upper-level algorithm (MPM-UPLA), and graph-based multi-agent system (GMAS). The algorithms for the comparison were chosen from the best values in their respective papers. With 43 solutions to the problem in the TS and PSO literature and 40 solutions to the problem in GMAS.