Preemptive scheduling on parallel processors with due dates

UTSePress Research/Manakin Repository

Search UTSePress Research

Advanced Search


My Account

Show simple item record Zinder, Yakov en_US Singh, Gaurav en_US 2009-12-21T02:28:01Z 2009-12-21T02:28:01Z 2005 en_US
dc.identifier 2005002882 en_US
dc.identifier.citation Zinder Yakov and Singh Gaurav 2005, 'Preemptive scheduling on parallel processors with due dates', World Scientific Publishing Co, vol. 22, no. 4, pp. 445-462. en_US
dc.identifier.issn 0217-5959 en_US
dc.identifier.other C1 en_US
dc.description.abstract The paper presents a priority algorithm for the maximum lateness problem with parallel identical processors, presedence constraints, and preemptions. The presented algorithm calculates the priority of each task by constructing a schedule for the set of its successors. The algorithm is motivated by comparison of its nonpreemptive counterpart with other algorithms for the problem with unit execution time tasks. It is shown that the presented algorithm constructs an optimal schedule for the problem with two processors and arbitrary precedence constaints, and for the problem with an arbitrary number of processors and precedence constraints in the form of an in-tree. This proof also indicates that the presented algorithm allows the worst case performace ratio previously extablished for the so-called Muntz-Coffman algorithm for a particular case of the considered problem where all due dates are zero. en_US
dc.publisher World Scientific Publishing Co en_US
dc.relation.isbasedon en_US
dc.title Preemptive scheduling on parallel processors with due dates en_US
dc.parent Asia-Pacific Journal of Operational Research en_US
dc.journal.volume 22 en_US
dc.journal.number 4 en_US
dc.publocation Singapore en_US
dc.identifier.startpage 445 en_US
dc.identifier.endpage 462 en_US SCI.Mathematical Sciences en_US
dc.conference Verified OK en_US
dc.for 150300 en_US
dc.personcode 930901 en_US
dc.personcode 0000022946 en_US
dc.percentage 100 en_US Business and Management en_US
dc.classification.type FOR-08 en_US
dc.description.keywords parallel identical processors; precedence constraints; maximum lateness preemptions en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record