Exact and heuristic algorithms for post prognostic decision in a single multifunctional machine



Published Nov 16, 2020
Asma Ladj Christophe Varnier Fatima Benbouzid Si Tayeb Noureddine Zerhouni


Prognostic and Health Management (PHM) benefits are strongly tied to the decision-making that follows the assimilation and interpretation of prognostics information. Hence, we deal in
this study with the post prognostic decision making in order to improve system safety and avoid downtime and inopportune maintenance spending. We investigate the problem of scheduling production jobs in a single multifunctional machine subjected to predictive maintenance based on PHM results. For this reason, we propose a new interpretation of PHM outputs to define the machine degradation corresponding to each job. We develop a Mixed Integer Linear Programming (MILP) model to find the best integrated scheduling that optimizes the total maintenance cost. Unfortunately, the MILP is not able to compute the optimal solution for large instances. Therefore, we design a Prognostic based Genetic Algorithm (Pro-GA). Computational results of different benchmarks setup show the efficiency and robustness of our scheme with an average deviation of about 0.2% over a newly proposed lower bound.

Abstract 171 | PDF Downloads 168



Maintenance Scheduling, predictive maintenance, degradation, Post-prognostics decision, Genetic Algorithm optimization, Mixed Integer Linear Programming

Aliustaoglu, C., Ertunc, H. M., & Ocak, H. (2009). Tool wear condition monitoring using a sensor fusion model based on fuzzy inference system. Mechanical Systems and Signal Processing, 23(2), 539–546.
Benbouzid-Sitayeb, F., Guebli, S. A., Bessadi, Y., Varnier, C., & Zerhouni, N. (2011). Joint scheduling of jobs and preventive maintenance operations in the flowshop sequencing problem: a resolution with sequential and integrated strategies. International Journal of Manufacturing Research, 6(1), 30–48.
Berdinyazov, A., Camci, F., Sevkli, M., & Baskan, S. (2009, Aug 2009). Economic analysis of maintenance policies for a system. In 2009 ieee international symposium on diagnostics for electric machines, power electronics and drives (p. 1-5).
Brotherton, T., Jahns, G., Jacobs, J., & Wroblewski, D. (2000). Prognosis of faults in gas turbine engines. In Aerospace conference proceedings, ieee (Vol. 6, pp. 163–171).
Byington, C. S., Roemer, M. J., & Galie, T. (2002). Prognostic enhancements to diagnostic systems for improved condition-based maintenance [military aircraft]. In 2002 ieee aerospace conference proceedings (Vol. 6, pp. 6–6).
CEN/EN. (2010). Maintenance - maintenance terminology (Tech. Rep. No. EN13306:2010). European committee for standardization.
Chrétien, S., Herr, N., Nicod, J. M., & Varnier, C. (2015, 22– 25 Jun 2015). A post-prognostics decision approach to optimize the commitment of fuel cell systems in stationary applications. In Ieee conference on prognostics and health management (phm) (pp. 1–7). TX, USA.
Coffman, E. G., Garey, M. R., & Johnson, D. S. (1984). Approximation algorithms for bin-packing - an updated survey. In G. Ausiello, M. Lucertini, & P. Serafini (Eds.), Algorithm design for computer system design (pp. 49–106). Vienna: Springer Vienna.
De Castro, L. T., & J. (2002). Artificial immune systems: A new computational intelligence approach. In Algorithm design for computer system design. Secaucus, NJ, USA: Springer-Verlag New York, Inc.
Duffuaa, S., Ben-Daya, M., Al-Sultan, K., & Andijani, A. (2001). A generic conceptual simulation model for maintenance systems. Journal of Quality in Maintenance Engineering, 7(3), 207–219.
Everitt, B., & Skrondal, A. (2010). The cambridge dictionary of statistics (3th ed.).
Goldberg, D. E. (1989). Genetic algorithms in search, optimization and machine learning (1st ed.). Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc.
GUROBI. (2014). Optimizer reference manual. Retrieved 2016-12-28, from http://www.gurobi.com/documentation/
Hadidi, L. A., Al-Turki, U. M., & Rahim, A. (2011). Integrated models in production planning and scheduling, maintenance and quality: a review. International Journal of Industrial and Systems Engineering, 10(1), 21–50.
Herr, N., Nicod, J. M., & Varnier, C. (2014, 18–22 Aug 2014). Prognostics-based scheduling in a distributed platform: Model, complexity and resolution. In Ieee international conference on automation science and engineering (case) (pp. 1054–1059). Taipei, Taiwan.
ISO. (2004). Condition monitoring and diagnostics of machines, prognostics part 1: General guidelines (Vol. ISO/IEC Directives Part 2; Tech. Rep. No. ISO13381- 1). International Organization for Standardization.
Iyer, N., Goebel, K., & Bonissone, P. (2006, 4–11 March 2006). Framework for post-prognostic decision support. In 2006 ieee aerospace conference (p. 10 pp.-). MT, USA.
Khatab, A., Ait-Kadi, D., & Rezg, N. (2014). Availability optimisation for stochastic degrading systems under imperfect preventive maintenance. International Journal of Production Research, 52(14), 4132–4141.
Ladj, A., Benbouzid-Si Tayeb, F., & Varnier, C. (2016, 24– 29 July 2016). An integrated prognostic based hybrid genetic-immune algorithm for scheduling jobs and predictive maintenance. In Ieee congress on evolutionary computation (pp. 2083–2089). Vancouver, BC, Canada.
Lebold, M., & Thurston, M. (2001, 6–9 May 2001). Open standards for condition-based maintenance and prognostic systems. In Maintenance and reliability conference (marcon) (Vol. 200). Gatlinburg, Tennesee, USA.
Liu, S., Zhang, H., Li, C., Lu, H., & Hu, Y. (2014). Fuzzy reliability estimation for cutting tools. Procedia CIRP, 15, 62–67.
Ma, Y., Chu, C., & Zuo, C. (2010). A survey of scheduling with deterministic machine availability constraints. Computers & Industrial Engineering, 58(2), 199–211.
Merten, A. G., & Muller, M. E. (1972). Variance minimization in single machine sequencing problems. Management Science, 18(9), 518–528.
Michalewicz, Z.,&Hartley, S. J. (1996). Genetic algorithms+ data structures= evolution programs. Mathematical Intelligencer, 18(3), 71.
Montgomery, D. C. (2008). Design and analysis of experiments. John Wiley & Sons.
Muller, A., Suhner, M. C., & Iung, B. (2008). Formalisation of a new prognosis model for supporting proactive maintenance implementation on industrial system. Reliability Engineering & System Safety, 93(2), 234–253.
Pan, E., Liao, W., & Xi, L. (2012). A joint model of production scheduling and predictive maintenance for minimizing job tardiness. The International Journal of Advanced Manufacturing Technology, 60(9), 1049–1061.
Reeves, C. R. (1995). A genetic algorithm for flowshop sequencing. Computers & operations research, 22(1), 5–13.
Rohlfshagen, P., & Bullinaria, J. A. (2010). Nature inspired genetic algorithms for hard packing problems. Annals of Operations Research, 179(1), 393–419.
Ruiz, R., García-Díaz, J. C., & Maroto, C. (2007). Considering scheduling and preventive maintenance in the flowshop sequencing problem. Computers & Operations Research, 34(11), 3314–3330.
Ruiz, R., Maroto, C., & Alcaraz, J. (2006). Two new robust genetic algorithms for the flowshop scheduling problem. Omega, 34(5), 461–476.
Sardinas, R. Q., Santana, M. R., & Brindis, E. A. (2006). Genetic algorithm-based multi-objective optimization of cutting parameters in turning processes. Engineering Applications of Artificial Intelligence, 19(2), 127–133.
Sidibe, I., Khatab, A., Claver, D., & Ait-Kadi, D. (2015). A maintenance optimization model for a second hand stochastically deteriorating system under different operating environments. In Control, engineering & information technology (ceit), 2015 3rd international conference on (pp. 1–5).
Tobon-Mejia, D., Medjaher, K., & Zerhouni, N. (2012). Cnc machine tool’s wear diagnostic and prognostic by using dynamic bayesian networks. Mechanical Systems and Signal Processing, 28, 167–182.
Varnier, C., & Zerhouni, N. (2012, 23–25 May 2012). Scheduling predictive maintenance in flow-shop. In Ieee conference on prognostics and system health management (phm) (pp. 1–6). Beijing, China.
Venkatasubramanian, V. (2005). Prognostic and diagnostic monitoring of complex systems for product lifecycle management: Challenges and opportunities. Computers & chemical engineering, 29(6), 1253–1263.
Technical Papers