{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T21:00:11Z","timestamp":1767992411612,"version":"3.49.0"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,5,27]],"date-time":"2021-05-27T00:00:00Z","timestamp":1622073600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,5,27]],"date-time":"2021-05-27T00:00:00Z","timestamp":1622073600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Real-Time Syst"],"published-print":{"date-parts":[[2022,3]]},"DOI":"10.1007\/s11241-021-09370-7","type":"journal-article","created":{"date-parts":[[2021,5,27]],"date-time":"2021-05-27T21:02:37Z","timestamp":1622149357000},"page":"85-102","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["An ILP representation of a DAG scheduling problem"],"prefix":"10.1007","volume":"58","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4541-3445","authenticated-orcid":false,"given":"Sanjoy","family":"Baruah","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,5,27]]},"reference":[{"key":"9370_CR1","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/0272-6963(82)90020-1","volume":"3","author":"K Baker","year":"1982","unstructured":"Baker K, Bertrand J (1982) A dynamic priority rule for scheduling against due-dates. J Oper Manag 3:37\u201342","journal-title":"J Oper Manag"},{"key":"9370_CR2","doi-asserted-by":"publisher","DOI":"10.1002\/9780470451793","volume-title":"Principles of sequencing and scheduling","author":"KR Baker","year":"2009","unstructured":"Baker KR, Trietsch D (2009) Principles of sequencing and scheduling. Wiley Publishing, New York"},{"key":"9370_CR4","doi-asserted-by":"crossref","unstructured":"Baruah S (2020a) Scheduling DAGs when processor assignments are specified. In: Proceedings of the twenty-fifth international conference on real-time and network systems, RTNS \u201920, New York, NY, USA. ACM","DOI":"10.1145\/3394810.3394813"},{"key":"9370_CR5","doi-asserted-by":"crossref","unstructured":"Baruah S (2020b) Work in progress: the ILP-tractability of schedulability analysis problems. In: Work in progress (WiP) session of the IEEE real-time systems symposium","DOI":"10.1109\/RTSS49844.2020.00046"},{"key":"9370_CR3","doi-asserted-by":"crossref","unstructured":"Baruah S, Mok A, Rosier L (1990) Preemptively scheduling hard-real-time sporadic tasks on one processor. In: Proceedings of the 11th real-time systems symposium, pp. 182\u2013190. Orlando, Florida. IEEE Computer Society Press","DOI":"10.1109\/REAL.1990.128746"},{"key":"9370_CR6","doi-asserted-by":"crossref","unstructured":"Baruah S, Bonifaci V, Marchetti-Spaccamela A (2015) The global EDF scheduling of systems of conditional sporadic DAG tasks. In: Proceedings of the 2014 26th Euromicro conference on real-time systems, ECRTS \u201915, pp 222\u2013231, Lund (Sweden). IEEE Computer Society Press","DOI":"10.1109\/ECRTS.2015.27"},{"key":"9370_CR7","unstructured":"Ben-Amor S (2021) Multicore scheduling of dependent tasks with probabilistic execution times. PhD thesis, Sorbonne Universit\u00e9"},{"key":"9370_CR8","doi-asserted-by":"crossref","unstructured":"Ben-Amor S, Cucu-Grosjean L, Maxim D (2019) Worst-case response time analysis for partitioned fixed-priority DAG tasks on identical processors. In: 24th IEEE international conference on emerging technologies and factory automation, ETFA 2019, Zaragoza, Spain, September 10\u201313, 2019, pp 1423\u20131426. IEEE","DOI":"10.1109\/ETFA.2019.8869147"},{"key":"9370_CR9","unstructured":"Bertogna M (2019) A view on future challenges for the real-time community. https:\/\/www.irit.fr\/rtns2019\/wp-content\/uploads\/2019\/11\/bertogna_keynote.pdf, Keynote talk at the 27th International Conference on Networks and Systems, Toulouse, France"},{"key":"9370_CR10","doi-asserted-by":"crossref","unstructured":"Cook S (1971) The complexity of theorem-proving procedures. In: Proceedings of the 3rd annual ACM symposium on the theory of computing, pp 151\u2013158","DOI":"10.1145\/800157.805047"},{"key":"9370_CR11","volume-title":"Introduction to algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen TH, Leiserson CE, Rivest RL, Stein C (2009) Introduction to algorithms, 3rd edn. MIT Press, New York","edition":"3"},{"key":"9370_CR12","volume-title":"Computers and intractability : a guide to the theory of NP-completeness","author":"M Garey","year":"1979","unstructured":"Garey M, Johnson D (1979) Computers and intractability : a guide to the theory of NP-completeness. W. H. Freeman and company, NewYork"},{"key":"9370_CR13","doi-asserted-by":"publisher","first-page":"1563","DOI":"10.1002\/j.1538-7305.1966.tb01709.x","volume":"45","author":"R Graham","year":"1966","unstructured":"Graham R (1966) Bounds for certain multiprocessing anomalies. Bell Syst Techn J 45:1563\u20131581","journal-title":"Bell Syst Techn J"},{"key":"9370_CR19","doi-asserted-by":"crossref","unstructured":"Houssam-Eddine Z, Capodieci N, Cavicchioli R, Lipari G (2020) The HPC-DAG task model for heterogeneous real-time systems. IEEE Trans Comput","DOI":"10.1109\/TC.2020.3023169"},{"issue":"3","key":"9370_CR14","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/0166-218X(94)90142-2","volume":"52","author":"K Jansen","year":"1994","unstructured":"Jansen K (1994) Analysis of scheduling problems with typed task systems. Discret Appl Math 52(3):223\u2013232","journal-title":"Discret Appl Math"},{"key":"9370_CR15","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of computer computations","author":"R Karp","year":"1972","unstructured":"Karp R (1972) Reducibility among combinatorial problems. In: Miller R, Thatcher J (eds) Complexity of computer computations. Plenum Press, New York, pp 85\u2013103"},{"key":"9370_CR16","doi-asserted-by":"crossref","unstructured":"Marchetti-Spaccamela A, Megow N, Schl\u00f6ter J, Skutella M, Stougie L (2020) On the complexity of conditional DAG scheduling in multiprocessor systems. In: IEEE International Parallel and Distributed Processing Symposium (IPDPS)","DOI":"10.1109\/IPDPS47924.2020.00112"},{"key":"9370_CR17","doi-asserted-by":"crossref","unstructured":"Melani A, Bertogna M, Bonifaci V, Marchetti-Spaccamela A, Buttazzo G (2015) Response-time analysis of conditional DAG tasks in multiprocessor systems. In: Proceedings of the 2014 26th Euromicro Conference on Real-Time Systems, ECRTS \u201915, pp 222\u2013231, Lund (Sweden). IEEE Computer Society Press","DOI":"10.1109\/ECRTS.2015.26"},{"issue":"3","key":"9370_CR18","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1016\/S0022-0000(75)80008-0","volume":"10","author":"J Ullman","year":"1975","unstructured":"Ullman J (1975) NP-complete scheduling problems. J Comput Syst Sci 10(3):384\u2013393","journal-title":"J Comput Syst Sci"}],"container-title":["Real-Time Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11241-021-09370-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11241-021-09370-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11241-021-09370-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,3]],"date-time":"2022-03-03T22:04:29Z","timestamp":1646345069000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11241-021-09370-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,27]]},"references-count":19,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,3]]}},"alternative-id":["9370"],"URL":"https:\/\/doi.org\/10.1007\/s11241-021-09370-7","relation":{},"ISSN":["0922-6443","1573-1383"],"issn-type":[{"value":"0922-6443","type":"print"},{"value":"1573-1383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,5,27]]},"assertion":[{"value":"18 May 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 May 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}