×

Partitioned EDF scheduling on a few types of unrelated multiprocessors. (English) Zbl 1291.68098

Summary: A polynomial-time approximation scheme (PTAS) is derived for the partitioned EDF scheduling of implicit-deadline sporadic task systems upon unrelated multiprocessor platforms that are comprised of a constant number of distinct types of processors. This generalizes earlier results showing the existence of polynomial-time approximation schemes for the partitioned EDF scheduling of implicit-deadline sporadic task systems on (1) identical multiprocessor platforms, and (2) unrelated multiprocessor platforms containing a constant number of processors.

MSC:

68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Andersson B, Raravi G, Bletsas K (2010) Assigning real-time tasks on heterogeneous multiprocessors with two unrelated types of processors. In: Proceedings of the real-time systems symposium, San Diego, CA. IEEE Comput Soc, Los Alamitos, pp 239–248 · Zbl 1291.68093
[2] Baruah S (2004) Partitioning real-time tasks among heterogeneous multiprocessors. In: Proceedings of the thirty-third annual international conference on parallel processing, Montreal, Canada. IEEE Comput Soc, Los Alamitos, pp 467–474
[3] Birkhoff G (1946) Tres observaciones sobre el algebra lineal. Rev Univ Nac Tucumán Ser A, Mat Fis Teor, 5, 147–151 · Zbl 0060.07906
[4] Chattopadhyay B, Baruah S (2011) A lookup-table driven approach to partitioned scheduling. In: Proceedings of the IEEE real-time technology and applications symposium (RTAS), Chicago. IEEE Comput Soc, Los Alamitos
[5] Dantzig GB (1963) Linear programming and extensions. Princeton University Press, Princeton · Zbl 0108.33103
[6] Hochbaum D, Shmoys D (1987) Using dual approximation algorithms for scheduling problems: theoretical and practical results. J ACM 34(1):144–162
[7] Hochbaum D, Shmoys D (1988) A polynomial time approximation scheme for scheduling on uniform processors using the dual approximation approach. SIAM J Comput 17(3):539–551 · Zbl 0647.68040
[8] Jansen K, Porkolab L (1999) Improved approximation schemes for scheduling unrelated parallel machines. In: Proceedings of the thirty-first annual ACM symposium on theory of computing. ACM, New York, pp 408–417 · Zbl 1082.90525
[9] Karmakar N (1984) A new polynomial-time algorithm for linear programming. Combinatorica 4:373–395 · Zbl 0557.90065
[10] Khachiyan L (1979) A polynomial algorithm in linear programming. Dokl Akad Nauk SSSR 244:1093–1096 · Zbl 0414.90086
[11] Lenstra J-K, Shmoys D, Tardos E (1987) Approximation algorithms for scheduling unrelated parallel machines. In: Chandra AK (ed) Proceedings of the 28th annual symposium on foundations of computer science, Los Angeles, CA. IEEE Comput Soc, Los Alamitos, pp 217–224
[12] Liu C, Layland J (1973) Scheduling algorithms for multiprogramming in a hard real-time environment. J ACM 20(1):46–61 · Zbl 0265.68013
[13] Lopez JM, Diaz JL, Garcia DF (2004) Utilization bounds for EDF scheduling on real-time multiprocessor systems. Real-Time Syst 28(1):39–68 · Zbl 1067.68025
[14] Papadimitriou CH (1981) On the complexity of integer programming. J ACM 28(4):765–768 · Zbl 0468.68050
[15] Verschae J, Wiese A (2011) On the configuration-LP for scheduling on unrelated machines. In: Demetrescu C, Halldórsson MM (eds) ESA. Lecture notes in computer science, vol 6942. Springer, Berlin, pp 530–542 · Zbl 1348.90317
[16] Williamson D, Shmoys D (2011) The design of approximation algorithms. Cambridge University Press, Cambridge · Zbl 1219.90004
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.