An iterative algorithm for scheduling unit-time taskswith precedence constraints to minimisethe maximum lateness

Yakov Zinder and Duncan Roper

Annals of Operations Research, 1998, vol. 81, issue 0, 343 pages

Abstract: We consider the maximum lateness problem in which all tasks have the same executiontime and must be processed on m > 1 parallel identical processors subject to precedenceconstraints. All tasks and all processors are available at time t=0, and each task has a duedate. If all due dates are zero, the maximum lateness problem converts to the makespanproblem, which is known to be NP-hard. We present a polynomial time algorithm thatenables us to obtain an optimal schedule for the case m=2 and gives an approximate solutionfor the general case. The upper bound for this algorithm is derived and proved to be tight. Ifall due dates are zero, then the upper bound obtained coincides with the upper bound for theCoffman - Graham algorithm, which is the best known for the makespan problem. Copyright Kluwer Academic Publishers 1998

Date: 1998
References: Add references at CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://hdl.handle.net/10.1023/A:1018917426360 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:81:y:1998:i:0:p:321-343:10.1023/a:1018917426360

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1023/A:1018917426360

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().