{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T01:06:19Z","timestamp":1743123979201,"version":"3.40.3"},"publisher-location":"Singapore","reference-count":44,"publisher":"Springer Nature Singapore","isbn-type":[{"type":"print","value":"9789812872500"},{"type":"electronic","value":"9789812872517"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-981-287-251-7_3","type":"book-chapter","created":{"date-parts":[[2022,8,8]],"date-time":"2022-08-08T13:03:18Z","timestamp":1659963798000},"page":"193-231","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Practical Considerations in Optimal Multiprocessor Scheduling"],"prefix":"10.1007","author":[{"given":"George","family":"Lima","sequence":"first","affiliation":[]},{"given":"Ernesto","family":"Massa","sequence":"additional","affiliation":[]},{"given":"Paul","family":"Regnier","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,8,9]]},"reference":[{"key":"3_CR1","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1109\/EMRTS.2000.853990","volume-title":"Proceedings of the 12th Euromicro Conference on Real-Time Systems (ECRTS 2000)","author":"JH Anderson","year":"2000","unstructured":"J.H. Anderson, A. Srinivasan, Early-release fair scheduling, in Proceedings of the 12th Euromicro Conference on Real-Time Systems (ECRTS 2000), (IEEE Computer Society, Washington, 2000a), pp. 35\u201343"},{"key":"3_CR2","first-page":"297","volume-title":"Proceedings of the 7th International Workshop on Real-Time Computing Systems and Applications (RTCSA 2000)","author":"JH Anderson","year":"2000","unstructured":"J.H. Anderson, A. Srinivasan, Pfair scheduling: beyond periodic task systems, in Proceedings of the 7th International Workshop on Real-Time Computing Systems and Applications (RTCSA 2000), (IEEE, Cheju Island, 2000b), pp. 297\u2013306"},{"key":"3_CR3","first-page":"31-1","volume-title":"Handbook of Scheduling: Algorithms, Models, and Performance Analysis","author":"J Anderson","year":"2004","unstructured":"J. Anderson, P. Holman, A. Srinivasan, Chapter 31: Fair scheduling of real-time tasks on multiprocessors, in Handbook of Scheduling: Algorithms, Models, and Performance Analysis, ed. by J. Y. Leung, (Chapman & Hall\/CRC, Boca Raton, 2004), pp. 31-1\u201331-21"},{"key":"3_CR4","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1109\/ECRTS.2008.9","volume-title":"Proceedings of the 20th Euromicro Conference on Real-Time Systems (ECRTS 2008)","author":"B Andersson","year":"2008","unstructured":"B. Andersson, K. Bletsas, Sporadic multiprocessor scheduling with few preemptions, in Proceedings of the 20th Euromicro Conference on Real-Time Systems (ECRTS 2008), (IEEE, Prague, 2008), pp. 243\u2013252"},{"key":"3_CR5","first-page":"322","volume-title":"Proceedings of the 12th IEEE Real-Time and Embedded Technology and Applications Symposium (RTCSA 2006)","author":"B Andersson","year":"2006","unstructured":"B. Andersson, E. Tovar, Multiprocessor scheduling with few preemptions, in Proceedings of the 12th IEEE Real-Time and Embedded Technology and Applications Symposium (RTCSA 2006), (IEEE, San Jose, 2006), pp. 322\u2013334"},{"key":"3_CR6","first-page":"321:321","volume-title":"Proceedings of the 22nd International Conference on Real-Time Networks and Systems (RTNS 2014)","author":"A Baldovin","year":"2014","unstructured":"A. Baldovin, G. Nelissen, T. Vardanega, E. Tovar, SPRINT: extending RUN to schedule sporadic tasks, in Proceedings of the 22nd International Conference on Real-Time Networks and Systems (RTNS 2014), (ACM, Versaille, 2014), pp. 321:321\u2013321:330"},{"key":"3_CR7","first-page":"28-1","volume-title":"Handbook of Scheduling: Algorithms, Models, and Performance Analysis","author":"S Baruah","year":"2004","unstructured":"S. Baruah, J. Goossens, Chapter 28: Scheduling real-time tasks: algorithms and complexity, in Handbook of Scheduling: Algorithms, Models, and Performance Analysis, ed. by J. Y. Leung, (Chapman & Hall\/CRC, Boca Raton, 2004), pp. 28-1\u201328-21"},{"issue":"4","key":"3_CR8","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/BF01995675","volume":"2","author":"SK Baruah","year":"1990","unstructured":"S.K. Baruah, L.E. Rosier, R.R. Howell, Algorithms and complexity concerning the preemptive scheduling of periodic, real-time tasks on one processor. Real-Time Syst. 2(4), 301\u2013324 (1990)","journal-title":"Real-Time Syst."},{"key":"3_CR9","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1109\/IPPS.1995.395946","volume-title":"Proceedings of the 9th International Symposium on Parallel Processing (IPPS 1995)","author":"S Baruah","year":"1995","unstructured":"S. Baruah, J. Gehrke, C.G. Plaxton, Fast scheduling of periodic tasks on multiple resources, in Proceedings of the 9th International Symposium on Parallel Processing (IPPS 1995), (IEEE Computer Society, Santa Barbara, 1995), pp. 280\u2013288"},{"issue":"6","key":"3_CR10","doi-asserted-by":"publisher","first-page":"600","DOI":"10.1007\/BF01940883","volume":"15","author":"S Baruah","year":"1996","unstructured":"S. Baruah, N.K. Cohen, C.G. Plaxton, D.A. Varvel, Proportionate progress: a notion of fairness in resource allocation. Algorithmica 15(6), 600\u2013625 (1996)","journal-title":"Algorithmica"},{"key":"3_CR11","first-page":"147","volume-title":"Proceedings of the 29th IEEE Real-Time Systems Symposium (RTSS 2008)","author":"SY Chen","year":"2008","unstructured":"S.Y. Chen, C.W. Hsueh, Optimal dynamic-priority real-time scheduling algorithms for uniform multiprocessors, in Proceedings of the 29th IEEE Real-Time Systems Symposium (RTSS 2008), (IEEE, Barcelona, 2008), pp. 147\u2013156"},{"key":"3_CR12","first-page":"101","volume-title":"Proceedings of the 28th IEEE Real-Time Systems Symposium (RTSS 2007)","author":"H Cho","year":"2006","unstructured":"H. Cho, B. Ravindran, E.D. Jensen, An optimal real-time scheduling algorithm for multiprocessors, in Proceedings of the 28th IEEE Real-Time Systems Symposium (RTSS 2007), (IEEE, Tucson, 2006), pp. 101\u2013110"},{"key":"3_CR13","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1109\/ECRTS.2007.14","volume-title":"Proceedings of the 19th IEEE Euromicro Conference on Real-Time Systems (ECRTS 2007)","author":"M Cirinei","year":"2007","unstructured":"M. Cirinei, T.P. Baker, EDZL scheduling analysis, in Proceedings of the 19th IEEE Euromicro Conference on Real-Time Systems (ECRTS 2007), (IEEE Computer Society, Pisa, 2007), pp. 9\u201318"},{"key":"3_CR14","first-page":"46","volume-title":"Approximation Algorithms for NP-Hard Problems","author":"EG Coffman Jr","year":"1997","unstructured":"E.G. Coffman Jr., M.R. Garey, D.S. Johnson, Approximation algorithms for bin packing: a survey, in Approximation Algorithms for NP-Hard Problems, ed. by D. S. Hochbaum, (PWS Publishing Co, Boston, 1997), pp. 46\u201393"},{"key":"3_CR15","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1109\/ECRTS.2014.27","volume-title":"Proceedings of the 26th Euromicro Conference on Real-Time Systems (ECRTS 2014)","author":"D Compagnin","year":"2014","unstructured":"D. Compagnin, E. Mezzetti, T. Vardanega, Putting RUN into practice: implementation and evaluation, in Proceedings of the 26th Euromicro Conference on Real-Time Systems (ECRTS 2014), (2014), pp. 75\u201384"},{"key":"3_CR16","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1109\/ECRTS.2015.18","volume-title":"Proceedings of the 27th Euromicro Conference on Real-Time Systems (ECRTS 2015)","author":"D Compagnin","year":"2015","unstructured":"D. Compagnin, E. Mezzetti, T. Vardanega, Experimental evaluation of optimal schedulers based on partitioned proportionate fairness, in Proceedings of the 27th Euromicro Conference on Real-Time Systems (ECRTS 2015), (Lund, Sweden, 2015), pp. 115\u2013126"},{"issue":"4","key":"3_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1978802.1978814","volume":"43","author":"RI Davis","year":"2011","unstructured":"R.I. Davis, A. Burns, A survey of hard real-time scheduling for multiprocessor systems. ACM Comput. Surv. 43(4), 1\u201344 (2011)","journal-title":"ACM Comput. Surv."},{"key":"3_CR18","unstructured":"M.L. Dertouzos, Control robotics: the procedural control of physical processes, in Proceedings of IFIP Congress (IFIP Congress 1974), (Stockholm, 1974), pp. 807\u2013813"},{"issue":"12","key":"3_CR19","doi-asserted-by":"publisher","first-page":"1497","DOI":"10.1109\/32.58762","volume":"15","author":"M Dertouzos","year":"1989","unstructured":"M. Dertouzos, A. Mok, Multiprocessor online scheduling of hard-real-time tasks. IEEE Trans. Softw. Eng. 15(12), 1497\u20131506 (1989)","journal-title":"IEEE Trans. Softw. Eng."},{"issue":"1","key":"3_CR20","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1287\/opre.26.1.127","volume":"26","author":"SK Dhall","year":"1978","unstructured":"S.K. Dhall, C.L. Liu, On a real-time scheduling problem. Oper. Res. 26(1), 127\u2013140 (1978)","journal-title":"Oper. Res."},{"issue":"1","key":"3_CR21","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1007\/s11241-010-9092-7","volume":"45","author":"N Fisher","year":"2010","unstructured":"N. Fisher, J. Goossens, S. Baruah, Optimal online multiprocessor scheduling of sporadic real-time tasks is impossible. Real-Time Syst. 45(1), 26\u201371 (2010)","journal-title":"Real-Time Syst."},{"key":"3_CR22","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1109\/ECRTS.2008.15","volume-title":"Proceedings of the 20th Euromicro Conference on Real-Time Systems (ECRTS 2008)","author":"K Funaoka","year":"2008","unstructured":"K. Funaoka, S. Kato, N. Yamasaki, Work-conserving optimal real-time scheduling on multiprocessors, in Proceedings of the 20th Euromicro Conference on Real-Time Systems (ECRTS 2008), (IEEE, Prague, 2008), pp. 13\u201322"},{"issue":"5","key":"3_CR23","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/s11241-011-9130-0","volume":"47","author":"S Funk","year":"2011","unstructured":"S. Funk, G. Levin, C. Sadowski, I. Pye, S. Brandt, DP-fair: a unifying theory for optimal hard real-time multiprocessor scheduling. Real-Time Syst. 47(5), 389\u2013429 (2011)","journal-title":"Real-Time Syst."},{"issue":"1","key":"3_CR24","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/BF01094172","volume":"9","author":"TM Ghazalie","year":"1995","unstructured":"T.M. Ghazalie, T.P. Baker, Aperiodic servers in a deadline scheduling environment. Real-Time Syst. 9(1), 31\u201367 (1995)","journal-title":"Real-Time Syst."},{"key":"3_CR25","doi-asserted-by":"crossref","unstructured":"K.S. Hong, J.Y.T. Leung, On-line scheduling of real-time tasks, in Proceedings of the 9th IEEE Real-Time Systems Symposium (RTSS 1988), (Huntsville, 1988), pp. 244\u2013250","DOI":"10.1109\/REAL.1988.51119"},{"issue":"10","key":"3_CR26","doi-asserted-by":"publisher","first-page":"1326","DOI":"10.1109\/12.166609","volume":"41","author":"KS Hong","year":"1992","unstructured":"K.S. Hong, J.Y.T. Leung, On-line scheduling of real-time tasks. IEEE Trans. Comput. 41(10), 1326\u20131331 (1992)","journal-title":"IEEE Trans. Comput."},{"issue":"1","key":"3_CR27","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1002\/nav.3800210113","volume":"21","author":"WA Horn","year":"1974","unstructured":"W.A. Horn, Some simple scheduling algorithms. Nav. Res. Logist. Q. 21(1), 177\u2013185 (1974)","journal-title":"Nav. Res. Logist. Q."},{"issue":"7","key":"3_CR28","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1016\/j.ipl.2010.12.007","volume":"111","author":"H Kim","year":"2011","unstructured":"H. Kim, Y. Cho, A new fair scheduling algorithm for periodic tasks on multiprocessors. Inf. Process. Lett. 111(7), 301\u2013309 (2011)","journal-title":"Inf. Process. Lett."},{"key":"3_CR29","first-page":"226","volume-title":"Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1998)","author":"G Koren","year":"1998","unstructured":"G. Koren, A. Amir, E. Dar, The power of migration in multiprocessor scheduling of real-time systems, in Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1998), (Society for Industrial and Applied Mathematics, San Francisco, 1998), pp. 226\u2013235"},{"key":"3_CR30","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1109\/ECRTS.2010.34","volume-title":"Proceedings of the 20th Euromicro Conference on Real-Time Systems (ECRTS 2010)","author":"G Levin","year":"2010","unstructured":"G. Levin, S. Funk, C. Sadowski, I. Pye, S. Brandt, DP-FAIR: a simple model for understanding optimal multiprocessor scheduling, in Proceedings of the 20th Euromicro Conference on Real-Time Systems (ECRTS 2010), (IEEE, Brussels, 2010), pp. 3\u201313"},{"issue":"1","key":"3_CR31","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1145\/321738.321743","volume":"20","author":"CL Liu","year":"1973","unstructured":"C.L. Liu, J.W. Layland, Scheduling algorithms for multiprogram in a hard real-time environment. J. ACM 20(1), 40\u201361 (1973)","journal-title":"J. ACM"},{"key":"3_CR32","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1109\/ECRTS.2014.19","volume-title":"Proceedings of the 26th Euromicro Conference on Real-Time Systems (ECRTS 2014)","author":"E Massa","year":"2014","unstructured":"E. Massa, G. Lima, P. Regnier, G. Levin, S. Brandt, Optimal and adaptive multiprocessor real-time scheduling: the quasi-partitioning approach, in Proceedings of the 26th Euromicro Conference on Real-Time Systems (ECRTS 2014), (IEEE, Madrid, 2014), pp. 291\u2013300"},{"issue":"5","key":"3_CR33","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1007\/s11241-016-9251-6","volume":"52","author":"E Massa","year":"2016","unstructured":"E. Massa, G. Lima, P. Regnier, G. Levin, S. Brandt, Quasi-partitioned scheduling: optimality and adaptation in multiprocessor real-time systems. Real-Time Syst. 52(5), 566\u2013597 (2016)","journal-title":"Real-Time Syst."},{"key":"3_CR34","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/mnsc.6.1.1","volume":"6","author":"R McNaughton","year":"1959","unstructured":"R. McNaughton, Scheduling with deadlines and loss functions. Manag. Sci. 6, 1\u201312 (1959)","journal-title":"Manag. Sci."},{"key":"3_CR35","first-page":"15","volume-title":"Proceedings of the 17th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA 2011)","author":"G Nelissen","year":"2011","unstructured":"G. Nelissen, V. Berten, J. Goossens, D. Milojevic, Reducing preemptions and migrations in real-time multiprocessor scheduling algorithms by releasing the fairness, in Proceedings of the 17th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA 2011), vol. 1, (IEEE, Toyama, 2011), pp. 15\u201324"},{"key":"3_CR36","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1109\/ECRTS.2012.36","volume-title":"Proceedings of the 24th Euromicro Conference on Real-Time Systems (ECRTS 2012)","author":"G Nelissen","year":"2012","unstructured":"G. Nelissen, V. Berten, V. N\u00e9lis, J. Goossens, D. Milojevic, U-EDF: an unfair but optimal multiprocessor scheduling algorithm for sporadic tasks, in Proceedings of the 24th Euromicro Conference on Real-Time Systems (ECRTS 2012), (IEEE, Pisa, 2012), pp. 13\u201323"},{"issue":"4","key":"3_CR37","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1007\/s11241-014-9201-0","volume":"50","author":"G Nelissen","year":"2014","unstructured":"G. Nelissen, H. Su, Y. Guo, D. Zhu, V. N\u00e9lis, J. Goossens, An optimal boundary fair scheduling. Real-Time Syst. 50(4), 456\u2013508 (2014)","journal-title":"Real-Time Syst."},{"issue":"1","key":"3_CR38","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/s11241-008-9051-8","volume":"40","author":"R Pellizzoni","year":"2008","unstructured":"R. Pellizzoni, M. Caccamo, M-CASH: a real-time resource reclaiming algorithm for multiprocessor platforms. Real-Time Syst. 40(1), 117\u2013147 (2008)","journal-title":"Real-Time Syst."},{"key":"3_CR39","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1109\/RTSS.2011.17","volume-title":"Proceedings of the 32nd IEEE Real-Time Systems Symposium (RTSS 2011)","author":"P Regnier","year":"2011","unstructured":"P. Regnier, G. Lima, E. Massa, G. Levin, S. Brandt, RUN: optimal multiprocessor real-time scheduling via reduction to uniprocessor, in Proceedings of the 32nd IEEE Real-Time Systems Symposium (RTSS 2011), (IEEE, Vienna, 2011), pp. 104\u2013115"},{"issue":"4","key":"3_CR40","doi-asserted-by":"publisher","first-page":"436","DOI":"10.1007\/s11241-012-9165-x","volume":"49","author":"P Regnier","year":"2013","unstructured":"P. Regnier, G. Lima, E. Massa, G. Levin, S. Brandt, Multiprocessor scheduling by reduction to uniprocessor: an original optimal approach. Real-Time Syst. 49(4), 436\u2013474 (2013)","journal-title":"Real-Time Syst."},{"issue":"5","key":"3_CR41","doi-asserted-by":"publisher","first-page":"925","DOI":"10.1287\/opre.27.5.925","volume":"27","author":"S Sahni","year":"1979","unstructured":"S. Sahni, Preemptive scheduling with due dates. Oper. Res. 27(5), 925\u2013934 (1979)","journal-title":"Oper. Res."},{"key":"3_CR42","doi-asserted-by":"crossref","unstructured":"A. Srinivasan, J.H. Anderson, Optimal rate-based scheduling on multiprocessors, in Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC 2002), (Montreal, 2002), pp. 189\u2013198","DOI":"10.1145\/509907.509938"},{"key":"3_CR43","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-5535-3","volume-title":"Deadline Scheduling for Real-Time Systems: Edf and Related Algorithms","author":"JA Stankovic","year":"1998","unstructured":"J.A. Stankovic, K. Ramamritham, M. Spuri, Deadline Scheduling for Real-Time Systems: Edf and Related Algorithms (Kluwer Academic Publishers, Norwell, 1998)"},{"key":"3_CR44","first-page":"142","volume-title":"Proceedings of the 24th IEEE International Real-Time Systems Symposium (RTSS 2003), RTSS 03","author":"D Zhu","year":"2003","unstructured":"D. Zhu, D. Moss\u00e9, R. Melhem, Multiple-resource periodic scheduling problem: how much fairness is necessary? in Proceedings of the 24th IEEE International Real-Time Systems Symposium (RTSS 2003), RTSS 03, (IEEE, Cancun, 2003), p. 142"}],"container-title":["Handbook of Real-Time Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-287-251-7_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,30]],"date-time":"2024-09-30T23:26:57Z","timestamp":1727738817000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-287-251-7_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9789812872500","9789812872517"],"references-count":44,"URL":"https:\/\/doi.org\/10.1007\/978-981-287-251-7_3","relation":{},"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"9 August 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}