Scheduling unit-time tasks with integer release times and deadlines. (English) Zbl 0508.68023


68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI


[1] Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., The Design and Analysis of Computer Algorithms (1974), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0286.68029
[2] Blasewicz, J., Simple algorithms for multiprocessor scheduling to meet deadlines, Inform. Process. Lett., 6, 5, 162-164 (1977) · Zbl 0381.68038
[3] Gabow, H. N.; Tarjan, R. E., A linear-time algorithm for a special case of disjoint set union, Boston. Boston, Proc. 15th ACM Symp. on Theory of Computing (1983), to appear
[4] Garey, M. R.; Johnson, D. S.; Simons, B. B.; Tarjan, R. E., Scheduling unit-time tasks with arbitrary release times and deadlines, SIAM J. Comput., 10, 2, 256-269 (1981) · Zbl 0472.68021
[5] Horowitz, E.; Sahni, S., Fundamentals of Data Structures (1976), Computer Science Press · Zbl 0408.68003
[6] Jackson, J. R., Scheduling a production line to minimize maximum tardiness, (Res. Rept. 43 (1955), Management Science Research Project, UCLA)
[7] Lang, T.; Fernandez, E. B., Scheduling of unit-length independent tasks with execution constraints, Inform. Process. Lett., 4, 4, 95-98 (1976) · Zbl 0314.90044
[8] Simons, B., A fast algorithm for multiprocessor scheduling, Sycracuse, NY. Sycracuse, NY, Proc. 21st Symp. on Foundations of Computer Science, 50-53 (1980)
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.