×

Evaluation of the expected makespan of a set of non-resumable jobs on parallel machines with stochastic failures. (English) Zbl 1357.90041

Summary: In this paper we consider a production process at operative level on \(m\) identical parallel machines, which are subject to stochastic machine failures. To avoid long downtime of the machines, caused by unexpected failures, preventive maintenance activities are planned and conducted, but if a failure could not be averted a corrective maintenance has to be performed. Both maintenance activities are assumed to restore the machine to be “as good as new”. The maintenance activities, the number of jobs and their allocation to machines as well as their sequence have a large impact on the performance of the production process and the delivery dates.
We study an order of \(n\) jobs, scheduled for a frozen period on the machines. It is assumed that jobs, interrupted by machine failure, have to get repeated right after the corrective maintenance is finished (non-resumable case). We first derive an exact formula for the expected makespan. Since the exact evaluation of a schedule is highly complex, we propose two approximations for the expected makespan. The excellent performance of the approximations is illustrated in a numerical study.

MSC:

90B25 Reliability, availability, maintenance, inspection in operations research
90B35 Deterministic scheduling theory in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adiri, I.; Bruno, J.; Frostig, E.; Rinnooy Kan, A. H.G., Single machine flow-time scheduling with a single breakdown, ACTA Informatica, 26, 679-696 (1989) · Zbl 0657.68033
[2] Berrichi, A.; Amodeo, L.; Yalaoui, F.; Châtelet, E.; Mezghiche, M., Bi-objective optimization algorithms for joint production and maintenance scheduling: Application to the parallel machine problem, Journal of Intelligent Manufacturing, 20, 389-400 (2009)
[3] Cassady, C. R.; Kutanoglu, E., Minimizing job tardiness using integrated preventive maintenance planning and production scheduling, IIE Transactions, 35, 503-513 (2003)
[4] Cassady, C. R.; Kutanoglu, E., Integrating preventive maintenance planning and production scheduling for a single machine, IEEE Transactions on Reliability, 54, 2, 304-309 (2005)
[5] Chen, J., Scheduling of nonresumable jobs and flexible maintenance activities on a single machine to minimize makespan, European Journal of Operational Research, 190, 90-102 (2008) · Zbl 1146.90028
[6] Cui, W.; Lu, Z.; Pan, E., Integrated production scheduling and maintenance policy for robustness in a single machine, Computers and Operations Research, 47, 81-91 (2014) · Zbl 1348.90247
[7] Garey, M. R.; Johnson, D. S., Computers and intractability: A guide to the theory of NP-completeness (1979), Freeman: Freeman NY · Zbl 0411.68039
[8] Graves, G. H.; Lee, C. Y., Scheduling maintenance and semiresumble jobs on a single machine, Naval Research Logistics, 46, 845-863 (1999) · Zbl 0931.90015
[9] Hadidi, L.; Al-Turki, U.; Rahim, A., Integrated models in production planning and scheduling, maintenance and quality: A review, International Journal of Industrial and Systems Engineering, 10, 1, 21-50 (2012)
[10] Kuo, Y.; Chang, Z., Integrated production scheduling and preventive maintenance planning for a single machine under a cumulative damage failure process, Naval Research Logistics, 54, 602-614 (2007) · Zbl 1151.90387
[11] Lee, C. Y., Machine scheduling with an availability constraint, Journal of Global Optimization, 9, 395-416 (1996) · Zbl 0870.90071
[12] Lee, C. Y.; Chen, Z. L., Scheduling of jobs and maintenance activities on parallel machines, Naval Research Logistics, 47, 61-67 (2000)
[13] Lee, C. Y.; Lin, C. S., Single-machine scheduling with maintenance and repair rate-modifying activities, European Journal of Operational Research, 135, 493-513 (2001) · Zbl 0989.90036
[14] Ma, Y.; Chu, C.; Zuo, C., A survey of scheduling with deterministic machine availability constraints, Computers & Industrial Engineering, 58, 199-211 (2010)
[15] Pandey, D.; Kulkarni, M.; Vrat, P., Joint consideration of production scheduling, maintenance and quality policies: A review and conceptual framework, International Journal of Advanced Operations Management, 2(1/2) (2010)
[16] Pandey, D.; Kulkarni, M.; Vrat, P., A methodology for joint optimization for maintenance planning, process quality and production scheduling, Computers & Industrial Engineering, 61, 1098-1106 (2011)
[17] Pinedo, M., Scheduling: Theory, algorithms, and systems (1995), Prentice-Hall: Prentice-Hall NJ · Zbl 1145.90393
[18] Qi, X.; Chen, T.; Tu, F., Scheduling the maintenance on a single machine, Journal of the Operational Research Society, 50, 1071-1078 (1999) · Zbl 1054.90550
[19] Sanlaville, E.; Schmidt, G., Machine scheduling with availability constraints, ACTA Informatica, 35, 795-811 (1998) · Zbl 0917.68018
[20] Schmidt, G., Scheduling with limited machine availability, European Journal of Operational Research, 121, 1-15 (2000) · Zbl 0959.90023
[21] Wang, H., A survey of maintenance policies of deteriorating systems, European Journal of Operational Research, 139, 469-489 (2002) · Zbl 0995.90020
[22] Xu, D.; Yin, Y.; Li, H., A note on “scheduling of nonresumable jobs and flexible maintenance activities on a single machine to minimize makespan”, European Journal of Operational Research, 197, 825-827 (2009) · Zbl 1159.68359
[23] Yulan, J.; Zuhua, J.; Wenrui, H., Multi-objective integrated optimization research on preventive maintenance planning and production scheduling for a single machine, International Journal of Advanced Manufacturing Technology, 39, 954-964 (2008)
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.