{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T10:09:03Z","timestamp":1767262143192,"version":"3.40.3"},"publisher-location":"Singapore","reference-count":31,"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_35","type":"book-chapter","created":{"date-parts":[[2022,8,8]],"date-time":"2022-08-08T13:03:18Z","timestamp":1659963798000},"page":"489-506","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Complexity of Uniprocessor Scheduling Analysis"],"prefix":"10.1007","author":[{"given":"Pontus","family":"Ekberg","sequence":"first","affiliation":[]},{"given":"Wang","family":"Yi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,8,9]]},"reference":[{"key":"35_CR1","doi-asserted-by":"crossref","unstructured":"K. Albers, F. Slomka, An event stream driven approximation for the analysis of real-time systems, in Proceedings of the 16th Euromicro Conference on Real-Time Systems (ECRTS), June 2004, pp. 187\u2013195","DOI":"10.1109\/EMRTS.2004.1311020"},{"key":"35_CR2","volume-title":"Optimal priority assignment and feasibility of static priority tasks with arbitrary start times","author":"N Audsley","year":"1991","unstructured":"N. Audsley, Optimal priority assignment and feasibility of static priority tasks with arbitrary start times. Technical report, University of York, England, 1991"},{"key":"35_CR3","doi-asserted-by":"crossref","unstructured":"S.K. Baruah, Feasibility analysis of recurring branching tasks, in Proceedings of the 10th Euromicro Workshop on Real-Time Systems (EWRTS), 1998, pp. 138\u2013145","DOI":"10.1109\/EMWRTS.1998.685078"},{"issue":"1","key":"35_CR4","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1023\/A:1021711220939","volume":"24","author":"SK Baruah","year":"2003","unstructured":"S.K. Baruah, Dynamic- and static-priority scheduling of recurring real-time tasks. Real-Time Syst. 24(1), 93\u2013128 (2003)","journal-title":"Real-Time Syst."},{"key":"35_CR5","doi-asserted-by":"crossref","unstructured":"S.K. Baruah, The non-cyclic recurring real-time task model, in Proceedings of the 31st Real-Time Systems Symposium (RTSS), 2010, pp. 173\u2013182","DOI":"10.1109\/RTSS.2010.19"},{"key":"35_CR6","doi-asserted-by":"crossref","unstructured":"S. Baruah, A.K. Mok, L.E. Rosier, Preemptively scheduling hard-real-time sporadic tasks on one processor, in Proceedings of the 11th Real-Time Systems Symposium (RTSS), 1990a, pp. 182\u2013190","DOI":"10.1109\/REAL.1990.128746"},{"issue":"4","key":"35_CR7","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/BF01995675","volume":"2","author":"S Baruah","year":"1990","unstructured":"S. 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 (1990b)","journal-title":"Real-Time Syst."},{"key":"35_CR8","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1023\/A:1008030427220","volume":"17","author":"S Baruah","year":"1999","unstructured":"S. Baruah, D. Chen, S. Gorinsky, A.K. Mok, Generalized multiframe tasks. Real-Time Syst. 17, 5\u201322 (1999)","journal-title":"Real-Time Syst."},{"key":"35_CR9","doi-asserted-by":"crossref","unstructured":"V. Bonifaci, A. Marchetti-Spaccamela, N. Megow, A. Wiese, Polynomial-time exact schedulability tests for harmonic real-time tasks, in Proceedings of the 34th Real-Time Systems Symposium (RTSS), Dec 2013, pp. 236\u2013245","DOI":"10.1109\/RTSS.2013.31"},{"key":"35_CR10","unstructured":"M.L. Dertouzos, Control robotics: the procedural control of physical processes, in Proceedings of the IFIP Congress, vol 74, 1974, pp. 807\u2013813"},{"key":"35_CR11","doi-asserted-by":"crossref","unstructured":"F. Eisenbrand, T. Rothvo\u00df, Static-priority real-time scheduling: response time computation is NP-hard, in Proceedings of the 29th Real-Time Systems Symposium (RTSS) (IEEE Computer Society, 2008), pp. 397\u2013406","DOI":"10.1109\/RTSS.2008.25"},{"key":"35_CR12","doi-asserted-by":"crossref","unstructured":"F. Eisenbrand, T. Rothvo\u00df, EDF-schedulability of synchronous periodic task systems is coNP-hard, in Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2010, pp. 1029\u20131034","DOI":"10.1137\/1.9781611973075.83"},{"key":"35_CR13","doi-asserted-by":"crossref","unstructured":"P. Ekberg, W. Yi, Uniprocessor feasibility of sporadic tasks remains coNP-complete under bounded utilization, in Proceedings of the 36th Real-Time Systems Symposium (RTSS), 2015a, pp. 87\u201395. https:\/\/doi.org\/10.1109\/RTSS.2015.16","DOI":"10.1109\/RTSS.2015.16"},{"key":"35_CR14","doi-asserted-by":"crossref","unstructured":"P. Ekberg, W. Yi, Uniprocessor feasibility of sporadic tasks with constrained deadlines is strongly coNP-complete, in Proceedings of the 27th Euromicro Conference on Real-Time Systems (ECRTS), 2015b, pp. 281\u2013286","DOI":"10.1109\/ECRTS.2015.32"},{"key":"35_CR15","doi-asserted-by":"crossref","unstructured":"P. Ekberg, W. Yi, Fixed-priority schedulability of sporadic tasks on uniprocessors is NP-hard, in Proceedings of the 38th Real-Time Systems Symposium (RTSS), 2017, pp. 139\u2013146. https:\/\/doi.org\/10.1109\/RTSS.2017.00020","DOI":"10.1109\/RTSS.2017.00020"},{"key":"35_CR16","doi-asserted-by":"crossref","unstructured":"N. Fisher, S. Baruah, A fully polynomial-time approximation scheme for feasibility analysis in static-priority systems with arbitrary relative deadlines, in Proceedings of the 17th Euromicro Conference on Real-Time Systems (ECRTS), July 2005, pp. 117\u2013126","DOI":"10.1109\/ECRTS.2005.1"},{"issue":"3","key":"35_CR17","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1145\/322077.322090","volume":"25","author":"MR Garey","year":"1978","unstructured":"M.R. Garey, D.S. Johnson, Strong NP-completeness results: motivation, examples, and implications. J. ACM 25(3), 499\u2013508 (1978)","journal-title":"J. ACM"},{"key":"35_CR18","unstructured":"J. Goossens, Scheduling of Hard Real-Time Periodic Systems with Various Kinds of Deadline and Offset Constraints. PhD thesis, Universit\u00e9 libre de Bruxelles, 1999"},{"issue":"5","key":"35_CR19","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1093\/comjnl\/29.5.390","volume":"29","author":"M Joseph","year":"1986","unstructured":"M. Joseph, P. Pandya, Finding response times in a real-time system. Comput. J. 29(5), 390\u2013395 (1986)","journal-title":"Comput. J."},{"key":"35_CR20","doi-asserted-by":"crossref","unstructured":"J.P. Lehoczky, Fixed priority scheduling of periodic task sets with arbitrary deadlines, in Proceedings of the 11th Real-Time Systems Symposium (RTSS), Dec 1990, pp. 201\u2013209","DOI":"10.1109\/REAL.1990.128748"},{"issue":"3","key":"35_CR21","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/0020-0190(80)90123-4","volume":"11","author":"JY-T Leung","year":"1980","unstructured":"J.Y.-T. Leung, M. Merrill, A note on preemptive scheduling of periodic, real-time tasks. Inf. Process. Lett. 11(3), 115\u2013118 (1980)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"35_CR22","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0166-5316(82)90024-4","volume":"2","author":"JY-T Leung","year":"1982","unstructured":"J.Y.-T. Leung, J. Whitehead, On the complexity of fixed-priority scheduling of periodic, real-time tasks. Perform. Eval. 2(4), 237\u2013250 (1982)","journal-title":"Perform. Eval."},{"issue":"1","key":"35_CR23","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1145\/321738.321743","volume":"20","author":"C-L Liu","year":"1973","unstructured":"C.-L. Liu, J.W. Layland, Scheduling algorithms for multiprogramming in a hard-real-time environment. J. ACM 20(1), 46\u201361 (1973)","journal-title":"J. ACM"},{"issue":"10","key":"35_CR24","doi-asserted-by":"publisher","first-page":"635","DOI":"10.1109\/32.637146","volume":"23","author":"AK Mok","year":"1997","unstructured":"A.K. Mok, D. Chen, A multiframe model for real-time tasks. IEEE Trans. Softw. Eng. 23(10), 635\u2013645 (1997)","journal-title":"IEEE Trans. Softw. Eng."},{"issue":"1","key":"35_CR25","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/BF02341920","volume":"1","author":"B Sprunt","year":"1989","unstructured":"B. Sprunt, L. Sha, J. Lehoczky, Aperiodic task scheduling for hard-real-time systems. Real-Time Syst. 1(1), 27\u201360 (1989)","journal-title":"Real-Time Syst."},{"key":"35_CR26","unstructured":"M. Stigge, Real-Time Workload Models: Expressiveness vs. Analysis Efficiency. PhD thesis, Uppsala University, Department of Information Technology, 2014"},{"key":"35_CR27","doi-asserted-by":"crossref","unstructured":"M. Stigge, W. Yi, Combinatorial abstraction refinement for feasibility analysis, in Proceedings of the 34th Real-Time Systems Symposium (RTSS), 2013, pp. 340\u2013349","DOI":"10.1109\/RTSS.2013.41"},{"issue":"5","key":"35_CR28","doi-asserted-by":"publisher","first-page":"602","DOI":"10.1007\/s11241-015-9234-z","volume":"51","author":"M Stigge","year":"2015","unstructured":"M. Stigge, W. Yi, Graph-based models for real-time workload: a survey. Real-Time Syst. 51(5), 602\u2013636 (2015)","journal-title":"Real-Time Syst."},{"key":"35_CR29","doi-asserted-by":"crossref","unstructured":"M. Stigge, P. Ekberg, N. Guan, W. Yi, On the tractability of digraph-based task models, in Proceedings of the 23rd Euromicro Conference on Real-Time Systems (ECRTS), July 2011a, pp. 162\u2013171","DOI":"10.1109\/ECRTS.2011.23"},{"key":"35_CR30","doi-asserted-by":"crossref","unstructured":"M. Stigge, P. Ekberg, N. Guan, W. Yi, The digraph real-time task model, in Proceedings of the 17th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), 2011b, pp. 71\u201380","DOI":"10.1109\/RTAS.2011.15"},{"key":"35_CR31","doi-asserted-by":"crossref","unstructured":"N. Tchidjo Moyo, E. Nicollet, F. Lafaye, C. Moy, On schedulability analysis of non-cyclic generalized multiframe tasks, in Proceedings of the 22nd Euromicro Conference on Real-Time Systems (ECRTS), 2010, pp. 271\u2013278","DOI":"10.1109\/ECRTS.2010.24"}],"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_35","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,30]],"date-time":"2024-09-30T23:27:10Z","timestamp":1727738830000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-287-251-7_35"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9789812872500","9789812872517"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-981-287-251-7_35","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"}}]}}