Modifying lines-of-flight in the planning process for improved maintenance robustness

As a part of their planning process, airlines construct lines-of-flight (LOFs ) - daily repeating sequences of flights, each of which will be flown by a single aircraft. In the week leading up to the actual day-of-operations, these LOFs are then assigned to specific aircraft (tails), forming multi-day aircraft routings that in turn enable the scheduling of routine maintenance checks. Operational disruptions, however, can lead to deviations from these routings, which in turn disrupt the maintenance plan. The goal of our research is to improve the construction of LOFs so as to increase the likelihood of being able to recover from maintenance disruptions without costly over-the-day aircraft swaps. We present a new metric, maintenance reachability (MR), which measures the robustness of a planned set of LOFs, and develop a mathematical programming approach to improving the MR of a given set of LOFs. We provide computational results based on data from a major U.S. carrier demonstrating that significant improvements in MR can be achieved with only a small number of changes to the original set of LOFs. Finally, we conclude by showing that even under imperfect input data, MR can be improved relative to a planned set of LOFs.     

Integrated production scheduling and maintenance policy for robustness in a single machine

This paper addresses the problem of finding robust production and maintenance schedules for a single machine with failure uncertainty. Both production and maintenance activities occupy the machine׳s capacity, while production depletes the machine׳s reliability and maintenance restores its reliability. Thus, we propose a proactive joint model which simultaneously determines the production scheduling and maintenance policy to optimize the robustness of schedules. Then, a three-Phase heuristic algorithm is devised to solve the mathematic model. Computational results indicate that the performance of solution can be significantly improved using our algorithm compared with the solutions by the traditional way. Furthermore, the balance of quality robustness and solution robustness and the impact of jobs׳ due dates are explored in detail.     

An integrated scenario-based approach for robust aircraft routing,crew pairing and re-timing

For reasons of tractability, the airline scheduling problem has traditionally been sequentially decomposed into various stages (e.g. schedule generation, fleet assignment, aircraft routing, and crew pairing), with the decisions from one stage imposed upon the decision-making process in subsequent stages. Whilst this approach greatly simplifies the solution process, it unfortunately fails to capture many dependencies between the various stages, most notably between those of aircraft routing and crew pairing, and how these dependencies affect the propagation of delays through the flight network. In Dunbar et al. (2012) [9] we introduced a new algorithm to accurately calculate and minimize the cost of propagated delay, in a framework that integrates aircraft routing and crew pairing. In this paper we extend the approach of Dunbar et al. (2012) [9] by proposing two new algorithms that achieve further improvements in delay propagation reduction via the incorporation of stochastic delay information. We additionally propose a heuristic, used in conjunction with these two approaches, capable of re-timing an incumbent aircraft and crew schedule to further minimize the cost of delay propagation. These algorithms provide promising results when applied to a real-world airline network and motivate our final integrated aircraft routing, crew pairing and re-timing approach which provides a substantially significant reduction in delay propagation.     

A robust approach for the single machine scheduling problem

This paper describes a robust approach for the single machine scheduling problem 1|r _i |L _max. The method is said to be robust since it characterizes a large set of optimal solutions allowing to switch from one solution to another, without any performance loss, in order to face potential disruptions which occur during the schedule execution. It is based on a dominance theorem that characterizes a set of dominant sequences, using the interval structure defined by the relative order of the release and the due dates of jobs. The performance of a set of dominant sequences can be determined in polynomial time by computing the most favorable and the most unfavorable sequences associated with each job, with regard to the lateness criterion. A branch and bound procedure is proposed which modifies the interval structure of the problem in order to tighten the dominant set of sequences so that only the optimal sequences are conserved.     

Aircraft maintenance,routing, and crew scheduling planning for airlines with a single fleet and a single maintenance and crew base

This work proposes an approach for solving the aircraft maintenance routing problem (AMRP) and the crew scheduling problem (CSP) in sequential and integrated fashions for airlines having a single fleet with a single maintenance and crew base, as is the case for most Latin American and many low-cost airlines. The problems were initially solved in the traditional sequential fashion. The AMRP was formulated to maximize revenue while satisfying fleet size. It was solved such that the final flight schedule was also determined. The CSP was solved by including a heuristic to obtain an efficient first feasible solution, and adapting a labeling algorithm to solve the pricing problems that arise in the column-generation technique. Finally, an integrated model was formulated and solved. Both approaches were tested on the real flight schedules of three important Latin American airlines. The solutions were coherent, independent of computational parameters, and obtained in short computational times in a standard PC (e.g. <1 h for up to 522 flights). Continuous relaxations gave very tight bounds (e.g. gaps < 0.8%). The integrated solutions offered small improvements over the sequential solutions (e.g. up to 0.6% or US$45,000 savings/year). However, these savings should increase drastically with fleet size and with the complexity of the flight schedule offered by the airline.     

Unsafe acts and unsafe outcomes in aircraft maintenance

Road safety studies using the Driver Behaviour Questionnaire (DBQ) have provided support for a three-way distinction between violations, skill-based errors and mistakes, and have indicated that a tendency to commit driving violations is associated with an increased risk of accident involvement. The aims of this study were to examine whether the three-way distinction of unsafe acts is applicable in the context of aircraft maintenance, and whether involvement in maintenance safety occurrences can be predicted on the basis of self-reported unsafe acts. A Maintenance Behaviour Questionnaire (MBQ) was developed to explore patterns of unsafe acts committed by aircraft maintenance mechanics. The MBQ was completed anonymously by over 1300 Australian aviation mechanics, who also provided information on their involvement in workplace accidents and incidents. Four factors were identified: routine violations, skill-based errors, mistakes and exceptional violations. Violations and mistakes were related significantly to the occurrence of incidents that jeopardized the quality of aircraft maintenance, but were not related to workplace injuries. Skill-based errors, while not related to work quality incidents, were related to workplace injuries. The results are consistent with the three-way typology of unsafe acts described by Reason et al. (1990) and with the DBQ research indicating an association between self-reported violations and accidents. The current findings suggest that interventions addressed at maintenance quality incidents should take into account the role of violations and mistakes, and the factors that promote them. In contrast, interventions directed at reducing workplace injury are likely to require a focus on skill-based errors.     

The robust vehicle routing problem with time windows

This paper addresses the robust vehicle routing problem with time windows. We are motivated by a problem that arises in maritime transportation where delays are frequent and should be taken into account. Our model only allows routes that are feasible for all values of the travel times in a predetermined uncertainty polytope, which yields a robust optimization problem. We propose two new formulations for the robust problem, each based on a different robust approach. The first formulation extends the well-known resource inequalities formulation by employing adjustable robust optimization. We propose two techniques, which, using the structure of the problem, allow to reduce significantly the number of extreme points of the uncertainty polytope. The second formulation generalizes a path inequalities formulation to the uncertain context. The uncertainty appears implicitly in this formulation, so that we develop a new cutting plane technique for robust combinatorial optimization problems with complicated constraints. In particular, efficient separation procedures are discussed. We compare the two formulations on a test bed composed of maritime transportation instances. These results show that the solution times are similar for both formulations while being significantly faster than the solutions times of a layered formulation recently proposed for the problem.     

Discrete firefly algorithm with compound neighborhoods for asymmetric multi-depot vehicle routing problem in the maintenance of farm machinery

We introduce a new variant of the vehicle routing problem, that is, the asymmetric multi-depot vehicle routing problem in the maintenance of farm machinery. When providing door-to-door service for farm machinery maintenance, there exists not only node service, (e.g., part replacement), but also directed arc service, (e.g., pulling the breakdown farm machinery from the farm location to the specified maintenance station). In the problem, there are multiple constraints, including the customer’s time window, maximum repairman working duration, fleet size, and vehicle capacity, etc. A mathematical programming model is formulated with the minimum total costs by transforming the problem into the asymmetric multi-depot vehicle routing problem with time windows. Discrete firefly algorithm with compound neighborhoods, presenting new neighborhood methods, is proposed to solve it. New procedures to evaluate the duration infeasibility are suggested with the reduced additional computational complexity. Computational results demonstrate that the proposed approach performs better than CPLEX solver, especially for large designed instances. Moreover, the proposed approach is superior to the other algorithms on solving benchmark instances of multi-depot vehicle routing problem with time windows. This study can provide decision support to door-to-door service for the maintenance of farm machinery.     

How to manage robust tactical planning with an APS (Advanced Planning Systems)

Nowadays, managing correctly the always changing customer demands is a challenge for companies, especially because of its impact on the Supply Chain (Forrester effect). Tactical planning is very useful in establishing robust plans. This paper proposes an alternative policy to traditional practices (frozen horizon . . .), the so-called “reference plan”, to obtain more stable and robust production plans at tactical level. Using an industrial application and simulations, we illustrate how the different practices contribute to robustness in planning. The “reference plan” policy seems to realize the best compromise between stability, robustness costs and service levels achieved by the tactical plans.     

Solving a robust airline crew pairing problem with column generation

In this study, we solve a robust version of the airline crew pairing problem. Our concept of robustness was partially shaped during our discussions with small local airlines in Turkey which may have to add a set of extra flights into their schedule at short notice during operation. Thus, robustness in this case is related to the ability of accommodating these extra flights at the time of operation by disrupting the original plans as minimally as possible. We focus on the crew pairing aspect of robustness and prescribe that the planned crew pairings incorporate a number of predefined recovery solutions for each potential extra flight. These solutions are implemented only if necessary for recovery purposes and involve either inserting an extra flight into an existing pairing or partially swapping the flights in two existing pairings in order to cover an extra flight. The resulting mathematical programming model follows the conventional set covering formulation of the airline crew pairing problem typically solved by column generation with an additional complication. The model includes constraints that depend on the columns due to the robustness consideration and grows not only column-wise but also row-wise as new columns are generated. To solve this difficult model, we propose a row and column generation approach. This approach requires a set of modifications to the multi-label shortest path problem for pricing out new columns (pairings) and various mechanisms to handle the simultaneous increase in the number of rows and columns in the restricted master problem during column generation. We conduct computational experiments on a set of real instances compiled from local airlines in Turkey.     

Skills,rules and knowledge in aircraft maintenance: errors in context

Automatic or skill-based behaviour is generally considered to be less prone to error than behaviour directed by conscious control. However, researchers who have applied Rasmussen's skill-rule-knowledge human error framework to accidents and incidents have sometimes found that skill-based errors appear in significant numbers. It is proposed that this is largely a reflection of the opportunities for error which workplaces present and does not indicate that skill-based behaviour is intrinsically unreliable. In the current study, 99 errors reported by 72 aircraft mechanics were examined in the light of a task analysis based on observations of the work of 25 aircraft mechanics. The task analysis identified the opportunities for error presented at various stages of maintenance work packages and by the job as a whole. Once the frequency of each error type was normalized in terms of the opportunities for error, it became apparent that skill-based performance is more reliable than rule-based performance, which is in turn more reliable than knowledge-based performance. The results reinforce the belief that industrial safety interventions designed to reduce errors would best be directed at those aspects of jobs that involve rule- and knowledge-based performance.     

A two-machine flowshop scheduling problem with a separated maintenance constraint

This paper considers a two-machine flowshop scheduling problem with a separated maintenance constraint. This means that the machine may not always be available during the scheduling period. It needs a constant time to maintain the machine after completing a fixed number of jobs at most. The objective is to find the optimal job combinations and the optimal job schedule such that the makespan is minimized. The proposed problem has some practical applications, for example, in electroplating process, the electrolytic cell needs to be cleaned and made up a deficiency of medicine. In this paper, we propose a heuristic algorithm to solve this problem. Some polynomially solvable cases and computational experiments are also provided.     

A robust green traffic-based routing problem for perishable products distribution

Nowadays, transportation and logistics are considered as the drivers of economic development in the countries due to their impacts on the main variables of the country's economy such as production, employment, price, and the cost of living. Statistics indicate that fuel consumption constructs a major part of transportation costs, where its optimization leads to the creation of an energy-efficient and sustainable transportation system. On the other hand, vehicles' traffic is also one of the main criteria affecting the travel time of vehicles between demand nodes in a supply chain, increasing fuel consumption, and, consequently, damaging effects of greenhouse gasses. In this paper, a novel robust mixed-integer linear programming model is developed for a green vehicle routing problem with intermediate depots considering different urban traffic conditions, fuel consumption, time windows of services, and uncertain demand for perishable products. To validate and solve the suggested model, CPLEX solver of GAMS software is employed as an exact method. Finally, a case study problem is investigated to evaluate the applicability of the proposed model and determine the optimal managerial insights and policies in the real-world conditions using sensitivity analyses. Moreover, a novel robustness threshold comparison is conducted to find the optimal level of budget assignment.     

Integrated staffing and scheduling for an aircraft line maintenance problem

This paper studies the problem of constructing the workforce schedules of an aircraft maintenance company. The problem involves both a staffing and a scheduling decision. We propose an enumerative algorithm with bounding in which each node of the enumeration tree represents a mixed integer linear problem (MILP). We reformulate the MILP such that it becomes tractable for commercial MILP solvers. Extensive computational tests on 40 instances that are derived from a real-life setting indicate that the algorithm is capable of finding close-to-optimal solutions.     

多目标军用飞机维修作业调度优化研究

为提升维修作业与现代战机的适应程度,对军用飞机维修作业调度模型构建与调度优化算法设计进行探讨。在沿用柔性作业车间调度问题的形式化描述构建维修作业调度模型的基础上,选取遗传算法对执行步骤进行设计,引入耦合算子重新调整工序排序部分染色体以避免染色体违背耦合约束无法解码的情况发生,并采用维修作业调度案例与Brandimarte测试数据验证多目标调度优化算法的适用性与优化性。维修作业调度模型构建与调度优化算法的探讨促进维修管理的精细化,为调度相关领域的深入研究拓宽思路。     

Open vehicle routing problem with demand uncertainty and its robust strategies

We investigate the open vehicle routing problem with uncertain demands, where the vehicles do not necessarily return to their original locations after delivering goods to customers. We firstly describe the customer’s demand as specific bounded uncertainty sets with expected demand value and nominal value, and propose the robust optimization model that aim at minimizing transportation costs and unsatisfied demands in the specific bounded uncertainty sets. We propose four robust strategies to cope with the uncertain demand and an improved differential evolution algorithm (IDE) to solve the robust optimization model. Then we analyze the performance of four different robust strategies by considering the extra costs and unmet demand. Finally, the computational experiments indicate that the robust optimization greatly avoid unmet demand while incurring a small extra cost and the optimal return strategy is the best strategy by balancing the trade-off the cost and unmet demand among different robust strategies.     

Motion planning for robotic manipulators using robust constrained control

Since their first appearance in the 1970's, industrial robotic manipulators have considerably extended their application fields, allowing end-users to adopt this technology in previously unexplored scenarios. Correspondingly, the way robot motion can be specified has become more and more complex, requiring new capabilities to the robot, such as reactivity and adaptability. For an even enhanced and widespread use of industrial manipulators, including the newly introduced collaborative robots, it is necessary to simplify robot programming, thus allowing this activity to be handled by non-expert users. Next generation robot controllers should intelligently and autonomously interpret production constraints, specified by an application expert, and transform them into motion commands only at a lower and real-time level, where updated sensor information or other kind of events can be handled consistently with the higher level specifications. The availability of several execution strategies could be then effectively exploited in order to further enhance the flexibility of the resulting robot motion, especially during collaboration with humans.This paper presents a novel methodology for motion specification and robust reactive execution. Traditional trajectory generation techniques and optimisation-based control strategies are merged into a unified framework for simultaneous motion planning and control. An experimental case study demonstrates the effectiveness and the robustness of this approach, as applied to an image-guided grasping task.     

Development of computer-aided maintenance resources planning (CAMRP): A case of multiple CNC machining centers

Total productive maintenance (TPM), total maintenance assurance, preventive maintenance, reliability-centered maintenance (RCM), and many other innovative approaches to maintenance problems all aim at enhancing the effectiveness of machines to ultimately improve productivity. Each of these concepts demands a unique decision support system for maintenance resources planning, and implementing each of them requires a radical restructuring of work. Introducing computer-aided maintenance resources planning (CAMRP) system is a major challenge because the maintenance operations environment is usually traditional and unfavorable to change. This paper presents a computer-aided planning system for a maintenance business unit that serves a number of manufacturing facilities, each consisting of a set of high-precision CNC machining centers. The workforce in the maintenance business unit is responsible for preventive as well as corrective maintenance activities of all CNC machines within the different manufacturing sites. The newly developed decision support tool embodies a set of structured heuristics methods for the coordination of tasks among maintenance crews which will help conduct different maintenance activities of manufacturing units in a more synchronized way. Through what-if-analyses, the tool generates well-founded decisions for capacity planning are; synchronizes maintenance activities to predict maintenance start and expected finishing times, thereby leads to lower costs.     

Scheduling a variable maintenance and linear deteriorating jobs on a single machine

We investigate a single machine scheduling problem in which the processing time of a job is a linear function of its starting time and a variable maintenance on the machine must be performed prior to a given deadline. The goals are to minimize the makespan and the total completion time. We prove that both problems are NP-hard. Furthermore, we show that there exists a fully polynomial time approximation scheme for the makespan minimization problem. For the total completion time minimization problem we point out that there exists a fully polynomial time approximation scheme for a special case.     

A robust algorithm for model-following control of under-actuated systems,and its application to a non-holonomic robot and an aircraft

In this paper, we present an algorithm for model-following control of under-actuated systems. To make the algorithm robust, we try to suppress computation errors from approximations which are often encountered in the cases of applying the existing algorithms to the under-actuated systems. In this view, we present an algorithm without any kinds of approximations, even in the cases of under-actuated systems. Finally, we check the examples in which the proposed algorithm is applied to a non-holonomic robot and an aircraft.