{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:35:58Z","timestamp":1750307758839,"version":"3.41.0"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2007,12,1]],"date-time":"2007-12-01T00:00:00Z","timestamp":1196467200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2007,12]]},"abstract":"<jats:p>In this paper, we present a novel approach to the constrained scheduling problem, while addressing a more general class of constraints that arise from the timing requirements on real-time embedded controllers. We provide general necessary and sufficient conditions for scheduling under precedence constraints and derive sufficient conditions for two well-known scheduling policies. We define mathematical problems that provide optimum priority and deadline assignments, while ensuring both precedence constraints and system's schedulability. We show how these problems can be relaxed to corresponding integer linear programming (ILP) formulations leveraging on available solvers. The results are demonstrated on a real design case.<\/jats:p>","DOI":"10.1145\/1324969.1324975","type":"journal-article","created":{"date-parts":[[2008,1,18]],"date-time":"2008-01-18T18:45:29Z","timestamp":1200681929000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Uniprocessor scheduling under precedence constraints for embedded systems design"],"prefix":"10.1145","volume":"7","author":[{"given":"Leonardo","family":"Mangeruca","sequence":"first","affiliation":[{"name":"Parades E.E.I.G., Roma, Italy"}]},{"given":"Massimo","family":"Baleani","sequence":"additional","affiliation":[{"name":"Parades E.E.I.G., Roma, Italy"}]},{"given":"Alberto","family":"Ferrari","sequence":"additional","affiliation":[{"name":"Parades E.E.I.G., Roma, Italy"}]},{"given":"Alberto","family":"Sangiovanni-Vincentelli","sequence":"additional","affiliation":[{"name":"University of California, Berkeley, California"}]}],"member":"320","published-online":{"date-parts":[[2007,12,12]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Baker T. 2005. An analysis of fixed-priority scheduling TR-050201 Florida State University. Tech. Rep. FSU-CS-TR-050201 Florida State University (June).  Baker T. 2005. An analysis of fixed-priority scheduling TR-050201 Florida State University. Tech. Rep. FSU-CS-TR-050201 Florida State University (June)."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00365393"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2003.1214341"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2004.103"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:TIME.0000048932.30002.d9"},{"key":"e_1_2_1_6_1","unstructured":"Coll P. Ribeiro C. and Souza C. 2003. Multiprocessor scheduling under precedence constraints: Polyhedral results. In Optimization Online Digest.  Coll P. Ribeiro C. and Souza C. 2003. Multiprocessor scheduling under precedence constraints: Polyhedral results. In Optimization Online Digest."},{"key":"e_1_2_1_7_1","volume-title":"Tech. Rep. Sloan Working Paper No. 4499-04, MIT (Aug).","author":"Correa J.","year":"2004","unstructured":"Correa , J. and Shulz , A . 2004 . Single machine scheduling with precedence constraints. Tech. Rep. Sloan Working Paper No. 4499-04, MIT (Aug). Correa, J. and Shulz, A. 2004. Single machine scheduling with precedence constraints. Tech. Rep. Sloan Working Paper No. 4499-04, MIT (Aug)."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1065110.1065114"},{"volume-title":"Proceedings of the 9th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS'03)","author":"Fersman E.","key":"e_1_2_1_9_1","unstructured":"Fersman , E. , Mokrushin , L. , Pettersson , P. , and Yi , W . 2003. Schedulability analysis using two clocks . In Proceedings of the 9th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS'03) . Springer, New York. 224--239. Fersman, E., Mokrushin, L., Pettersson, P., and Yi, W. 2003. Schedulability analysis using two clocks. In Proceedings of the 9th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS'03). Springer, New York. 224--239."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539791218664"},{"key":"e_1_2_1_11_1","unstructured":"Graphviz. web page http:\/\/www.graphviz.org.  Graphviz. web page http:\/\/www.graphviz.org."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-5316(82)90024-4"},{"volume-title":"Proceedings of the Work-in-Progress and Industrial Sessions, 13th Euromicro Conference on Real-Time Systems.","author":"Lisper B.","key":"e_1_2_1_13_1","unstructured":"Lisper , B. and Mellgren , P . 2001. Response-time calculation and priority assignment with integer programming methods . In Proceedings of the Work-in-Progress and Industrial Sessions, 13th Euromicro Conference on Real-Time Systems. Lisper, B. and Mellgren, P. 2001. Response-time calculation and priority assignment with integer programming methods. In Proceedings of the Work-in-Progress and Industrial Sessions, 13th Euromicro Conference on Real-Time Systems."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/321738.321743"},{"key":"e_1_2_1_15_1","unstructured":"Makhorin A. 2003. Glpk web page http:\/\/www.gnu.org\/software\/glpk\/glpk.html.  Makhorin A. 2003. Glpk web page http:\/\/www.gnu.org\/software\/glpk\/glpk.html."},{"volume-title":"Proceedings of the 17th Real-Time Systems Symposium (RTSS'96)","author":"Mok A.","key":"e_1_2_1_16_1","unstructured":"Mok , A. , Tsou , D.-C. , and Rooij , R. D . 1996. The msp.rtl real-time scheduler synthesis tool . In Proceedings of the 17th Real-Time Systems Symposium (RTSS'96) . IEEE Computer Society, Washington, DC, 118. Mok, A., Tsou, D.-C., and Rooij, R. D. 1996. The msp.rtl real-time scheduler synthesis tool. In Proceedings of the 17th Real-Time Systems Symposium (RTSS'96). IEEE Computer Society, Washington, DC, 118."},{"volume-title":"Proceedings of the 6th International Conference on Integer Programming and Combinatorial Optimization (IPCO'98)","author":"Munier A.","key":"e_1_2_1_17_1","unstructured":"Munier , A. , Queyranne , M. , and Schulz , A . 1998. Approximation bounds for a general class of precedence constrained parallel machine scheduling problems . In Proceedings of the 6th International Conference on Integer Programming and Combinatorial Optimization (IPCO'98) . Munier, A., Queyranne, M., and Schulz, A. 1998. Approximation bounds for a general class of precedence constrained parallel machine scheduling problems. In Proceedings of the 6th International Conference on Integer Programming and Combinatorial Optimization (IPCO'98)."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.57058"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:TIME.0000045315.61234.1e"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.338100"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/32.48943"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1324969.1324975","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1324969.1324975","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:39:27Z","timestamp":1750253967000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1324969.1324975"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,12]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2007,12]]}},"alternative-id":["10.1145\/1324969.1324975"],"URL":"https:\/\/doi.org\/10.1145\/1324969.1324975","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"type":"print","value":"1539-9087"},{"type":"electronic","value":"1558-3465"}],"subject":[],"published":{"date-parts":[[2007,12]]},"assertion":[{"value":"2006-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2006-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2007-12-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}