×

Machine scheduling performance with maintenance and failure. (English) Zbl 1149.90341

Summary: In manufacturing control, machine scheduling research has mostly dealt with problems either without maintenance or with deterministic maintenance when no failure can occur. This can be unrealistic in practical settings. In this work, an experimental model is developed to evaluate the effect of corrective and preventive maintenance schemes on scheduling performance in the presence of machine failure where the scheduling objective is to minimize schedule duration. We show that neither scheme is clearly superior, but that the applicability of each depends on several system parameters as well as the scheduling environment itself. Further, we show that parameter values can be chosen for which preventive maintenance does better than corrective maintenance. The results provided in this study can be useful to practitioners and to system or machine administrators in manufacturing and elsewhere.

MSC:

90B35 Deterministic scheduling theory in operations research
90B25 Reliability, availability, maintenance, inspection in operations research

Software:

DIMACS
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Albers, S.; Schroder, B., An experimental study of online scheduling algorithms, ACM Journal of Experimental Algorithmics, 7, 3, 123-154 (2002)
[2] Baev, J. D.; Meleis, W. M.; Eichenberger, A., An experimental study of algorithms for weighted completion time scheduling, Algorithmica, 33, 34-51 (2002) · Zbl 0994.68175
[3] Barr, R. S.; Golden, B. L.; Kelly, J. P.; Resende, M. G.C.; Stewart, W. R., Designing and reporting on computational experiments with heuristic methods, Journal of Heuristics, 1, 1, 9-32 (2001) · Zbl 0853.68154
[4] J.L. Bentley, D.S. Johnson, T. Leighton, C.C. McGeoch, An experimental study of bin packing, in: Proc. 21st Annual Allerton Conference on Communication, Control, and Computing, 1983, pp. 51-60; J.L. Bentley, D.S. Johnson, T. Leighton, C.C. McGeoch, An experimental study of bin packing, in: Proc. 21st Annual Allerton Conference on Communication, Control, and Computing, 1983, pp. 51-60
[5] Coffman, E. G.; Garey, M. R.; Johnson, D. S., An application of bin-packing to multiprocessor scheduling, SIAM Journal on Computing, 7, 1-17 (1978) · Zbl 0374.68032
[6] Guo, Y.; Lim, A.; Rodrigues, B.; Yu, S., Minimizing total flow time in a single machine environment with release time: Experimental analysis, Computers and Industrial Engineering, 47, 123-140 (2004)
[7] Graham, R. L., Bounds on multiprocessing timing anomalies, SIAM Journal of Applied Mathematics, 17, 263-269 (1969) · Zbl 0188.23101
[8] Hooker, J. N., Needed: An empirical science of algorithms, Journal of Operations Research, 42, 201-212 (1994) · Zbl 0805.90119
[9] Hooker, J. N., Testing heuristics: We have it all wrong, Journal of Heuristics, 1, 1, 33-42 (1996) · Zbl 0853.68155
[10] Johnson, D. S., A theoretician’s guide to the experimental analysis of algorithms, (Goldwasser, M. H.; Johnson, D. S.; McGeoch, C. C., Fifth and Sixth DIMACS Implementation Challenges (2002), American Mathematical Society: American Mathematical Society Providence) · Zbl 1103.68997
[11] M. Kaspi, B. Montreuil, On the scheduling of identical parallel processes with arbitrary initial processor available time, Research report 88-12, School of Industrial Engineering, Purdue University, 1988; M. Kaspi, B. Montreuil, On the scheduling of identical parallel processes with arbitrary initial processor available time, Research report 88-12, School of Industrial Engineering, Purdue University, 1988
[12] Lee, C. Y.; Massey, J. D., Multiprocessor scheduling: Combining LPT and MULTIFIT, Discrete Applied Mathematics, 20, 233-242 (1988) · Zbl 0655.90036
[13] Lee, C. Y., Machine scheduling with an availability constraint, Journal of Global Optimization, 9, 395-416 (1996) · Zbl 0870.90071
[14] Lee, C. Y., Parallel machines scheduling with nonsimultaneous machine available time, Journal of Discrete Applied Mathematics, 30, 53-61 (1991) · Zbl 0722.90032
[15] Lee, C. Y.; Liman, S. D., Single machine flow-time scheduling with scheduled maintenance, Acta Informatica, 29, 375-382 (1992) · Zbl 0738.68043
[16] McGeoch, C. C.; Moret, B. M.E., How to present a paper on experimental work with algorithms, SIGACT News, 30, 4, 85-90 (1999)
[17] McGeoch, C. C., Experimental analysis of algorithms, Notices of the American Mathematical Society, 48, 3, 304-311 (2001) · Zbl 0981.68187
[18] Moret, B. M.E., Towards a discipline of experimental algorithmics, (Goldwasser, M. H.; Johnson, D. S.; McGeoch, C. C., Fifth and Sixth DIMACS Implementation Challenges (2002), American Mathematical Society: American Mathematical Society Providence) · Zbl 1103.68972
[19] Pinedo, M., Scheduling: Theory, Algorithms, and Systems (1995), Prentice Hall: Prentice Hall New Jersey · Zbl 1145.90393
[20] 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
[21] M.W.P. Savelsbergh, R.N. Uma, J. Wein, An experimental study of LP-based approximation algorithms for scheduling problems in: Proceedings of 9th Annual ACM-SIAM Symposium on Discrete Algorithms, 1998, pp. 453-462; M.W.P. Savelsbergh, R.N. Uma, J. Wein, An experimental study of LP-based approximation algorithms for scheduling problems in: Proceedings of 9th Annual ACM-SIAM Symposium on Discrete Algorithms, 1998, pp. 453-462 · Zbl 0938.68534
[22] Schmidt, G., Scheduling independent tasks with deadlines on semi-identical processors, Journal of Operational Research Society, 39, 271-277 (1988) · Zbl 0657.90051
[23] A. Turkcan, Machine Scheduling with Availability Constraints. Available at: benli.bcc.bilkent.edu.tr/ ie672/docs/present/turkcan.ps; A. Turkcan, Machine Scheduling with Availability Constraints. Available at: benli.bcc.bilkent.edu.tr/ ie672/docs/present/turkcan.ps
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.