{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T12:27:52Z","timestamp":1773404872655,"version":"3.50.1"},"reference-count":0,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Parallel Process. Lett."],"published-print":{"date-parts":[[1993,3]]},"abstract":"<jats:p> Papadimitrjou and Yannakakis showed that unit execution time tasks in interval orders can be scheduled in linear time on N processors when communication cost is ignored. The objective function was to minimize the schedule length. They have also shown that the generalization of this problem to arbitrary execution times is NP- complete . In this paper, we study the problem of scheduling task graphs with communication on N processors when the task graph is an interval order. We prove that this scheduling problem can be solved in polynomial time when the execution cost of the system tasks is identical and equal to the communication cost between any pair of processors. We introduce an algorithm of O(Ne) to minimize the schedule length, where e is the number of arcs in the interval order. <\/jats:p>","DOI":"10.1142\/s0129626493000083","type":"journal-article","created":{"date-parts":[[2004,11,23]],"date-time":"2004-11-23T03:29:30Z","timestamp":1101180570000},"page":"53-58","source":"Crossref","is-referenced-by-count":15,"title":["THE TIME COMPLEXITY OF SCHEDULING INTERVAL ORDERS WITH COMMUNICATION IS POLYNOMIAL"],"prefix":"10.1142","volume":"03","author":[{"given":"HESHAM H.","family":"ALI","sequence":"first","affiliation":[{"name":"Department of Mathematics and Computer Science,  University of Nebraska at Omaha, Omaha, NE 68182\u20130243, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"HESHAM","family":"EL-REWINI","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science,  University of Nebraska at Omaha, Omaha, NE 68182\u20130243, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,21]]},"container-title":["Parallel Processing Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129626493000083","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T16:24:34Z","timestamp":1565108674000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129626493000083"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,3]]},"references-count":0,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2011,11,21]]},"published-print":{"date-parts":[[1993,3]]}},"alternative-id":["10.1142\/S0129626493000083"],"URL":"https:\/\/doi.org\/10.1142\/s0129626493000083","relation":{},"ISSN":["0129-6264","1793-642X"],"issn-type":[{"value":"0129-6264","type":"print"},{"value":"1793-642X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,3]]}}}