zbMATH — the first resource for mathematics

Minimizing the total completion time in single-machine scheduling with aging/deteriorating effects and deteriorating maintenance activities. (English) Zbl 1205.90141
Summary: In a real manufacturing system, a machine may need multiple maintenance activities to improve its production efficiency due to the effects of aging or deteriorating. This paper considers scheduling with aging or deteriorating effects and deteriorating maintenance activities simultaneously on a single machine. We assume that the machine may be subject to several maintenance activities during the planning horizon. However, due to the restriction of budget of maintenance, the upper bound of the maintenance frequency on the machine is assumed to be known in advance. Moreover, we assume that the duration of each maintenance activity depends on the running time of the machine. The objective is to find jointly the optimal maintenance frequencies, the optimal maintenance positions, and the optimal job sequence for minimizing the total completion time. We show that all the problems studied are polynomially solvable.

90B35 Deterministic scheduling theory in operations research
90B25 Reliability, availability, maintenance, inspection in operations research
Full Text: DOI
[1] Schmidt, G., Scheduling with limited machine availability, European journal of operational research, 121, 1-15, (2000) · Zbl 0959.90023
[2] Ma, Y.; Chu, C.; Zuo, C., A survey of scheduling with deterministic machine availability constraints, Computers & industrial engineering, 58, 199-211, (2010)
[3] Alidaee, B.; Womer, N.K., Scheduling with time dependent processing times: review and extensions, Journal of the operational research society, 50, 711-720, (1999) · Zbl 1054.90542
[4] Cheng, T.C.E.; Ding, O.; Lin, B.M.T., A concise survey of scheduling with time-dependent processing times, European journal of operational research, 152, 1-13, (2004) · Zbl 1030.90023
[5] Bachman, A.; Janiak, A., Scheduling jobs with position-dependent processing times, Journal of the operational research society, 55, 257-264, (2004) · Zbl 1095.90033
[6] Janiak, A.; Kovalyov, M.Y., Scheduling deteriorating jobs, (), 12-25 · Zbl 1144.90381
[7] Janiak, A.; Rudek, R., Scheduling problems with position dependent job processing times, (), 26-32
[8] Biskup, D., A state-of-the-art review on scheduling with learning effects, European journal of operational research, 188, 315-329, (2008) · Zbl 1129.90022
[9] Janiak, A.; Rudek, R., Experience based approach to scheduling problems with the learning effect, IEEE transactions on systems, man, and cybernetics—part A, 39, 344-357, (2009)
[10] Gawiejnowicz, S., Time-dependent scheduling, (2008), Springer-Verlag Inc. New York · Zbl 1155.90004
[11] Wu, C.-C.; Lee, W.-C., Scheduling linear deteriorating jobs to minimize makespan with an availability constraint on a single machine, Information processing letters, 87, 89-93, (2003) · Zbl 1161.68367
[12] Ji, M.; He, Y.; Cheng, T.C.E., Scheduling linear deteriorating jobs with an availability constraint on a single machine, Theoretical computer science, 362, 115-126, (2006) · Zbl 1100.68009
[13] Lee, W.-C.; Wu, C.-C., Multi-machine scheduling with deteriorating jobs and scheduled maintenance, Applied mathematical modelling, 32, 362-373, (2008) · Zbl 1187.90134
[14] Low, C.; Hsu, C.-J.; Su, C.-T., Minimizing the makespan with an availability constraint on a single machine under simple linear deterioration, Computers and mathematics with applications, 56, 257-265, (2008) · Zbl 1145.90389
[15] Lodree, E.J.; Geiger, C.D., A note on the optimal sequence position for a rate-modifying activity under simple linear deterioration, European journal of operational research, 201, 644-648, (2010) · Zbl 1192.90076
[16] Gawiejnowicz, S.; Kononov, A., Complexity and approximability of scheduling resumable proportionally deteriorating jobs, European journal of operational research, 200, 305-308, (2010) · Zbl 1183.90170
[17] Yang, S.-J.; Yang, D.-L.; Cheng, T.C.E., Single-machine due-window assignment and scheduling with job-dependent aging effects and deteriorating maintenance, Computers & operations research, 37, 1510-1514, (2010) · Zbl 1183.90203
[18] Gawiejnowicz, S., Scheduling deteriorating jobs subject to job or machine availability constraints, European journal of operational research, 180, 472-478, (2007) · Zbl 1114.90034
[19] Kuo, W.-H.; Yang, D.-L., 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, (2008) · Zbl 1145.90387
[20] Zhan, C.-L.; Tang, H.-Y., Single machine scheduling with general job-dependent aging effect and maintenance activities to minimize makespan, Applied mathematical modelling, 34, 837-841, (2010) · Zbl 1185.90106
[21] Yang, S.-J.; Yang, D.-L., Minimizing the makespan on single-machine scheduling with aging effect and variable maintenance activities, Omega, 38, 528-533, (2010)
[22] Kubzin, M.A.; Strusevich, V.A., Two-machine flow shop no-wait scheduling with machine maintenance, 4OR: A quarterly journal of operations research, 3, 303-313, (2005) · Zbl 1134.90387
[23] Kubzin, M.A.; Strusevich, V.A., Planning machine maintenance in two-machine shop scheduling, Operation research, 54, 789-800, (2006) · Zbl 1167.90669
[24] Mosheiov, G.; Sidney, J.B., Scheduling a deteriorating maintenance activity on a single machine, Journal of the operational research society, 61, 882-887, (2010) · Zbl 1193.90106
[25] Mosheiov, G., Parallel machine scheduling with a learning effect, Journal of the operational research society, 52, 1165-1169, (2001) · Zbl 1178.90159
[26] Graham, R.L.; Lawler, E.L.; Lenstra, J.K.; Rinnooy Kan, A.H.G., Optimization and approximation in deterministic sequencing and scheduling: a survey, Annals of discrete mathematics, 5, 287-326, (1979) · Zbl 0411.90044
[27] Hardy, G.H.; Littlewood, J.E.; Polya, G., Inequalities, (1967), Cambridge University Press London · Zbl 0634.26008
[28] Mosheiov, G.; Sidney, J.B., Scheduling with general job-dependent learning curves, European journal of operations research, 147, 665-670, (2003) · Zbl 1037.90529
[29] Biskup, D., Single-machine scheduling with learning considerations, European journal of operational research, 115, 173-178, (1999) · Zbl 0946.90025
[30] Papadimitriou, C.H.; Steiglitz, K., Combinatorial optimization: algorithms and complexity, (1982), Prentice-Hall New Jersey · Zbl 0503.90060
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.