×

A two-stage coupled algorithm for an integrated maintenance planning and flowshop scheduling problem with deteriorating machines. (English) Zbl 1328.90031

Summary: We address a novel integrated maintenance and production scheduling problem in a multi-machine and multi-period production system, considering maintenance as a long-term decision. Deterioration of machines over time decreases production capacity. Since maintenance activities not only improve machine conditions, increasing production capacity, but also take time that cannot be used for production, the challenge is to assign maintenance to periods and to schedule maintenance and production activities within each period to minimize the combined cost of maintenance and lost production over the planning horizon. Motivated by logic-based Benders decomposition, we design an integrated two-stage algorithm to solve the problem. The first stage assigns maintenance to machines and time periods, abstracting the scheduling problem, while the second stage creates a schedule for the current time period. The first stage is then re-solved using feedback from the schedule. This iteration between maintenance planning and scheduling continues until the solution costs in two stages converge. The integrated approach models the interdependencies between maintenance and scheduling decisions in highly coupled processes such as wafer fabrication in the semiconductor manufacturing. Our results demonstrate that the benefit of integrated decision making increases when maintenance is less expensive relative to lost production cost and that a longer horizon for maintenance planning is beneficial when maintenance cost increases.

MSC:

90B25 Reliability, availability, maintenance, inspection in operations research
90B35 Deterministic scheduling theory in operations research
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aggoune, R. (2004). Minimizing the makespan for the flow shop scheduling problem with availability constraints. European Journal of Operational Research, 153, 534-543. · Zbl 1099.90536 · doi:10.1016/S0377-2217(03)00261-3
[2] Aghezzaf, E., & Najid, N. M. (2008). Integrated production planning and preventive maintenance in deteriorating production systems. Information Sciences, 178, 3382-3392. · Zbl 1142.90365 · doi:10.1016/j.ins.2008.05.007
[3] Akturk, M. S., Ghosh, J. B., & Gunes, E. D. (2004). Scheduling with tool changes to minimize total completion time: Basic results and SPT performance. European Journal of Operational Research, 157, 784-790. · Zbl 1067.90038 · doi:10.1016/S0377-2217(03)00232-7
[4] Allaoui, H., & Artiba, A. (2004). Integrating simulation and optimization to schedule a hybrid flow shop with maintenance constraints. Computers and Industrial Engineering, 47, 431-450. · doi:10.1016/j.cie.2004.09.002
[5] Allaoui, H., & Artiba, A. (2006). Scheduling two-stage hybrid flow shop with availability constraints. Computers and Operations Research, 33, 1399-1419. · Zbl 1126.90017 · doi:10.1016/j.cor.2004.09.034
[6] Aramon Bajestani, M., Banjevic, D., & Beck, J. C. (2014). Integrated maintenance planning and production scheduling with Markovian deteriorating machine conditions. International Journal of Production Research, 52, 7377-7400. · doi:10.1080/00207543.2014.931609
[7] Aramon Bajestani, M., & Beck, J. C. (2012). Minimizing the number of late jobs in a flow shop with processing times dependent on maintenance. In Technical Report MIE-OR-TR2012-03, Department of Mechanical & Industrial Engineering, University of Toronto. · Zbl 1276.68040
[8] Aramon Bajestani, M., & Beck, J. C. (2013). Scheduling a dynamic aircraft repair shop with limited repair resources. Journal of Artificial Intelligence Research, 47, 35-70. · Zbl 1276.68040
[9] Beck, J. C. (2010). Checking-up on branch-and-check. In Proceedings of the Sixteenth International Conference on Principles and Practice of Constraint Programming (CP2010) (pp. 84-98). · Zbl 1171.90392
[10] Beck, J. C., & Wilson, N. (2007). Proactive algorithms for job shop scheduling with probabilistic durations. Journal of Artificial Intelligence Research, 28, 183-232. · Zbl 1182.68023
[11] Benders, J. (1962). Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik, 4, 238-252. · Zbl 0109.38302 · doi:10.1007/BF01386316
[12] Blau, J. (2003). News analysis: Europe’s semiconductor makers are back in the game. IEEE Specrnim Magazine, 18-19.
[13] Budai, G., Huisman, D., & Dekker, R. (2006). Scheduling preventive railway maintenance activities. Journal of the Operational Research Society, 57, 1035-1044. · Zbl 1171.90392 · doi:10.1057/palgrave.jors.2602085
[14] Cai, X., Sun, A., & Zhou, X. (2003). Stochastic scheduling with preemptive-repeat machine breakdowns to minimize the expected weighted flow time. Probability in the Engineering and Information Sciences, 17, 467-485. · Zbl 1176.90258
[15] Cai, X., Sun, X., & Zhou, X. (2004). Stochastic scheduling subject to machine breakdowns: The preemptive-repeat model with discounted reward and other criteria. Naval Research Logistics, 51, 800-817. · Zbl 1075.90035 · doi:10.1002/nav.20024
[16] Cai, X., & Vairaktarakis, G. L. (2012). Coordination of outsourced operations at a third-party facility subject to booking, overtime, and tardiness costs. Operations Research, 60, 1436-1450. · Zbl 1262.90062 · doi:10.1287/opre.1120.1110
[17] Cassady, C. R., & Kutanoglu, E. (2003). Minimizing job tardiness using integrated preventive maintenance planning and production scheduling. IIE Transactions, 35, 503-513. · doi:10.1080/07408170304416
[18] Cassady, C. R., & Kutanoglu, E. (2005). Integrating preventive maintenance planning and production scheduling for a single machine. IEEE Transactions on Reliability, 54, 304-309. · doi:10.1109/TR.2005.845967
[19] Chen, J. S. (2006). Single-machine scheduling with flexible and periodic maintenance. Journal of the Operational Research Society, 57, 703-710. · Zbl 1121.90052 · doi:10.1057/palgrave.jors.2602043
[20] Cho, I. D., & Parlar, M. (1991). A survey of maintenance models for multi-unit systems. European Journal of Operational Research, 51, 1-23. · doi:10.1016/0377-2217(91)90141-H
[21] Dekker, R., Wildeman, R. E., & van der Duyn Schouten, F. A. (1997). A review of multi-component maintenance models with economic dependence. Mathematical Methods of Operations Research, 45, 411-435. · Zbl 0893.90071 · doi:10.1007/BF01194788
[22] Dekker, R., Wildeman, R. E., & van Egmond, R. (1996). Joint replacement in an operational planning phase. European Journal of Operational Research, 91, 74-88. · Zbl 0947.90512 · doi:10.1016/0377-2217(94)00363-7
[23] Fazel-Zarandi, M. M., & Beck, J. C. (2011). Using logic-based Benders decomposition to solve the capacity- and distance-constrained plant location problem. INFORMS Journal on Computing, 24, 399-415.
[24] Geoffrion, A. M., & Graves, G. W. (1974). Multicommodity distribution system design by Benders decomposition. Management Science, 20, 822-844. · Zbl 0304.90122 · doi:10.1287/mnsc.20.5.822
[25] Grigoriev, A., van de Klundert, J., & Spieksma, F. C. R. (2006). Modeling and solving the periodic maintenance problem. European Journal of Operational Research, 172, 783-797. · Zbl 1111.90028 · doi:10.1016/j.ejor.2004.11.013
[26] Gupta, J. N. D., & Stafford, E. F, Jr. (2006). Flowshop scheduling research after five decades. European Journal of Operational Research, 169, 699-711. · Zbl 1079.90001 · doi:10.1016/j.ejor.2005.02.001
[27] Hadidi, L. A., Al-Turki, U. M., & Rahim, M. A. (2011). An integrated cost model for production scheduling and perfect maintenance. International Journal of Mathematics in Operational Research, 3, 395-413. · Zbl 1217.90105 · doi:10.1504/IJMOR.2011.040875
[28] Hadidi, L. A., Al-Turki, U. M., & Rahim, M. A. (2012a). Integrated models in production planning and scheduling, maintenance and quality: A review. International Journal of Industrial and Systems Engineering, 10, 21-50. · doi:10.1504/IJISE.2012.044042
[29] Hadidi, L. A., Al-Turki, U. M., & Rahim, M. A. (2012b). Joint job scheduling and preventive maintenance on a single machine. International Journal of Operational Research, 13, 174-184. · Zbl 1362.90189 · doi:10.1504/IJOR.2012.045185
[30] Hooker, J. (2005). A hybrid method for planning and scheduling. Constraints, 10, 385-401. · Zbl 1122.90054 · doi:10.1007/s10601-005-2812-2
[31] Hooker, J. (2007). Planning and scheduling by logic-based Benders decomposition. Operations Research, 55, 588-602. · Zbl 1167.90512 · doi:10.1287/opre.1060.0371
[32] Hooker, J., & Ottosson, G. (2003). Logic-based Benders decomposition. Mathematical Programming, 96, 33-60. · Zbl 1023.90082
[33] Hooker, J., & Yan, H. (1995). Logic circuit verification by Benders decomposition. In V. Saraswat & P. Van Hentenryck (Eds.), Principles and Practice of Constraint Programming: The Newport Papers, Chap. 15 (pp. 267-288). Cambridge, MA: MIT Press. · Zbl 0983.90020
[34] Ji, M., He, Y., & Cheng, T. C. E. (2007). Single machine scheduling with periodic maintenance to minimize makespan. Computers and Operations Research, 34, 1764-1770. · Zbl 1159.90404 · doi:10.1016/j.cor.2005.05.034
[35] Kellerer, H., Rustogi, K., & Strusevich, A. (2013). Approximation schemes for scheduling on a single machine subject to cumulative deterioration and maintenance. Journal of Scheduling, 16, 675-683. · Zbl 1280.90055 · doi:10.1007/s10951-012-0287-8
[36] Kim, B. S., & Ozturkoglu, Y. (2013). Scheduling a single machine with multiple preventive maintenance activities and position based deteriorations using genetic algorithms. International Journal of Advanced Manufacturing Technology, 67, 1127-1137. · doi:10.1007/s00170-012-4553-x
[37] Kovacs, A., & Beck, J. C. (2007). Single-machine scheduling with tool changes: A constraint-based approach. In Proceedings of the 26th Workshop of the UK Planning and Scheduling Special Interest Group (pp. 71-78). · Zbl 0947.90512
[38] Kumar, S., & Kumar, P. R. (2001). Queueing network models in the design and analysis of semiconductor wafer fabs. IEEE Transactions on Robotics and Automation, 17, 548-561. · doi:10.1109/70.964657
[39] Kuo, W. H., & Yang, D. L. (2008). Minimizing the makespan in a single-machine scheduling problem with the cyclic process of an aging effect. Journal of the Operational Research Society, 59, 416-420. · Zbl 1145.90387 · doi:10.1057/palgrave.jors.2602363
[40] Kuo, Y., & Chang, Z. (2007). Integrated production scheduling and preventive maintenance planning for a single machine under a cumulative damage failure process. Naval Research Logistics, 54, 602-614. · Zbl 1151.90387 · doi:10.1002/nav.20232
[41] Lee, C. Y. (1996). Machine scheduling with an availability constraint. Journal of Global Optimization, 9, 395-416. · Zbl 0870.90071 · doi:10.1007/BF00121681
[42] Lee, C. Y. (1999). Two-machine flow shop scheduling with availability constraints. European Journal of Operational Research, 114, 420-429. · Zbl 0971.90031 · doi:10.1016/S0377-2217(97)00452-9
[43] Lee, C-Y, Handbook of scheduling: Algorithms, models and performance analysis (2004), London · Zbl 1103.90002
[44] Lee, C. Y., & Leon, V. J. (2001). Machine scheduling with a rate-modifying activity. European Journal of Operational Research, 128, 119-128. · Zbl 0983.90020 · doi:10.1016/S0377-2217(99)00066-1
[45] Lenstra, J. K., Rinnooy Kan, A. H. G., & Brucker, P. (1977). Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1, 342-362.
[46] Liao, C. J., & Chen, W. J. (2003). Single-machine scheduling with periodic maintenance and non-resumable jobs. Computers and Operations Research, 30, 1335-1347. · Zbl 1037.90031 · doi:10.1016/S0305-0548(02)00074-6
[47] Lodree, E. J, Jr, & Geiger, C. D. (2010). A note on the optimal sequence position for a rate-modifying activity under simple linear deterioration. European Journal of Operational Research, 201, 644-648. · Zbl 1192.90076 · doi:10.1016/j.ejor.2009.03.027
[48] Ma, Y., & Chu, C. (2010). A survey of scheduling with deterministic machine availability constraints. Computers and Industrial Engineering, 58, 199-211. · doi:10.1016/j.cie.2009.04.014
[49] McCall, J. J. (1965). Maintenance policies for stochastically failing equipment. Management Science, 11, 493-524. · Zbl 0129.11913 · doi:10.1287/mnsc.11.5.493
[50] Mönch, L., Fowler, J. W., Dauzére-Pèrés, S., Mason, S. J., & Rose, O. (2011). A survey of problems, solution techniques, and future challenges in scheduling semiconductor manufacturing operations. Journal of Scheduling, 14, 583-599. · doi:10.1007/s10951-010-0222-9
[51] Mosheiov, G., & Sarig, A. (2009). Scheduling a maintenance activity and due-window assignment on a single machine. Computers and Operations Research, 36, 2541-2545. · Zbl 1179.90146 · doi:10.1016/j.cor.2008.10.007
[52] Mosheiov, G., & Sidney, J. B. (2010). Scheduling a deteriorating maintenance activity on a single machine. Journal of the Operational Research Society, 61, 882-887. · Zbl 1193.90106 · doi:10.1057/jors.2009.5
[53] Naderi, B., Zandieh, M., & Fatemi Ghomi, S. M. T. (2009). A study on integrating sequence dependent setup time flexible flow lines and preventive maintenance scheduling. Journal of Intelligent Manufacturing, 20, 683-694. · Zbl 0893.90071
[54] Nicolai, R. P., & Dekker, R. (2008). Optimal maintenance of multi-component systems: A review. Complex system maintenance handbook. Berlin: Springer Series in Reliability Engineering. · Zbl 1122.90054
[55] Pinedo, M. (2002). Scheduling, theory, algorithms, and systems (2nd ed.). New Jersey: Prentice Hall. · Zbl 1145.90394
[56] Pintelon, L.; Parodi-Herz, A., Maintenance: An evolutionary perspective (2008), Berlin
[57] Ramíez-Hernández, J. A., & Fernández-Gaucherand, E. (2003). An algorithm to convert wafer to calendar-based preventive maintenance schedules for semiconductor manufacturing systems. In Proceedings of the 42nd IEEE Conference on Decision and Control (pp. 5926-5931). · Zbl 1182.68023
[58] Ruiz, R., García-Díaz, J. C., & Maroto, C. (2007). Considering scheduling and preventive maintenance in the flowshop sequencing problem. Computers and Operations Research, 34, 3314-3330. · Zbl 1128.90031 · doi:10.1016/j.cor.2005.12.007
[59] Rustogi, K., & Strusevich, A. (2012). Single machine scheduling with general positional deterioration and rate-modifying maintenance. Omega, 40, 791-804. · Zbl 1231.90222
[60] Schmidt, G. (2000). Scheduling with limited machine availability. European Journal of Operational Research, 121, 1-15. · Zbl 0959.90023 · doi:10.1016/S0377-2217(98)00367-1
[61] Shabtay, D. (2012). The just-in-time scheduling problem in a flowshop scheduling system. European Journal of Operational Research, 216, 521-532. · Zbl 1237.90097 · doi:10.1016/j.ejor.2011.07.053
[62] Sloan, T. W. (2004). A periodic review production and maintenance model with random demand, deteriorating equipment, and binomial yield. Journal of Operational Research Society, 55, 647-656. · Zbl 1060.90012 · doi:10.1057/palgrave.jors.2601725
[63] Sloan, T. W. (2008). Simultaneous determination of production and maintenance schedules using in-line equipment condition and yield information. Naval Research Logistics, 55, 117-129. · Zbl 1152.90409 · doi:10.1002/nav.20270
[64] Uzsoy, R., Lee, C. Y., & Martin-Vega, L. A. (1992). A review of production planning and scheduling models in semiconductor industry, Part I: System characteristics, performance evaluation and production planning. IIE Transactions, 24, 47-60. · doi:10.1080/07408179208964233
[65] Wang, H. (2002). A survey of maintenance policies of deteriorating systems. European Journal of Operational Research, 139, 469-489. · Zbl 0995.90020 · doi:10.1016/S0377-2217(01)00197-7
[66] Xu, D., Yin, Y., & Li, H. (2010). Scheduling jobs under increasing linear machine maintenance time. Journal of Scheduling, 13, 443-449. · Zbl 1231.90222 · doi:10.1007/s10951-010-0182-0
[67] Yang, S. J., & Yang, D. L. (2010). Minimizing the makespan on single-machine scheduling with aging effects and variable maintenance activities. Omega, 38, 528-533. · doi:10.1016/j.omega.2010.01.003
[68] Yao, X., Fernández-Gaucherand, E., Fu, M. C., & Marcus, S. I. (2004). Optimal preventive maintenance scheduling in semiconductor manufacturing. IEEE Transactions on Semiconductor Manufacturing, 17, 345-356. · doi:10.1109/TSM.2004.831948
[69] Yu, X., Zhang, Y., & Steiner, G. (2014). Single-machine scheduling with periodic maintenance to minimize makespan revisited. Journal of Scheduling, 17, 263-270. · Zbl 1297.68045 · doi:10.1007/s10951-013-0350-0
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.