p.86
p.97
p.112
p.119
p.139
p.147
p.156
p.170
p.191
Joint Scheduling of Jobs and Variable Maintenance Activities in the Flowshop Sequencing Problems: Review, Classification and Opportunities
Abstract:
Much of the scheduling theory assumes that machines are always available to process jobs at any time during the scheduling horizon. However, machines may be unavailable for various reasons in realistic practices, such as unexpected failures or variable maintenance activities. This article discusses in depth the works published in the literature of joint scheduling of jobs and variable maintenance activities in the flowshop sequencing problems. Our literature review focuses first on the basic concepts of scheduling problems, and more specifically, the scheduling strategies of production and maintenance that have been identified in the literature. Subsequently, we focus our attention on the principal methods for solving scheduling problems, while presenting in the following the main published works for the aforementioned systems. Lastly, a comparative analysis is carried out to highlight the fundamental ideas leading to the adoption of an effective approach capable of producing an optimal solution in a reasonable calculation time.
Info:
Periodical:
Pages:
170-190
Citation:
Online since:
November 2018
Authors:
Price:
Сopyright:
© 2018 Trans Tech Publications Ltd. All Rights Reserved
Citation:
* - Corresponding Author
[1] S. M. Johnson, Optimal two and three-stage production schedules with setup times included, Naval Research Logistics Quarterly. 1 (1) (1954) 61-68.
[2] I. Adiri, J. Bruno, E. Frostig, A.H.G. Rinnooy Kan, Single machine flow-time scheduling with a single breakdown, Acta Informatica. 26 (1989) 679-696.
DOI: 10.1007/bf00288977
[3] Weiwei Cui, Zhiqiang Lu, Chen Li, Xiaole Han .A proactive approach to solve integrated production scheduling and maintenance planning problem in flow shops.Computers & Industrial Engineering. 115 (2018) 342–353.
[4] Shijin Wang & Ming Liu, Two-machine flow shop scheduling integrated with preventive maintenance planning, International Journal of Systems Science. 900137(2014) 10-1080.
[5] Emmons, H., Vairaktarakis, G. Flowshop Scheduling: Theory, Algorithms, and Managerial Insights. ISOR (2012)182.
[6] Ghita Lebbar, Abdellah El Barkany, Abdelouahhab Jabri, Scheduling Problems of Flexible Manufacturing Systems: Review, Classification and Opportunities,, International Journal of Engineering Research in Africa. 1663-4144 (2016) 142-160.
[7] R.L. Graham, E.L. Lawler, J.K. Lenstra, A.H. G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals Discrete Math., 5(1979) 287 - 326.
[8] C. Y. Lee and Z. L. Chen. Scheduling jobs and maintenance activities on parallel machines. Naval Research Logistics, 47: ( 2000) 145–165.
DOI: 10.1002/(sici)1520-6750(200003)47:2<145::aid-nav5>3.0.co;2-3
[9] M. Bembla. Ordonnancement conjoint production et maintenance : Critère et heuristique de résolution. Mémoire de dea, U.F.R des Sciences et Techniques de l'Université de Franche Comté, (2002).
[10] Amel Yahyaoui. Élaboration de nouveaux outils non conventionnels intelligents pour l'ordonnancement conjoint de la production et de la maintenance : application au cas d'un job shop. Automatique / Robotique. Université de Tunis - ECOLE SUPERIEURE DES SCIENCES ET TECHNIQUES DE TUNIS(2011).
[11] R. Aggoune, Ordonnancement d'ateliers sous contraintes de disponibilités des machines. Thèse de PhD. Université de Metz, France, (2002).
[12] T.W. Sloan and J.G. Shanthikumar. Combined production and maintenance scheduling for a multiple product, single machine production system. Production and Operation Management, 9(4): (2000)379–399.
[13] M. Brandolese, M. Franci, and A. Pozzetti. Production and maintenance integrated planning. International Journal of production Research, 34(7): (1996)2059–(2075).
[14] S.A. Cook, The Complexity of Theorem Proving Procedures. Proceedings of the Third Annual ACM Symposium on the Theory of Computing, Association of Computing Machinery, New York, (1971)151-158.
[15] R.M. Karp, Reducibility Among Combinatorial Problems. in Miller, R.E. and Thatcher, J. W. (eds).Complexity of Computer Computations, Plenum Press, New York, (1972)85-104.
[16] M.R. Garey, M.R. Johnson, Computers and intractability: A guide to the theory of NP-completeness. San Francisco: Freeman, (1979).
[17] C. Sriskandarajah and S. K. Goyal. The Journal of the Operational Research Society. 40 (10) (1989) 907-921.
[18] M.Garey, and D. S. Jonhson. Two-processor scheduling with start times and deadlines, SIAM J. Comput, 6(3) (1977) 416-426.
DOI: 10.1137/0206029
[19] Ahmed Gara-Ali n, Marie-Laure Espinouse .Erratum to: Simultaneously scheduling n jobs and the preventive maintenance on the two-machine flow shop to minimize the makespan,, Int. J. Production Economics 153 (2014) 361–363.
[20] A. Gara-Ali et M.-L. Espinouse. A two-machine flow-shop scheduling with a deteriorating maintenance activity on the second machine. In Industrial Engineering and Systems Management (IESM), International Conference, 481– 488 (2015).
[21] G.B. Dantzig, R. Fulkerson, S. Johnson, Solution of a large-scale travelingsalesman problem. Operational Research 2 (1954) 393-410.
[22] W. Kubiak, J. Blazewicz, P. Formanowicz, J. Breit, G. Schmidt, Two-machine flow shops with limited machine availability, European Journal of Operational Research,136(2002)528-540.
[23] J. Kaabi, C. Varnier, and N. Zerhouni. Ordonnancement conjoint de la production et de la maintenance dans un flow shop. In 5ème Conférence Francophone de Modélisation et Simulation, Nantes, France, 1-3 septembre (2004).
[24] Faten Ben Chihaoui, Imed Kacem, Atidel B. Hadj-Alouane, Najoua Dridi, Nidhal Rezg. No-wait Scheduling of a Two-machine Flow-shop to Minimize the Makespan under Non-Availability Constraints and Different Release Dates. International Journal of Production Research, Taylor & Francis, 2011, p.1.
[25] Faicel Hnaien n, Farouk Yalaoui, Ahmed Mhadhbi .Makespan minimization on a two-machine flowshop with an availability constraint on the first machine. Int. J. Production Economics 164 (2015) 95–104.
[26] M. Gondran, M. Minoux, Graphs and Algorithms. John Wiley and Sons, New York. 21(1984).
[27] R. Bellman, Dynamic Programming, A Markovian Decision Process ,Princeton University Press. Journal of Mathematics and Mechanics, Vol. 6, No. 5 (1957), pp.679-684.
[28] C.-Y. Lee, Minimizing the makespan in the two-machine flowshop scheduling problem with an availability constraint, Operations Research Letters, 20(3):129 – 139(1997).
[29] C.Y. Lee, Two-machine flowshop scheduling with availability constraints, European Journal of Operational Research, 114 (1999) 420-429.
[30] C.T. Ng, M.Y. Kovalyov, An FPTAS for scheduling a two-machine flowshop with one unavailability interval, Naval Research Logistics, 51, 3(2003) 307-315.
DOI: 10.1002/nav.10107
[31] H. Allaoui, H. Artiba, F. Riane, Scheduling of two-machine flow-shops with availability constraints. Dans : Proceedings of 18th ORBEL conference. Brussels, Belgium(2003).
[32] Ng, C.T., & Kovalyov, M.K. ,An FPTAS for scheduling a two-machine flow shop with one unavailability interval, Naval Research Logistics, 51(2004) 307–315.
DOI: 10.1002/nav.10107
[33] M.A. Kubzin, V.A. Strusevich, Planning Machine Maintenance in Two-Machine Shop Scheduling, Operations Research, 54, 4, (2006) 789-800.
[34] H. Allaoui, A. Artiba, S.E. Elmaghraby, F. Riane, Scheduling of a two-machine flow shop with availability constaints on the first machine,International Journal of Production Economics, 99, 1-2, (2006)16-27.
[35] Rapine, C.,Erratum to Scheduling of a two-machine flowshop with availability constraints on the first machine, [Int. J. Prod. Econ. 99 (2006) 16–27].Int. J. Prod. Econ. 142 (2013)211–212.
[36] Vahedi Nouri, B., P. Fattahi, and R. Ramezanian. Hybrid Firefly-simulated Annealing Algorithm for the Flow Shop Problem with Learning Effects and Flexible Maintenance Activities., International Journal of Production Research 51 (12) (2013).
[37] Reza Ramezanian , Mohammad Saidi-Mehrabad , Parviz Fattahi .MIP formulation and heuristics for multi-stage capacitated lot-sizing and scheduling problem with availability constraints. Journal of Manufacturing Systems 32 (2013) 392–401.
[38] N. Kangarloo, J. Rezaeian, X. Khosrawi ,JIT scheduling problem on flexible flow shop with machine break down, machine eligibility and setup times, J. Math. Computer Sci. 16 (2016)50-68.
[39] J. Erscher, C. Merce, Consistency of the disaggregation process in hierarchical planning. Operation Research, 34(1985) 464-469.
[40] Choi, B. C., Lee, K., Leung, J. Y. T., & Pinedo, M. L, Flow shops with machine maintenance: Ordered and proportionate cases, European Journal of Operational Research, 207(2010)97–104.
[41] Cheng, C-Y., Ying, K-C., Chen, H-H., Lin, J-X., Optimization algorithms for proportionate flowshop scheduling problems with variable maintenance activities, Computers & Industrial Engineering (2018).
[42] M.C. Portmann, Méthodes de décomposition spatiales et temporelles en ordonnancement. RAIRO-APII, 22, 5(1988) 439-451.
[43] S. Kirkpatrick, C.D. Gellatt, M.P. Vecchi, Optimization by Simulated Annealing.Science, 220 (1983)671-680.
[44] M.L. Espinouse, P. Formanowicz, B. Penz, Minimizing the makespan in the two-machine no-wait flow-shop, Computers and Industrial Engineering, 37(1999) 497-500.
[45] T.C.E. Cheng, G. Wang, Two-machine flow shop scheduling with consecutive availability constraints, Information Processing Letters, 71, 2(1999) 49-54.
[46] T.C.E. Cheng, G. Wang ,An improved heuristic for two-machine owshop scheduling with an availability constraint ,Operations Research Letters 26 (2000) 223-229.
[47] Blazewicz, J., Breit, J., Formanowicz, P., Kubiak, W., & Schmidt,G. ,Heuristic algorithms for the two-machine flow shop with limited machine availability, Omega, 29(2001) 599–608.
[48] G. Wang, T.C.E. Cheng, Heuristics for two-machine no-wait flowshop scheduling with an availability constraint, Information Processing Letters, 80, 6(2001) 305-309.
[49] O. Braun, G. Schmidt, Y. Sotskov, Stability of Jonson's Schedule with limited Machine availability. Actes de la 3e conférence francophone de Modélisation et de Simulation (MOSIM'01), Troyes, Conception, analyse et gestion des systèmes industriels, SCS European Publishing House, 2(2001).
[50] M.L. Espinouse, P. Formanowicz, B. Penz, Complexity results and approximation algorithms for the two machine no-wait flow-shop with limited machine availability, Journal of the Operational Research Society, 52, 1(1999) 116-121.
[51] R.Aggoune, A.Halim Mahdi and Marie-Claude Portmann, GeneticAlgorithms for the Flow Shop Scheduling Problem with Availability Constraints , 0-7803-7087-2(2001).
[52] J. Kaabi, C. Varnier, and N. Zerhouni. ordonnancement de la production et de la maintenance: cas d'un atelier de type flow shop à deux machines. APII-JESA, décembre (2003) 37:641–660.
[53] Aggoune, R., & Portmann, M. C., Flow shop scheduling problem with limited machine availability: A heuristic approach, International Journal of Production Economics, 99(1–2), (2006) 4–15.
[54] X. Wang, T.C.E. Cheng, Heuristics for two-machine flowshop scheduling with setup times and an availability constraint, Computers and Operations Research 34, (2007)152-162.
[55] Ruiz, R., García-Díaz, J. C., & Maroto, C.,Considering scheduling and preventive maintenance in the flowshop sequencing problem,Computers & Operations Research,34(2007) 3314–3330.
[56] H. Allaoui, S. Lamouri, A. Artiba, E. Aghezzaf . Simultaneously scheduling n jobs and the preventive maintenance on the two-machine flow shop to minimize the makespan Int. J. Production Economics 112 (2008) 161–167.
[57] Yang, D.L., Hsu, C.J., & Kuo, W.H. ,A two-machine flow shop scheduling problem with a separated maintenance constraint, Computers & Operations Research, 35(2008)876–883.
[58] Hamid Allaoui, AbdelHakim Artiba .Johnson's algorithm: A key to solve optimally or approximately flow shop scheduling problems with unavailability periods. Int. J. Production Economics 121 (2009) 81–87.
[59] Hadda, H., Dridi, N., Hajri-Gabouj, S., An improved heuristic for two-machine flow shop scheduling with an availability constraint and nonresumable jobs.4OR - Q. J. Oper. Res. 8(2010)87–99.
[60] Vahedi-Nouri, B., Fattahi, P., Tavakkoli-Moghaddam, R., & Ramezanian, R, A general flow shop scheduling problem with consideration of position-based learning effect and multiple availability constraints. International Journal of Advanced Manufacturing Technology, 73(2014).
[61] Hatem Hadda, A note on Simultaneously scheduling n jobs and the preventive maintenance on the two-machine flow shop to minimize the makespan,, Int. J. Production Economics 159 (2015) 221–222.
[62] Wei-Wei Cui, Zhiqiang Lu, Binghai Zhou, Chen Li & Xiaole Han ,A hybrid genetic algorithm for non-permutation flow shop scheduling problems with unavailability constraints, International Journal of Computer Integrated Manufacturing, 10.10801130247(2016).
[63] Zahedi, Rojalib, Rinto Yusriski .Stepwise Optimization for Model of Integrated Batch Production and Maintenance Scheduling for Single Item Processed on Flow Shop with Two Machines in JIT Environment .Procedia Computer Science 116 (2017) 408–420.
[64] Smith, W.E., Various Optimizers for Single-Stage Production,, Naval Research Logistics Quarterly, 3(1956) 59-66.
[65] F. Glover, Heuristics for Integer Programming Using Surrogate Constraints, Decision Sciences, 8, 1(1977)156-166.
[66] Aggoune, R. ,Minimizing the makespan for the flow shop scheduling problem with availability constraints, European Journal of Operational Research, 153(3) (2004) 534–543.
[67] J. Holland, Adaptive in Natural and Artificial Systems. University of Michigan Press, Ann Arbor(1975).
[68] T.C.E. Cheng, Z. Liu, 3/2-approximation for two-machine no-wait flowshop scheduling with availability constraints, Information Processing Letters, 88(2003) 161-165.
[69] B. Naderi a, M. Zandieh b, M. Aminnayeri. Incorporating periodic preventive maintenance into flexible flowshop scheduling problems. Applied Soft Computing 11 (2011) 2094–2101.
[70] Faicel Hnaien , Farouk Yalaoui. A Fuzzy Multi-objective algorithm to obtain Trade-off Between Cmax and Availability of Flow-Shop .Proceedings of the 14th IFAC . 978-3-902661-98-2 (2012).
[71] Faicel Hnaien ,Farouk Yalaoui .A bi-criteria flow-shop scheduling with preventive maintenance. 7th IFAC. 978-3-902823-35-9 (2013).
[72] Lei Xiao, Sanling Song, Xiaohui Chen and David W. Coit,Joint optimization of production scheduling and machine group preventive maintenance , Reliability Engineering and System Safety. 10.1016.(2015).10.013.
[73] Andrew Junfang Yu, Javad Seif .Minimizing tardiness and maintenance costs in flow shop scheduling by a lower-bound-based GA. Computers & Industrial Engineering 97(2016)26–40.
[74] Sanlaville, E., & Schmidt, G., Machine scheduling with availability constraints, Acta Informatica, 35 (1998) 795–811.
[75] Schmidt, G., Scheduling with limited machine availability, European Journal of Operational Research. 121(1) (2000) 1–15.
[76] Pinedo, M. ,Scheduling: Theory, algorithms, and systems.Upper Saddle River, NJ: Prentice-Hall. (2002).
[77] O. Braun, T.C. Lai, G. Schmidt, Y.N. Sotskov ,Stability of Johnsons schedule with respect to limited machine availability, International Journal of Production Research,40, 17(2002) 4381 4400.
[78] Kubzin, M.A., Potts, C.N., & Strusevich, V.A. Approximation results for flow shop scheduling problems with machine availability constraints, Computers & Operations Research,36,(2009)379–390.
[79] Allahverdi, A., & Mittenthal, J, Dual criteria scheduling on a two-machine flow shop subject to random breakdowns, International Transactions in Operational Research,5(4) (1998) 317–324.
[80] T.C.E. Cheng, Z. Liu, Approximability of two-machine no-wait flowshop scheduling with availability constraints, Operations Research Letters, 31(2003) 319-322.
[81] J. Breit, An improved approximation algorithm for two-machine flow shop scheduling with an availability constraint, Information Processing Letters 90 (2004) 273-278.
[82] Breit, J., A polynomial-time approximation scheme for the two-machine flow shop scheduling problem with an availability constraint, Computers and Operations Research, 33(8), (2006)2143–2153.
[83] X. Wang, T.C.E. Cheng, An approximation scheme for two-machine flowshop scheduling with setup times and an availability constraint, Computers and Operations Research, 34, 10(2007) 2894-2901.
[84] S.L. Khelifati, F. Benbouzid-Sitayeb, A multi-agent scheduling approach for the joint scheduling of jobs and maintenance operations in the flow shop sequencing problem, Comput. Collect. Intell. Technol. Appl. 6923 (2011) 60–69.
[85] Hadda, H. ,A polynomial-time approximation scheme for the two machine flow shop problem with several availability constraints. Optimization Letters, 6 (2012) 559–569.
[86] Shoaardebili, N., & Fattahi, P. ,Multi-objective meta-heuristics to solve three-stage assembly flow shop scheduling problem with machine availability constraints,International Journal of Production Research, 53, (2015)944–968.
[87] Hany Seidgar, Mostafa Zandieh & Iraj Mahdavi ,Bi-objective optimization for integrating production and preventive maintenance scheduling in twostage assembly flow shop problem, Journal of Industrial and Production Engineering. 10.1080.1173599(2016).
[88] Asma Ladj, Fatima Benbouzid-Si Tayeba, Christophe Varnierb, Ali Ayoub Dridia, Nacer Selmane .A Hybrid of Variable Neighbor Search and Fuzzy Logic for the permutation flowshop scheduling problem with predictive maintenance. Procedia Computer Science 112 (2017).
[89] Cassady, C.R., & Kutanoglu, E,Integrating preventive maintenance planning and production scheduling for a single machine. IEEE Transactions on Reliability, 54(2) (2005) 304–309.
[90] J. Kaabi, C. Varnier, and N. Zerhouni. Scheduling with machine availability :An integrated approach. In Proc.of International conference on industrial Engineering and Production Management, IEPM'03, sur CD ROM, 7 pages,Porto, Portugal, mai 26-28 (2003).
[91] M.A. Kubzin and V.A. Strusevich, Two-machine flow shop no-wait scheduling with machine maintenance, A Quarterly Journal of Operations Research 4OR 3: 303–313 (2005).
[92] Rong-Hwa Huang and Shun-Chi Yu .Two-stage multiprocessor flow shop scheduling with deteriorating maintenance in cleaner production. Journal of Cleaner Production 135 (2016) 276e283.
[93] Cassady, C. R., & Kutanoglu, E.Minimizing job tardiness using integrated preventive maintenance planning and production scheduling. IIE Transactions, 35(2003) 503–513.
[94] Sortrakul, N., Nachtmann, H. L., & Cassady, C. R.,Genetic algorithms for integrated preventive maintenance planning and production scheduling for a single machine. Computers in Industry, 56(2005)161–168.
[95] Jabbarizadeh, F., Zandieh, M., & Talebi, D. ,Hybrid flexible flowshops with sequence-dependent setup times and machine availability constraints,Computers & Industrial Engineering, 57(2009) 949–957.
[96] Leon, V. J., Wu, S. D., & Storer, R. H. ,Robust measures and robust scheduling for job shops, IIE Transactions, 26(1994) 32–43.
[97] O'Donovan, R., Uzsoy, R., & McKay, K. N. ,Predictable scheduling on a single machine with breakdowns and sensitive jobs. International Journal of Production Research, 37(1999)4217–4233.
[98] Goren, S., & Sabuncuoglu, I., Robustness and stability measures for scheduling:single machine environment, IIE Transactions, 40(2008) 66–83.
[99] Al-Hinai, N., & ElMekkawy, T. Y., Robust and stable flexible job shop scheduling with random machine breakdowns using a hybrid genetic algorithm. International Journal of Production Economics, 132(2011) 279–291.
[100] Briskorn, D., Leung, J., & Pinedo, M. ,Robust scheduling on a single machine using time buffers. IIE Transactions, 43(2011) 383–398.
[101] Rahmani, D., Heydari, M., Makui, A., & Zandieh, M. ,A new approach to reducing the effects of stochastic disruptions in flexible flow shop problems with stability and nervousness. International Journal of Management Science and Engineering Management,8(3) (2013).
[102] Rahmani, D., & Ramezanian, R.,A stable reactive approach in dynamic flexible flow shop scheduling with unexpected disruptions: A case study. Computers & Industrial Engineering, 98(2016) 360–372.
[103] Rahmani, D., & Heydari, M. ,Robust and stable flow shop scheduling with unexpected arrivals of new jobs and uncertain processing times. Journal of Manufacturing Systems, 33(2014) 84–92.
[104] Cui, W. W., Lu, Z., & Pan, E. ,Integrated production scheduling and maintenance policy for robustness in a single machine, Computers & Operations Research, 47(2014) 81–91.
[105] Lu, Z., Cui, W. W., & Han, X. ,Integrated production and preventive maintenance scheduling for a single machine with failure uncertainty. Computers & Industrial Engineering, 80(2015)236–244.
[106] Aguezzoul, A., Third-party logistics selection problem: A literature review on criteria and methods. Omega, 49(2014) 69-78.
[107] Merigo,José M.,and Jian-Bo Yang. A Bibliometric Analysis of Operations Research and Management Science .,Omega (2016).
[108] Gorman,M.F, A"Metasurvey" analysis in operations Research and Management Science:A survey of literature reviews. Surveys in Operations Research and Management Science, 21(1)(2016)18-28.
[109] Ahmed Gara-Ali. Ordonnancement des tâches et de périodes d'indisponibilité de durée variable. Autre. Université Grenoble Alpes, 2016. Fran¸cais. 01492812 (2016).