A note on scheduling on a single processor with speed dependent on a number of executed jobs. (English) Zbl 0875.68080

Summary: In this note the makespan scheduling problem on a single processor is considered. The speed of a processor depends on the number of already processed jobs and is described by a function. Several polynomial-time algorithms for finding an optimal schedule are given.


68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
68W10 Parallel algorithms in computer science
Full Text: DOI


[1] Błazewicz, J.; Ecker, K.; Schmidt, G.; Wȩglarz, J., Scheduling in Computer and Manufacturing Systems (1993), Springer: Springer Berlin · Zbl 0767.90033
[2] Browne, S.; Yechiali, U., Scheduling deteriorating jobs on a single processor, Oper. Res., 38, 495-498 (1990) · Zbl 0703.90051
[3] Dror, M.; Stern, H. J.; Lenstra, J. K., Parallel machine scheduling: Processing rates dependent on number of jobs in operation, Management Sci., 33, 1001-1009 (1987) · Zbl 0636.90044
[4] Gawiejnowicz, S.; Pankowska, L., Scheduling jobs with varying processing times, Inform. Process. Lett., 54, 175-178 (1995) · Zbl 0875.68421
[5] Gupta, J. N.D.; Gupta, S. K., Single facility scheduling with nonlinear processing times, Comput. and Ind. Eng., 14, 387-393 (1988)
[6] Hardy, G. H.; Littlewood, J. E.; Polya, G., Inequalities (1934), University Press · Zbl 0010.10703
[7] Ho, K. I.-J.; Leung, J. Y.-T.; Wei, W.-D., Complexity of scheduling tasks with time-dependent execution times, Inform. Process. Lett., 48, 315-320 (1993) · Zbl 0942.68508
[8] Kubiak, W.; van de Velde, S. L., Scheduling deteriorating jobs to minimize makespan, (Rept. LPOM-94-12 (1994), Laboratory of Production and Operations Management, Dept. of Mechanical Engineering, University of Twente) · Zbl 0936.90026
[9] Mosheiov, G., Scheduling jobs under simple linear deterioration, Comput. Oper. Res., 21, 653-659 (1994) · Zbl 0810.90074
[10] Wȩglarz, J., Multiprocessor scheduling with memory allocation — A deterministic approach, IEEE Trans. Comput., 29, 703-710 (1980) · Zbl 0441.68034
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.