Quantum-inspired hybrid algorithm for integrated process planning and scheduling

Abstract

Process planning and job shop scheduling problems are the two classical but crucial activities in manufacturing system. With the approach of integrated process planning and scheduling, the two actual activities are combined to conduct operation selection and operation sequencing with the constraints of practical job shop status. In this article, a quantum-inspired hybrid algorithm with the objective of minimum makespan is proposed, aiming to solve integrated process planning and scheduling problems in dynamic manufacturing systems. A hybrid-coding representation is suggested, which is a three-layer structure in numerical representation and Q-bit representation adopted from quantum-inspired evolutionary algorithm. Based on the hybrid-coding representation, customized converting and repairing rules and methods are presented to generate feasible individuals. Q-gate rotation and group leader optimization algorithm are integrated systematically for the population evolution to accelerate the convergence speed of the proposed algorithm. In order to increase the diversity of population, a chaotic map called logistic map is introduced, bringing the stochastic initial individuals. Experiments show that the proposed hybrid algorithm can generate outstanding outcomes for integrated process planning and scheduling instances.

Introduction

In traditional approaches, process planning and scheduling were carried out in a sequential way. Process planning, in a systematic way, determines how a product should be manufactured economically and competitively.^1,2 A schedule based on some objectives is determined by suitable process plan, manufacturing resources, and sequenced operations which satisfy the technological constraints. ³ After conducting process planning, scheduling assigns a specific task to a specific machine in order to satisfy a given performance measure.^4,5 The two functions of process planning and scheduling are tightly interwoven with each other. ⁶

However, there are disturbances in job shop,^7–9 such as machine breakdowns, order cancellation, rush order, stochastic job arrivals. When scheduling is always conducted separately after the process plans, the two important manufacturing planning activities may come into conflict. For instance, production machines may be unbalance, and process plan may be infeasible for dynamic manufacturing, ¹⁰ and the constraints considered in the planning phase may change greatly in the subsequent scheduling phase. ⁷

Integrated process planning and scheduling (IPPS) was proposed to solve the above realistic manufacturing problems and adapt to the dynamic manufacturing environment. IPPS has been studied for around 31 years since proposed by Chryssolouris et al. ¹¹ in 1984. IPPS problems are about n parts processed on m machines with alternative process plans, manufacturing resources and other technological constraints. ¹² IPPS combines design, manufacturing, and dynamic manufacturing environment and can improve flexibility, dynamism, adaptability, agility, and productivity of distributed manufacturing system. ¹² Meanwhile, IPPS can measure throughput time, resource utilization, work-in-process inventory, average flow time, and average tardiness. ¹³ Besides, it takes consideration on the conflicting criteria simultaneously, which can result in production cost reduction, bottleneck elimination, balanced level of machine utilization, and improved facility productivity. ¹⁴ Furthermore, the integration eliminates the mistiming ¹⁵ of production planning and plan execution. Thus, the plan is more realistic without frequent modification. ¹⁶

As an NP-hard, IPPS problems have been widely researched by academics. To improve solution quality of IPPS, and solve the problems more efficiently and effectively, a lot of research work have been done on it. However, the best method has not been found yet. Aiming to make some contributions to efficient algorithms, a quantum-inspired hybrid algorithm (QHA) combining the merits of three different algorithms is proposed in this article.

The rest of this article is organized as follows: section “Literature review” gives relevant literature reviews on IPPS, quantum-inspired evolutionary algorithm (QIEA), group leader optimization algorithm (GLOA), and chaotic maps (CMs). Section “Representation of the IPPS problem” presents the representation of the IPPS problem. QHA is elaborated in section “Proposed QHA.” Experimental studies and discussions are displayed in section “Experimental studies and discussions.” Finally, section “Conclusion and future work” draws the conclusions and suggests the future work.

Literature review

In this section, the literature researching on IPPS, QIEA, GLOA, and CM is reviewed separately. Algorithms for solving IPPS problems are reviewed first. Sequentially, concepts and applications of QIEA are given as the second aspect of this section. In addition, concepts and the advantages of GLOA and CM are introduced, respectively.

Algorithms for IPPS

As described in section “Introduction,” IPPS has attracted many researchers’ attention. In addition to integration models^17,18 and implementation approaches,^19,20 algorithms innovation or improvements^7,21–23 have been well studied in the previous research.

It is impossible to achieve optimal solutions by traditional accurate algorithms with reasonable efforts, ⁶ as IPPS problems are NP-hard. A wide variety of algorithms have been adopted to find near-optimal solutions efficiently, ²¹ in which genetic algorithm (GA) is the most popular heuristic algorithm.^{7,14,21,24–27} GA has a good global search capability. It was used to generate the feasible sequences of operations and identify the optimal tool sequence in process planning for machining. ²⁷ It was relatively rare to apply GA individually. ²⁸ GA was usually applied combining with other algorithms or in a modified form.

Shao et al. ²⁹ developed a modified genetic algorithm (MGA)–based approach. In order to improve IPPS, in this algorithm, genetic representations and operator schemes were modified. First, process planning and scheduling were encoded and decoded separately. Process planning individual was composed of OR string and process plan string (pps). OR string with numerical indexes determined which process plan was chosen. Scheduling population consisted of scheduling plan string (sps) and pps. Second, the tournament selection scheme was used for reproduction operation. OR relationship was defined to describe the processing flexibility which the same manufacturing feature could be processed by different process procedures. ²⁹

Based on the research work of Shao et al., ²⁹ Li et al. ²⁰ employed MGA as an optimization agent to get more effective solutions. Furthermore, this research team developed MGA to solve a mathematical mode of IPPS based on the methodology of nonlinear process planning. ¹⁷ The mentioned research team introduced another algorithm Tabu search (TS) to combine with GA. ³⁰ TS was adopted as the local search strategy for every individual, while GA was employed to search global solution space. As a further study, the hybrid algorithm composed of GA and TS was applied to improve search speed, and Nash equilibrium was introduced to solve the between objectives in multiobjective IPPS problem. ³¹ Meanwhile, the researchers in the team developed GA with learning ability ²⁵ to facilitate the integration and optimization of process planning and scheduling. Besides, an MGA was adopted to explore the optimal solution (Pareto solution) between energy consumption and makespan. ³² This was an HA consisted of GA and simulated annealing (SA).

In order to generate a feasible and near-optimal initial individual for process plan from the process plan network that could include all the possible combination, Qiao and Lv ¹⁰ proposed an initial process plan selection method to generate the near-optimal individuals from all existing feasible process plans based on GA. Meanwhile, a hybrid genetic algorithm (HGA) with problem-specific genetic operators and a local search procedure was introduced in Amin-Naseri and Afshari. ¹⁴ A fast multiobjective GA with archive mechanism and generalized Pareto-based scale-independent fitness function was proposed to deal with IPPS problem with objectives of makespan and minimization of the maximum variation of workload of machine. ²⁶

Lv and Qiao ³³ developed an improved EA with new genetic representation for the scheduling plan based on GA. To solve the IPPS problem in multiplant consisted of a network of production facilities, Moon and Seo ³⁴ developed GA combined with a topological sort technique. Also, another HGA was applied to solve IPPS problems. ³⁵

In the newest research work, Mohapatra et al. ²⁴ proposed an improved controlled elitist nondominated sorting genetic algorithm (NSGA) to take into account the computational intractability of IPPS. An HA of GA and particle swarm optimization (PSO) was adopted, ²⁴ while Zhang and Wong ²¹ proposed an algorithm called object-coding genetic algorithm (OCGA) to improve the representation schemes. OCGA was composed of the real-object represented chromosome, customized genetic operations, and reconstructed evolutionary strategies. The “object” referred to a machining operation on a dedicated processing machine for IPPS problems.

Some other algorithms were also introduced in this area such as imperialist competitive algorithm (ICA), ²³ ant colony optimization, ²² PSO, ⁷ SA algorithm, ³⁶ and so on. Some of the research work is described in the following.

A branch and bound algorithm was chosen for searching. ³⁷ It started by sequencing one of the available jobs, called branching the node. In branching process, a new node was formed and kept in the search space, if its lower bound value was better than the upper bound value and vice versa. The algorithm stopped when the upper bound value was smaller than all lower bound values, and the process plan was the sequence that yielded the upper bound solution. The algorithm’s robust and enumerative nature yielded a near-optimal solution.

Considering process planning and scheduling as two different populations, Kim et al. ⁶ proposed a symbiotic evolutionary algorithm (SEA). SEA was a cooperative algorithm, based on positive fitness interactions between individuals of different populations. The strategies of localized interactions, steady-state reproduction, and random symbiotic partner, as well as genetic representations and operator scheme selection, were adopted in this algorithm.

To improve the global searching ability of standard SA, Mohammadi et al. ³⁶ combined it with TS. Compared with GA and SA proposed by Li et al., ³⁸ Guo et al. ³⁹ presented a modified PSO algorithm. In this algorithm, initial solutions were formed and encoded into particles. Meanwhile, operators of mutation, crossover, and shift were developed and incorporated.

Li et al. ⁴⁰ modified the PSO algorithm to solve the discrete problems, aiming to consider the operation selection and operation sequencing concurrently to achieve optimal or near-optimal solutions. What is more, the researchers developed efficient encoding, updating, and random search methods to improve the performance of the approach.

ICA was not a widely applied algorithm in IPPS area. Lian et al. ²³ employed it with an extended operation-based representation scheme, which included information on various flexibilities of process planning with respect to determined job shop scheduling, and another new algorithm nested partition algorithm was employed by Mohapatra et al. ⁴¹

The mentioned algorithms performed outstandingly in solving IPPS problems and generated good results by benchmarking. However, the majority of the mentioned heuristic algorithms were applied to find the near-optimal solutions. The adjacent degree between the near-optimal solutions and optimal solutions could not be determined, and in some cases, improvements of the solutions were not very manifest.

QIEA

QIEA was adapted from quantum computing in Physics. ⁴² Similar to the evolutionary algorithms (EAs), QIEA is also characterized by the representation of the individual, the evaluation function, and the population dynamics. However, a Q-bit is used instead of binary, numeric, or symbolic representation. Also, a Q-gate is used as the evolutionary operator, and an observation process is employed to connect the Q-bit representation with the optimization variables. ⁴³

Q-bit is the smallest unit of information as probabilistic representation. It may be in the “1” state, in the “0” state, or in any superposition of the two. A Q-bit is defined with a pair of numbers $(\alpha ,\beta )$ as

$${[\alpha ,\beta ]}^T$$

(1)

where ${\left|\alpha \right|}^2+{\left|\beta \right|}^2=1$ . ${\left|\alpha \right|}^2$ gives the probability that the Q-bit will be found in the “0” state, and ${\left|\beta \right|}^2$ gives the probability that the Q-bit will be found in the “1” state.

A Q-bit individual is defined by a string of Q-bits. For example, an individual of n Q-bits can be defined as

$$\left[\begin{array}{c}{\alpha }_1\hfill \\ \multicolumn{1}{c}{{\beta }_1}\end{array}|\begin{array}{c}{\alpha }_2\hfill \\ \multicolumn{1}{c}{{\beta }_2}\end{array}|\begin{array}{c}\cdots \hfill \\ \multicolumn{1}{c}{\cdots }\end{array}|\begin{array}{c}{\alpha }_n\hfill \\ \multicolumn{1}{c}{{\beta }_n}\end{array}\right]$$

(2)

where ${\left|{\alpha }_i\right|}^2+{\left|{\beta }_i\right|}^2=1,i=1,2,\dots ,n$ .

A Q-bit individual has the advantage that it can represent a linear superposition of states in search space probabilistically. When employing the probabilistic observation process, each Q-bit can be rendered into one binary bit. Thus, the Q-bit representation has a better characteristic of population diversity than other representations. The number of the linear superposition of states is $2^n$ .

For example, when $n=3$ in equation (2), the string may be

$$\left[\begin{array}{c}{\alpha }_1\hfill \\ \multicolumn{1}{c}{{\beta }_1}\end{array}|\begin{array}{c}{\alpha }_2\hfill \\ \multicolumn{1}{c}{{\beta }_2}\end{array}|\begin{array}{c}{\alpha }_3\hfill \\ \multicolumn{1}{c}{{\beta }_3}\end{array}\right]=\left[\begin{array}{c}\frac{1}{3}\hfill \\ \multicolumn{1}{c}{\frac{2\sqrt{2}}{3}}\end{array}|\begin{array}{c}\frac{\sqrt{15}}{4}\hfill \\ \multicolumn{1}{c}{\frac{-1}{4}}\end{array}|\begin{array}{c}\frac{1}{2}\hfill \\ \multicolumn{1}{c}{\frac{\sqrt{3}}{2}}\end{array}\right]$$

(3)

For each Q-bit, a very small value ${\eta }_i,{\eta }_i\in [0,1]$ is generated randomly. If ${\eta }_i<{\left|{\alpha }_i\right|}^2$ , the observation value of the ith Q-bit is 0. Otherwise, it is 1. ${\left|{\beta }_i\right|}^2=1-{\left|{\alpha }_i\right|}^2$ . The observed superposition of equation (3) will be $|010〉$ , $|011〉$ , $|000〉$ , $|001〉$ , $|110〉$ , $|111〉$ , $|100〉$ , and $|101〉$ , and the number of superposition of states is $2^3=8$ .

Regrettably, in existing articles, the multi-Q-system’s superposition of states was not applied widely in QIEA for individual representation. Instead, the observed state of each Q-bit was used directly. To be specific, if a binary individual with 160 bits is needed, two Q-bit representing ways can be employed. The first one is to construct a Q-bit individual with five Q-bits and then observe superposition of states. The number of superposition is $2^5=32$ . Then obtain the binary individual with $32\times 5=160\mathrm{bits}$ . The second one is to construct a Q-bit individual with 160 Q-bits and observe the state of each Q-bit and obtain the result. Obviously, when the number of bits of a binary individual needed is very large, the second way will occupy big storage space.

A Q-gate is used to modify the state of a Q-bit, playing the role of evolutionary operator. There are various gates such as the rotation gate, NOT gate, AND gate, NAND gate, and Hadamard gate. ⁴⁴ Rotation Q-gate is employed in this article.

QIEA has been significantly developed since proposed by Han and Kim ⁴² It was always employed combining with other conventional heuristic algorithms. PSO was one of the most frequently used one.^45–52 Other incorporated algorithms included GA,^53–57 gravitational search algorithm,^58–60 back-propagation (BP) neural network algorithm, ⁶¹ and so on.

QIEA has the characteristics of strong searching capability, rapid convergence, short computing time, and small population size. ⁵⁷ Due to high performance of QIEA, there were many successful efforts that variations of QIEA have been applied to practical real-world problems. The solved problems included job shop scheduling,^53,55,56 the 0-1 knapsack sharing problem,^45,58,60,61 traveling salesman problem, ⁵¹ quality of service (QoS) multicast routing in networks, ⁴⁹ and so on. The previous research showed that heuristic algorithms combining with QIEA could solve problems much more efficiently. However, QIEA has not been widely noted in the field of IPPS.

GLOA

GLOA is a new global optimization EA. It was first proposed by Daskina and Kais ⁶² in 2011. GLOA was inspired by the leaders’ social characteristics. Leaders in social groups command members to complete task. Members’ characteristics and performance are affected by the leaders’ qualities. When a member’s leadership is trained to be better than the old leader, the new one is substituted for the old one.

GLOA is a continuous iteration and cycle process. ⁶³ The following six steps constitute the standard GLOA process: ⁶²

• Step 1. Generate g groups and m members for each group randomly.

• Step 2. Calculate fitness values for all members in all groups.

• Step 3. Appoint the leader for each group. A member with the best fitness value in the group is the leader.

• Step 4: mutation and recombination. This step aims to create new excellent members using the old members, group leader, and a random element. The expression is as follows

$$\mathrm{new}=r_1\times x+r_2\times \mathrm{leader}+r_3\times \mathrm{random}$$

(4)

where $r_1$ is the genetic probability of old member, $r_2$ is the impact factor of group leader, $r_3$ is the random factor, and x is the old member to be mutated. $r_1+r_2+r_3⩽1$ . If the new member’s fitness value is better than the old one, then the new one replaces the old one. Otherwise, retain the old member.

• Step 5: one-way crossover. This operator is performed from the first group to the last one. Choose a member in the group randomly and then transfer some parameters of it from another random member in another random group. If the generated new member has a better fitness value, then substitute it for the old one. Otherwise, keep the old member.

• Step 6. Repeat steps 3–5 number of given iteration times.

GLOA is able to search the solution space surrounding the leaders, which are possibly local or global minima. The members of the groups are not subjected to a local minimization. Therefore, GLOA allows the population to converge on global minima in a very fast way. For more details of GLOA refer to Daskina and Kais. ⁶²

CMs

Chaos is the highly unstable motion of deterministic systems in finite phase space which often exists in nonlinear systems.^64,65 Chaos theory was epitomized as so-called butterfly effect by Lorenz. ⁶⁶ For a chaotic system, its inherent structure is exquisite with nonperiod, nonconverging, and bounded. It has a very sensitive dependence on its initial condition and parameter. Although the difference in the initial value is very small, it would rise to large in its long-time behavior. That is to say, a slight change may yield the chaotic system to great differences in the output. ⁶⁷

CMs^68–70 are usually used for modeling chaos. A CM is a dynamical discrete-time continuous value function. It defines the relationship between the current and following state of a chaotic system

$$Z_{k+1}=f\left(Z_k\right),0<Z_k<1,k=0,1,2,\dots$$

(5)

running in chaotic state. The chaotic sequence $\{Z_k:k=0,1,2,\mathrm{\dots }\}$ can be used as spread-spectrum sequence as random number sequence.

Logistic map (LM) is one of CMs, which is adopted in this article. The expression of LM can be described as in equation (6)

$$Z_{n+1}=u{Z}_n(1-Z_n)$$

(6)

where $0<u⩽4,Z_n\in (0,1)$ . The equation appears in nonlinear dynamics. It generates chaotic sequences in (0, 1), which appeals how complex behavior can arise from a very simple nonlinear dynamical equation. Because of the characteristics of randomicity and ergodicity, CMs have attracted a great deal of researchers’ interesting.

Zhang et al. ⁷¹ proposed an HA, consisting of artificial immune system (AIS), chaos operator, and PSO, to solve the path-finding problem in stochastic networks. Chaos operator was used to generate new offspring. For the algorithm performance studies, Alatas ⁶⁷ combined CMs with harmony search (HS). The experiments showed that CMs could improve the global searching capability of HS by escaping the local solutions. It was because chaotic number generators could generate a random number each time needed by the classical HS algorithm. As extended work, Alatas ⁷² utilized CMs with artificial bee colony (ABC) for parameter adaptation. Taking advantages of CMs, HS with CM and ABC with CM were applied in work by Xu et al. ⁶⁴ and Pan et al., ⁷³ respectively, to escape the local optimal solutions and avoid from the premature of the individuals.

To further enhance the global search ability of accelerated PSO (APSO), Gandomi et al. ⁷⁰ introduced 12 different CMs into APSO and found a most efficient combined algorithm. In application, CMs were employed as a compound chaotic search to emphasize exploitation ability of PSO for the job shop scheduling problem. ⁶⁹ And for scheduling a stochastic parallel processor system, Mokhtari and Salmasnia ⁶⁸ employed eight CMs combined with a differential evolution (DE) algorithm. The combination avoided the algorithm being trapped in local optimum.

The three algorithms or methods have their own advantages separately. Regrettably, none of the research has focused on the HA of the three. Thus, in this article, the authors first attempt to combine them to solve IPPS problems.

Representation of the IPPS problem

IPPS problems studied in this article can be described as n jobs performed on m machines. Each job has several operations, and each operation can be operated on one or more machines. ²⁴ The job may indicate a part or a product. The operations of one job may have conjunction, disjunction, and precedence relationships between them. ²¹

An AND-OR graph is usually used to represent the alternative performed sequences for one job. As shown in Figure 1, in an AND-OR graph, there are six node types: starting node, operation node, ending node, OR node, AND node, and JOIN node. ¹⁰ A starting node and an ending node are dummy ones and, respectively, indicate the start and the completion of the manufacturing process of a job. ⁶

Figure 1.

AND-OR graph of alternative process plans of (a) job 1 and (b) job 2.

An operation node contains the alternative machines and the corresponding processing times. The unidirectional solid arrows connecting the nodes represent the precedence relation between them. OR nodes express that the links after them are the alternative processed paths for the same manufacturing feature. The end of the OR-link path is denoted by a JOIN node. AND nodes denoting the links after them are the sequence of operations. AND-link paths end to a JOIN node.

Two jobs’ alternative process plans are shown in Figure 1. In Figure 1(a), path 1-2-3-4-5 is the only one path for job 1. In Figure 1(b), paths 1-3-5-6-7-8 and 2-4-5-6-7-8 are the alternative paths for job 2, linked by the OR node.

Proposed QHA

In QHA, Q-bit of QIEA is employed for individuals’ presentation, and rotation Q-gate is used as one evolutionary operator. GLOA is blended with QIEA as searching strategies, and LM is applied to initialize Q-bit individuals.

QHA framework

The framework of QHA is shown in Figure 2. It is composed of two sections. The first one is generating the initial solutions. Q-bit-encoded and chaotic-generated individuals have good diversity because of the superposition of states and stochastic processes. The second one is improving the members toward the leaders to get the best solution by evolutionary operation. However, algorithm performance would be decreased significantly if invoking mutation and crossover operators is too frequent. To avoid such drawback, the crossover operation between different groups is abandoned.

Figure 2.

Framework of QHA.

Encoding, converting, repairing, and decoding

Encoding

With regard to IPPS problems, the operation flexibility, sequencing flexibility, and processing flexibility bring in three different dimensions. Thus, each member in QHA consists of three parts with different lengths as shown in Figure 3.

Figure 3.

Strings of a member.

The first part of a member is pps. The length of pps is n. n is the number of jobs. Each bit in the string denotes the selected process plan of each job. In other words, the numerical index in the ith bit represents the selected alternative process plan of job i. For instance, in Figure 1, job 2 has two alternative process plans. In Figure 3, the numerical index “2” in the second bit of pps means the second process plan is chosen for job 2, and the processed path is determined as 2-4-5-6-7-8, simultaneously.

The second part is Q-bit sps (q_sps). Each bit of q_sps is a pair of complex number $\alpha$ and $\beta$ . ${\left|\alpha \right|}^2+{\left|\beta \right|}^2=1$ . The length of the string is N

$$N=\left[{\log }_2^{\mathrm{op}}\right]+1$$

(7)

where op is the sum of maximum number of operations which is in the alternative process plans of each job. In Figure 1, op is 11. [] specifies [x] = max{z|z ⩽ x, z is an integer}. ⁵⁵

The third part is machine string (mns). It is generated according to the selected process plans in pps. Once the process plan of job i is determined, the candidate machines are generated. Then choose machine for each operation randomly from the candidates. mns encodes in a numerical way. The length of mns is ope. ope is the sum of the number of operations in selected process plans in pps. It is divided into n parts. Each part represents the processing machines of each selected operations of each job. As shown is Figure 3, part 1 in mns is [1,3,3,4,4]. It denotes that the five operations of job 1 will be performed on machines “1,”“3,”“3,”“4,” and “4,” respectively.

A member represented by a three-layer structure is similar to which was used in Li et al. ³⁰ However, differing from it, Q-bit is substituted for the numeric representation for sps. The length of the Q-bit string is much shorter than the one encoded in a numerical way, on account of the advantage of multi-Q-bit system. Also, the diversity of individual will be greatly improved.

Converting

Because the permutated job numbers are represented in the decimal system, the Q-bit in q_sps cannot be used directly. So, a converting mechanism is necessary to be introduced. The pseudocode of converting is shown in Figure 4, and the details of the mechanism are described as follows:

• Step 1. Observe the probability amplitudes $\alpha$ and $\beta$ . As described in section “QIEA,” for each Q-bit, generate ${\eta }_i$ randomly in [0, 1]. ${\left|{\alpha }_i\right|}^2+{\left|{\beta }_i\right|}^2=1,i=1,2,\dots ,n$ . If ${\eta }_i<{\left|{\alpha }_i\right|}^2$ , ${\alpha }_i$ is converted to 0, and ${\beta }_i$ is converted to 1, and vice versa. For example, as one possible case, q_sps in Figure 3 is converted to

$$\left[\begin{array}{c}0\hfill \\ \multicolumn{1}{c}{1}\end{array}|\begin{array}{c}1\hfill \\ \multicolumn{1}{c}{0}\end{array}|\begin{array}{c}0\hfill \\ \multicolumn{1}{c}{1}\end{array}|\begin{array}{c}1\hfill \\ \multicolumn{1}{c}{0}\end{array}\right]$$

• Step 2. Observe the superposition of states. The number of observed superposition is $2^N=16,N=4$ . Each superposition is a four-bit binary string. For example, [0101], [0001], [1111], and [1010] are four samples of the 16 groups of superposition of states.

• Step 3. Convert binary strings to decimal ones. Each of the observed superposition is converted to a decimal number. For instance, the four samples given in step 2 are converted to 5, 1, 15, and 10, respectively. Thus, 16 decimal numbers are generated. Actually, the decimal string is composed by the numbers from 0 to 15 in a random arrangement.

• Step 4. Modify the decimal string to create operation-based sps. The operator “ $\mathrm{mod}(x,n)+1$ ” is employed here. “mod” is an operator for calculating the remainder x being divided by n. x is the decimal number in the decimal string generated in step 3. n is the number of jobs. In this way, a permutation of n jobs is obtained. The jth occurrence of a job number refers to the jth operation in the processed path of this job.

Figure 4.

Pseudocode of converting.

Figure 4 reveals the regularity of converting Q-bit string to a binary one, taking superposition of states into account. A two-job example for converting q_sps to decimal sps (d_sps) in decimal representation is shown in Figure 5.

Figure 5.

Converting process for a two-job example.

The converting mechanism is somewhat analogous to the one presented by Gu et al. ⁵⁵ But what much improved for the coding is that the length of the string is much shorter. In that article, researchers directly used the observed state “0” or “1” as the converted elements. In this article, the authors use the observed superposition for converting. The string performs better in diversity and needs much less storage space, despite a little complex converting process. Furthermore, because permutation of binary string is stochastic, the step of ordering a permutation of decimal string from small to big in Gu et al. ⁵⁵ is no longer required as well.

Repairing

The length of d_sps in Figure 5 is larger than final sps. It is because the value of 2 ^N is always bigger than the sum of the quantity of all selected operations. Assume the length of the final sps is ope, which is the same as the length of mns. Consequently, to confirm the string is feasible, $(2^N-\mathrm{ope})$ bits of d_sps should be removed. For pseudocode of repairing, see Figure 6. The detailed descriptions are as follows:

• Step 1. Obtain ope_i. ope_i is the number of operations in selected processed path of job i. It can be obtained according to pps. For instance, job 2 in Figure 1 has two alternative process plans. The numerical index in the second bit in pps is 2. That is to say, the selected process plan of job 2 is 2. In Figure 1, the number of operations of the second plan of job 2 is 6. Consequently, ope₂ is 6.

• Step 2. Check the occurrence times $o{t}_i$ of job i in d_sps in turn. The small job index occurrence probability is larger than the big one according to the experimental data. Convert $(o{t}_i-\mathrm{op}{e}_i)$ bits of job i to 0 randomly and vice versa.

• Step 3. Delete 0 in d_sps. As one possible case, d_sps is transformed into $[2,2,1,1,1,2,2,2,2,1,1]$ .

Figure 6.

Pseudocode of repairing.

After the three steps, a feasible sps is obtained, and a new three-layer model is structured. Then decoding is implemented to acquire the selected process plans and the sequence of operations with corresponding machines.

Decoding

The new three-layer structure is shown in Figure 7. sps is encoded in operation-based representation. The important feature of operation-based representation is that any permutation of the individual can be decoded to a feasible schedule. The notations used to explain decoding procedure are described in Appendix 1.

Figure 7.

New three-layer structure.

Bierwirth ⁷⁴ presented the procedures of decoding the permutations into semi-active, active, nondelay, and hybrid schedules. In this article, the active decoded is adapted from Qiao and Lv, ¹⁰ and Li et al. ³⁰ as follows:

• Step 1. Construct a set P and a set MT. P is the alternative process plans with corresponding technology sequence of operations for each job, and MT is the alternative machines with corresponding processing time for each operation.

• Step 2. Scan pps, sps, and mns from left to right. Then determine pp _i for job i. pp _i is the selected process plan with operation sequence of job i according to pps and P. Subsequently, determine the processing machines and corresponding processing time for each job according to MT.

• Step 3. Generate initial sets IT, ST, and CT, respectively. IT contains the initial idle time areas $[0,\infty )$ of each machine. ST and CT are the sets separately storing the start time and completion time of every operation.

• Step 4. The allowable start time for every operation, $\mathrm{as}{t}_{\mathrm{ilj}}=\mathrm{ec}{t}_{\mathrm{il}(j-1)}$ , $\mathrm{ec}{t}_{\mathrm{il}(j-1)}$ is the completion time of the preoperation of $O_{\mathrm{ilj}}$ of the same job.

• Step 5. Determine the earliest start time for $O_{\mathrm{iljk}}$ . Check idle time areas of machine k in turn. If $max(\mathrm{as}{t}_{\mathrm{iljk}},\mathrm{idle}\_s_k)+p{t}_{\mathrm{iljk}}⩽\mathrm{idle}\_c_k$ , the earliest start time is $\mathrm{es}{t}_{\mathrm{ilj}}=\mathrm{idle}\_s_k$ . Otherwise, $\mathrm{es}{t}_{\mathrm{ilj}}=max(\mathrm{as}{t}_{\mathrm{iljk}},\mathrm{ect}(O_{\mathrm{iljk}}-1))$ , $\mathrm{ect}(O_{\mathrm{iljk}}-1)$ is the completion time of the preoperation of $O_{\mathrm{iljk}}$ on the same machine. Then, change the idle time areas of machine k.

• Step 6. The completion time of every operation, $\mathrm{ec}{t}_{\mathrm{ilj}}=\mathrm{es}{t}_{\mathrm{ilj}}+p{t}_{\mathrm{iljk}}$ .

• Step 7. Store the start time and completion time of $O_{\mathrm{iljk}}$ .

After these seven steps, a schedule for a job shop is generated.

Integrated principle initialization and individual evaluation

Population initialization is crucial in EAs because it can affect the convergence speed and the quality of the final solution. ⁷³ Thus, chaotic theory is utilized for initialization in this article. The chaotic principle is for q_sps. The initial population of pps and mns is generated based on the encoding principles. The solution space is divided into G groups. M members each of whom carries three strings are assigned to each group. That is to say, the total members are G × M. The initial population of q_sps is generated as follows:

• Step 1. Define the pair of ${\alpha }_{\mathrm{gmd}}$ and ${\beta }_{\mathrm{gmd}}$ as the dth bit of mth q_sps in gth group. $g=1,2,\dots ,G;m=1,3,\dots ,M;d=1,2,\dots ,N$ .

• Step 2. Generate G × N random number ${\alpha }_{g1d}$ from the uniform distribution (−1, 1). ${\left|{\beta }_{g1d}\right|}^2=1-{\left|{\alpha }_{g1d}\right|}^2$ .

• Step 3. Generate ${\alpha }_{\mathrm{gmd}}$ and ${\beta }_{\mathrm{gmd}}$ by employing equation (6). $g=1,2,\dots ,G;m=2,3,\dots ,M;d=1,2,\dots ,N$ .

After these three steps, G groups G × M sps are generated.

Individual evaluation is closely related to the optimization criteria. ²¹ In this article, the objective is to minimize the makespan. Makespan is defined as the maximum time a machine processing all its tasks in a set of machines.^24,75 Thus, the objective becomes minimizing the maximum time of all the operations in a machine

$$f=\min \left(\underset{k}{\max }\left(c_{\mathrm{ijk}}\right)\right)$$

(8)

where f is makespan and $c_{\mathrm{ik}}$ is the completion time of the jth operation of job i performed on machine k. A member with a smaller makespan is a better solution.

Evolution

Because Q-bit strings have characteristic of diversity due to quantum superposition of states, the crossover or mutation in high probability will decrease QIEA performance. Accordingly, one-way crossover between groups is left out. Leaders’ impact is the main consideration. The developing principle is to avoid generating the infeasible new member.

One-way crossover and mutation are applied in one member simultaneously. One-way crossover is for pps and mns, and mutation is for q_sps.

At every iteration and in each group, all the members except the leader are traveled by sequential traversal method. The following strategy is for one group, and other groups are executed in the same way.

• Step 1. Choose a bit i of pps of member m randomly and then transfer the bit in the same location of leader’s pps to member m at a certain probability.

• Step 2. Transfer the ith part of mns of leader to the ith part of mns of member m.

• Step 3. Rotate q_sps of member m directed to leader. The rotation strategy is as follows ⁷⁶

$$\Delta {\theta }_{\mathrm{xm}}=\{\begin{array}{cc}0,\hfill & {\theta }_{\mathrm{xl}}={\theta }_{\mathrm{xm}}\hfill \\ \multicolumn{1}{c}{\frac{{\theta }_0({\theta }_{\mathrm{xl}}-{\theta }_{\mathrm{xm}})}{{\theta }_{\mathrm{xl}}-{\theta }_{\mathrm{xm}}},}& {\theta }_{\mathrm{xl}}\ne {\theta }_{\mathrm{xm}}\hfill \end{array}$$

(9)

where $x=1,2,\dots ,N,m=1,2,\dots ,M$ and ${\theta }_0$ is a very small positive real number given previously, usually $0<{\theta }_0<1$ . ${\theta }_{\mathrm{xm}}$ is the ith bit of q_sps of member m. ${\theta }_{\mathrm{xl}}$ is the xth bit of q_sps of leader. Then

$$\theta {\prime }_{\mathrm{xm}}={\theta }_{\mathrm{xm}}+\Delta {\theta }_{\mathrm{xm}},x=1,2,\dots ,N$$

(10)

${\theta }_{\mathrm{xm}}$ is updated by

$${\theta ″}_{\mathrm{xm}}=\{\begin{array}{cc}-{\theta \prime }_{\mathrm{xm}},\hfill & {\theta \prime }_{\mathrm{xm}}<0\hfill \\ \multicolumn{1}{c}{2-{\theta \prime }_{\mathrm{xm}},}& {\theta \prime }_{\mathrm{xm}}>1\hfill \\ \multicolumn{1}{c}{{\theta \prime }_{\mathrm{xm}},}& 0⩽{\theta \prime }_{\mathrm{xm}}⩽1\hfill \end{array}x=1,2,\dots ,N$$

(11)

where ${\theta ″}_{\mathrm{xm}}$ is the new number in the xth bit of q_sps of member m.

• Step 4. Convert and repair strings according to sections “Converting” and “Repairing.” Taking into account crossover of pps and mns, a new member $\mathrm{new}\_m$ is generated.

• Step 5. Calculate the makespan of $new\_m$ . If it is better than the old one, replace m by $\mathrm{new}\_m$ . Otherwise, keep m in the group and proceed to the next one.

Integrating Q-gate rotation and GLOA systematically is beneficial not only for accelerating the convergence speed but also for simplifying the algorithm process. This is because the permutation of jobs and operations are unnecessary to be considered, due to the Q-bit encoded way.

Terminate criteria

If the number of iteration runs reaches to the maximum generations, the algorithm stops.

Experimental studies and discussions

For system implementation, the software MATLAB 2013a was employed. In this article, experiments were conducted on a personal computer equipped with Intel(R) Core(TM) i3-4030U central processing unit (CPU; 1.9 GHz) and 4-GB RAM.

The parameters and coefficients were set as follows: number of groups $G=30$ , number of members in each group $M=70$ , iteration $\mathrm{IT}=30$ , the genetic probability of old member $r_1=0$ , the impact factor of group leader $r_2=1$ , the random factor $r_3=0$ , number of transferred bits of pps in one-way crossover $n\prime =1$ for small- and medium-scale problems and $n\prime =4$ for large-scale problems, chaotic coefficient $u=4$ , and the small positive real number in rotation strategy ${\theta }_0=0.025$ . Every problem of the test bed was repeated for 20 times, and the best solutions with the smallest makespans at each time were recorded. The main reason for conducting 20 runs of simulations was to compare the performance of QHA with other algorithms which also recorded results of similar simulation runs.

Experiment 1: the validation verification

To verify the proposed QHA, an example adopted from Zhang and Wong ²¹ is studied. AND-OR graph is displayed in Figure 1. The Gantt chart of simulation result is shown in Figure 8.

Figure 8.

Gantt chart of experiment 1.

The number tags on the color bars contain two aspects information. Take “201” for example. The first number “2” in “201” means job 2. The last two numbers is “01.” It means the first operation. That is to say, “201” indicates the first operation of job 2. Other number tags on the color bars are named in the same way. According to Figure 8, the selected processed path of job 2 is 1-3-5-6-7-8. The value of makespan is the same as Zhang and Wong ²¹ with different processing machine arrangements. It reveals that QHA can solve the IPPS problem effectively.

Experiment 2: the large-scale experiments

To validate the performance of QHA, some large-scale experiments have been performed. For benchmarking, the IPPS problem test bed proposed by Kim et al. ⁶ was adopted for the experiments, considering operation flexibility, sequencing flexibility, and processing flexibility of manufacturing. The test bed is composed of 18 separate jobs with 300 operations and 15 machines. Different combinations of the 18 jobs form 24 problems, which can reflect practical manufacturing situations of various complexities and flexibility. The 24 problems are divided into five categories which include nine 6-job problems, six 9-job problems, six 12-job problems, two 15-job problems, and one 18-job problem.

Qiao and Lv ¹⁰ performed the 24 problems and gave the low bound of the makespans for each problem. They took the maximum of the shortest process plans in each case as the low bound. However, the low bound was merely near-optimal one. The near-optimal process plan was obtained by parsing singly job, and the combined processes were not taken into consideration. Much lower makespans of the most problems were obtained in this article. Consequently, the low bound is worthy of further study.

The comparisons of the makespans and the best result of makespan in this work are given in Table 1. The compared methods are QHA, SEA employed by Kim et al., ⁶ an HA (TS combined with GA) employed by Li et al., ³⁰ an improved genetic algorithm (IGA) employed by Qiao and Lv, ¹⁰ and OCGA employed by Zhang and Wong. ²¹ The data in the columns of SEA, IGA, and OCGA are adopted from Zhang and Wong. ²¹ The data in the column of HA are adopted from Li et al. ³⁰ The column “Improved rate” in Table 1 depicts the relative improved rate of QHA result compared with the minimum value yielded by the other four algorithms. A positive improved rate denotes that QHA presents the best result out of the five algorithms.

Table 1.

Comparisons of best makespans.

Problems	Jobs	SEA	HA	IGA	OCGA	QHA	Improved rate (%) a
1	1, 2, 3, 10, 11, 12	428	427	427	427	266	37.70
2	4, 5, 6, 13, 14, 15	343	343	343	343	255	25.66
3	7, 8, 9, 16, 17, 18	347	345	344	344	247	28.20
4	1, 4, 7, 10, 13, 16	306	306	306	306	273	10.78
5	2, 5, 8, 11, 14, 17	319	322	304	318	232	23.68
6	3, 6, 9, 12, 15, 18	438	429	427	427	251	41.22
7	1, 4, 8, 12, 15, 17	372	372	372	372	266	28.49
8	2, 6, 7, 10, 14, 18	343	343	342	343	247	27.78
9	3, 5, 9, 11, 13, 16	428	427	427	427	244	42.86
10	1, 2, 3, 5, 6, 10, 11, 12, 15	443	430	427	427	327	23.42
11	4, 7, 8, 9, 13, 14, 16, 17, 18	369	369	368	348	304	12.64
12	1, 4, 5, 7, 8, 10, 13, 14, 16	328	327	312	318	299	4.17
13	2, 3, 6, 9, 11, 12, 15, 17, 18	452	436	429	427	332	22.25
14	1, 2, 4, 7, 8, 12, 15, 17, 18	381	380	386	372	319	14.25
15	3, 5, 6, 9, 10, 11, 13, 14, 16	434	427	427	427	305	28.57
16	1, 2, 3, 4, 5, 6, 10, 11, 12, 13, 14, 15	454	446	433	427	403	5.62
17	4, 5, 6, 7, 8, 9, 13, 14, 15, 16, 17, 18	431	423	415	370	367	0.81
18	1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17	379	377	364	351	342	2.56
19	2, 3, 5, 6, 8, 9, 11, 12, 14, 15, 17, 18	490	476	450	427	416	2.58
20	1, 2, 4, 6, 7, 8, 10, 12, 14, 15, 17, 18	447	432	429	384	384	0.00
21	2, 3, 5, 6, 7, 9, 10, 11, 13, 14, 16, 18	477	446	433	427	405	5.15
22	2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 14, 16, 17, 18	534	518	491	446	443	0.67
23	1, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18	498	470	465	394	397	−0.76
24	1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18	587	544	532	458	521	−13.76

SEA: symbiotic evolutionary algorithm; HA: hybrid algorithm; IGA: improved genetic algorithm; OCGA: object-coding genetic algorithm; QHA: quantum-inspired hybrid algorithm. Bold values in column QHA are results in this work, while bold values in column SEA, HA, IGA, OCGA are the minimum results in the compared work.

a

Result in this work is compared with the minimum one in the compared work.

Table 1 reveals that QHA achieved significant improvements in 16 of the 24 problems whose improved rates are >5%. The 16 outperformed problems are problems 1–11, 13–16, and 21. The improved rates of problems 1–3, 5–10, 13, and 15 are >20%, in which improved rates of problems 1, 6, and 9 are >35%. For problems 12, 17–20, and 22, QHA just made a slight improvement compared with the other four algorithms. Only the last two improved rates are negative, and QHA did a bit worse than OCGA, but better than the other three algorithms.

The results in Table 1 reveal that QHA performed wonderfully in solving complex IPPS problems, especially for small- and medium-scale ones. For large-scale problems, it may converge to local optimum.

To demonstrate the facticity of the results in Table 1, 8 Gantt charts of the 24 problems are displayed in Figures 9–16. Because the 24 problems are divided into five categories, 1–2 problems are chosen from each category separately.

Figure 9.

Gantt chart of problem 6.

Figure 10.

Gantt chart of problem 9.

Figure 11.

Gantt chart of problem 10.

Figure 12.

Gantt chart of problem 15.

Figure 13.

Gantt chart of problem 16.

Figure 14.

Gantt chart of problem 21.

Figure 15.

Gantt chart of problem 22.

Figure 16.

Gantt chart of problem 24.

Figures 9 and 10 are the Gantt charts of problems 6 and 9, which are the best two performed results out of the nine 6-job problems. Figures 11 and 12 are the Gantt charts of problems 10 and 15, which are the best two performed results out of the six 9-job problems. Figures 13 and 14 are the Gantt charts of problems 16 and 21, which are the best two performed results out of the six 12-job problems. Figure 15 is the Gantt charts of problem 22, which is the best performed result out of the two 15-job problems. Figure 16 is the Gantt chart of problem 24 which is the largest scale problem.

The number tags on the color bars indicate the operations of the jobs, which is named in the same way as in experiment 1. Take Figure 10 for example. “310” on the first bar in the second line means the 10th operation of the third job. Because of the OR nodes in those AND-OR graphs in Kim, ⁷⁷ the operation numbers are displayed discontinuously in following Gantt charts. In addition, some operations of one job would start simultaneously on account of OR links. Hence, operations with bigger serial numbers may start earlier than the ones with smaller serial numbers in the Gantt charts.

The figures illustrate that good results can be obtained by employing QHA. Besides the process plans, scheduling plans with corresponding machines can be learnt from the Gantt charts. In light of the length of this article, simulation results of problem 9 in Figure 10 are only exhibited. Because it is a six-job problem, there are six different colors in Figure 10. Jobs 1–6 in the Gantt chart represent jobs 3, 5, 9, 11, 13, and 16 in the test bed. According to the number tags on the color bars, the number of operations of each job can be known. Those operations are selected from the alternative operation sets. The optimal process plan of problem 9 is shown in Table 2.

Table 2.

Process plan of problem 9.

Job number	Operation number
3	1	2	3	5	6	4	7	8	9	10	11	13	14	15	12	16	17	18	19
5	1	10	11	12	13	14	15	16	17	18
9	1	2	3	6	7	10	11	12	13	14	15	16	18	19	20
11	1	2	3	4	5	6	7	8	9
13	1	12	13	14	15	16	17	18
16	1	6	12	13	14	15	16	17	18	20	21

There are 72 color bars in Figure 10. That is to say, there are 72 operations of the scheduling plan processed on the 15 machines. Table 3 is the optimal scheduling plan with corresponding machines of problem 9. Numbers in rows 2, 5, 8, and 11 indicate the jobs number. The jth occurrence of a job number expresses the jth operation of this job. For example, in row 2 (row SPPs 1–18), column 19, the number is 1. This means the 18th operation of the overall scheduling plan is an operation of job 1. It is the third occurrence, which means the third operation of job 1. Actually, job 1 in problem 9 represents job 3 in the test bed. According to Table 2, the number of the third operation of job 3 is 3. Therefore, numerical index 1 in row 2 column 19 refers to operation 3 of job 3 which processed on machine 1.

Table 3.

Scheduling plan and corresponding machines of problem 9.

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
SPPs 1–18	2	2	6	4	6	6	4	6	6	2	2	4	6	2	1	3	1	1
CMs 1–18	11	9	1	6	6	8	8	8	9	14	12	11	7	15	11	5	2	1
	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36
SPPs 19–36	3	3	1	3	1	3	1	3	5	3	1	3	1	3	5	1	2	4
CMs 19–36	7	9	4	5	7	10	2	14	10	3	1	6	1	2	4	13	10	14
	37	38	39	40	41	42	43	44	45	46	47	48	49	50	51	52	53	54
SPPs 37–54	4	6	4	2	4	2	6	2	4	6	4	6	2	6	3	5	1	1
CMs 37–54	6	12	2	3	15	4	15	7	11	5	5	15	10	2	5	9	4	4
	55	56	57	58	59	60	61	62	63	64	65	66	67	68	69	70	71	72
SPPs 55–72	3	5	3	1	3	1	3	1	5	1	3	1	1	5	1	5	1	5
CMs 55–72	9	14	4	15	11	2	2	1	3	1	6	10	13	11	13	8	14	2

SPPs: scheduling plan procedures; CMs: corresponding machines.

Experiment 3: the impact of the chaotic initialization

For deeper research, experiments without chaotic initialization method were repeated with the same context setting and the same running conditions as experiment 2. Figure 17 depicts the comparison of makespans under the chaotic and nonchaotic methods. This figure shows chaotic method has slight advantage compared with nonchaotic one.

Figure 17.

Comparison of chaotic and nonchaotic initialization for 24 problems.

Conclusion and future work

Based on the characteristics of QIEA, GLOA, CMs, and IPPS problems, a QHA is proposed in this article. Each of the three adopted algorithms has wonderful performance separately. For individual representation, a three-layer hybrid encoded structure is adopted, in which Q-bit representation is applied. In addition, the logical relation between the number of operations and the number of Q-bits of sps is revealed. Sequentially, in order to generate feasible individuals, customized converting and repairing mechanisms are designed. Based on chaotic theory, the stochastic individuals are generated, and the diversity of population is improved. For evolution, Q-gate rotation and GLOA are systematically integrated, leading to noticeable search ability and high performance. To validate the performance of QHA, experiments on benchmark problems are carried out, yielding outstanding results.

The main contributions of this article are as follows:

1. Hybrid encoding technology is utilized to increase the diversity of individuals and simplify the encoding process.

2. Chaotic theory is employed to generate stochastic initial individuals to enhance the randomicity of population.

3. QIEA and GLOA are systematically integrated to improve the search ability, which are rarely applied in IPPS problems.

4. The regularity of converting Q-bit string to a binary one is given, considering the superposition of states, which is useful for programming.

Despite the mentioned contributions, some work is remained to be researched. First of all, improving the algorithm performance in large-scale problems should be paid much attention. Second, multiobjective IPPS problems will be studied. As further work, the proposed QHA can be extended to cope with rescheduling problems in dynamic, complex, and distributed manufacturing environment with unpredictable issues, such as machine breakdowns and rush order.