Selective maintenance optimisation for series-parallel systems alternating missions and scheduled breaks with stochastic durations

This paper deals with the selective maintenance problem for a multi-component system performing consecutive missions separated by scheduled breaks. To increase the probability of successfully completing its next mission, the system components are maintained during the break. A list of potential imperfect maintenance actions on each component, ranging from minimal repair to replacement is available. The general hybrid hazard rate approach is used to model the reliability improvement of the system components. Durations of the maintenance actions, the mission and the breaks are stochastic with known probability distributions. The resulting optimisation problem is modelled as a non-linear stochastic programme. Its objective is to determine a cost-optimal subset of maintenance actions to be performed on the components given the limited stochastic duration of the break and the minimum system reliability level required to complete the next mission. The fundamental concepts and relevant parameters of this decision-making problem are developed and discussed. Numerical experiments are provided to demonstrate the added value of solving this selective maintenance problem as a stochastic optimisation programme.     

A reliability/availability approach to joint production and maintenance scheduling with multiple preventive maintenance services

In classical scheduling problems, it is often assumed that the machines are available during the whole planning horizon, while in realistic environments, machines need to be maintained and therefore may become unavailable within production periods. Hence, in this paper we suggest a joint production and maintenance scheduling (JPMS) with multiple preventive maintenance services, in which the reliability/availability approach is employed to model the maintenance aspects of a problem. To cope with the suggested JPMS, a mixed integer nonlinear programming model is developed and then a population-based variable neighbourhood search (PVNS) algorithm is devised for a solution method. In order to enhance the search diversification of basic variable neighbourhood search (VNS), our PVNS uses an epitome-based mechanism in each iteration to transform a group of initial individuals into a new solution, and then multiple trial solutions are generated in the shaking stage for a given solution. At the end of the local search stage, the best obtained solution by all of the trial solutions is recorded and the worst solution in population is replaced with this new solution. The evolution procedure is continued until a predefined number of iterations is violated. To validate the effectiveness and robustness of PVNS, an extensive computational study is implemented and the simulation results reveal that our PVNS performs better than traditional algorithms, especially in large size problems.     

Multi-threaded simulated annealing for a bi-objective maintenance scheduling problem

A parallel Simulated Annealing algorithm with multi-threaded architecture is proposed to solve a real bi-objective maintenance scheduling problem with conflicting objectives: the minimisation of the total equipment downtime caused by maintenance jobs and the minimisation of the multi-skilled workforce requirements over the given horizon. The maintenance jobs have different priorities with some precedence relations between different skills. The total weighted flow time is used as a scheduling criterion to measure the equipment availability. The multi-threaded architecture is used to speed up a multi-objective Simulated Annealing algorithm to solve the considered problem. Multi-threading is a form of parallelism based on shared memory architecture where multiple logical processing units, so-called threads, run concurrently and communicate via shared memory. The performance of the parallel method compared to the exact method is verified using a number of test problems. The obtained results imply the high efficiency and robustness of the proposed heuristic for both solution quality and computational effort.     

Reliability-based maintenance and job scheduling for identical parallel machines

Quality has an important role in manufacturing, and on the other hand, machine condition has a significant effect on quality. Based on this fact, all manufacturers integrate the production scheduling with maintenance activities to keep the machines in perfect conditions. In this paper, we propose a mixed integer nonlinear model to optimise the quality cost, maintenance cost, earliness–tardiness cost and interruption cost simultaneously. We assume that if machines work in undesirable conditions, their quality is reduced, resulting in quality cost. On the other hand, if the machines are repaired to decrease the quality cost, maintenance cost and other cost such as earliness–tardiness cost and interruption cost are imposed to the manufacturer. Several numerical instances are implemented by the proposed model to show the model effectiveness to obtain the best maintenance and production scheduling with minimum quality cost.     

A genetic algorithm approach for production scheduling with mould maintenance consideration

The traditional approach for maintenance scheduling concerns single-resource (machine) maintenance during production which may not be sufficient to improve production system reliability as a whole. Besides, in the literature many researchers schedule maintenance activities periodically with fixed maintenance duration. However, in a real manufacturing system maintenance activities can be executed earlier and the maintenance duration will become shorter since less time and effort are required. A practical example is that in a plastic production system, the proportion of machine-related downtime is even lower than mould-related downtime. The planned production operations are usually interrupted seriously because of the mismatch among the maintenance periods between injection machine and mould. In this connection, this paper proposes to jointly schedule production and maintenance tasks of multi-resources in order to improve production system reliability by reducing the mismatch among various processes. To integrate machine and mould maintenance tasks in production, this paper attempts to model the production scheduling with mould scheduling (PS-MS) problem with time-dependent deteriorating maintenance schemes. The objective of this paper is to propose a genetic algorithm approach to schedule maintenance tasks jointly with production jobs for the PS-MS problem, so as to minimise the makespan of production jobs.     

Decision-making on multi-mould maintenance in production scheduling

The reliability of a critical tool like a mould on a machine affects the productivity seriously in many manufacturing firms. In fact, its breakdown frequency is even higher than machines. The decision-making on when mould maintenance should be started become a challenging issue. In the previous study, the mould maintenance plans were integrated with the traditional production schedules in a plastics production system. It was proven that considering machine and mould maintenance in production scheduling could improve the overall reliability and productivity of the production system. However, the previous model assumed that each job contained single operation. It is not workable in other manufacturing systems such as die stamping which may contain multiple operations with multiple moulds in each job. Thus, this study models a new problem for multi-mould production-maintenance scheduling. A genetic algorithm approach is applied to minimise the makespan of all jobs in 10 hypothetical problem sets. A joint scheduling (JS) approach is proposed to decide the start times of maintenance activities during scheduling. The numerical result shows that the JS approach has a good performance in the new problem and it is sensitive to the characteristic of the setup time defined.     

A new multi-objective optimization model for preventive maintenance and replacement scheduling of multi-component systems

In this article, a new multi-objective optimization model is developed to determine the optimal preventive maintenance and replacement schedules in a repairable and maintainable multi-component system. In this model, the planning horizon is divided into discrete and equally-sized periods in which three possible actions must be planned for each component, namely maintenance, replacement, or do nothing. The objective is to determine a plan of actions for each component in the system while minimizing the total cost and maximizing overall system reliability simultaneously over the planning horizon. Because of the complexity, combinatorial and highly nonlinear structure of the mathematical model, two metaheuristic solution methods, generational genetic algorithm, and a simulated annealing are applied to tackle the problem. The Pareto optimal solutions that provide good tradeoffs between the total cost and the overall reliability of the system can be obtained by the solution approach. Such a modeling approach should be useful for maintenance planners and engineers tasked with the problem of developing recommended maintenance plans for complex systems of components.     

Joint optimization of preventive maintenance and flexible flowshop sequence-dependent group scheduling considering multiple setups

This study focuses on a joint optimization problem regarding preventive maintenance (PM) and non-permutation group scheduling for a flexible flowshop manufacturing cell in order to minimize makespan. A mixed-integer linear programming model for the investigated problem is developed, which features the consideration of multiple setups, the relaxation of group technology assumptions, and the integration of group scheduling and PM. Based on the model, a lower bounding technique is presented to evaluate the quality of solutions. Furthermore, a genetic algorithm (GA) is proposed to improve computational efficiency. In the GA, a threshold-oriented PM policy, a hybrid crossover and a group swap mutation operator are applied. Numerical experiments are conducted on 45 test problems with various scales. The results show that the proposed model can remarkably reduce makespan. Comparative experiments reveal that the GA outperforms CPLEX, particle swarm optimization and cuckoo search with respect to effectiveness and efficiency.     

Integrated maintenance planning and production scheduling with Markovian deteriorating machine conditions

In many industries, production capacity diminishes as machine conditions deteriorate. Maintenance operations improve machine conditions, but also occupy potential production time, possibly delaying the customer orders. Therefore, one challenge is to determine the joint maintenance and production schedule to minimize the combined costs of maintenance and lost production over the long term. In this paper, we address the problem of integrated maintenance and production scheduling in a deteriorating multi-machine production system over multiple periods. Assuming that at the beginning of each period the demand becomes known and machine conditions are observable, we formulate a Markov decision process model to determine the maintenance plan and develop sufficient conditions guaranteeing its monotonicity in both machine condition and demand. We then formulate an integer programming model to find the maintenance and the production schedule in each period. Our computational results show that exploiting online condition monitoring information in maintenance and production decisions leads to 21% cost savings on average compared to a greedy heuristic and that the benefit of incorporating long-term information in making short-term decisions is highest in industries with medium failure rates.     

Manpower supply planning for aircraft line maintenance under stochastic incidents

We plan the manpower supply for aircraft line maintenance, taking into account two types of stochastic incidents: manpower demands for a flight and the number of aircraft needing to be serviced at one time. The problem is solved to find the shift and maintenance group combinations best suited for the given airline. The optimal aircraft maintenance certification for a crew is also analyzed to improve the entire manpower structure. In addition, the addition of temporary manpower required for actual daily operations is also considered as a part of understanding the total manpower utilized in actual operations. An integrated method including scenario generation and a stochastic model is developed to deal with the problem. Finally, we perform a case study based on operating data obtained from a major airline in Taiwan. The results and findings are compared with the airline’s current manpower plan in the discussion, and suggestions for improvement are made.     

A multi-point simulated annealing heuristic for solving multiple objective unrelated parallel machine scheduling problems

This study considers the problem of job scheduling on unrelated parallel machines. A multi-objective multi-point simulated annealing (MOMSA) algorithm was proposed for solving this problem by simultaneously minimising makespan, total weighted completion time and total weighted tardiness. To assess the performance of the proposed heuristic and compare it with that of several benchmark heuristics, the obtained sets of non-dominated solutions were assessed using four multi-objective performance indicators. The computational results demonstrated that the proposed heuristic markedly outperformed the benchmark heuristics in terms of the four performance indicators. The proposed MOMSA algorithm can provide a new benchmark for future research related to the unrelated parallel machine scheduling problem addressed in this study.     

Integrated production quality and condition-based maintenance optimisation for a stochastically deteriorating manufacturing system

This paper investigates the problem of optimally integrating production quality and condition-based maintenance in a stochastically deteriorating single- product, single-machine production system. Inspections are periodically performed on the system to assess its actual degradation status. The system is considered to be in ‘fail mode’ whenever its degradation level exceeds a predetermined threshold. The proportion of non-conforming items, those that are produced during the time interval where the degradation is beyond the specification threshold, are replaced either via overtime production or spot market purchases. To optimise preventive maintenance costs and at the same time reduce production of non-conforming items, the degradation of the system must be optimally monitored so that preventive maintenance is carried out at appropriate time intervals. In this paper, an integrated optimisation model is developed to determine the optimal inspection cycle and the degradation threshold level, beyond which preventive maintenance should be carried out, while minimising the sum of inspection and maintenance costs, in addition to the production of non-conforming items and inventory costs. An expression for the total expected cost rate over an infinite time horizon is developed and solution method for the resulting model is discussed. Numerical experiments are provided to illustrate the proposed approach.     

Solving a stochastic berth allocation problem using a hybrid sequence pair-based simulated annealing algorithm

In this article, a continuous berth allocation problem is studied with stochastic ship arrival and handling times. The objective is to minimize a weighted sum of the expected waiting costs, berthing deviation costs and expected overtime costs. The sequence pair representation is utilized to project the solution space of the problem into two permutations. Then, a scenario-based method is used to capture the uncertainty. To effectively solve the problem over the sequence pair solution space, a simulated annealing is combined with two algorithms. One of the algorithms is used to determine the berthing positions and the other one is used to determine the berthing times. Computational experiments are conducted to evaluate the performance of the solution method and to verify the advantages of the proposed stochastic approach. The results indicate that the proposed methodology is both efficient and effective.     

Single-machine scheduling with deteriorating effects and machine maintenance

In this paper, the single-machine scheduling problems with deteriorating effects and a machine maintenance are studied. In this circumstance, the deterioration rates of the jobs during the machining process are the same which reduces the production efficiency. The actual processing time of the job is a linearly increasing function of the starting time. In this process, the machine only performs a maintenance activity, and the maintenance time is a fixed value. After the maintenance work is completed, the machine will be restored to the initial state, and the deterioration of the job will be start again. The goal is to determine the optimal schedule in order to minimise the maximum completion time (i.e. the makespan) and the sum of job completion times. We prove that both problems are polynomial time solvable, and we also provide the corresponding algorithms.     

Daily scheduling of caregivers with stochastic times

This paper addresses a daily caregiver scheduling and routing problem arising in home health care or home care service providers. The problem is quite challenging due to its uncertainties in terms of travel and service times derived from changes in road traffic conditions and customer health status in practice. We first model the problem as a stochastic programme with recourse, where the recourse action is to skip customers without services if the caregiver arrives later than their latest starting service time (i.e. hard time window requirements). Then, we formulate the problem as a set partitioning model and solve it with a branch-and-price (B&P) algorithm. Specifically, we devise an effective discrete approximation method to calculate the arrival time distribution of caregivers, incorporate it into a problem-specific label algorithm, and use a removal-and-insertion-based heuristic and the decremental state-space relaxation technique to accelerate the pricing process. Finally, we conduct numerical experiments on randomly generated instances to validate the effectiveness of the discrete approximation method and the proposed B&P algorithm.     

Single machine scheduling with preventive maintenances

We consider the single machine total flow time problem in which the jobs are non-resumable and the machine is subject to preventive maintenance activities of known starting times and durations. We propose a branch-and-bound algorithm that employs powerful optimality properties and bounding procedures. Our extensive computational studies show that our algorithm can solve large-sized problem instances with up to 80 jobs in reasonable times. We also study a two-alternative maintenance planning problem with minor and major maintenances. We give a polynomial-time algorithm to find the optimal maintenance times when the job sequence is fixed.     

Availability optimisation for stochastic degrading systems under imperfect preventive maintenance

This paper deals with imperfect preventive maintenance (PM) optimisation problem. The system to be maintained is typically a production system assumed to be continuously monitored and subject to stochastic degradation. To assess such degradation, the proposed maintenance model takes into account both corrective maintenance (CM) and PM. The system undergoes PM whenever its reliability reaches an appropriate value, while CM is performed at system failure. After a given number of maintenance actions, the system is preventively replaced by a new one. Both CM as well as PM are considered imperfect, i.e. they bring the system to an operating state which lies between two extreme states, namely the as bad as old state and as good as new state. The imperfect effect of CM and PM is modelled on the basis of the hybrid hazard rate model. The objective of the proposed PM optimisation model consists on finding the optimal reliability threshold together with the optimal number of PM actions to maximise the average availability of the system. A mathematical model is then proposed. To solve this problem an algorithm is provided. A numerical example is presented to illustrate the proposed maintenance optimisation model.     

Single machine scheduling problem with stochastic sequence-dependent setup times

In this study, we consider stochastic single machine scheduling problem. We assume that setup times are both sequence dependent and uncertain while processing times and due dates are deterministic. In the literature, most of the studies consider the uncertainty on processing times or due dates. However, in the real-world applications (i.e. plastic moulding industry, appliance assembly, etc.), it is common to see varying setup times due to labour or setup tools availability. In order to cover this fact in machine scheduling, we set our objective as to minimise the total expected tardiness under uncertain sequence-dependent setup times. For the solution of this NP-hard problem, several heuristics and some dynamic programming algorithms have been developed. However, none of these approaches provide an exact solution for the problem. In this study, a two-stage stochastic-programming method is utilised for the optimal solution of the problem. In addition, a Genetic Algorithm approach is proposed to solve the large-size problems approximately. Finally, the results of the stochastic approach are compared with the deterministic one to demonstrate the value of the stochastic solution.     

Cash transportation vehicle routing and scheduling under stochastic travel times

Stochastic disturbances occurring in real-world operations could have a significant influence on the planned routing and scheduling results of cash transportation vehicles. In this study, a time–space network flow technique is utilized to construct a cash transportation vehicle routing and scheduling model incorporating stochastic travel times. In addition, to help security carriers to formulate more flexible routes and schedules, a concept of the similarity of time and space for vehicle routing and scheduling is incorporated into the model. The test results show that the model could be useful for security carriers in actual practice.     

Optimal joint selective imperfect maintenance and multiple repairpersons assignment strategy for complex multicomponent systems

This paper addresses the joint selective maintenance and repairperson assignment problem (JSM–RAP) for complex multicomponent systems. The systems perform consecutive missions separated by scheduled finite duration breaks and are imperfectly maintained during the breaks. Current selective maintenance (SM) models usually assume that only one repair channel is available or that the repairperson assignment optimisation can be done at a subsequent stage. Using a generalised reliability function for k-out-of-n systems, we formulate the JSM–RAP for multicomponent systems more complex than the series-parallel systems commonly used in previous SM models. Two nonlinear formulations and their corresponding binary integer programming models are then proposed and optimally solved. Numerical experiments show the added value of the proposed approach and highlight the benefit of jointly carrying out the selection of the components to be maintained, the maintenance level to be performed and the assignment of the maintenance tasks to repairpersons. It is also shown that the flexibility provided by mixed skill cohorts of repairpersons over uniform cohorts can yield higher performance levels when the skillsets are significantly different.