Premium
Scheduling identical jobs on uniform parallel machines
Author(s) -
Dessouky M.I.,
Lageweg B.J.,
Lenstra J.K.,
Velde S.L.
Publication year - 1990
Publication title -
statistica neerlandica
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.52
H-Index - 39
eISSN - 1467-9574
pISSN - 0039-0402
DOI - 10.1111/j.1467-9574.1990.tb01276.x
Subject(s) - tardiness , job shop scheduling , scheduling (production processes) , mathematical optimization , due date , mathematics , time complexity , computer science , minimax , arrival time , combinatorics , algorithm , schedule , engineering , operating system , transport engineering
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 ( n 3 ) time. We give a more concise formulation for minsum criteria, and show that general minmax criteria can be minimized in O ( n 2 ) time. We present faster algorithms, requiring only O ( n + m log m ) time for minimizing makespan and total completion time, O ( n log n ) time for minimizing total weighted completion time, maximum lateness, total tardiness and the weighted number of tardy jobs, and O ( n log 2 n ) time for maximum weighted tardiness. In the case of release dates, we propose an O ( n log n ) algorithm for minimizing makespan, and an O ( mn 2m+1 ) time dynamic programming algorithm for minimizing total completion time.