Study on the self-evolution problem of an aircraft-engine assembly workshop with uncertain number of assembly times

Abstract

Self-evolution problem of an aircraft-engine assembly workshop with uncertain number of assembly times in knowledgeable manufacturing environment is studied in this article. The whole dynamic self-evolution process is decomposed into a series of static ones by using the rolling horizon procedure. A rolling rule, which is employed to select operations into rolling windows, is designed on the basis of the level priority of each operation. An algorithm for the self-evolution algorithm is then proposed. Due to the deterministic production information, a static decision sub-problem is needed to be solved at each decision point. A general mathematical model of sub-problems is built to minimize the production cost. For solving it, a bi-level genetic algorithm is proposed. In the lower level genetic algorithm, an improved decoding method is also designed by considering production features. Finally, simulation results demonstrate the feasibility and validity of the model and algorithms. Then, computational data indicate that the system with self-evolution capability pays lower costs for production.

Introduction

Self-evolution is one of the most important features of the knowledgeable manufacturing system (KMS), which is initially introduced by Yan and Liu. ¹ The key idea of self-evolution is how to improve production performances and respond timely to dynamic environment by self-adjusting of manufacturing systems.

For further study, the principle of self-evolution is introduced to an aircraft-engine assembly workshop in this article. The structure of an aircraft-engine can be shown by a tree diagram where each node represents an operation in the whole assembly process. The production scheduling problem of tree-structured products is usually called assembly job shop scheduling problem (AJSSP), which is more complex than the common job shop scheduling problem (JSSP). Omkumar et al. ² proposed an optimization heuristic method on the basis of genetic algorithm (GA) to minimize the makespan. Omkumar and Shahabudeen ³ developed an optimization heuristic algorithm based on ant colony algorithm (ACO) for the AJSSP in static manufacturing environment. Wong and Ngan ⁴ proposed a hybrid genetic algorithm (HGA) and a hybrid particle swarm optimization (HPSO) to solve AJSSP with the lot streaming (LS) technique. Xie et al. ⁵ introduced a hierarchical scheduling algorithm based on the improved processing operation tree to solve the complex product flexible scheduling problem with constraints between jobs. Liu et al. ⁶ introduced some dispatching rules based on the proposed order review/release (ORR) rule to optimize due-date and flow-time related production performances.

As far as authors know, few studies have dealt with the assembly scheduling problem of an aircraft-engine assembly workshop. At the meantime, majority of those articles mentioned above only considered the static scheduling problem. However, in the real manufacturing environment, the presence of unexpected disruptions is inevitable, which means that those algorithms proposed for the static scheduling problem cannot be directly used in the dynamic environment. In an aircraft-engine assembly workshop, the assembly process of each engine has two stages, where engines will be disassembled and reassembled if they are tested to be substandard in inspection stations. Thus, the number of assemblies is at least twice and viewed as an uncertain factor in the workshop. In generally, dynamic scheduling is an effective approach to the realization of actual scheduling. Many studies have been made on this topic for general workshops, such as job shop, flow shop, but few literatures about AJSSP have been found. Thiagarajan and Rajendran ⁷ addressed a dynamic AJSSP with the consideration of different holding and tardiness costs for different jobs and developed some efficient dispatching rules to minimize the scheduling cost consisting of the sum of holding and tardiness costs. Thiagarajan and Rajendran ⁸ considered the scheduling problem in dynamic assembly job-shops where jobs have different earliness, tardiness and holding costs and presented some dispatching rules. Natarajan et al. ⁹ proposed new priority dispatching rules to minimize the performance measures related to weighted flow time and weighted tardiness of jobs. However, all of the above researches ignored the adjustability of system parameters, which may affect the production performance to a great extent. For the aircraft-engine assembly workshop, processing times of operations depend on the number of workers assigned to each work group. Thus, the number of workers can be treated as a kind of system parameters here.

For this end, the principle of self-evolution is introduced to an aircraft-engine assembly workshop with uncertain number of assembly times. The rolling horizon procedure is employed to implement the self-evolution process of the workshop. At each decision moment, numbers of workers in work groups are adjusted first, and the optimal scheduling scheme is acquired based on the worker assignment. A general mathematical model is established for the static decision sub-problem at each decision point, and then, a bi-level genetic algorithm (BiGA) with a new decoding method is designed to solve the model. In addition, a rolling rule which is suitable for the self-evolution problem of the aircraft-engine assembly workshop is presented, and on the basis of which an algorithm for solving the self-evolution problem is proposed. Simulation results demonstrate the feasibility and effectiveness of the proposed model and algorithms.

Some related definitions of self-evolution

• Definition 1. Self-evolution operations are the series of actions, by which a new system adjustment scheme and a new scheduling result can be acquired.

• Definition 2. Self-evolution decision is the combination of the new system adjustment scheme and scheduling result obtained by self-evolution operations.

• Definition 3. Decision moment is the time moment at which dynamic events occur or the regular time of self-evolution is up; self-evolution moment is the moment at which self-evolution decision starts to be performed.

Aircraft-engine assembly workshop

Seen from Figure 1, the assembly process of an aircraft-engine has the two stages. If the first assembly stage is finished, and the engine is up to standard in the factory test, then disassembly, wash and inspection are conducted in succession; after that the engine is reassembled in the second assembly stage. If the engine is still qualified in the check test, it can be delivered to customers. At any stage, the unqualified product will be reassembled till it is qualified. Thus, each engine should be assembled twice at least. In the figure, solid arrows address the normal assembly process, and dashed ones show the reassembling processes.

Figure 1.

Aircraft-engine assembly process.

The workshop consists of some work teams with different tasks, such as the final assembly team, balance team and so on. In each work team, work groups with the same tasks to fulfill are equipped with several workers, tools and equipments. Furthermore, assembly vehicles are also provided to facilitate production which can move among work groups.

• Definition 4. The tree diagram introduced to describe assembly constraints between operations is called product tree. Nodes on product trees are expressed as product index|assembly stage|operation code. For example, in Figure 2, B|1|3 denotes Operation 3 of Engine B at the first assembly stage, whose children are B|1|6 and B|1|7.

• Definition 5. A product tree, which is generated by combining product trees of engines, and adding a common virtual root node (VRN), is defined as virtual product tree. In terms of the level of each node on the virtual product tree shown in Figure 3, a level priority is assigned, for example, the VRN at Level 0 has the lowest priority and so on. ¹⁰

Figure 2.

Product trees of Engines A and B.

Figure 3.

Virtual product trees of Engines A and B.

Self-evolution of aircraft-engine assembly workshop

Rolling horizon procedure^11–15 is often adopted to solve the scheduling problem, whose rolling optimization technique can also be applied to the self-evolution problem. In this study, the hybrid event-driven and periodic-driven self-evolution mechanism is selected to trigger self-evolution operations.

Approach for dealing with uncertain disruptions

Uncertain reassembling is viewed as the only dynamic event in this article. Since the assembly process starts from leaf nodes to root node, the remaining unprocessed operations still posses a tree structure. Assume that all operations of Engine A at the first assembly stage have been completed at a time moment, the virtual product tree of remaining operations of Engines A and B is shown in Figure 4. After the factory test of Engine A, during which operations of Engine B are continued to be processed, it is found to be unqualified, and then, the new virtual product tree is shown in Figure 5.

Figure 4.

Virtual product tree of the remaining operations.

Figure 5.

New virtual product tree of Engines A and B.

Decision-making process

At $T=0$ , an initial rolling window is generated according to the known production information. Then, the first static decision sub-problem is solved to acquire a worker assignment and a scheduling scheme. With the self-evolution decision, the completion time of the first $\eta$ operations is set to be the new decision moment $T$ . Because of the parallel production of operations, more than one operation may be completed at $T$ , thus the real number of completed operations $\sigma$ will not be less than $\eta$ , that is, $\sigma \ge \eta$ . Moreover, there may be $\beta (\beta \ge 0)$ operations being processed at the moment $T$ , thus the number of remaining unprocessed operations in the current window equals to $(\epsilon -\sigma -\beta )$ . To generate a new window, the $(\sigma +\beta )$ operations should be deleted from the current window first, and then, a new operation set is created by selecting $(\sigma +\beta )$ unscheduled operations from outside the current window. Due to the limited number of operations, the size of the last window may be less than $\epsilon$ . At this point, the self-evolution process will be terminated if operations are all completed.

A special case should be noticed here. Assume that there is an engine failed in the factory test. At this moment, dynamic event occurs and a new rolling window needs to be generated. According to the generation method above, there may be $\varsigma (\varsigma \ge 0)$ remaining unprocessed operations of the failed engine at the second assembly stage in the current window. To avoid the $\varsigma (\varsigma \ge 0)$ operations entering into the window prior to those of the same failed engine at the first assembly stage, the $\varsigma (\varsigma \ge 0)$ operations should also be removed before generating the new window and $(\sigma +\beta +\varsigma )$ unprocessed operations are selected from outside the current window.

Mathematical formulation

Problem statement

According to the decision-making process above, the system’s self-evolution is a dynamic process, but the production information (i.e. set of operations to be scheduled, working states of work groups, etc.) is always deterministic at each decision point. Therefore, a static decision problem, including two sub-problems (worker assignment and production scheduling problem) should be discussed.

To formulate the static mathematical model, several aspects should be considered as follows: (1) assembly constraints between operations, (2) adjustability of the number of workers in each work group and (3) uncertain number of assemblies. The optimization objective is minimizing the production cost which is the weighted sum of worker adjustment cost and scheduling cost. Some necessary assumptions are listed as below:

1. Operations are not allowed to be preempted once started;

2. Two operations cannot be processed in the same work group at the same moment;

3. Processing time is monotone decreasing function of the number of workers, whose maximum value is certain and known;

4. An operation cannot be reassigned to another work group once started;

5. Workers can only be assigned in the same work team they belong to by considering the eligibility constraints;

6. The time of test, disassembly, washing and fault inspection is fixed and known for each engine;

7. The number of assembly vehicles is enough for the assembly production;

8. The number of workers in each group cannot be changed until the next self-evolution comes;

9. The movement times of workers and setup times between operations are negligible.

Model establishment

A bi-level programming model is established where the worker assignment is modeled at the higher level, and the scheduling problem lies at the lower place. Related symbols and variables are defined as below:

• $Z$  Production cost

• $F$  Scheduling cost, whose minimum value is expressed as $F_{min}$

• $H$  Set of work team in the current window

• $G_h$  Set of work groups in the hth work team

• $R_h$  Number of workers in the hth work team

• $M$  Set of work groups in the current window

• $r_m$  Number of workers in the mth work group, $r_m\in [r_{mmin},r_{mmax}]$

• $r{\prime }_m$  Initial number of workers in the mth work group, $r{\prime }_m\in [r_{mmin},r_{mmax}]$

• ${\phi }_m$  Cost coefficient of the worker adjustment

• $\alpha$  Weight coefficient vector, $\alpha =({\alpha }_1,{\alpha }_2)$

• $I$  Set of engines corresponding to the operations in the current window

• $J_{i\delta }$  Set of operations belong to the ith engine at the δth assembly stage in the current window

• $O_{i\delta j}$  Operation j of the ith engine at the δth assembly stage

• $K$  Set of rework operations in the current window

• $C{\prime }_{i\delta }$  The last completion time of Engine i corresponding to rework operation $O_{i\delta j}$ at the δth assembly stage

• ${\lambda }_{i\delta j}$  Cost coefficieny of the completion time of $O_{i\delta j}$

• $C_{i\delta j}$  End time of $O_{i\delta j}$

• $C_{i1}$  End time of the ith engine at the first assembly stage

• $S_{i\delta j}$  Start time of $O_{i\delta j}$

• $O_{\mathrm{P}(i\delta j)}$  Parent operation of $O_{i\delta j}$

• $S_{\mathrm{P}(i\delta j)}$  Start time of $O_{\mathrm{P}(i\delta j)}$

• $T$  Decision-making point

• $t_i$  The sum time of test, disassembly and fault inspection of the ith engine

• $\phi$  A large positive constant

• $\theta$  A constant lies between 0 and 1, whose value expresses the influence of worker assignment on processing times. For a larger value of $\theta$ , the worker assignment has a greater impact on the processing time reductions. $\theta$ equals to 0.5 unless further distinction is needed

• $\Delta {\overline{t}}_m$  Remaining time of the operation being processed in the mth work group with the original parameter $r{\prime }_m$ at $T$

• $\Delta t$  Time which is spent in getting a self-evolution decision, and can be got by simulations

• $T\prime$  Self-evolution moment, $T\prime =T+\Delta t$

• $\Delta t{\prime }_m$  Remaining time of the operation being processed in the mth work group with the original parameters at $T\prime$ , $\Delta {t\prime }_m=max\{\Delta {\overline{t}}_m-\Delta t,0\}$

• $\Delta t_m$  Remaining time of the operation being processed in the mth assembly group with the new parameters $r_m$ at $T\prime$

• $p_{i\delta \mathrm{jm}}$  Processing time of $O_{i\delta j}$ in the mth work group, the maximum value is ${\overline{p}}_{i\delta \mathrm{jm}}$

• $p_{i\delta j}$  Actual processing time of $O_{i\delta j}$

• $x_{i\delta \mathrm{jm}}$  0–1 variable; if $O_{i\delta j}$ is processed in the mth work group, $x_{i\delta \mathrm{jm}}=1$ , otherwise $x_{i\delta \mathrm{jm}}=0$

• $y_{i\delta \mathrm{ji}\prime \delta \prime j\prime m}$  0–1 variable; if $O_{i\delta j}$ precedes $O_{i\prime \delta \prime j\prime }$ in the mth work group, $y_{i\delta \mathrm{ji}\prime \delta \prime j\prime m}=1$ , otherwise $y_{i\delta \mathrm{ji}\prime \delta \prime j\prime m}=0$

$$\mathrm{Upper}\mathrm{level}:minZ={\alpha }_1\sum _{m=1}^{\left|M\right|}{\mu }_m|r_m-{r\prime }_m|+{\alpha }_2{F}_{min}$$

(1)

$$\mathrm{s}.\mathrm{t}.\sum _{m\in G_h}{r}_m\le R_h,h\in H$$

(2)

$$r_{mmin}\le r_m\le r_{mmax},m\in M$$

(3)

$$\mathrm{Lower}\mathrm{level}:minF=\sum _{i=1}^{\left|I\right|}\sum _{\delta =1}^2\sum _{j\in J_{i\delta }}{\lambda }_{i\delta j}{C}_{i\delta j}$$

(4)

$$\mathrm{s}.\mathrm{t}.C_{i\delta j}-S_{i\delta j}=p_{i\delta j},\forall \delta ,i\in I,j\in J_{i\delta }$$

(5)

$$S_{i\delta j}\ge T\prime +\sum _{m=1}^{\left|M\right|}{x}_{i\delta \mathrm{jm}}\Delta t_m,\forall \delta ,i\in I,j\in J_{i\delta }$$

(6)

$$S_{P(i\delta j)}-C_{i\delta j}\ge 0,\forall \delta ,i\in I,j\in J_{i\delta }$$

(7)

$$S_{i2j}\ge C_{i1}+t_i,i\in I,j\in J_{i\delta }$$

(8)

$$\begin{array}{c}\multicolumn{1}{c}{C_{i\delta j}-C_{i\prime \delta \prime j\prime }+\phi y_{i\delta \mathrm{ji}\prime \delta \prime j\prime m}\ge p_{i\delta j},}\\ \multicolumn{1}{c}{\forall \delta ,\delta \prime ;i,i\prime \in I;j,j\prime \in J_{i\delta };m\in \overline{M}}\end{array}$$

(9)

$$\begin{array}{cc}{C}_{i\prime \delta \prime j\prime }-C_{i\delta j}+\phi (1-y_{i\delta \mathrm{ji}\prime \delta \prime j\prime m})\ge p_{i\prime \delta \prime j\prime },\hfill & \forall \delta ,\delta \prime ;i,i\prime \in I;j,j\prime \in J_{i\delta };m\in \overline{M}\hfill \end{array}$$

(10)

$$S_{i\delta j}\ge C{\prime }_{i\delta }+t_i,O_{i\delta j}\in K$$

(11)

$$\sum _{m=1}^{\left|M\right|}{x}_{i\delta \mathrm{jm}}=1,\forall \delta ,i\in I,j\in J_{i\delta }$$

(12)

$$\begin{array}{cc}{p}_{i\delta \mathrm{jm}}=[1-\theta (1-r_{mmin}/r_{mmin}{r}_m{r}_m)]{\overline{p}}_{i\delta \mathrm{jm}},\hfill & \forall \delta ,i\in I,j\in J_{i\delta },m\in M\hfill \end{array}$$

(13)

$$p_{i\delta j}=\sum _{m=1}^{\left|M\right|}{x}_{i\delta \mathrm{jm}}{p}_{i\delta \mathrm{jm}},\forall \delta ,i\in I,j\in J_{i\delta }$$

(14)

$$\Delta t_m=\frac{(1-\theta (1-r_{mmin}/r_{mmin}{r}_m{r}_m))\Delta {t\prime }_m}{1-\theta (1-r_{mmin}/r_{mmin}{r\prime }_m{r\prime }_m)},m\in M$$

(15)

$$x_{i\delta \mathrm{jm}}\in \{0,1\},\forall \delta ,i\in I,j\in J_{i\delta },m\in M$$

(16)

$$y_{i\delta \mathrm{ji}\prime \delta \prime j\prime m}\in \{0,1\},\forall \delta ,\delta \prime ;i,i\prime \in I;j,j\prime \in J_{i\delta };m\in M$$

(17)

Equation (1) expresses the higher level objective to minimize the production cost, constraint (2) defines the workforce resource constraints, constraint (3) gives the value range of $r_m$ , equation (4) gives the lower level objective to minimize the scheduling cost, constraint (5) ensures the non-preemption of operations, constraint (6) shows the earliest start time of an operation, constraint (7) guarantees the assembly constraints between operations, constrain (8) means that the start time of an operation at the second assembly stage cannot be less than the sum of the completion time of the first assembly stage and the interval time between two assembly stages, constraints (9) and (10) define that two operations must not be processed simultaneously in the same work group, constraint (11) means that the start time of the rework operation $O_{i\delta j}$ is not allowed to be less than the sum of the last completion time of the δth assembly stage and the interval time $t_i$ , constraint (12) guarantees that operations cannot be reassigned once started, constrain (13) gives the processing times of operations, constraint (14) shows the actual processing times of operations, constraint (15) gives the remaining time of the operation being processed in the mth work group under the new parameter $r_m$ and constraints (16) and (17) show that $x_{i\delta \mathrm{jm}}$ and $y_{i\delta \mathrm{ji}\prime \delta \prime j\prime m}$ are 0–1 variables.

In this model, for a higher level worker assignment solution, the processing time of operations can be easily calculated by equation (13). At this point, the lower level problem is exactly an AJSSP, which is a special form of the JSSP. ¹⁶ As presented in Garey and Johnson, ¹⁷ the JSSP is NP-Complete and computationally intensive to solve. Thus, there is no way to get the optimal solution of the static decision problem directly via the mathematical model. According to the structure of the model, a BiGA (see below) is designed to solve the problem.

Rolling rule

• Definition 8. The rule, by which operations are selected into the rolling window at each decision-making moment, is called rolling rule.

• Definition 9. The operation which has no preceding ones on the current virtual product tree is termed a selectable operation.

The proposed rolling rule is described as below (Figure 6):

• Step 1. Determine the current set of selectable operations.

• Step 2. Select an operation from the set into the rolling window. The operation at the lowest level on the virtual product tree has the highest priority. In addition, for two operations at the same level, to break a tie, the one with the greater ${\lambda }_{i\delta j}$ should be selected first.

• Step 3. Delete the selected operation from the virtual product tree.

• Step 4. If the number of operations needed in the current rolling window is satisfied, go to Step 5, otherwise go to Step 1.

• Step 5. End the operation selection procedure.

Figure 6.

Flow chart of the rolling rule.

Algorithm for solving the self-evolution problem

Specified steps of the proposed algorithm are listed as follows (Figure 7):

• Step 1. Generate the initial virtual product tree and initialize the parameters $\epsilon$ and $\eta$ .

• Step 2. Select operations into the rolling window based on the proposed rolling rule.

• Step 3. Perform the BiGA to acquire a self-evolution decision scheme and start the production.

• Step 4. Judge whether a dynamic event occurs. If yes, go to Step 6, otherwise go to Step 5, but if the size of the current window is smaller than $\epsilon$ , then go to Step 7 after finishing all operations.

• Step 5. Judge whether the first $\eta$ operations are completed. If yes, go to Step 6, otherwise continue the production by the decision in Step 3.

• Step 6. Determine the working state and remaining processing time of each work group and generate the new virtual product tree, go to Step 2.

• Step 7. Terminate the algorithm.

Figure 7.

Flow chart of the algorithm for the self-evolution problem.

BiGA

GA is a stochastic search algorithm that is effective and has been applied very widely to get the global optimal value.^18–22 A BiGA developed to deal with the static mathematical model. The algorithm has two genetic optimization processes at different levels where the lower level GA is embedded in the higher level one. The higher level GA aims to obtain the optimal worker assignment scheme, and the lower level one targets the optimal start and complete times of operations.

Higher level GA

• 1. Encoding scheme.

Based on the number of work teams, the high-level chromosome is divided into $\left|H\right|$ gene blocks. The length of each block is the number of work groups in the work team, and the size of the chromosome is the number of work groups $\left|M\right|$ . In the encoding scheme, gene values are the numbers of workers assigned to work groups.

• 2. Generation of the initial population.

Under the premise that constraint (2) holds, each individual is created by random selection from the value ranges of genes.

• 3. Selection, crossover and mutation.

The roulette, partially matched crossover method (PMX) and single-point mutation method are employed, respectively.

Lower level GA

• 1. Encoding.

Each chromosome consists of two parts, whose length equals the size of the current window. In the first part, a character string encoding is adopted, and each gene value is equal to the code of an operation. In the second part, an integer encoding is used, and gene values, which are stored in a fixed order, are the indices of work groups.

• 2. Generation of initial population.

The first part is generated by a random permutation of operations, and the second part is generated by a random selection of eligible work groups.

• 3. Selection.

The selection method adopted is roulette in this algorithm.

• 4. Crossover.

Order crossover operator ²³ is used in the first part, and two-point crossover is employed in the second part.

• 5. Mutation.

In the first part, reverse mutation operator ²⁴ is used. A single-point mutation method is adopted in the second part where the mutation gene value is the index of the work group selected randomly.

• 6. Decoding.

The second part of a lower level chromosome is always feasible because gene values are always determined based on the eligible work groups of operations. However, in contrast, the first part is most possibly unfeasible due to the presence of assembly constraints. By considering the production features of the aircraft-engine assembly workshop, an improved decoding method is proposed in this article on the basis of the one developed by Wang et al. ²⁵ to avoid the computational burden from repair actions of every chromosome. The detailed steps go as follows (Figure 8):

• Step 1. Store the first part of the candidate chromosome into a string array and set $p\prime =1$ .

• Step 2. Scan the array from left to right. If the current element is empty, set the current position $p\prime =p\prime +1$ , otherwise go to Step 3. If all elements are empty, go to Step 6.

• Step 3. Judge whether the current operation is processable. If yes, go to Step 4, otherwise set the current position $p\prime =p\prime +1$ ; if the element is not empty, repeat Step 3, otherwise $p\prime =p\prime +1$ . If the current position is the end of the array, set $p\prime =1$ and go to Step 2.

• Step 4. Find out the work group from the second part of the chromosome and determine the start time and completion time of the operation.

• Step 5. Set the element to be empty, $p\prime =p\prime +1$ and go to Step 3.

• Step 6. End the decoding procedure.

Figure 8.

Flow chart of the decoding process.

BiGA

Detailed steps of BiGA go as below (Figure 9):

• Step 1. Initialize the parameters of the bi-level algorithm, such as population sizes, crossover rates, mutation rates and so on.

• Step 2. Generate the higher level initial population and set $k_1=k_2=1$ .

• Step 3. Employ the lower level GA to solve the scheduling problem by using the parameters acquired from the higher level individual $k_2$ .

• Step 3.1. Calculate the processing times of operations by equation (12).

• Step 3.2. Generate the lower level initial population and set $k_3=1$ .

• Step 3.3. Perform the decoding method, calculate the fitness values of lower level individuals following the fitness function $\gamma /F$ ( $\gamma$ is a constant).

• Step 3.4. If $k_3$ is greater than the lower level maximum iterations, then go to Step 4, otherwise perform the lower level selection, crossover and mutation operations and set $k_3=k_3+1$ ; then go to Step 3.3.

• Step 4. Substitute the minimum value $F_{min}$ into $Z$ and calculate the fitness value of the higher level individual $k_2$ following the fitness function $\rho /Z$ where $\rho$ is a constant.

• Step 5. Set $k_2=k_2+1$ . If $k_2$ is greater than the size of the higher level population, reset $k_2=1$ and go to Step 6, otherwise go to Step 3.

• Step 6. If $k_1$ is greater than the higher level maximum iterations, go to Step 7; otherwise execute the higher level selection, crossover and mutation operations, set $k_1=k_1+1$ , and then go to Step 3.

• Step 7. Terminate the algorithm and output the results.

Figure 9.

Flow chart of the BiGA.

Numerical experiment

Feasibility analysis

Algorithms are coded in FORTRAN and MATLAB and compiled on a personal computer (PC) with Intel (R) Core (TM) i5-2400 central processing unit (CPU) at 3.10 GHz and 4 GB main memory under WINXP. Table 1 gives the parameters of BiGA, Table 2 shows the resource allocation situation of work teams, Table 3 gives some related data of Engine F and Figure 10 expresses the tree structure of Engine F at the first assembly stage.

Table 1.

Parameters of BiGA.

Level	Population size	Generation	Crossover rate	Mutation rate
Higher level	20	40	0.8	0.15
Lower level	30	50	0.75	0.1

Table 2.

Resource allocation of work teams.

Work team	Number of work groups	Work team	Total number of workers	Value range of the number of workers in each group
Accessory gearbox team	1	1	6	[2,6]
Front-rear gearbox team	2	2,3	12	[3,9]
Gearbox guider team	2	4,5	10	[3,7]
Gearbox team	1	6	6	[3,6]
Assembly team	3	7,8,9	10	[2,8]
Machining team	3	10,11,12	10	[2,6]
Balance team	1	13	7	[4,7]
Weld team	2	14,15	12	[3,9]
Augmentation team	2	16,17	9	[3,6]
Drive assembly team	2	18,19	5	[1,4]
Final assembly team	1	20	5	[2,5]

Table 3.

Partial data of Engine F.

Operation	Work team	Cost coefficient of the complete time	Maximum of processing time (h)
F|1|1	Final assembly team	11.0	20.0
F|1|2	Drive assembly team	3.0	12.0
F|1|3	Weld team	4.0	11.0
…	…	…	…
F|1|29	Balance team	3.0	3.0
F|1|30	Accessory gearbox team	4.0	4.0
…	…	…	…
F|1|40	Augmentation team	1.0	13.0
F|1|41	Front-rear gearbox team	4.0	9.0

Figure 10.

Product tree of Engine F at the first assembly stage.

Four engines C, D, E and F need to be assembled, and all work groups are available at $T=0$ . The initial worker assignment is [2,3,5,3,3,6,2,2,2,3,2,2,4,4,4,3,5,2,3,5]. It is assumed that Engine C is disqualified after the first assembly stage is finished. Parameters of the rolling horizon procedure are $\epsilon =60$ and $\eta =40$ , respectively, the time spent in getting a self-evolution decision $\Delta t\approx 0.12\mathrm{h}$ , which is negligible here. The scheduling result is shown in Figure 11, where each solid vertical line indicates a decision moment, and rectangles represent the operations.

Figure 11.

Scheduling result after self-evolution.

Seen from Figure 11, eight self-evolutions are included in the whole production process, where Engine C is disqualified at $T=91\mathrm{h}$ and reassembled at $T=101\mathrm{h}$ . Thus, the model and algorithms are demonstrated to be feasible and effective.

Effect of self-evolution on the production performance

To acquire the comparison of production performances between two cases, 10 groups of simulations are conducted, each of which contains two sub-experiments. In Case 1, self-evolution operations are performed with adjustable parameters. In Case 2, no self-evolution operations are adopted, and the number of workers in each group is invariant. The experimental data in Table 4 indicate that, although with a higher worker assignment cost, the workshop with self-evolution operations promises far less scheduling and production costs than that without. In the table, $B^{*}$ , $F^{*}$ and $Z^{*}$ , respectively, are the worker assignment cost, scheduling cost and production cost in Case 1; $B\prime$ , $F\prime$ and $Z\prime$ are the worker assignment cost, scheduling cost and production cost in Case 2.

Table 4.

Comparison of costs between two cases.

Cost	1	2	3	4	5	6	7	8	9	10	Average
$B^{*}$	2819	2796	2813	2754	2789	2804	2732	2845	2810	2769	2793
$F^{*}$	86,334	86,721	86,315	86,733	87,561	86,845	87,987	85,846	86,241	86,854	86,744
$Z^{*}$	61,280	61,544	61,264	61,539	62,129	61,633	62,411	60,953	61,212	61,629	61,559
$B\prime$	0	0	0	0	0	0	0	0	0	0	0
$F\prime$	119,123	119,225	119,953	120,474	121,557	120,100	119,093	120,324	120,910	121,612	120,237
$Z\prime$	83,386	83,458	83,967	85,032	85,090	84,070	83,365	84,227	84,637	85,128	84,236

Conclusion

In this article, the self-evolution problem of KMSs has been studied by using the example of an aircraft-engine assembly workshop with uncertain number of assembly times. A solution algorithm was developed and a general mathematical model of static decision problems formulated. To solve the model, a BiGA was proposed by considering product features. Computational results show that the workshop with self-evolution operations has better performance than the one without.

For future research, considering the actual manufacturing environment, setup times between operations and movement times of workers are highly recommended to be incorporated. In addition, more effective algorithms are also worth exploring to solve the static model.