{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,3]],"date-time":"2026-04-03T23:20:06Z","timestamp":1775258406812,"version":"3.50.1"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2018,10,26]],"date-time":"2018-10-26T00:00:00Z","timestamp":1540512000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Real-Time Syst"],"published-print":{"date-parts":[[2019,4]]},"DOI":"10.1007\/s11241-018-9319-6","type":"journal-article","created":{"date-parts":[[2018,10,26]],"date-time":"2018-10-26T07:10:53Z","timestamp":1540537853000},"page":"349-386","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["A parallel branch-and-bound algorithm to compute a tighter tardiness bound for preemptive global EDF"],"prefix":"10.1007","volume":"55","author":[{"given":"Mauro","family":"Leoncini","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8827-5495","authenticated-orcid":false,"given":"Manuela","family":"Montangero","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paolo","family":"Valente","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,10,26]]},"reference":[{"key":"9319_CR1","unstructured":"Anderson JH, Srinivasan A (2004) Mixed pfair\/erfair scheduling of asynchronous periodic tasks. J Comput Syst Sci 68(1):157\u2013204"},{"key":"9319_CR2","doi-asserted-by":"publisher","first-page":"600","DOI":"10.1007\/BF01940883","volume":"15","author":"SK Baruah","year":"1996","unstructured":"Baruah SK, Cohen NK, Plaxton CG, Varvel DA (1996) Proportionate progress: a notion of fairness in resource allocation. Algorithmica 15:600\u2013625","journal-title":"Algorithmica"},{"key":"9319_CR3","unstructured":"Bastoni A, Brandenburg B, Anderson J (2010) An empirical comparison of global, partitioned, and clustered multiprocessor real-time schedulers. In: Proceedings of the 31st IEEE real-time systems symposium, pp 14\u201324"},{"key":"9319_CR4","doi-asserted-by":"publisher","unstructured":"Bastoni A, Brandenburg BB, Anderson JH (2010) An empirical comparison of global, partitioned, and clustered multiprocessor EDF schedulers. In: Proceedings of the 2010 31st IEEE real-time systems symposium, RTSS \u201910, pp 14\u201324. IEEE Computer Society, Washington, DC. https:\/\/doi.org\/10.1109\/RTSS.2010.23","DOI":"10.1109\/RTSS.2010.23"},{"key":"9319_CR5","doi-asserted-by":"publisher","unstructured":"Brandenburg BB, Gl M (2016) Global scheduling not required: Simple, near-optimal multiprocessor real-time scheduling with semi-partitioned reservations. In: Proceedings of the 2016 IEEE real-time systems symposium (RTSS), pp 99\u2013110. https:\/\/doi.org\/10.1109\/RTSS.2016.019","DOI":"10.1109\/RTSS.2016.019"},{"key":"9319_CR6","doi-asserted-by":"crossref","unstructured":"Cavicchioli R, Capodieci N, Bertogna M (2017) Memory interference characterization between CPU cores and integrated GPUS in mixed-criticality platforms. In: Proceedings of the 22nd IEEE international conference on emerging technologies and factory automation (ETFA)","DOI":"10.1109\/ETFA.2017.8247615"},{"key":"9319_CR7","unstructured":"Devi UC, Anderson JH (2005) Tardiness bounds under global EDF scheduling on a multiprocessor. In: Proceedings of the RTSS, pp 330\u2013341. IEEE Computer Society. http:\/\/dblp.uni-trier.de\/db\/conf\/rtss\/rtss2005.html#DeviA05"},{"issue":"2","key":"9319_CR8","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/s11241-007-9042-1","volume":"38","author":"UC Devi","year":"2008","unstructured":"Devi UC, Anderson JH (2008) Tardiness bounds under global edf scheduling on a multiprocessor. Real-Time Syst 38(2):133\u2013189","journal-title":"Real-Time Syst"},{"key":"9319_CR9","first-page":"219","volume-title":"Inherently parallel algorithms in feasibility and optimization and their applications, studies in computational mathematics","author":"J Eckstein","year":"2001","unstructured":"Eckstein J, Phillips CA, Hart WE (2001) Pico: an object-oriented framework for parallel branch and bound. In: Butnariu D, Censor Y, Reich S (eds) Inherently parallel algorithms in feasibility and optimization and their applications, studies in computational mathematics, vol 8. Elsevier, New York, pp 219\u2013265"},{"key":"9319_CR10","unstructured":"Erickson JP, Anderson JH (2012) Fair lateness scheduling: reducing maximum lateness in g-edf-like scheduling. In: Proceedings of the ECRTS, pp 3\u201312"},{"key":"9319_CR11","doi-asserted-by":"crossref","unstructured":"Erickson JP, Devi U, Baruah SK (2010) Improved tardiness bounds for global EDF. In: Proceedings of the ECRTS, pp 14\u201323","DOI":"10.1109\/ECRTS.2010.25"},{"issue":"1","key":"9319_CR12","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/s11241-013-9190-4","volume":"50","author":"JP Erickson","year":"2014","unstructured":"Erickson JP, Anderson JH, Ward BC (2014) Fair lateness scheduling: reducing maximum lateness in G-EDF-like scheduling. Real-Time Syst 50(1):5\u201347. https:\/\/doi.org\/10.1007\/s11241-013-9190-4","journal-title":"Real-Time Syst"},{"key":"9319_CR13","unstructured":"Experiment-scripts: code used for experiments (2014). http:\/\/algogroup.unimore.it\/people\/paolo\/harmonic-bound\/"},{"key":"9319_CR14","volume-title":"Fundamentals of computer algorithms","author":"E Horowitz","year":"1978","unstructured":"Horowitz E, Sahni S (1978) Fundamentals of computer algorithms. Computer Science Press, New York"},{"key":"9319_CR15","unstructured":"Kenna CJ, Herman JL, Brandenburg BB, Mills AF, Anderson JH (2011) Soft real-time on multiprocessors: Are analysis-based schedulers really worth it? In: Proceedings of theRTSS, pp 93\u2013103. IEEE Computer Society. http:\/\/dblp.uni-trier.de\/db\/conf\/rtss\/rtss2011.html#KennaHBMA11"},{"issue":"6","key":"9319_CR16","doi-asserted-by":"publisher","first-page":"768","DOI":"10.1109\/TPAMI.1984.4767600","volume":"6","author":"V Kumar","year":"1984","unstructured":"Kumar V, Kanal LN (1984) Parallel branch-and-bound formulations for and\/or tree search. IEEE Trans Pattern Anal Mach Intell 6(6):768\u2013778","journal-title":"IEEE Trans Pattern Anal Mach Intell"},{"issue":"10","key":"9319_CR17","doi-asserted-by":"publisher","first-page":"962","DOI":"10.1109\/TC.1985.6312201","volume":"C\u201334","author":"TH Lai","year":"1985","unstructured":"Lai TH, Sprague A (1985) Performance of parallel branch-and-bound algorithms. IEEE Trans Comput C\u201334(10):962\u2013964","journal-title":"IEEE Trans Comput"},{"key":"9319_CR18","doi-asserted-by":"publisher","unstructured":"Leoncini M, Montangero M, Valente P (2017) A branch-and-bound algorithm to compute a tighter bound to tardiness for preemptive global edf scheduler. In: Proceedings of the 25th international conference on real-time networks and systems, RTNS \u201917, pp 128\u2013137. ACM, New York. https:\/\/doi.org\/10.1145\/3139258.3139277","DOI":"10.1145\/3139258.3139277"},{"key":"9319_CR19","doi-asserted-by":"publisher","unstructured":"Li J, Agrawal K, Lu C, Gill C (2013) Analysis of global EDF for parallel tasks. In: Proceedings of the 2013 25th Euromicro Conference on Real-Time Systems, pp 3\u201313. https:\/\/doi.org\/10.1109\/ECRTS.2013.12","DOI":"10.1109\/ECRTS.2013.12"},{"issue":"2","key":"9319_CR20","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1016\/j.sysarc.2013.07.001","volume":"60","author":"C Liu","year":"2014","unstructured":"Liu C, Anderson JH (2014) Supporting soft real-time parallel applications on multiprocessors. J Syst Arch 60(2):152\u2013164","journal-title":"J Syst Arch"},{"key":"9319_CR21","doi-asserted-by":"publisher","unstructured":"Maia C, Yomsi PM, Nogueira L, Pinho LM (2015) Semi-partitioned scheduling of fork-join tasks using work-stealing. In: Proceedings of the 2015 IEEE 13th international conference on embedded and ubiquitous computing, pp 25\u201334. https:\/\/doi.org\/10.1109\/EUC.2015.30","DOI":"10.1109\/EUC.2015.30"},{"key":"9319_CR22","doi-asserted-by":"crossref","unstructured":"Megel T, Sirdey R, David V (2010) Minimizing task preemptions and migrations in multiprocessor optimal real-time schedules. In: Proceedings of the 2013 IEEE 34th real-time systems symposium, pp 37\u201346. http:\/\/doi.ieeecomputersociety.org\/10.1109\/RTSS.2010.22","DOI":"10.1109\/RTSS.2010.22"},{"key":"9319_CR23","doi-asserted-by":"publisher","unstructured":"Mills A, Anderson J (2010) A stochastic framework for multiprocessor soft real-time scheduling. In: Proceedings of the real-time and embedded technology and applications symposium (RTAS), 2010 16th IEEE, pp 311\u2013320. https:\/\/doi.org\/10.1109\/RTAS.2010.33","DOI":"10.1109\/RTAS.2010.33"},{"key":"9319_CR24","doi-asserted-by":"crossref","unstructured":"Regnier P, Lima G, Massa E, Levin G, Brandt SA (2011) Run: Optimal multiprocessor real-time scheduling via reduction to uniprocessor. In: Proceedings of the RTSS, pp 104\u2013115","DOI":"10.1109\/RTSS.2011.17"},{"key":"9319_CR25","unstructured":"SchedCAT: the schedulability test collection and toolkit (2014). https:\/\/github.com\/brandenburg\/schedcat\/"},{"issue":"4","key":"9319_CR26","doi-asserted-by":"publisher","first-page":"486","DOI":"10.1007\/s11241-015-9237-9","volume":"52","author":"P Valente","year":"2016","unstructured":"Valente P (2016) Using a lag-balance property to tighten tardiness bounds for global EDF. Real-Time Syst 52(4):486\u2013561. https:\/\/doi.org\/10.1007\/s11241-015-9237-9","journal-title":"Real-Time Syst"},{"key":"9319_CR27","doi-asserted-by":"crossref","unstructured":"Valente P, Lipari G (2005) An upper bound to the lateness of soft real-time tasks scheduled by edf on multiprocessors. In: Proceedings of the IEEE 26th real-time systems symposium, pp 311\u2013320. http:\/\/doi.ieeecomputersociety.org\/10.1109\/RTSS.2005.8","DOI":"10.1109\/RTSS.2005.8"},{"key":"9319_CR28","unstructured":"Ward BC, Erickson JP, Anderson JH (2013) A linear model for setting priority points in soft real-time systems. In: Proceedings of real-time systems: the past, the present, and the future, pp 192\u2013205"},{"key":"9319_CR29","doi-asserted-by":"publisher","unstructured":"Yang K, Anderson JH (2014) Optimal GEDF-based schedulers that allow intra-task parallelism on heterogeneous multiprocessors. In: Proceedings of the 2014 IEEE 12th symposium on embedded systems for real-time multimedia (ESTIMedia), pp 30\u201339. https:\/\/doi.org\/10.1109\/ESTIMedia.2014.6962343","DOI":"10.1109\/ESTIMedia.2014.6962343"},{"key":"9319_CR30","doi-asserted-by":"publisher","unstructured":"Yun H, Yao G, Pellizzoni R, Caccamo M, Sha L (2013) Memguard: Memory bandwidth reservation system for efficient performance isolation in multi-core platforms. In: Proceedings of the 2013 IEEE 19th real-time and embedded technology and applications symposium (RTAS), pp 55\u201364 . https:\/\/doi.org\/10.1109\/RTAS.2013.6531079","DOI":"10.1109\/RTAS.2013.6531079"}],"container-title":["Real-Time Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11241-018-9319-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11241-018-9319-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11241-018-9319-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,3]],"date-time":"2026-04-03T21:57:28Z","timestamp":1775253448000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11241-018-9319-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,10,26]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,4]]}},"alternative-id":["9319"],"URL":"https:\/\/doi.org\/10.1007\/s11241-018-9319-6","relation":{},"ISSN":["0922-6443","1573-1383"],"issn-type":[{"value":"0922-6443","type":"print"},{"value":"1573-1383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,10,26]]},"assertion":[{"value":"26 October 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}