Abstract
Although scheduling problems with machine availability have attracted many researchers’ attention, most of the past studies are mainly focused on one or several prefixed machine maintenance activities. In this research, we assume that the time needed to perform one maintenance activity is an increasing linear function of the total processing time of the jobs that are processed after the machine’s last maintenance activity. We consider two scheduling problems with such maintenance requirement in this paper. The first problem is a parallel machine scheduling problem where the length of the time interval between any two consecutive maintenance activities is between two given positive numbers. The objective is to minimize the maintenance makespan, i.e., the completion time of the last finished maintenance. The second problem is a single machine scheduling problem where the length of the time interval between any two consecutive maintenance activities is fixed and the objective is to minimize the makespan, i.e., the completion time of the last finished job. We propose two approximation algorithms for the considered problems and analyze their performances.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Baase, S., & Gelder, A. V. (2000). Computer algorithms: introduction to design and analysis (3rd ed.). Massachusetts: Addison-Wesley.
Coffman, Jr., E. G., Garey, M. R., & Johnson, D. S. (1978). An application of bin-packing to multiprocessor scheduling. SIAM Journal on Computing, 7, 1–17.
Coffman, Jr., E. G., Garey, M. R., & Johnson, D. S. (1997). Approximation algorithms for bin packing: a survey. In D. S. Hochbaum (Ed.), Approximation algorithms for NP-hard problems (pp. 46–93). Boston: PWS.
Graham, R. L. (1966). Bounds for certain multiprocessor anomalies. Bell System Technical Journal, 45, 1563–1581.
Graham, R. L., Lawer, E. L., Lenstra, J. K., & Rinnooy Kan, A. H. G. (1979). Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics, 5, 287–326.
Ji, M., He, Y., & Cheng, T. C. E. (2007). Single-machine scheduling with periodic maintenance to minimize makespan. Computers & Operations Research, 34, 1764–1770.
Lee, C. Y. (2004). Machine scheduling with availability constraints. In J. Y.-T. Leung (Ed.), Handbook of scheduling: algorithms, models, and performance analysis. Boca Raton: Chapman & Hall/CRC (Chap. 22).
Sanlaville, E., & Schmidt, G. (1998). Machine scheduling with availability constraints. Acta Informatica, 35, 795–811.
Schmidt, G. (2000). Scheduling with limited machine availability. European Journal of Operational Research, 121, 1–15.
Simchi-Levi, D. (1994). New worst-case results for the bin packing problem. Naval Research Logistics, 41, 579–585.
Xu, D. H., Sun, K. B., & Li, H. X. (2008). Parallel machine scheduling with almost periodic maintenance and non-preemptive jobs to minimize makespan. Computers & Operations Research, 35, 1344–1349.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Xu, D., Yin, Y. & Li, H. Scheduling jobs under increasing linear machine maintenance time. J Sched 13, 443–449 (2010). https://doi.org/10.1007/s10951-010-0182-0
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10951-010-0182-0