{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T00:17:28Z","timestamp":1648685848683},"reference-count":4,"publisher":"World Scientific Pub Co Pte Lt","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2001,10]]},"abstract":"<jats:p> While many forms of schedule decision problems are known to be NP-complete, two forms of schedule analysis problems are shown to be coNP-complete in the strong sense. Each of these involve guaranteeing that all deadlines are met for a set of task-graphs in statically-mapped, priority-based, multiprocessor schedules given particular variabilities. Specifically, the first of these allows run-times which axe bracketed, where the actual run-time of some tasks can take on any value within a given range. The second deals with task-graphs which arrive asynchronously, that is where the release-time for each task-graphs may take either any or a bracketed value. These variations correspond to task-graphs with either release-time or run-time jitter. The results are robust in the sense that they apply when schedules are either preemptive or non-preemptive as well as for several other problem variations. <\/jats:p>","DOI":"10.1142\/s0129054101000667","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T06:58:59Z","timestamp":1027753139000},"page":"565-580","source":"Crossref","is-referenced-by-count":0,"title":["TWO CONP-COMPLETE SCHEDULE ANALYSIS PROBLEMS"],"prefix":"10.1142","volume":"12","author":[{"given":"David L.","family":"Rhodes","sequence":"first","affiliation":[{"name":"US Army CECOM, Research and Development Center, Fort Monmouth, NJ 07703, US"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wayne","family":"Wolf","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering, Princeton University, Princeton, NJ 08544, US"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"p_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.9.6.841"},{"key":"p_2","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1969.222573"},{"key":"p_4","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(75)80008-0"},{"key":"p_5","doi-asserted-by":"publisher","DOI":"10.1016\/0164-1212(94)00118-7"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054101000667","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T20:47:59Z","timestamp":1565124479000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054101000667"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,10]]},"references-count":4,"journal-issue":{"issue":"05","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2001,10]]}},"alternative-id":["10.1142\/S0129054101000667"],"URL":"https:\/\/doi.org\/10.1142\/s0129054101000667","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2001,10]]}}}