Yao-hua LI, Chen LIANG, Dong-dong WEI

(Aeronautic Engineering College, Civil Aviation University of China, Tianjin 300300, China)

Abstract: In maintenance resource scheduling problems, the optimal scheduling of civil aircraft is playing a more and more significant role. However, the existing researches are mainly focused on maintenance task scheduling while there are few studies on air material scheduling. Base on this background, an air material scheduling model is presented to solve different maintenance tasks of civil aircraft in real time and to optimize the material scheduling cost in the paper. The model is based on the real-time environment of the air material storehouse, and the time windows of task demanding and punishment of aircraft shutdown has been taken into account. To solve the model effectively, an improved genetic algorithm (IGA), instead of traditional genetic algorithm (GA), is introduced. The simulation results show that this model is valid and efficient.

Key words: Air material, Scheduling, Time windows, GA

1 Introduction

As the key component of civil aircraft maintenance resources, air-material is the primary resource in maintenance support work. In the implementation of the planned maintenance task, it is an urgent problem to meet the needs of the different maintenance tasks in different time periods, aiming at the real-time scheduling of the existing stock of air material.

In view of resource scheduling problem, relevant domestic and foreign scholars have made corresponding research. Zhang Sijia [1] and others put forward a multi-objective air material storage decision-making optimization method based on bat algorithm and achieved multiple objectives with the highest combat readiness and the lowest cost. However, the demand for each kind of air material obeys the Poisson process with a failure rate of λ, and the shortage time is independent of each other and obeys the same distribution with a mean of T. This ignores the demand relationship between air material allocation and maintenance tasks, and ignores the real-time, complexity and randomness of maintenance tasks. Based on the diversity of material distribution route between work centers and the time variability of route circulation ability, Siguo Li et al. [2] constructed a mathematical model of material distribution problem based on the real-time environment of the workshop by combining the requirements of the work center to the arrival time window of the material, and solved the mathematical model constructed by the improved genetic algorithm. Most of the existing research on resource scheduling is aimed at small scale static scheduling for the available allowance, ignoring the real time of the inventory. And there is a lack of large-scale research on the optimal scheduling of air-materials in the case of “self-sacrifice” and not just pursuing single optimization.

In addition, Zhou [3] and Muller [4] have studied the vehicle routing problem of material distribution with time window requirements from the VRPTW (vehicle routing problems with time windows, VRPTW) problem and solved by the heuristic algorithm. Shuihua Wang [5] solved the optimization of the MDVRP with adaptive genetic algorithm, which is an extended version of the VRP, and multi-depot, multiple customers, and multiple products are considered.

Although both the air material dispatching and air material distribution have the complexity of the traditional VRP (i.e., vehicle routing problems) problem [6-9], the air material scheduling also has other characteristics depending on the maintenance task, such as the dynamic remainder monitoring and the time window demand of the maintenance task, etc. Most of the researches focus on the generalized maintenance resources, and there is no specific research on the scheduling research of air material distinguished from other maintenance resources.

To ensure the real-time air material demand for maintenance tasks under planned maintenance, this paper combines the demand time window and the shutdown penalty as time constraint. Based on the real time allowance of the air material stock and the transportation route between the storehouses, this paper considers the factors of the inventory limit and the cost of the management, the cost of the shutdown penalty and the cost of transportation. Based on the requirement of maintenance task for arrival time windows of air-material, this paper constructs a mathematical model of air material scheduling problem based on the real-time condition of air material storage. Finally, the improved genetic algorithm is adopted to solve the constructed mathematical model, and the validity and feasibility of the model and algorithm are verified by numerical simulations.

2 Air material scheduling model

2.1 Problem description

According to the scheduled maintenance, the scheduling and planning of the air material demand according to the maintenance task and the air material dispatching service shared by the stock are carried out. Different levels of storehouse have different original inventory and different levels of maintenance tasks at different time requirements. The demand scheduling of air material will be affected by the real time allowance of the storehouse, and the distribution route between the storehouses will produce different distribution costs due to the difference between distance and road condition. Air-material scheduling is constrained by the time window of task demand. If the air material does not arrive at the given time, the corresponding penalty function will be established. Fig.1 shows a possible scheduling scheme fromTt=0 toTt=1 under the condition of the following factors: maintenance task demands including update and urgent situation, real-time storage, transportation constrains, costs and so on.

Fig.1 Air material scheduling model under dynamic inventory

Based on the above, a plan for minimizing the total cost of air materiel scheduling under specific inventory conditions is presented, which meets the needs of real-time aviation materials at all levels of maintenance tasks. To establish a dynamic scheduling model for air materials, the following limitations are made for the air material scheduling：

(1) Only one time and one direction transportation is provided for each storehouse in a scheduling period, and the type and quantity of air material is not restricted.

(2) Single transport can be completed within a scheduling cycle.

(3) The maintenance base is attached to the air material storehouse, and only one maintenance task is arranged in a scheduling cycle in each storehouse.

(4) The management cost of different levels of air material storehouse is different, the transportation cost between different storehouses is different, and the shutdown cost caused by different maintenance bases is different.

(5) The air material should be delivered in the time window of the mission. If it does not arrive on time, it will cause huge shutdown costs and establish a corresponding penalty mechanism. To simplify the calculation under the actual conditions, the penalty function in this paper is expressed as a linear function.

(1)

Where,TtVkiis the arrival time of transporting air materialVito thek-th storehouse within the timeTt,TtHkhis the execution time of the task, andλkis the penalty coefficient for delay.

2.2 Problem formulation

2.2.1 The objective function

Mathematically, the objective function is formulated as:

(2)

Subjected to:CMandCB

2.2.2 Scheduling model

During the maintenance and support process, each kind of air materials may be stored in one or more air materials storehouses, and the storage quantity in each storehouse is different. There is a maintenance support organization, the collection of storehouses isS={Sj,j=1,2,…,N},Sjrepresents thej-th storehouse; collection of air materials isV={Vi,i=1,2,…,M},Virepresents thei-th air-material.

According to the statistics of the number of different kinds of air materials allocated in each storehouse, the supply matrix of air materials is shown as follows,

SV=(SVji)N×M=

(3)

Where,SVjiindicates the number of thei-th air material in thej-th storehouse. AndTSV=[TtSVji]N×M×T,t∈[1,T] is the supply matrix of air materials int-th scheduling period.

According to the actual situation, it is assumed that different maintenance tasks are arranged in each air material storehouse. The collection of maintenance tasksHSj={HSjh，h=1，2，…，H},HSjhrepresents theh-th maintenance task in thej-th storehouse. According to the statistics of air materials required by each maintenance sub-task, the demand matrix of maintenance task and air materials inSjis shown as follows,

HSjV=(HSjhVi)H×M=

(4)

Where,HSjhVirepresents the demand fori-th air-material ofh-th maintenance task fromj-th storehouse.

The demand matrix of each maintenance station (storehouse) isASV=[ASVji]N×M,ASVjiindicates the demand quantity ofj-th storehouse fori-th air-material. They have following relations:

(5)

Eq. is the demand statistics of the air material for the maintenance task.

When it comes toASVji>SVji, storehouseASjhas shortage in air material. To solve the shortage problem, it is necessary to make an emergency deployment of air materials between the warehouses, request support from other storehouses equipped with enough aircraft materials.

The scheduling matrix isTtVR=[TtViRlk]N×N×M, whereTtViRlk，l,k∈[1,N],t∈[1,T] is the scheduling number ofl-th storehouse tok-th storehouse int-th scheduling period. The scheduling result matrix varies after thet-th scheduling period isTtBSV=[TtBSVji]N×M,TtBSVjiindicates the number ofi-th air-material in thej-th storehouse after thet-th scheduling period and the quantity statistics ofi-th air material aftert-th scheduling period is shown in Eq..

(6)

The constrainsCMof air material limits andCBtransportation limits are shown as follow,

(7)

Eq. is an adjustable quantity constraint fori-th air material duringt-th scheduling period.

(8)

(9)

Eq. indicates that the number of scheduling times in a scheduling cycle must be less than the total number of storehouses. Eq. is the vehicle transportation constraints of storehouse.

Ttxlkis the judgment matrix of transportation between storehouses, ifSltransport the air material toSk,Ttxlkis set to 1, otherwise,Ttxlkis set to 0.

For cost management,W=[wj]Nis the cost matrix of storehouse management;Y=[ylk]N×Nis the matrix of transportation cost between storehouses.

3 Using IGA to solve the model

The genetic algorithm, which is proposed by Holland [10], is a robust spatial search technique. It can use the evolutionary principle in linear time to obtain a feasible solution from a larger search space [11]. In genetic algorithms, a solution in a search space is represented as an individual (regarded as a chromosome). The collection of these individuals is called a population. Each generation of groups continues to evolve, and the better individuals will be left to produce a new generation. The quality of an individual in a population is determined by the fitness function, which describes the quality of an individual relative to other individuals in the population.

The problem of this paper is based on the dynamic inventory, the research on the air material scheduling planning for the maintenance task with time window, involving three sub-problems:

(1) The selection of the quantity of air material dispatching.

(2) The distribution of the air material distribution sequence.

(3) The optimal combination of distribution storehouse.

For NP-Hard (non-deterministic polynomial, NP) mathematical programming problems, GA as a stochastic optimization technique simulating natural selection and genetic mechanism, has a significant advantage in solving optimal scheduling problems and has a good characteristic of solving combinatorial optimization problems[12-14].

3.1 Coding form of individuals

Before the operation of genetic algorithm, it is necessary to design chromosomes for the problem, including the length of the gene string and the meaning of the gene representation. That is, the feasible solution to search space is presented in the form of encoding. The general encoding method uses binary encoding, and there are also integers, real numbers, and words. According to the structural form of feasible solution, the coding method of this paper is chromosome set. According to the constraints based on the above model, the number of chromosomes in each chromosome set is determined by the number of air-material storehouse. That is, if there are n storehouses, n kinds of distribution situations can be generated at most under a certain scheduling scheme, which the number of chromosomes is n. Each chromosome is mirror binary coded, and the mirror binary is mirror symmetric with the conventional binary.

In this paper, the problem of resource scheduling is studied. Therefore, the combination of air- materials storehouse and the number of air-materials allocated should be reflected in the chromosome coding. And each chromosome is based on the number of air materials storehouse and the total number of such air-materials to determine its code length. The whole chromosome is composed of 1+V segment, and V represents the number of types of air-materials. The length of the first gene is determined by the quantity of the storehouse, and the length of the remaining V segment is determined by the total number of each air material.

The coding method is illustrated by an example of one scheduling scheme of 3 storehouses and 3 kinds of air materials in a scheduling period. Table 1 shows an example of chromosome; Fig.2 is the corresponding gene expression.

Table 1 Chromosome examples

The line number in Fig.1 indicates the number of the supply storehouse; the first column represents the distribution storehouse number; the second to fourth column represents the dispatch volume of first to third kinds of air-materials.

Fig.2 Gene expression

3.2 Adaptive genetic operation

he crossover ratepcand mutation ratepmin the genetic algorithm have a very important influence on the convergence and performance of the genetic algorithm, which directly determines whether the genetic algorithm can converge to the global convergence. However, the same probability cannot meet the needs of the population evolution. For example, at the early stage of iteration, the population needs a higher probability of crossover and mutation, which has reached the goal of finding the best solution quickly. In the later period of convergence, the population needs smaller crossover and mutation probability to help the population to find the optimal solution quickly. Therefore, the invariable probability of crossover and mutation affects the efficiency of the algorithm. For preventing premature convergence of the GA to a local optimum, we need to preserve ‘good’ solutions of the population. In this paper, the adaptive genetic algorithm is used to adaptively changepcandpmin the genetic process according to the variation of chromosomal fitness values.

Here, the adaptive genetic algorithm of [15-18] was extracted for improvement. When the crossover operation is carried out, if the smaller fitness value of the two chromosomes to be crossed is lower than the average fitness value of the current population, the mutation probability should be reduced to preserve the better individuals and the algorithm convergence should be accelerated. On the contrary, a larger value should be taken to increase the crossover probability to promote the generation of new individuals. When it comes to mutation operation, if the adaptive value of the mutant is lower than the average adaptive value, the mutation probability should be reduced to zero to accelerate the convergence of the algorithm. If it is higher than the average value, the mutation probability should be increased to generate new individuals. The expressions that we have chosen forpcandpmare of the form

pc=pc1(f′-fmin)/(favg-fmin),f′

pc=pc2,f′≥favg

(10)

and

pm=pm1(f-fmin)/(favg-fmin),f

pm=pm2,f≥favg

(11)

Where,pc1

In the above formula,favgandfminare the average fitness values of each generation population and the smallest fitness value of the population;f′ andfare the smaller fitness values and the fitness values of the two individuals in the crossover operation.

In the above genetic operation,pcandpmchanges dynamically with the adaptive value of the individual, effectively protecting the superior individual, enhancing the variation ability of the worse individual, and maintain the diversity of individuals within the population. This can not only accelerate the convergence, but also improve the precision of the algorithm, enhancing the ability of global convergence.

3.3 Solving steps of genetic algorithm

In view of the above situation, the basic steps of a typical genetic algorithm are shown in Fig.3, which is applied to solve the real-time scheduling problem of air material sharing.

Step1: input the parameters needed to solve the model, mainly including the basic data of storehouse, task requirements and initial number of air material.

Step2: initialization of the algorithm parameters, set the number of stopping iterations, the maximum number of termination iterations, the initial cross probability of chromosomes and the probability of variation, and randomly generate the initial population.

Step3: select operation and adopt fitness ratio selection method.

Fig.3 The flow chart of genetic algorithm.

Step4: calculate the adaptive crossover probability and mutation probability according to formula and.

Step5: with a crossover probability, cross over the parents to form a new child; with a mutation probability method mutates new child at each chromosome; check the rationality of the gene and replace the original gene with the unlawful gene.

Step6: evaluate each chromosome in the initial population using the objective function, search for the best value of the objective function.

Step7: place new child in a new population and use new generated population for a further run of algorithm. If the stopping criteria is satisfied then go to Step 8, else go to Step 3.

Step8: outputting the adaptive value (cost) of the current optimal generation of chromosomes.

4 Simulation study and numerical results

To verify the model and algorithm, the practical case is applied in this paper and uses MATLAB to carry out simulation experiments. A maintenance unit has 4 air-materials storehouses (with maintenance stations) and each storehouse has 5 kinds of air materials. Each maintenance station is scheduled to have 3 maintenance tasks in aTtime cycle. Among them, the unit of service time and the demand time window are in day, and the demand and quantity are in piece. Each air material storehouse provides only one time and one direction transport in a scheduling cycle, and it can be completed in a scheduling cycle. The maintenance station only arranges one maintenance task in a scheduling cycle. During the production process, it is necessary to plan for the next period of maintenance tasks, and to carry out the real-time scheduling of the dynamic inventory. In this paper, the scheduling plan and minimum total scheduling cost are discussed under the constraint.

The specific genetic parameters are as follows: the population size is 50, the number of iterations is 200, the maximum evolution algebra 5 000,Pc1=0.5,Pc2=1,Pm1=0.25,Pm2=0.5. The basic parameters of the air-material storehouse are shown in Table 2, and the requirements of each maintenance station under planned maintenance are shown in Table 3.

Table 2 Basic parameters of air-material storehouse

Table 3 Task requirements (with time window)

Continued Table

Table 4 shows the optimal scheduling scheme with all tasks are completed within the time window. It lists the distribution of air material for each storehouse in every scheduling period. The optimization of each scheduling cycle is independent. Thus, the model can flexibly update the resource configuration according to the real-time requirements of the maintenance task, and will not affect the decision of the scheduling cycle before this. An optimal scheduling scheme result based on adaptive genetic algorithm related to each scheduling period is shown in Fig.4, which shows the satisfactory result of the program. It provides a feasible solution and method for solving the real-time scheduling problem of shared air material which has certain guiding significance.

Fig.5 is the comparison between the basic genetic algorithm and the adaptive genetic algorithm in the scheduling simulation process oft=2. From the simulation results, one can see that the improved genetic algorithm based on the chromosome group shows certain advantages in solving large-scale scheduling problem. The optimal value is higher than the basic genetic algorithm, and the number of iterations is obviously less than that of the basic genetic algorithm, which lays the foundation for solving a more large-scale scheduling.

From the results presented in Table 4, Fig.4 and Fig.5, we can infer that, in solving the air material scheduling problem for the maintenance task with time window, compared with the manual operation, the optimization model greatly improves the efficiency and provides a better feasible solution. Under the large data analysis, the speed and accuracy of the calculation are more advantageous and can reduce the cost output of the air material in a global way. The model can optimize the real-time scheduling of the air material under the dynamic inventory monitoring for the maintenance task with time window and can respond to the emergency maintenance task in time and update the scheduling scheme in the scheduling interval. The model is effective, maneuverable and feasible, and can be widely used in system modelling of maintenance resource scheduling.

Table 4 Optimal scheduling scheme

Fig.4 An optimal scheduling scheme based on adaptive genetic algorithm

Fig.5 Simulation analysis comparison diagram

5 Conclusion

By analyzing the balance relationship between the maintenance task demand and the dynamic inventory with the soft time window, an optimal scheduling method for air materials based on adaptive genetic algorithm is proposed, which provides a certain basis for the optimization of air material scheduling. As the frontier theory of air material support scheduling, the model can be applied to the configuration of air material requirements for emergency maintenance tasks and update the scheduling scheme timely. It provides a new idea for the dynamic inventory management of civil aircraft maintenance based on the planned maintenance task.