Uniform-machines scheduling: Difference between revisions

Revision as of 15:36, 18 June 2021

Revision as of 15:37, 18 June 2021

Line 31:

Later,<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> they developed a PTAS for ''uniform'' machines.

'''Epstein and Sgall'''<ref>{{Cite journal|last=Epstein|first=Leah|last2=Sgall|first2=Jiri|date=2004-05-01|title=Approximation Schemes for Schedulingon Uniformly Related and Identical Parallel Machines|url=https://doi.org/10.1007/s00453-003-1077-7|journal=Algorithmica|language=en|volume=39|issue=1|pages=43–57|doi=10.1007/s00453-003-1077-7|issn=1432-0541}}</ref> generalized this PTAS to handle more general objective functions. Let ''sC_i'' (for ''i'' between 1 and ''km'') be the makespan of processormachine ''i'' in a given schedule. Instead of minimizing the objective function max(''sC_i''), one can minimize the objective function max(''f''(''sC_i'')), where ''f'' is any fixed function. Similarly, one can minimize the objective function sum(''f''(''sC_i'')).

== Extensions ==