Uniform-machines scheduling: Difference between revisions

Revision as of 14:49, 18 June 2021

Revision as of 14:53, 18 June 2021

Line 12:

'''Horowitz and Sahni<ref>{{Cite journal|last=Horowitz|first=Ellis|last2=Sahni|first2=Sartaj|date=1976-04-01|title=Exact and Approximate Algorithms for Scheduling Nonidentical Processors|url=https://doi.org/10.1145/321941.321951|journal=Journal of the ACM|volume=23|issue=2|pages=317–327|doi=10.1145/321941.321951|issn=0004-5411}}</ref>''' present several algorithms for both uniform machines and unrelated machines, with various objective functions:

* ExactAn algorithmsexact algorithm for minimizing the ''maximum'' completion time, andon forboth minimizinguniform aand weightedunrelated averagemachines, ofwith theexponential completion timesrun-time (where each job mayboth havethese aproblems differentare weightNP-hard).

*An exact algorithm for minimizing the ''average'' completion time on ''uniform'' machines, with run time O(''n'' log ''m n'').

*An exact algorithms for minimizing the weighted-average completion time on uniform machines, with exponential run-time (this problem is NP-hard).

'''Hochbaum and Shmoys''',<ref>{{Cite journal|last=Hochbaum|first=Dorit S.|last2=Shmoys|first2=David B.|date=1988-06-01|title=A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach|url=https://epubs.siam.org/doi/abs/10.1137/0217033|journal=SIAM Journal on Computing|volume=17|issue=3|pages=539–551|doi=10.1137/0217033|issn=0097-5397}}</ref> who developed a PTAS for identical processors, extended their PTAS to handle processors with different speeds.