{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,20]],"date-time":"2026-08-20T15:12:41Z","timestamp":1787238761276,"version":"build-2736575974"},"reference-count":12,"publisher":"World Scientific Pub Co Pte Ltd","issue":"11n12","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Soft. Eng. Knowl. Eng."],"published-print":{"date-parts":[[2018,11]]},"abstract":"<jats:p>The timing requirements of real-time systems can be guaranteed by well-designed scheduling policies. The analysis of such scheduling uses an abstract task model of the system to diagnose the practicability of timing requirements. The task models have evolved from periodic models to more sophisticated graph-based ones, among which digraph real-time (DRT) task model is the most applicable because of its good expressiveness and analysis efficiency. However, the DRT model cannot support the commonly used precedence constraints within or between tasks. In this paper, we propose a new task model that extends the DRT model to support precedence constraints. Based on our model, we present two methods of uniprocessor schedulability analysis for static priority scheduling policy and earliest deadline first (EDF) scheduling policy. We also introduce an optimization technique to improve the efficiency of model analysis. Our experiments show that, despite a high computational complexity of the problem, our approach scales very well for large sets of tasks with precedence constraints.<\/jats:p>","DOI":"10.1142\/s0218194018400181","type":"journal-article","created":{"date-parts":[[2019,1,15]],"date-time":"2019-01-15T03:44:18Z","timestamp":1547523858000},"page":"1575-1595","source":"Crossref","is-referenced-by-count":2,"title":["Schedulability Analysis of Graph-Based Real-Time Task Model with Precedence Constraints"],"prefix":"10.1142","volume":"28","author":[{"given":"Rongfei","family":"Xu","sequence":"first","affiliation":[{"name":"School of Computer Science and Engineering, Beihang University, Xue Yuan Road No. 37, HaiDian District, Beijing 100191, P. R. China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Li","family":"Zhang","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, Beihang University, Xue Yuan Road No. 37, HaiDian District, Beijing 100191, P. R. China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ning","family":"Ge","sequence":"additional","affiliation":[{"name":"School of Software, Beihang University, Xue Yuan Road No. 37, HaiDian District, Beijing 100191, P. R. China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xavier","family":"Blanc","sequence":"additional","affiliation":[{"name":"LaBRI, UMR5800, University of Bordeaux, Bordeaux INP, CNRS, 351 Cours de la Liberation, Talence 33400, France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"219","published-online":{"date-parts":[[2019,1,15]]},"reference":[{"key":"S0218194018400181BIB001","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008656726700"},{"key":"S0218194018400181BIB002","doi-asserted-by":"publisher","DOI":"10.1007\/s11241-009-9075-8"},{"key":"S0218194018400181BIB005","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008030427220"},{"key":"S0218194018400181BIB006","first-page":"1","author":"Bonifaci V.","year":"2012","journal-title":"Computing Research Depository"},{"issue":"2","key":"S0218194018400181BIB007","first-page":"129","volume":"11","author":"Fersman E.","year":"2004","journal-title":"Nordic J. Comput."},{"key":"S0218194018400181BIB012","volume-title":"Real-Time Systems","author":"Krishna C. M.","year":"1999"},{"key":"S0218194018400181BIB013","doi-asserted-by":"publisher","DOI":"10.1145\/321738.321743"},{"key":"S0218194018400181BIB015","volume-title":"Fundamental Design Problems of Distributed Systems for the Hard-Realtime Environment","author":"Mok A. K.","year":"1983"},{"key":"S0218194018400181BIB018","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-017-0519-z"},{"key":"S0218194018400181BIB019","doi-asserted-by":"publisher","DOI":"10.1145\/3126505"},{"key":"S0218194018400181BIB020","doi-asserted-by":"publisher","DOI":"10.1023\/B:TIME.0000045315.61234.1e"},{"key":"S0218194018400181BIB024","doi-asserted-by":"publisher","DOI":"10.1007\/s11241-015-9234-z"}],"container-title":["International Journal of Software Engineering and Knowledge Engineering"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218194018400181","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T23:03:58Z","timestamp":1565132638000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218194018400181"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,11]]},"references-count":12,"journal-issue":{"issue":"11n12","published-online":{"date-parts":[[2019,1,15]]},"published-print":{"date-parts":[[2018,11]]}},"alternative-id":["10.1142\/S0218194018400181"],"URL":"https:\/\/doi.org\/10.1142\/s0218194018400181","relation":{},"ISSN":["0218-1940","1793-6403"],"issn-type":[{"value":"0218-1940","type":"print"},{"value":"1793-6403","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,11]]}}}