{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T11:58:09Z","timestamp":1725537489885},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642041273"},{"type":"electronic","value":"9783642041280"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-04128-0_39","type":"book-chapter","created":{"date-parts":[[2009,9,14]],"date-time":"2009-09-14T18:16:36Z","timestamp":1252952196000},"page":"432-443","source":"Crossref","is-referenced-by-count":3,"title":["An Average-Case Analysis for Rate-Monotonic Multiprocessor Real-Time Scheduling"],"prefix":"10.1007","author":[{"given":"Andreas","family":"Karrenbauer","sequence":"first","affiliation":[]},{"given":"Thomas","family":"Rothvo\u00df","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"39_CR1","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1145\/321738.321743","volume":"20","author":"C.L. Liu","year":"1973","unstructured":"Liu, C.L., Layland, J.W.: Scheduling algorithms for multiprogramming in a hard-real-time environment. J. ACM\u00a020(1), 46\u201361 (1973)","journal-title":"J. ACM"},{"key":"39_CR2","doi-asserted-by":"crossref","unstructured":"Lehoczky, J.P., Sha, L., Ding, Y.: The rate monotonic scheduling algorithm: Exact characterization and average case behavior. In: IEEE Real-Time Systems Symposium (1989)","DOI":"10.1109\/REAL.1989.63567"},{"key":"39_CR3","doi-asserted-by":"crossref","unstructured":"Lehoczky, J.P.: Fixed priority scheduling of periodic task sets with arbitrary deadlines. In: IEEE Real-Time Systems Symposium, pp. 201\u2013213 (1990)","DOI":"10.1109\/REAL.1990.128748"},{"key":"39_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1007\/BFb0035103","volume-title":"PARLE \u201991. Parallel Architectures and Languages Europe","author":"J. Korst","year":"1991","unstructured":"Korst, J., Aarts, E.H.L., Lenstra, J.K., Wessels, J.: Periodic multiprocessor scheduling. In: Aarts, E.H.L., van Leeuwen, J., Rem, M. (eds.) PARLE 1991. LNCS, vol.\u00a0505, pp. 166\u2013178. Springer, Heidelberg (1991)"},{"key":"39_CR5","doi-asserted-by":"crossref","unstructured":"Audsley, A.N., Burns, A., Richardson, M., Tindell, K.: Applying new scheduling theory to static priority pre-emptive scheduling. Software Engineering Journal, 284\u2013292 (1993)","DOI":"10.1049\/sej.1993.0034"},{"issue":"3","key":"39_CR6","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/BF01088806","volume":"9","author":"Y. Oh","year":"1995","unstructured":"Oh, Y., Son, S.H.: Allocating fixed-priority periodic tasks on multiprocessor systems. Real-Time Syst.\u00a09(3), 207\u2013239 (1995)","journal-title":"Real-Time Syst."},{"key":"39_CR7","unstructured":"Davari, S., Dhall, S.K.: On-line algorithms for allocating periodic-time-critical tasks on multiprocessor systems. Informatica (Slovenia)\u00a019(1) (1995)"},{"issue":"12","key":"39_CR8","doi-asserted-by":"publisher","first-page":"1429","DOI":"10.1109\/12.477248","volume":"44","author":"J. Liebeherr","year":"1995","unstructured":"Liebeherr, J., Burchard, A., Oh, Y., Son, S.H.: New strategies for assigning real-time tasks to multiprocessor systems. IEEE Trans. Comput.\u00a044(12), 1429\u20131442 (1995)","journal-title":"IEEE Trans. Comput."},{"issue":"4","key":"39_CR9","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1287\/ijoc.9.4.351","volume":"9","author":"J. Korst","year":"1997","unstructured":"Korst, J., Aarts, E., Lenstra, J.K.: Scheduling periodic tasks with slack. INFORMS J. Comput.\u00a09(4), 351\u2013362 (1997)","journal-title":"INFORMS J. Comput."},{"key":"39_CR10","doi-asserted-by":"crossref","unstructured":"Oh, D.I., Baker, T.P.: Utilization bounds for N-processor rate monotone scheduling with static processor assignment. Real-Time Systems (1998)","DOI":"10.1023\/A:1008098013753"},{"key":"39_CR11","series-title":"Computer and Information Science Series","volume-title":"Handbook of Scheduling \u2014 Algorithms, Models, and Performance Analysis","author":"S. Baruah","year":"2004","unstructured":"Baruah, S., Goossens, J.: Scheduling real-time tasks: Algorithms and complexity. In: Leung, J.Y.T. (ed.) Handbook of Scheduling \u2014 Algorithms, Models, and Performance Analysis. Computer and Information Science Series, vol.\u00a028. Chapman & Hall\/CRC, Boca Raton (2004)"},{"key":"39_CR12","volume-title":"ECRTS 2005","author":"N. Fisher","year":"2005","unstructured":"Fisher, N., Baruah, S.: A fully polynomial-time approximation scheme for feasibility analysis in static-priority systems with arbitrary relative deadlines. In: ECRTS 2005. IEEE Computer Society, Los Alamitos (2005)"},{"key":"39_CR13","doi-asserted-by":"crossref","DOI":"10.1201\/9780203489802","volume-title":"Handbook of Scheduling: Algorithms, Models, and Performance Analysis","author":"J. Leung","year":"2004","unstructured":"Leung, J., Kelly, L., Anderson, J.H.: Handbook of Scheduling: Algorithms, Models, and Performance Analysis. CRC Press, Inc., Boca Raton (2004)"},{"key":"39_CR14","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/0097-3165(76)90001-7","volume":"21","author":"M.R. Garey","year":"1976","unstructured":"Garey, M.R., Graham, R.L., Johnson, D.S., Yao, A.C.C.: Resource constrained scheduling as generalized bin packing. J. Combin. Theory Ser. A\u00a021, 257\u2013298 (1976)","journal-title":"J. Combin. Theory Ser. A"},{"key":"39_CR15","unstructured":"Johnson, D.S.: Near-optimal bin packing algorithms. PhD thesis, MIT, Cambridge, MA (1973)"},{"key":"39_CR16","volume-title":"FOCS 1984","author":"P.W. Shor","year":"1984","unstructured":"Shor, P.W.: The average-case analysis of some on-line algorithms for bin packing. In: FOCS 1984, Singer Island, FL. IEEE, Los Alamitos (1984)"},{"issue":"4\/5","key":"39_CR17","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1016\/0020-0190(80)90041-1","volume":"11","author":"G.N. Frederickson","year":"1980","unstructured":"Frederickson, G.N.: Probabilistic analysis for simple one- and two-dimensional bin packing algorithms. Information Processing Letters\u00a011(4\/5), 156\u2013161 (1980)","journal-title":"Information Processing Letters"},{"key":"39_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/3-540-10856-4_104","volume-title":"Mathematical Foundations of Computer Science 1981","author":"W. Kn\u00f6del","year":"1981","unstructured":"Kn\u00f6del, W.: A bin packing algorithm with complexity O(n logn) and performance\u00a01 in the stochastic limit. In: Gruska, J., Chytil, M.P. (eds.) MFCS 1981. LNCS, vol.\u00a0118, pp. 369\u2013378. Springer, Heidelberg (1981)"},{"key":"39_CR19","unstructured":"Lueker, G.S.: An average-case analysis of bin packing with uniformly distributed item sizes. Technical Report 181, Dept. Inf. and CS, University of California at Irvine (1982)"},{"issue":"4","key":"39_CR20","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/BF02579456","volume":"1","author":"W. Fernandez de la Vega","year":"1981","unstructured":"Fernandez de la Vega, W., Lueker, G.S.: Bin packing can be solved within 1\u2009+\u2009\u03b5 in linear time. Combinatorica\u00a01(4), 349\u2013355 (1981)","journal-title":"Combinatorica"},{"key":"39_CR21","first-page":"312","volume-title":"FOCS 1982","author":"N. Karmarkar","year":"1982","unstructured":"Karmarkar, N., Karp, R.M.: An efficient approximation scheme for the one-dimensional bin-packing problem. In: FOCS 1982, pp. 312\u2013320. IEEE, Los Alamitos (1982)"},{"key":"39_CR22","series-title":"CISM Courses and Lectures","first-page":"49","volume-title":"Algorithm design for computer system design","author":"E.G. Coffman Jr.","year":"1984","unstructured":"Coffman Jr., E.G., Garey, M.R., Johnson, D.S.: Approximation algorithms for bin-packing\u2014an updated survey. In: Algorithm design for computer system design. CISM Courses and Lectures, vol.\u00a0284, pp. 49\u2013106. Springer, Vienna (1984)"},{"key":"39_CR23","doi-asserted-by":"crossref","unstructured":"Eisenbrand, F., Rothvo\u00df, T.: Static-priority Real-time Scheduling: Response Time Computation is NP-hard. In: IEEE Real-Time Systems Symposium, RTSS (2008)","DOI":"10.1109\/RTSS.2008.25"},{"key":"39_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1007\/978-3-540-70575-8_21","volume-title":"Automata, Languages and Programming","author":"F. Eisenbrand","year":"2008","unstructured":"Eisenbrand, F., Rothvo\u00df, T.: A PTAS for static priority real-time scheduling with resource augmentation. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol.\u00a05125, pp. 246\u2013257. Springer, Heidelberg (2008)"},{"key":"39_CR25","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/S0019-9958(80)90050-9","volume":"44","author":"E.G.J. Coffman","year":"1980","unstructured":"Coffman, E.G.J., So, K., Hofri, M., Yao, A.C.: A stochastic model of bin-packing. Inf.\u00a0Control\u00a044, 105\u2013115 (1980)","journal-title":"Inf.\u00a0Control"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2009"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-04128-0_39","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,10]],"date-time":"2021-10-10T18:06:40Z","timestamp":1633889200000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-04128-0_39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642041273","9783642041280"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-04128-0_39","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}