Carrier-based aircraft maintenance tasks are conducted in time-critical, resource-constrained, and uncertain environments. Optimizing the scheduling allocation scheme of maintenance personnel and equipment, reasonably responding to uncertainty disturbances, and maintaining a high fleet availability are vital to the combat and training missions of carrier-based aircraft. The maintenance task scheduling problem for carrier-based aircraft is investigated in this study. First, a mathematical model for comprehensive carrier-based aircraft maintenance task scheduling that considers constraints such as maintenance personnel, equipment/shop, space, and parallel capacity is developed. Second, to generate the baseline scheduling scheme, an improved non-dominated sorting genetic algorithm II (I_NSGA-II) with local neighborhood search is proposed for the model optimization solution; I_NSGA-II uses the serial scheduling generation scheme mechanism to generate the time sequence scheduling scheme for maintenance personnel and equipment/workshop of different fleet sizes. Third, to cope with dynamic uncertainty disturbances, two reactive scheduling methods, i.e., complete rescheduling and partial rescheduling, are proposed to perform reactive scheduling corrections to the baseline schedule. Case simulation shows that the established mathematical model is reasonable and practical, and that the proposed I_NSGA-II is superior to the current mainstream algorithms. In addition, the decision maker can select between the two reactive scheduling methods flexibly based on the different forms and scales of disturbance.
Hinweise
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Introduction
Aircraft carriers and amphibious assault ship formations are the core combat forces of joint maritime maneuvering operations, and carrier-based aircraft are the main combat forces of these formations [1]. Maintenance restores and maintains the good technical conditions of carrier-based aircraft and enable various flight missions, such as combat, readiness, and training, to be performed as intended. Airborne equipment and airframe structure troubleshooting maintenance, scheduled maintenance, and aero-engine maintenance maintain or restore the technical condition of each type of carrier-based aircraft during stationing, maintain a high level of integrity of the fleet, and serve as preparation for the combat and training missions of flying activities (i.e., waves or sorties).
The maintenance and support capability of carrier-based aircraft is associated closely with the level of ship-based equipment and maintenance personnel skills; furthermore, it is limited by the decision maker’s command and control capability. Meanwhile, the battlefield environment is complex, and maintenance tasks for carrier-based aircraft execution processes will be affected by various uncertainty disturbances, if the improper disposal of maintenance delays will directly delay the carrier-based aircraft combat and training mission, so the maintenance of dynamic decision-making capabilities put forward higher requirements [2]. Based on the characteristics of ship-based maintenance, scientific timing planning, and resource allocation for maintenance personnel and equipment/workshop, the development of an efficient scheduling scheme and dynamic environment response method to solve the maintenance task scheduling problem is key to improving the efficiency of maintenance, which is crucial for restoring carrier-based aircraft to a usable state and forming combat capability as soon as possible.
Anzeige
Currently, owing to insufficient openness, complex constraints, and specific research fields associated with the maintenance task scheduling problem for carrier-based aircraft (MTSPCA), the results obtained both in China and abroad are insufficient. In the field of equipment maintenance task scheduling, which has been investigated extensively in recent years, differences in scheduling mathematical models applicable to different equipment maintenance tasks are indicated. When constructing a model, the following are typically prioritized: the traveling salesman problem [3], job shop scheduling problem [4, 5], ant colony system approach [6], vehicle routing problem [7‐9], vehicle fleet maintenance scheduling optimization problem [10], resource-constrained project scheduling problem (RCPSP) [11, 12] and multi-objective resource-constrained project scheduling problem [5, 7, 10]. The MTSPCA is a complex scheduling problem involving multiple carrier-based aircraft and multiple maintenance tasks, which include multiple constraints (maintenance process constraints, maintenance equipment coverage constraints, parallel operation constraints in maintenance workshops, maintenance resource allocation constraints, etc.). Maintenance operations should satisfy serial and parallel constraints. Different equipment/workshops and maintenance personnel are constrained by time, space, and quantity. Meanwhile, uncertainties exist in maintenance tasks, such as resource interruption (equipment/workshop failure and personnel reduction) and time interruption (a longer time required for equipment maintenance). The allocation of limited maintenance personnel and equipment/workshops via optimization methods has been investigated, which involved multi-objective and uncertain dynamic environments. Therefore, the MTSPCA involves the collaborative scheduling of related maintenance personnel and equipment/workshops. From the perspective of operation content and time, it is a maintenance task with priority relation constraints under resource-constrained conditions. In terms of the complexity of scheduling problems, it is a multi-objective optimal scheduling problem, which is the core difficulty in full-process operation scheduling for aircraft carriers and amphibious assault ships. Hence, using a multi-objective, resource-constrained project scheduling optimization model is the ideal solution. For carrier and civil aircraft maintenance scheduling, Zeng et al. [13] proposed a comprehensive availability constraint model while considering a regular schedule and random coverage time, as well as used a heuristic solution algorithm to generate a scheduling scheme for carrier coverage operations and equipment planned maintenance schedules. Han et al. [14] developed a simplified personnel allocation model for carrier-based aircraft maintenance and assurance, as well as computed the model using a queuing theory approach. Deng et al. [15] proposed a novel decision support system for optimizing aircraft maintenance check schedules and task allocation to optimize aircraft maintenance task allocation. Lin et al. [16] proposed a solution algorithm inspired by the propagation of yeast process to develop a fleet maintenance assurance-based model that can minimize the maintenance completion time, as well as balance the number of hangar bay resources and the maintenance cost of the fleet. Each of these models simplifies one or two of several significant factors.
1.
Constraints such as operation processes or maintenance personnel are only considered during model construction, whereas constraints such as resources, space, and parallel operations are not considered completely.
2.
Aircraft maintenance tasks include a combination of fault repair and scheduled maintenance, which exhibit node-networked precedence relationships rather than serial relationships.
3.
The task objective of the MTSPCA is to maintain a high level of availability of the fleet and the sustainability of the maintenance operations of the maintenance personnel, instead of simple task scheduling with a single optimization objective of minimizing the makespan of the maintenance process.
Based on the analysis above, the MTSPCA is classified as a class of branches of the resource-constrained project scheduling problem (RCPSP), which has been proven to be an NP-hard problem. Numerous results pertaining to the RCPSP associated with the current study, including flight deck operation scheduling and RCPSPs, can be used as a reference.
In recent years, significant results have been achieved for the RCPSP in the field of flight deck operation scheduling. Su et al. [17] systematically analyzed pit-stop support routing and resource constraints, and an optimized pit-stop support scheduling mathematical model on the deck of carrier planes was established. Cui et al. [18] established a detailed mathematical model for carrier-based aircraft flight deck operation scheduling. Cui et al. [19] further analyzed the precedence and resource constraints in flight deck operations and established a model of the multi-aircraft integrated scheduling problem with transfer times. The abovementioned studies have inspired researchers to develop a mathematical model for the MTSPCA. Dynamic flight deck operation scheduling has been investigated in rolling horizon scheduling [20], robust scheduling [21], proactive scheduling [22], and proactive robust scheduling [23].
Although the RCPSP has been extensively investigated by scholars worldwide, it has not been applied to the MTSPCA. Zeng et al. [24] used a combination of heuristic algorithms and hybrid Petri nets to solve the uncertainty scheduling model with reserved spare downtime, which improved the scheduling ability for managing unexpected events. Elloumi et al. [25] proposed three heuristic square algorithms to fix the multi-mode resource-constrained project scheduling problem caused by interruptions in initial scheduling triggered by unexpected conditions. Rostami et al. [26] proposed a new strategy for solving stochastic resource-constrained project scheduling. Ouelhadj et al. [27] presented a review of the manufacturing system and the dynamic scheduling problem, as well as classified dynamic scheduling into fully reactive scheduling, baseline-reactive scheduling, and robust scheduling. Baseline-reactive scheduling is derived in a certain environment using baseline scheduling as the standard. When the occurrence of uncertainty disturbance causes the baseline scheduling scheme to be less optimal or infeasible, the appropriate reactive scheduling method must be adopted timely to correct the baseline schedule such that the scheduling tasks proceed seamlessly. Reactive scheduling theory and methods are primarily used in the manufacturing field, where the uncertainty disturbing events include various uncertainties, such as temporary task insertion [28, 29], partial process delays [30], and equipment failures [31, 32]. Vieira et al. [33] used a complete rescheduling (CR) method to fix the baseline schedule. Abumaizar et al. [34] and Sanmarti et al. [35] investigated this problem using a partial rescheduling (PR) approach.
Anzeige
Based on the analysis above regarding the current state of research, we believe refined mathematical models for the MTSPCA, a relatively new research area investigated in this study, are insufficient. The MTSPCA is a large-scale problem with strict constraints, and using heuristic algorithms is the ideal solution to solve such problems currently. Simultaneously, the dynamic scheduling of the MTSPCA should be considered using the reactive scheduling method in the field of dynamic scheduling, which will render the application scenario of the model more practical.
In this study, we focus on the MTSPCA and the dynamic maintenance environment in which it is located, and innovations are reflected in the following three aspects:
1.
A comprehensive mathematical model is constructed for the MTSPCA to maximize wave availability and minimize the variance of maintenance personnel load, while considering the constraints of maintenance personnel, resources, space, and operation flow.
2.
Using the MTSPCA as the research object as well as the computational complexity of the problem, an improved non-dominated sorting genetic algorithm II (I_NSGA-II) with local neighborhood search for codes is proposed to calculate the baseline scheduling scheme for maintenance personnel and equipment/workshop. It offers better performance than other alternatives and achieves better optimization and solution efficiency for the solution of baseline scheduling.
3.
Based on the baseline schedule, we propose two reactive scheduling methods, i.e., CR and PR to manage dynamic uncertainty disturbances encountered in maintenance tasks. In the two methods, two distinct scheduling strategies are adopted: active scheduling and baseline logical constrained scheduling. The analysis results can be used as reference by the decision maker when selecting the appropriate reactive scheduling method.
The remainder of this paper is organized as follows: in the next section, the maintenance task scheduling problem for carrier-based aircraft is described. In the next section, the mathematical model of the MTSPCA is presented. In the following section, the process and improvement measures of the I_NSGA-II are described. In the following section, the baseline scheduling and reactive scheduling methods are introduced. In the next section, a case analysis and details regarding the simulations performed are presented. Finally, conclusions as well as suggestions for future studies are presented in the last section.
Problem statement
A practical carrier-based aircraft maintenance task scheduling problem is investigated in this study. The carrier-based aircraft must be inspected before and after a mission, and once the equipment and airframe structure failure is diagnosed or the scheduled maintenance date is reached, the carrier-based aircraft must be transferred to the ship-based maintenance hangar bay such that it can undergo fault repair or periodic inspection after it is tethered in position. Airborne equipment and airframe structure troubleshooting maintenance refers to the failure of airborne equipment, components, and accessories; in situ adjustments, replacements, and disassembly repairs; mechanical structure deformation, cracks, and fracture damage; and other forms of on-site repair for restoring the structure shape and performance.
Carrier-based aircraft scheduled maintenance primarily involves the flight time, landing and takeoff times, and calendar time control, e.g., 25, 50, and 100 h scheduled maintenance of carrier-based aircraft.
The main objective of the maintenance is to maintain a high fleet availability, maximize the fleet availability, and ensure maintenance task sustainability to achieve the scheduled waves (sorties) scheme. Therefore, under resource-constrained conditions, the scheduling of maintenance personnel and equipment/workshop is key to achieving the maintenance task objectives and is the essence of the MTSPCA. Maintenance task scheduling refers to the reasonable allocation of limited maintenance personnel and equipment/workshop, as well as the formulation of efficient and detailed time sequence scheduling that satisfies realistic objectives and ensures the full utilization of resources to obtain the optimal scheduling solution. The precedence relationships of scheduled maintenance and fault repair operations are typically modeled as activity on node network (AON). The operations are flexibly selected by maintenance personnel based on the demand for maintenance skills. Ship-based maintenance equipment can be categorized into fixed-class resource stations and mobile-maintenance equipment. Fixed-class resource stations are typically regarded as power supply stations. Each power supply station has a limited usable area that depends on the pipeline length. Maintenance workshops are distributed around the hangar bay to provide off-site maintenance of faulty or scheduled components and are categorized into aviation machine repair, oil and fluid inspection, electronic equipment maintenance, and ordnance maintenance workshops. Owing to the different maintenance specialties available, any workshop can accommodate a certain number of processes for parallel maintenance. Maintenance personnel are transferred within each workshop, depending on the type of maintenance required for the aircraft. The comprehensive posture of the Kuznetsov aircraft carrier hangar bay environment is illustrated in Fig. 1.
Fig. 1
Maintenance resources and environment of Kuznetsov aircraft carrier hangar bay
×
The carrier-based aircraft performs combat and training missions dispatched in waves after maintenance. The decision maker must establish a planned start time of each maintenance process for each carrier-based aircraft as well as the overall maintenance process scheduling, including maintenance personnel and equipment/workshop scheduling, before the maintenance mission is commenced. If the number of carrier-based aircraft, maintenance modes, and process time are clearly defined, personnel and equipment/workshop are available, and no failure is encountered, then the MTSPCA is a static scheduling problem, i.e., baseline scheduling with reference under deterministic conditions. However, carrier-based aircraft maintenance tasks are often perturbed by uncertainties, such as equipment and facility failures, which result in prolonged process work times and changes in the tasks of the maintenance personnel, rendering it difficult to perform subsequent tasks according to the prior scheme; as such, rescheduling solutions are necessitated. Meanwhile, the MTSPCA involves dynamic scheduling problems, and the decision maker must select a suitable rescheduling method to dynamically adjust the baseline schedule.
Mathematical formulation
In this study, a mathematical model of the MTSPCA was developed based on some model assumptions combined with the model constraints. The notations used in our mathematical model are listed in Table 1.
Table 1
Relevant notations used in model of MTSPCA
Notation
Definition
I
The set of carrier-based aircraft to be repaired, \(I = \left\{ {1,2, \ldots ,Nm} \right\}\),\(Nm\) is the number of aircraft
J
The set of maintenance processes for the fleet,\(J = \left\{ {\left( {i,j} \right)\left| {i \in I,j \in J_{i} } \right.} \right\}\)
Ji
The set of maintenance processes for the carrier-based aircraft i, \(J_{i} = \left\{ {1,2, \ldots ,\left| {J_{i} } \right|} \right\}\)
Oij
The jth maintenance operation of the carrier-based aircraft i,\(\forall i \in I,\forall j \in J_{i}\)
dij
The maintenance time of Oij
Pi
The maintenance parking spots
Psij
The set of immediately preceding operations of Oij
BM
The set of a sufficiently large positive number
Exi
The tethering completion time of carrier-based aircraft i
Ti
The maintenance makespan of carrier-based aircraft i
The set of all maintenance processes when the fleet is in the execution state at moment t
Ait
The set of maintenance operations of the carrier-based aircraft i in the execution state at moment t
Lp
The set of maintenance personnel
Kc
The set of classification of skills, \(Kc = \left\{ {1,2, \ldots ,\left| {Kc} \right|} \right\}\)
Ke
The category set of maintenance equipment/workshop in the hangar bay
Ks
The set of workspace categories, \(Ks = \left\{ {1,2, \ldots ,\left| {Ks} \right|} \right\}\)
nsik
The maximum number of maintenance personnel of type-k workspace of aircraft i that can accommodate parallel operations
Nekl
The number of operations that can accommodate parallel operations in the lth workshop of type-k
\(\lambda_{kl}^{p}\)
The maintenance equipment/workshop coverage status quantity, where 1 implies that the lth equipment/workshop of type-k can cover Pi, whereas 0 implies otherwise
rsijk
The demand indicator variable, where 1 implies that Oij corresponds to the existence of demand for type-k\(\left( {k \in Ks} \right)\) of the maintenance equipment/workshop, whereas 0 implies otherwise
reijk
The number of Oij to the demand of type-k maintenance equipment/workshop
rcijk
The number of the kth classification of skills demanded by Oij
Smij
A decision variable representing the start time of Oij
Emij
A decision variable representing the end time of Oij
Xeijkl
A decision variable of value 0 or 1, where 1 implies that Oij is assigned to the \(l{\text{th}}\left( {l \in Le_{k} } \right)\) maintenance equipment/workshop of type \(k\left( {k \in Ke} \right)\), whereas 0 implies otherwise
Xpijkl
A decision variable of value 0 or 1, where 1 implies that Oij is assigned to the \(l{\text{th}}\left( {l \in Lp} \right)\) maintenance personnel and the kth classification of skills is used, whereas 0 implies otherwise
Ypijeg
A decision variable of value 0 or 1, where 1 implies that Oij is assigned to the same maintenance personnel as operation Oeg, and Oij is prioritized over Oeg, whereas 0 implies otherwise
Yeijeg
A decision variable of value 0 or 1, where 1 implies that Oij is assigned to the same maintenance equipment/workshop as operation Oeg, and Oij is prioritized over Oeg, whereas 0 implies otherwise
Problem assumptions
1.
All transfer times in the hangar bay are disregarded.
2.
Single maintenance operations cannot be interrupted once it begins.
3.
No transfer of parking space during maintenance.
4.
Maintenance personnel with skills corresponding to the failure can repair all aircraft for the maintenance mode.
5.
Only one type of maintenance mode is used for one carrier aircraft.
6.
The time interval of wave departure is the same and can be obtained in advance.
7.
The maintenance start time corresponds to the time at which the wave begins.
8.
The reactive scheduling decision time is negligible.
Constraints
1) Maintenance process constraint.
The aircraft to be repaired in the hangar bay must begin the first maintenance operation in the maintenance parking spots after being tethered in position. The maintenance start time constraint is formulated as follows:
$$ {\text{Sm}}_{i1} \ge {\text{Ex}}_{i} ,\forall i \in I, $$
(1)
where \(Sm_{i1}\) is the maintenance start time of the first maintenance operation of the carrier-based aircraft \(i\left( {i \in I} \right)\).
The maintenance operation is performed sequentially based on the established precedence relationships, and the subsequent operation must begin after the completion of the immediately preceding operation. The constraint is written as
The maintenance operation is executed only once in the maintenance process, and the single execution constraint of the maintenance operation is written as
The fixed category of maintenance equipment and resource stations, such as power supply stations, is only guaranteed for carrier-based aircraft whose maintenance parking spots are within the coverage, whereas the visual maintenance workshop is a fixed category of equipment whose range encompasses the entire hangar domain. The constraint is written as
The constraint on the maximum number of maintenance personnel of type \(k\left( {k \in Ks} \right)\) at the same time imposed by the maintenance operation \(O_{ij}\) of the carrier-based aircraft \(i\) is written as
$$ \sum\limits_{{j \in A_{it} }} {rs_{ijk} } \le ns_{ik} ,\forall i \in I,\forall k \in Ks,\forall t > 0. $$
(6)
4) Parallel operation constraint in maintenance workshop.
The maintenance equipment was set up in a dedicated workshop with a parallel workload of 1. The workshop can accommodate the number of parallel maintenance tasks corresponding to the number of professional maintenance constraints as follows:
$$ \sum\limits_{{j \in A_{t} }} {re_{ijk} \cdot Xe_{ijkl} } \le Ne_{kl} ,\forall i \in I,\forall k \in Ke,\forall l \in Le_{k} ,\forall t > 0. $$
(7)
(5) Maintenance resource allocation constraints.
The number of skills required for a maintenance operation should match the number of maintenance personnel assigned to the operation using the skills. The constraint is written as
The resources allocated to the operation correspond to the number of maintenance equipment/workshops required. The maintenance operation resource matching constraint is expressed as follows:
Since the numbers of maintenance personnel and maintenance equipment/workshops are limited, when different operations demand the same resources, they must be prioritized in the order of precedence relationships. The constraints are expressed as follows:
1) Objective function for baseline scheduling. The optimization objective of current studies pertaining to equipment maintenance scheduling is typically to minimize the maximum makespan of the maintenance process to achieve high maintenance efficiency for the rapid recommissioning of equipment. However, owing to the combat and training nature of carrier-based aircraft, which typically launch attacks in concentrated groups, carrier-based aircraft sorties are primarily waves, and maximizing the number of available aircraft in the sorties scheme is a prerequisite for the waves [13]. Simultaneously, maintaining multi-wave operational sustainability requirements is equally important for the workload balance of maintenance personnel. Using two objective functions for Pareto solutions can avoid the non-uniformity of the magnitude when synthesizing a single objective function, circumvent the difficulty in determining the weights, and avoid the loss of target information. Herein, we define the wave availability objective function to represent the weighted availability of the fleet to be repaired at the preparation time of each subsequent departure wave. A greater wave availability results in a more intact aircraft afforded by the repair operation for each wave, as well as better capability in satisfying requirements pertaining to the number of wave sorties. The objective function for wave availability is defined as follows:
where \(W\) is the set of departure waves; \({\text{SW}}_{w}\) is the departure preparation start time of the wave \(w\); \(v_{w}\) indicates the wave weight of the wave availability, where the more important the preceding wave is to the battlefield, the greater is the weight; \({\text{fun}}_{w} \left( {{\text{Em}}_{i} - {\text{SW}}_{w} } \right)\) is the wave availability calculation function, which the decision maker can partition into segments based on the different tolerance levels and each wave of the maintenance tasks to accommodate the delay in the maintenance makespan of the carrier-based aircraft; \({\text{WA}}\) is the average availability of the subsequent waves at the start of fleet maintenance. The objective of function \(f_{1}\) is to maximize the sum of the weighted availability of the set of waves.
To maintain the sustainability of the maintenance personnel operations, the variance of the task assignment workload of the maintenance personnel in the baseline schedule must be minimized, and the baseline scheduling maintenance personnel load variance is formulated as follows:
where \({\text{TB}}_{l}\) is the sum of the maintenance time of the maintenance personnel in the \(l{\text{th}}\)\(\left( {l \in {\text{Lp}}} \right)\) position, and \(\overline{{{\text{TB}}}}\) is the mean value of the maintenance time of the maintenance personnel.
2) Objective function of reactive scheduling. Compared with baseline scheduling, in reactive scheduling, the system stability must be considered after scheduling is performed, and the optimization objectives of baseline scheduling must be retained. Because the maintenance tasks are assigned to the relevant maintenance equipment/workshop and maintenance personnel/skills in the baseline schedule, the relevant maintenance personnel and equipment/workshop are prepared for the maintenance tasks before the maintenance tasks begins. Suppose that abrupt dynamic uncertainty disturbances occur in the maintenance process, such as the extension of the maintenance time (resulting in delays), and the transfer of maintenance personnel. In this case, the resource allocation of the subsequent maintenance baseline scheduling scheme will be affected, and extensive scheme adjustments are necessitated, resulting in a decrease in efficiency. Therefore, in reactive scheduling, the extent to which the rescheduling deviates from the baseline schedule should be minimized. In this study, the principle of minimizing scheduling perturbations was applied, i.e., the smaller the scheduling deviation compared with baseline scheduling, the more stable the system will be. The scheduling deviation was analyzed based on the following two aspects:
1) Wave availability deviation.
The change in wave availability measures the effect on the wave departure mission after reactive scheduling when uncertain disturbances occur:
where \({\text{WA}}_{bs}\) is the wave availability of the baseline schedule, and \({\text{WA}}_{rs}\) is the wave availability after reactive scheduling.
2) Operation deviation loss.
The maintenance time/operation variation caused by the uncertain environment affects the execution of the baseline scheduling scheme. Consequently, the actual maintenance operation time \(d_{ij}^{*}\) differs from the \(d_{ij}\) of the baseline scheduling scheme, and the actual maintenance operation guarantees the start time \({\text{Sm}}_{ij}^{*}\) of the subsequent tasks deviating from \({\text{Sm}}_{ij}\) of the baseline scheduling scheme. The operational deviation loss function is defined accordingly. Let the set of maintenance operations that have not yet started on carrier-based aircraft \(i\) after the uncertainty disturbance be \(J_{i}^{*}\). Subsequently, the loss objective function of the operation deviation is defined as follows:
where \(\omega_{ij}\) is the penalty factor for maintenance operation \(O_{ij}\), which is in fact the cost of the maintenance deviation of the operation. We specify a larger penalty factor if the carrier-based aircraft that can be deployed in a certain wave in the baseline scheduling scheme cannot be deployed in the original wave after a dynamic disturbance. The penalty factor is specified individually for each carrier-based aircraft based on the wave in which the makespan is located; the more advanced the wave, the larger is the penalty factor. A specific value can be specified based on the weight of each wave.
Algorithm for baseline scheduling
Based on the analysis of the characteristics of the MTSPCA mathematical model above, it is discovered that conventional exact solution methods cannot efficiently solve such complex multi-objective optimization problems. The use of heuristic algorithms to solve this problem has been extensively investigated recently. Studies that apply the algorithm to the scheduling and planning of maintenance tasks for carrier-based aircraft are rare, and its application potential to the MTSPCA remains to be investigated.
Among the many heuristic multi-objective optimization algorithms, I_NSGA-II is an efficient multi-objective optimization algorithm with three main improvements associated with the non-dominated sorting genetic algorithm (NSGA-II), as follows:
1.
the use of a non-dominated sorting algorithm;
2.
the use of a crowded-comparison operator for crowding distance calculation;
3.
elitism.
The three improvements above enable NSGA-II to converge to the optimal Pareto front more rapidly [36]. Herein, based on the NSGA-II framework, we propose an I_NSGA-II optimization algorithm that incorporates a new stage of local neighborhood search for elite population coding, which can be used to achieve better problem adaptation and optimization performance by implementing changes in the local neighborhood coding structure such that the search range can be extended directly, and a fall into a local extremum can be avoided. A flowchart of the I_NSGA-II is presented in Fig. 2. Each component of the algorithm is explained in detail in the following section.
Fig. 2
Flowchart of I_NSGA-II for MTSPCA
×
Initialization
Initialization of population
First, the algorithm sets the basic parameters, including the number of times the algorithm population fitness is evaluated, population size, individual selection link, and probability of variation. Next, maintenance guarantee information is input, including the establishment of the objective function, constraints, maintenance scheduling model, and other related parameters. Finally, the population information is initialized, and coding and decoding operations are performed on the population individuals.
Encoding
The encoding strategy affects the effectiveness and efficiency of an algorithmic search. The main coding strategies for solving the RCPSP include activity list coding, random key coding, and priority rule coding [37]. Owing to the priority relationships between operations in the maintenance scheduling process, the combination of operations that do not conform to the scheduling constraints may be obtained in the subsequent crossover and mutation operations via activity list coding and priority rule coding; hence, random key coding based on the operation start time correction to generate individual coding for forward pass scheduling was performed in this study. Individual coding was performed by arranging the start time priority numbers of each carrier-based aircraft to be repaired in the order of operations; for example, \(R_{12}\) represents the priority code for the second maintenance operation of the first carrier-based aircraft. Subsequently, all carrier-based aircraft codes are stitched to form a discrete matrix coding that is \({\text{Nm}} \times \left| {J_{{{\text{Nm}}}} } \right|\) long. All codes were integrated, as shown in Fig. 3. The resulting population coding can avoid the generation of individuals that do not conform to the constraints in the subsequent operations.
Fig. 3
Coding diagram of a single individual
×
Decoding
The decoding operation translates the chromosomal code of an individual to the maintenance process, reveals the scheduling process represented by the individual through decoding, and calculates the objective function value of the population to evaluate the merits of the individual. The RCPSP performs decoding operations through a scheduling generation scheme, which includes a serial scheduling generation scheme (SSGS) and a parallel scheduling generation scheme (PSGS) [38]. Han et al. [39] indicated that the solution space range of the PSGS is smaller than that of the SSGS; therefore, in this study, the SSGS decoding operation was selected. The SSGS obtains an active schedule that cannot be started earlier for an operation without changing the schedule of other operations. Simultaneously, under the constraints of the MTSPCA mathematical model, the maintenance personnel skills of the maintenance tasks are assigned based on the priority rule of balancing the maintenance time. Maintenance equipment/workshops for the maintenance tasks are assigned based on the minimum total processing time remaining in the covering area.
NSGA-II main loop
The pseudocode for the NSGA-II main loop is described in Algorithm 1. This section details the steps involved in the NSGA-II main loop.
×
Non-domination sorting algorithm and crowded-comparison operator
I_NSGA-II inherits the NSGA-II solution framework, which relies on non-domination rank \(i_{{{\text{rank}}}}\) and crowding distance \(i_{{{\text{distance}}}}\) metrics to quantify the quality of genetic operators. Here, \(i_{{{\text{rank}}}}\) represents the non-domination hierarchy property of individual solutions, and \(i_{{{\text{distance}}}}\) the density estimation of solutions around individual population solutions. The non-domination sorting algorithm is used to calculate \(i_{{{\text{rank}}}}\); two solutions, A and B, are regarded as non-dominated if A is better than B in one objective and worse in another [36]. The population \({\text{Np}}\) is stratified by the non-dominated sorting algorithm, and the dominant and non-dominated relationships between each individual are compared successively until all non-dominated individuals are identified. The set of non-dominated individuals obtained at this point is known as the first rank of the non-dominated layer; subsequently, the set of non-dominated individuals is excluded from the next round of comparison of dominance and non-dominance relationships until all individuals in the population have been stratified. The crowding distance is used to calculate the \(i_{{{\text{distance}}}}\) of the individual solutions. The calculation of the crowding distance ensures the diversity of the population, and the calculation of the crowding distance requires population sorting in the ascending order of the magnitude of each objective function (i.e., if the first rank of the non-dominated layer is obtained, then it is sorted based on the magnitude of the objective function; subsequently, the distance is calculated). In particular, for each objective function, the boundary solution (the solution with the highest and lowest values) is specified as a value of infinite distance. The crowding distance of the \(i{\text{th}}\) solution is the average distance between the two closest points along each objective in front of the corresponding point. The crowding distance is calculated as shown in Fig. 4. The calculation formula is as follows:
$$ i_{{{\text{distance}}}} = \mathop \sum \limits_{k = 1}^{m} \frac{{f_{k} (i + 1) - f_{k} (i - 1)}}{{f_{k}^{\max } - f_{k}^{\min } }},2 \le i \le n - 1, $$
(18)
where \(m\) is the number of objective functions; \(f_{k} (i)\) is the value of the \(k{\text{th}}\) objective function of the \(i{\text{th}}\) solution; \(f_{k}^{\max }\) and \(f_{k}^{\min }\) are the maximum and minimum values of the first objective function, respectively.
Fig. 4
Crowding distance calculation
×
After the non-dominated sorting and crowding distance calculations are performed, each individual is compared, and the crowded-comparison operator \(\prec_{n}\) [40] is defined to derive the offspring populations as follows:
where the non-dominated rank in which individual \(i\) is located is better than that of individual \(j\), or individual \(i\) and \(j\) are located in the same non-dominated rank, but the crowding distance of individual \(i\) is greater than that of \(j\); hence, individual \(i\) wins and proceeds to the next operation.
Selection, crossover, and mutation
Tournament selection is used for the selection operation: two individuals are randomly selected at a time, the winning decision is determined using the comparison mechanism of the crowded-comparison operator \(\prec_{n}\), and the non-inferior parent individuals of size \(0.5 \, {\text{Np}}\) are selected for the next crossover operation.
The crossover operation involves an improved shuffle crossover strategy, which generates two row vectors containing two random permutations of the integers from one to \(0.5 \, {\text{Np}}\) without repeating elements, where two row vectors are paired individually to form \(0.5 \, {\text{Np}}\) arrays. Two parents of the crossover operation are selected according to \(0.5 \, {\text{Np}}\) arrays, and a crossover site \({\text{pos}}\) is selected randomly. The chromosome codes of the two parents are broken at \({\text{pos}}\), and crossover integration is performed to generate two new offspring individuals. Traversing \(0.5 \, {\text{Np}}\) arrays of parents will generate \( \, {\text{Np}}\) offspring populations.
The mutation operation mutates the random key coding based on the maintenance operation start time correction for the offspring with a set mutation probability. The mutation strategy is set to reuse the random values of the operation start time at random mutation points to maintain the diversity of the population.
Elitism
Elitism is used to obtain an offspring population \(Q_{t}\) from the parent population \(P_{t}\) after selection, crossover, and mutation genetic operations. After combining \(P_{t}\) and \(Q_{t}\), a population \(R_{t}\) with a population size of \(2 \, {\text{Np}}\) is obtained. Subsequently, elitism is implemented toward group population \(R_{t}\): all individuals are categorized into non-dominated ranks via non-dominated sorting. The individual solutions of the dominant rank are retained for the next generation, and the total number of individuals is accumulated based on the rank order. Until a certain rank is reached, where the number of individual solutions exceeds \({\text{Np}}\), some individual solutions exceeding \({\text{Np}}\) will be disregarded, and the remaining individuals will form a new parent population, \(P_{t + 1}\). The elements of the NSGA-II are shown in Fig. 5.
Fig. 5
Elitism of NSGA-II
×
Local neighborhood search
The local neighborhood search activates the following three low-level heuristics neighborhood search for population update based on an equal probability alternative:
(1) Swap the local neighborhood.
The structure is constructed by randomly selecting a maintenance operation, selecting the maximum value of the start time of its preceding operation as the lower bound, selecting the minimum value of the start time of the immediately following operation as the upper bound to construct a free time window, randomly selecting another operation, and performing the swap operation of the start time codes of the two operations if the constraints of the time window are satisfied. The pseudocode of the swap in the local neighborhood is described in Algorithm 2.
×
(2) Insert the local neighborhood.
The structure is constructed by randomly selecting a maintenance operation with the maximum calculated start time as the lower bound and the minimum start time immediately after the operation as the upper bound, constructing a free time window, selecting the list of operations that satisfy the time window, randomly selecting an operation code to be scheduled, and then inserting it into the time window interval. The pseudocode for inserting the operation code to the local neighborhood is described in Algorithm 3.
×
(3) Inverse local neighborhoods.
The structure is constructed by randomly selecting a certain time \(t\) in the maintenance process and screening out \(num\) operations with a start time at approximately time \(t\) with a step size of 1 to form a set of operations which waiting for inversion operations. Subsequently, the codes are arranged in the descending order of the start time, and the chromosome codes are reassigned. The pseudocode of the inverse local neighborhood is described in Algorithm 4.
×
Baseline scheduling and reactive scheduling methods
Baseline scheduling method
Baseline scheduling generates a reference scheduling scheme in a deterministic environment, uses a heuristic algorithm with \(\max {\text{WA}}\) and \(\min {\text{LBM}}\) as the objective, and identifies the earliest start time for all maintenance task processes using a forward-pass scheduling method. These times form an early start schedule for the maintenance personnel and equipment/workshops. A Gantt chart can be used to represent the schedule.
Reactive scheduling method
The reactive scheduling method is used for rescheduling to generate a rescheduling scheme with the expected optimization objectives. If uncertainty disturbances occur during the baseline scheduling process, the baseline schedule must be corrected and re-optimized, and the baseline scheme is adjusted based on the reactive scheduling. Reactive scheduling methods can be broadly classified into simple random rescheduling (SR), time-priority rule rescheduling (TR), and right-shift (RS). SR implies that after each interruption timepoint, several feasible scheduling schemes are randomly generated, and the scheme with the optimal objective is selected as the new reactive scheduling scheme. TR implies that after each interruption timepoint, the operations that have not yet started are sorted in the ascending order based on the process time, resulting in a priority list. Subsequently, a new reactive scheduling is obtained via decoding. The RS delays the entire schedule based on the duration of interruption. In a graphical representation, the effect is depicted by pushing the schedule forward in time or shifting it to the right by adding a fixed time increment to each operation of the current schedule. Herein, we propose two reactive scheduling methods for uncertainty disturbances: CR and PR. The two scheduling methods have their own advantages and disadvantages for uncertain environments, and the performance indexes of their applicable scenarios are compared comprehensively in the following sections.
CR
The reactive scheduling method retains the active schedule characteristics of baseline scheduling, and rescheduling after a disturbance can result in the rational deployment of maintenance personnel and equipment/workshops. The specific steps are as follows: Based on the baseline scheduling scheme, the baseline scheduling breakdown time \(t_{bd}\) is first input; the occupied resource status is initialized, and the set of operations that have been and are being scheduled, \(F_{g}\) (including all maintenance operations with scheduled start times and resource allocation), is recorded. Second, the set of operations to be selected, \(D_{g}\) (all immediately preceding operations belong to the set of candidate maintenance operations in \(F_{g}\)), is initialized. Next, operation \((i,j)\) is selected from set \(D_{g}\), advanced with a step size of 1 from \(t_{bd}\); furthermore, the start and end times of \((i,j)\) are specified. If the resource occupation status satisfies the demand of \((i,j)\), and assign maintenance personnel and equipment/workshop to \((i,j)\); Finally, \((i,j)\) is added to \(F_{g}\), and the scheduling schedule is expanded continuously to complete the scheduling assignment of the entire maintenance task. The procedure for CR is shown in Fig. 6.
Fig. 6
Procedure for complete rescheduling
×
PR
The purpose of PR is to retain the baseline scheduling scheme as much as possible. The start time for maintenance operations is recalculated with uncertain disturbances to maximize the reservation of maintenance personnel and equipment/workshop planning in baseline scheduling. Hence, the overall stability of the scheduling scheme can be maintained, and scheduling confusion caused by large-scale task allocation changes can be avoided. The specific steps are as follows: before PR is commenced, the maintenance personnel equipment/workshop is converted into logical constraints between operations, and then logical constraints are added to the mainline of the PSGS progress plans to ensure that maintenance processes that satisfy the constraints begin the soonest possible. Based on the time advancement process, while satisfying the resource constraints, the assessment of the baseline scheduling logic constraints is added. Hence, the active schedule characteristics of baseline scheduling are not degraded to non-delay schedule characteristics, while the baseline scheduling constraints are retained. This ensures that the scheduling scheme adheres to the framework of the baseline schedule in general.
Maintenance task case analysis
Maintenance task case generation
Based on the Kuznetsov ship-based maintenance resource environment and the requirements of actual wave missions, three sets of pre-sortie maintenance task cases were established. The performance of the algorithms was compared based on the evaluation index of the generated baseline scheduling scheme. The optimal scheduling results under the comparison conditions were obtained and regarded as the baseline scheduling scheme for maintenance missions, which serves as a benchmark reference for subsequent reactive scheduling affected by uncertainty disturbances.
The maintenance task cases were classified into three groups of 10, 13, and 16 carrier-based aircraft based on small, medium, and large-scale maintenance sorties before the start time of the wave. The subsequent wave was set to three waves, the wave time interval was 110 min, the weight of each wave was \(v_{w} = \left[ {0.5,0.3,0.2} \right]\), and the three groups of cases were set by combining two maintenance items: airborne equipment and airframe structure troubleshooting maintenance, and scheduled maintenance.
An AON-directed network diagram is used to describe the precedence relationships of maintenance task operations. For fault repair tasks, the maintenance operations, i.e., fault location, fault repair, and re-inspection, are associated serially with each other. For scheduled maintenance tasks, the maintenance operations exhibit networked precedence relationships, i.e., the set of immediately preceding operations for any process is not unique. As shown in Fig. 7, operations 1 and 20 represent the virtual start and end of the process, respectively. The virtual operations do not require any guaranteed resources, and their maintenance time is zero. Its role is to integrate all maintenance operations, and 18 actual operations are required for scheduled maintenance.
Fig. 7
General AON network for single carrier-based aircraft
×
Combined with the actual demands of the maintenance task cases, four types of maintenance skills were considered: special equipment, avionics, ordnance, and machinery for the configuration of the maintenance personnel, i.e., \({\text{Kc}} = \left\{ {1,2,3,4} \right\}\), with numbers [5, 6, 4, 10], i.e., \({\text{Lp}} = \left\{ {1,2, \ldots ,25} \right\}\). The maintenance skills were compatible, the special equipment and avionics skills were compatible with each other, the ordnance and machinery skills were compatible with each other, and the number of compatible persons was the first four persons. The default maintenance operation requires one person with maintenance specialty; if more maintenance personnel are required, then the number of persons will be indicated in parentheses. In the maintenance tasks set in the cases, six modes were considered: mechanical failure; avionics system failure; special equipment system failure; 25 h, 50 h, and 100 h scheduled maintenance. The maintenance and workshop categories include power supply station, aviation machine repair workshop, oil and fluid inspection workshop, ordnance maintenance workshop, and electronic equipment maintenance workshop, i.e., \({\text{Ke}} = \{ 1,2,3,4,5\}\). The workspace constraint only considers the cockpit space, which is expressed by \({\text{Ks}} = 1\), and the number of persons who can operate in parallel is only one. The correspondence among carrier-based aircraft, maintenance parking spots, and time for tethering completion is shown in Table 2. The time and resource requirements for the aircraft maintenance process are shown in Table 3.
Table 2
Correspondence among carrier-based aircraft, maintenance parking spots, and time for tethering completion
Maintenance tasks
Maintenance parking spots number
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Carrier-based aircraft number; tethering completion time (min)
Case 1
I;1
N;0
O;8
J;0
B;9
A;4
C;0
E;2
K;3
P;15
–
–
–
–
–
–
Case 2
I;1
N;0
O;8
J;0
B;9
A;4
C;0
E;2
K;3
P;15
H;16
L;7
F;13
–
–
–
Case 3
I;1
N;0
O;8
J;0
B;9
A;4
C;0
E;2
K;3
P;15
H;16
L;7
F;13
M;119
D;123
G;5
Table 3
Duration and requirements of maintenance operations for carrier-based aircraft
Carrier-based aircraft number
Maintenance modes
Operation number
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Maintenance time of different maintenance modes (min)
C,G,I,O
M1
0
0
0
0
24
0
0
0
0
44
0
0
0
0
0
12
0
0
0
0
B,K,N
M2
0
0
0
0
19
0
0
0
0
53
0
0
0
0
0
22
0
0
0
0
A,J,M
M3
0
0
0
0
26
0
0
0
0
47
0
0
0
0
0
17
0
0
0
0
E,L,P
M4
0
18
30
8
6
8
10
6
8
15
20
15
16
18
13
3
10
8
6
0
D,F
M5
0
25
45
8
8
8
12
6
8
30
30
26
26
28
16
8
18
10
10
0
H
M6
0
34
66
10
12
10
15
10
12
48
40
45
33
44
46
16
26
18
14
0
Maintenance resource requirements
\(Kc\)
–
4
4(2)
3
1,2,3,4
2
2
1
1
1,2,4
4
4(2)
2(2)
1(2)
3(2)
1,2,4
2
1
3
–
\(Ke\)
–
–
–
–
1
–
1
–
1
2,5
3
3
5
5
4
1
1
1
1
–
\(Ks\)
–
–
–
–
1
–
1
–
1
–
–
–
–
–
–
1
1
1
1
–
Three wave availability calculation functions were specified based on the importance of the waves, as shown in Fig. 8. Each of the three wave availability calculation functions is introduced in Eq. 14 based on the wave used. A decrease in the importance of the wave increases the acceptance of the makespan overruns.
Fig. 8
Wave availability calculation function
×
Baseline scheduling scheme generation
Performance comparison of I_NSGA-II and population-based metaheuristic algorithms
To verify the solution performance of the I_NSGA-II proposed herein for the solving MTSPCA, population-based metaheuristic algorithms that are typically to solve the RCPSP were selected, as follows: the differential evolution algorithm (DE), genetic algorithm (GA), and teaching–learning-based optimization (TLBO) for the performance comparison of algorithms generated by baseline scheduling. The parameters of each algorithm were set as follows: for I_NSGA-II, population size \({\text{Np}} = 60\), tournament selection population size \({\text{tour}} = 2\), and probability of variation \({\text{Pm}} = 0.005\); for TLBO, class student population size \({\text{Np}} = 30\), elite teacher population size \({\text{Nt}} = 5\); for GA, population size \({\text{Np}} = 30\), crossover probability \({\text{Pc}} = 0.5\), and probability of variation \({\text{Pm}} = 0.005\); for DE, population size \({\text{Np}} = 30\), crossover probability \({\text{cr}} = 0.1\), and probability of variation \(F = 0.1\). The adaptation function of the population-based metaheuristic comparison algorithm above was set as \(f = \left( {1 - {\text{WA}}} \right) + \alpha {\text{LBM}}\), where the weight coefficient of variance of maintenance personnel loads was \(\alpha = 10^{ - 6}\). In the algorithms above, the number of evaluations \(Q_{\max } = 5000\) was set to at the end of the iteration.
The case simulation algorithms were programmed using MATLAB 2020 (a) software and executed on a personal computer (Intel(R) Core (TM) i5-8265U CPU@ 1.60 GHz). Each algorithm was executed independently 30 times, and the results of the optimization objectives are listed in Table 4. Bold values in the table mark the better solution for the same set of comparison experiments, as do the other tables. A boxplot of the repeated independent operation results of \({\text{WA}}\) is shown in Fig. 9.
Table 4
Optimal solution results of different algorithms
\(n\)
Algorithms
\({\text{WA}}\)
\({\text{LBM}}\)
\({\text{ROBU}}\)
Wave completion of carrier-based aircraft
10
I_NSGA-II
0.8500
129.1616
830
[1,2,3,5,7,9,10] [4,6,8][–]
TLBO
0.7529
264.1216
1198
[1,3,5,9,10] [2,6,7] [4,8]
GA
0.8231
133.0816
1059
[1,2,5,7,9,10] [3,4,8] [6]
DE
0.7623
185.0816
987
[1,2,5,7,9] [3,4,6,10] [8]
13
I_NSGA-II
0.7694
22.2784
996
[1,2,3,7,9,10,11][4,5,6,8,12,13][–]
TLBO
0.7224
31.3984
1263
[2,3,7,9,10,11] [1,4,5,12,13] [6,8]
GA
0.7472
89.9584
1034
[1,2,3,7,9,11,13] [4,5,8,10,12] [6]
DE
0.7056
27.7184
1087
[1,2,7,9,10,11] [3,4,5,12,13] [6,8]
16
I_NSGA-II
0.7077
63.3216
930
[1,2,3,7,9,11,13][4,5,6,10,12,14,15,16][8]
TLBO
0.6622
122.0416
918
[2,3,7,10,13,16] [1,5,6,9,11,12,14,15] [4,8]
GA
0.6838
176.6816
1016
[1,2,3,7,9,10,13] [5,6,11,12,14,15,16] [4,8]
DE
0.6568
124.9216
1012
[1,3,7,9,10,11] [2,5,6,8,13,14,15,16] [4,12]
Fig. 9
Results of WA for different algorithms
Fig. 10
Pareto front obtained using I_NSGA-II
×
×
As shown in Table 4, I_NSGA-II performed better in terms of evaluation indexes \({\text{WA}}\) and \({\text{LBM}}\), whereas it performed worse in terms of the \({\text{ROBU}}\). Considering that the \({\text{ROBU}}\) defined herein uses the sum of the interval times of maintenance personnel executing operations as the calculation method, it is clear that a more lenient interval time enables more task conflicts and interruptions caused by baseline scheduling in an uncertain environment to be incorporated. However, the addition of excessive time buffers will reduce the efficiency of the baseline scheduling scheme, which contradicts the optimization objective of maximizing wave availability and incurs an additional resource occupation cost (a higher robustness cost); hence, the wave availability will decrease. Meanwhile, in actual carrier-based aircraft maintenance tasks, maximizing the number of available aircraft in the waves is the highest priority in scheduling. Therefore, maximizing \({\text{WA}}\) was the primary optimization objective, and a box-line diagram analysis was performed.
As shown by the box plot in Fig. 9, in terms of the key objective \({\text{WA}}\) on the MTSPCA, I_NSGA-II achieved the highest median, 25th percentile, and maximum value in all three sets of cases compared with the three classical metaheuristic algorithms; furthermore, it demonstrated high stability.
The analysis above shows that I_NSGA-II is superior to other mainstream algorithms; therefore, the scheduling schedule obtained by I_NSGA-II was used as the baseline scheduling. As shown in Fig. 10, the Pareto front was obtained using I_NSGA-II.
Baseline scheduling scheme
Figures 11, 12, and 13 show the Gantt charts of the baseline scheduling scheme for maintenance personnel and equipment/workshops using the I_NSGA-II algorithm. It is noteworthy that in the personnel scheduling scheme, the vertical coordinate “Lp-l” represents the \(l{\text{th}}\) maintenance personnel, which is numbered based on the skills for maintaining specific equipment, avionics, ordnance, and machinery, whereas \(i - j\) represents the maintenance operation \(O_{ij}\). In the equipment/workshop scheduling scheme, the vertical coordinate \(Le_{k}^{l}\) represents the \(l{\text{th}}\) power supply station only when \(k = 1\). For a uniform representation, the remainder of the chart represents the \(k - 1\) maintenance workshop when \(k > 1\), and \(Le_{k}^{l}\) indicates the \(k - 1\) parallel maintenance operation line of the \(l{\text{th}}\) maintenance workshop.
Fig. 11
Baseline schedule for 10 carrier-based aircraft
Fig. 12
Baseline schedule for 13 carrier-based aircraft
Fig. 13
Baseline schedule for 16 carrier-based aircraft
×
×
×
Reactive scheduling generation
Delay event disturbance of maintenance operation
In an uncertain environment, to counteract disturbances such as operation delays, resource shortages, and personnel transfers that occur during scheduling, a baseline schedule that assumes a deterministic environment is developed as the expected start time of the process during task execution; in fact, it is typically proposed to provide an initial reference for the scheduling process. As task scheduling progresses, uncertain disturbances may result in an unreasonable or even invalid baseline scheduling scheme; therefore, the actual scheduling scheme must be rescheduled based on the baseline schedule to correct and optimize the effect of the disturbances. This process is known as the reactive scheduling scheme generation.
In fact, considering the objective, efficiency, and cost of scheduling, the decision maker can quantify the decision support based on the perturbation factors and adopt the reactive scheduling method, which is more practical than proactive scheduling. By promptly adjusting the baseline scheme and providing the best rescheduling solution in real time, the task is guaranteed to proceed seamlessly.
In this section, we first consider the most typical operational delay events in the actual maintenance process to analyze reactive scheduling decisions and design three groups of operational delay events based on the time length.
I. Short delay event: A 5 min delay occurs at 65 min of baseline scheduling for the 11th operation of the 4th carrier-based aircraft in maintenance mode M5.
II. Moderate delay event: A 10 min delay occurs at 20 min of baseline scheduling for the 3rd operation of the 5th carrier-based aircraft in maintenance mode M4.
III. Longer delay event: A 13 min delay occurs at 60 min of baseline scheduling for the 2nd operation of the 2nd carrier-based aircraft in maintenance mode M2.
Three sets of delay events were implemented in the process of the three sets of maintenance task cases. To verify the advantages of the proposed CR and PR methods for the reactive adjustment of baseline scheduling as compared with methods used in previous studies, we selected SR, TR, and RS introduced in “Reactive scheduling method”, and used delay event II as the case analysis to compare three reactivity evaluation indexes of change_WA, wave_LOSS, and delta_Cmax based on three fleet sizes. Delta _Cmax is the difference between the reactive scheduling and baseline scheduling. The comparison results are shown in Fig. 14.
Fig. 14
Data comparison of different reactivity methods
Fig. 15
Complete rescheduling of delay event I for 10 carrier-based aircraft
Fig. 16
Complete rescheduling of delay event II for 13 carrier-based aircraft
Fig. 17
Partial rescheduling of delay event III for 16 carrier-based aircraft
×
×
×
×
As shown in Fig. 14, the effectiveness of the proposed CR and PR reactive scheduling methods improved compared with the previous three reactive methods, particularly for small fleet sizes The next section presents a comparative analysis of the advantages and disadvantages of the CR and PR methods via more case analyses combined with the reactivity evaluation indexes.
The following conclusions were obtained by analyzing the results shown in Table 5:
Table 5
Comparison results of two rescheduling methods
Type
\({\text{change\_WA}}\)
\({\text{wave\_LOSS}}\)
\({\text{ROBU}}\)
Wave completion of carrier-based aircraft
I
10
Complete
6.9368E−11
18.6
2130
[1,2,3,5,7,9,10][4,6,8][–]
Partial
2.73E−10
7.5
2108
[1,2,3,5,7,9,10][4,6,8][–]
13
Complete
2.1219E−07
12.9
1765
[1,2,3,7,9,10,11][4,5,6,8,12,13][–]
Partial
6.45E−07
27
1769
[1,2,3,7,9,10,11][4,5,6,8,12,13][–]
16
Complete
0.0444
389.9
2714
[1,2,3,7,9,13] [4,5,6,10,11,12,15,16] [8,14]
Partial
0
2.7
2677
[1,2,3,7,9,11,13][4,5,6,10,12,14,15,16][8]
II
10
Complete
2.7308E−10
26.4
2121
[1,2,3,5,7,9,10][4,6,8][–]
Partial
2.06E−05
62.6
2263
[1,2,3,5,7,9,10][4,6,8][–]
13
Complete
0.0152
120
2009
[1,2,3,7,9,10,11] [4,12,13] [5,6,8]
Partial
0.0229
114.9
1869
[1,2,3,9,10,11][4,5,7,12,13][6,8]
16
Complete
0.0319
654.6
2687
[1,2,3,7,9,13] [4,5,6,10,11,12,14,15,16] [8]
Partial
0.0074
48.2
2662
[1,2,3,7,9,11,13][4,5,6,10,12,14,15][8,16]
III
10
Complete
6.77E−06
28
2019
[1,2,3,5,7,9,10][4,6,8][–]
Partial
2.81E−05
45.4
2003
[1,2,3,5,7,9,10][4,6,8][–]
13
Complete
0.0061
38.5
1874
[1,2,3,7,9,10,11][4,5,6,12,13][8]
Partial
0.0061
59.8
1864
[1,2,3,7,9,10,11][4,5,6,12,13][8]
16
Complete
0.0561
503.2
2516
[1,2,3,7,9,13] [4,5,10,11,12,15,16] [6,8,14]
Partial
0.0138
117.5
2661
[1,2,3,7,9,11,13][4,5,10,12,15,16][6,8,14]
1) Comparing the results of reactive scheduling schemes under different maintenance sorties, under the same rescheduling method and delay event conditions, \({\text{change\_WA}}\) in general indicated a positive correlation, in that the value increased correspondingly with the sortie size and maintenance pressure; ROBU did not exhibit clear regular characteristics; \({\text{wave\_LOSS}}\) indicated a positive correlation with the increase in the sortie size when it was fixed as CR but did not exhibit clear regular features when it was fixed as PR. Meanwhile, the following were observed upon further analysis: under the delay event I condition of the CR method, the \({\text{change}}\_{\text{WA}}\) values of the three groups of maintenance sorties indicated significant and similar changes in the order of magnitude; under the delay event II and III conditions, \({\text{change}}\_{\text{WA}}\) in the small and medium maintenance sorties increased significantly, whereas the medium and large maintenance sorties saturated; \({\text{wave\_LOSS}}\) exhibited a similar trend to \({\text{change\_WA}}\) during CR. This might have occurred, because the CR method is more effective in optimizing low and medium maintenance sorties (Fig. 15). The difference between the wave availabilities of reactive scheduling and baseline scheduling was slight, and the operation deviation loss was controlled more effectively.
2) Comparing the results of the reactive scheduling scheme under different delay event conditions, under the same rescheduling method and maintenance sortie size, a positive correlation was observed, in that the value of reactive scheduling \({\text{change\_WA}}\) increased with the process delay time and gradually entered the optimization bottleneck; the value of \({\text{change\_WA}}\) was high, which triggered a decrease in the wave availability after reactive scheduling; the overall change of \({\text{ROBU}}\) was not insignificant; the \({\text{change\_WA}}\) and \({\text{wave\_LOSS}}\) in event II of 13 aircraft conditions showed the anomalous phenomenon of first ascending and then descending. This might be due to the fact that the maintenance sortie scale of 13 aircraft baseline scheduling makespans \(C_{{{\text{max}}}} = 218\), near the second wave time of 220 min, delay event II causes the corresponding carrier-based aircraft cannot be completed before the third wave, thereby causing a significant change in \({\text{change\_WA}}\); in other words, if the carrier aircraft is not completed within the baseline scheduling scheme wave, then the value of \({\text{change\_WA}}\) changes significantly, which implies that the number of aircraft completed in the wave has changed, resulting in a significant loss in operation deviation (Fig. 16).
3) Comparing the results of the reactive scheduling scheme under different methods, under the same delay event, a correlation was observed between different rescheduling methods and maintenance sortie sizes. For the small and medium maintenance sorties, the CR scheme was better than the PR scheme, but the difference between two rescheduling methods \({\text{change\_WA}}\) and \({\text{wave\_LOSS}}\) remained slight and were of the same order of magnitude. When the maintenance sorties reached a large scale, both \({\text{change\_WA}}\) and \({\text{wave\_LOSS}}\) indicated high values, and a comparison between the two rescheduling methods revealed that the PR method afforded better control over \({\text{change\_WA}}\) and \({\text{wave\_LOSS}}\), where \({\text{wave\_LOSS}}\) indicated a more significant optimization effect. By contrast, the performance of the CR method deteriorated. This is attributable to the few operations in the small and medium maintenance sorties, the short maintenance makespan, and the large interval time between scheduling operations. However, when the large maintenance sorties are reached, using the CR method will significantly modify the baseline scheduling (Fig. 17). When numerous operations are involved, the operation deviation loss during the start/end time change will be significant. PR is used to absorb disturbances on a small scale to obtain a better optimization effect.
In summary, it is concluded that in the cases investigated in this study, all three sets of operation delay events using CR performed better for small and medium maintenance sorties; by contrast, using PR yielded better schemes on large maintenance sorties.
Maintenance personnel transfer disturbance
Resource shortage is a typical uncertainty disturbance in an uncertain environment. Maintenance personnel are the direct carriers of the maintenance skills required for maintenance operations. Performing personnel transfer when maintenance is conducted can significantly affect the baseline schedule. In this study, a disturbance event was designed for small and medium maintenance sorties, and random maintenance personnel were notified by the decision maker 10 min after the start of scheduling and then transferred from the maintenance task after they have completed the ongoing maintenance operation. Based on the conclusions presented in the previous section, a reactive scheduling scheme was generated using CR for the personnel transfer disturbance event. In addition, \({\text{change\_WA}}\) and \({\text{wave\_LOSS}}\) after reactive scheduling were evaluated for the following two cases:
I. Effect of length of maintenance time of transferred maintenance personnel on reactive scheduling.
II. Effect of type of maintenance skills of transferred maintenance personnel on reactive scheduling.
First, we consider the effect of the length of the maintenance time of the transferred maintenance personnel in baseline scheduling on reactive scheduling. One may assume that the longer the maintenance time in the baseline scheduling, the higher are the values of \({\text{change\_WA}}\) and \({\text{wave\_LOSS}}\) after reactive scheduling, and the worse are the reactive scheduling results. For example, Fig. 18 shows a bar chart of the maintenance time for maintenance personnel in the baseline scheduling for small and medium maintenance sorties. Meanwhile, Figs. 19 and 20 show the correlation between the maintenance time and \({\text{change\_WA}}\) (\({\text{wave\_LOSS}}\)) evaluation indexes.
Fig. 18
Bar chart of maintenance time for maintenance personnel in baseline scheduling
Fig. 19
Correlation between maintenance time and evaluation indexes for 10 carrier-based aircraft
Fig. 20
Correlation between maintenance time and evaluation indexes for 13 carrier-based aircraft
×
×
×
As shown in Figs. 19 and 20, the length of maintenance time and \({\text{change\_WA}}\) (\({\text{wave\_LOSS}}\)) did not exhibit any clear correlation, and a situation occurred where the maintenance times were similar, but the corresponding \({\text{change\_WA}}\) and \({\text{wave\_LOSS}}\) values were significantly different. This is attributed to CR, in which the remaining operations of the transferred personnel are split, reorganized, and integrated into the maintenance processes of the remaining personnel who have the same type of maintenance skills as the transferred personnel, thereby eliminating the possibility of subpar evaluations after reactive scheduling owing to the significant proportion of the transferred personnel’s maintenance time in the baseline schedule. Next, we analyze the effect of the maintenance skill classification of the maintenance personnel transferred. The analysis above shows that the remaining maintenance personnel performed the remaining operations of the transferred personnel in the baseline schedule with the same classification of skills. The classification of the skills of the transferred maintenance personnel is associated with the \({\text{change\_WA}}\) and \({\text{wave\_LOSS}}\) evaluation indexes.
The correlation between the transferred maintenance personnel (classification of skills) and the evaluation indicators is shown in Figs. 21 and 22.
Fig. 21
Correlation between transferred maintenance personnel (classification of skills) and evaluation indexes for 10 carrier-based aircraft
Fig. 22
Correlation between transferred maintenance personnel (classification of skills) and evaluation indexes for 13 carrier-based aircraft
×
×
As shown in Figs. 21 and 22 in the case involving the small maintenance sortie size, the machinery maintenance skill imposed a more significant effect on \({\text{change\_WA}}\) and \({\text{wave\_LOSS}}\). This may be because the maintenance operations of the required machinery skills were concentrated in the scheduled maintenance mode, which resulted in more maintenance operations and a longer maintenance time. In addition, the 21st and 22nd maintenance personnel with machinery skills exhibited greater similarity in terms of maintenance operations, and follow-up operations, where personnel were transferred were fewer; therefore, the effect of personnel transfer on \({\text{change\_WA}}\) and \({\text{wave\_LOSS}}\) was less significant than that of other personnel with machinery skills. In the medium maintenance sortie, the transfer of personnel with ordnance skills significantly affected the evaluation index of reactive scheduling. A possible reason is that, as the sortie size of maintenance increases, the disadvantage of personnel reduction with ordnance skills becomes more apparent. Only three personnel with ordnance skills satisfied the requirements of the maintenance tasks after personnel transfer. The larger maintenance pressure resulted in a more significant change in the wave availability and operational deviation loss. However, in the initial maintenance task planning, one may consider to increase the number of maintenance personnel with ordnance maintenance skills to increase the robustness of the baseline schedule.
In summary, in the cases investigated in this study, the effect of the length of maintenance time on reactive scheduling can be eliminated using CR for small and medium maintenance sorties, and the effect of the maintenance skill classification of the transferred maintenance personnel on reactive scheduling can be predicted based of the type of aircraft maintenance modes in the maintenance task. For cases involving more maintenance operations and fewer personnel with corresponding maintenance skills, feedback can be provided after the prediction to enhance the scheduling robustness (Fig. 23).
Fig. 23
Complete rescheduling of transferred No.1 maintenance personnel for 10 carrier-based aircraft
×
Conclusions and future studies
In this study, we investigated the MTSPCA. After performing a literature review, we discovered that investigations pertaining to the MTSPCA in China and abroad are insufficient owing to the complex constraints imposed in certain research fields. Hence, we developed a comprehensive mathematical model for the MTSPCA to maximize the wave availability and minimize the variance of the maintenance personnel load, where the constraints were fully integrated.
For the mathematical model, the algorithm performance was improved based on NSGA-II by implementing changes in the local neighborhood structure to directly extend the search range and avoid falling into local extremes, thereby improving problem adaptation and optimization performance. The results showed that I_NSGA-II afforded a better optimization effect than the other advanced algorithms. The baseline scheduling scheme of the output maintenance personnel and equipment/workshop was reasonable and efficient; hence, it provides guiding significance in a deterministic environment.
For the actual scheduling uncertain environment, we proposed a CR method that reschedules maintenance personnel and resources while preserving the active schedule characteristics of baseline scheduling, as well as a PR method that uses the PSGS generation mechanism and incorporates the logical constraints of baseline scheduling. Results from the maintenance task case show that in operation delay disturbance events, CR is applicable to small and medium maintenance sorties, whereas PR is applicable to large maintenance sorties. In the cases involving small and medium maintenance sorties, the effect of the length of maintenance time of the transferred maintenance personnel can be eliminated using CR during reactive scheduling, and the effect of maintenance personnel maintenance skill classification on reactive scheduling can be predicted in advance with feedback based on the results.
In the future, an improved mathematical model for the MTSPCA should be designed. For example, the inclusion of maintenance personnel’s moving time for different aircrafts, the rescheduling decision time, and other simplified components of the model presented herein should be considered. In addition, the adaptive proactive–reactive scheduling method with deep reinforcement learning can be used to solve dynamic disturbances from feedback in an uncertain environment.
Acknowledgements
The authors highly appreciate the valuable comments provided by the reviewers, whose comments will greatly contribute to the improvement of the paper.
Declarations
Conflict of interest
All authors certify that they have no affiliations with or involvement in any organization or entity with any financial interest or non-financial interest in the subject matter or materials discussed in this manuscript.
Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
