Scheduling identical jobs on uniform parallel machines

M.I. Dessouky, B.J. Lageweg, J.K. Lenstra and S.L. van de Velde

Statistica Neerlandica, 1990, vol. 44, issue 3, 115-123

Abstract: We address the problem of scheduling n identical jobs on m uniform parallel machines to optimize scheduling criteria that are nondecreasing in the job completion times. It is well known that this can be formulated as a linear assignment problem, and subsequently solved in O(n3) time. We give a more concise formulation for minsum criteria, and show that general minmax criteria can be minimized in O(n2) time. We present faster algorithms, requiring only O(n+mlog m) time for minimizing makespan and total completion time, O(nlogn) time for minimizing total weighted completion time, maximum lateness, total tardiness and the weighted number of tardy jobs, and O(nlog2n) time for maximum weighted tardiness. In the case of release dates, we propose an O(nlogn) algorithm for minimizing makespan, and an O(mn2m+1) time dynamic programming algorithm for minimizing total completion time.

Date: 1990
References: Add references at CitEc
Citations: View citations in EconPapers (15)

Downloads: (external link)
https://doi.org/10.1111/j.1467-9574.1990.tb01276.x

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:bla:stanee:v:44:y:1990:i:3:p:115-123

Ordering information: This journal article can be ordered from
http://www.blackwell ... bs.asp?ref=0039-0402

Access Statistics for this article

Statistica Neerlandica is currently edited by Miroslav Ristic, Marijtje van Duijn and Nan van Geloven

More articles in Statistica Neerlandica from Netherlands Society for Statistics and Operations Research
Bibliographic data for series maintained by Wiley Content Delivery ().