Content deleted Content added
Erel Segal (talk | contribs) No edit summary |
Erel Segal (talk | contribs) |
||
Line 4:
A special case of uniform machine scheduling is '''identical machine scheduling''', in which all machines have the same speed. This variant is denoted by '''P''' in the first field. For example, " '''P||'''<math>C_\max</math>" is an identical machine scheduling problem with no constraints, where the goal is to minimize the maximum completion time. This problem is also a special case of the [[multiway number partitioning]] problem. In both problems, the goal is to partition numbers into subsets with nearly-equal sum; identical machine scheduling is a special case in which the objective is to minimize the largest sum. Many algorithms for multiway number partitioning, both exact and approximate, can be used to attain this objective.
In some variants of the problem, instead of minimizing the ''maximum'' completion time, it is desired to minimize the ''average'' completion time (averaged over all ''n'' jobs). More generally, when some jobs are more important than others, it may be desired to minimize a ''[[Weighted arithmetic mean|weighted average]]'' of the completion time, where each job has a different weight.
==Algorithms==
The simple algorithm called [[greedy number partitioning]], or the '''LPT algorithm''' (Longest Processing Time), sorts the jobs by their length, longest first, and then assigns them to the processor with the earliest end time so far. While originally developed for identical processors, it has good asymptotic convergence properties even with different speeds.<ref>{{Cite journal|last=Frenk|first=J. B. G.|last2=Rinnooy Kan|first2=A. H. G.|date=1987-05-01|title=The Asymptotic Optimality of the LPT Rule|url=https://pubsonline.informs.org/doi/abs/10.1287/moor.12.2.241|journal=Mathematics of Operations Research|volume=12|issue=2|pages=241–254|doi=10.1287/moor.12.2.241|issn=0364-765X}}</ref>
'''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:
* Exact algorithms for minimizing the maximum completion time, and for minimizing a weighted average of the completion times (where each job may have a different weight).
'''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.
Line 12 ⟶ 18:
'''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 ''s<sub>i</sub>'' (for ''i'' between 1 and ''k'') be the makespan of processor ''i'' in a given schedule. Instead of minimizing the objective function max(''s<sub>i</sub>''), one can minimize the objective function max(''f''(''s<sub>i</sub>'')), where ''f'' is any fixed function. Similarly, one can minimize the objective function sum(''f''(''s<sub>i</sub>'')).
==
'''Dependent jobs''': In some cases, the jobs may be dependent. For example, take the case of reading user credentials from console, then use it to authenticate, then if authentication is successful display some data on the console. Clearly one task is dependent upon another. This is a clear case of where some kind of [[Order theory|ordering]] exists between the tasks. In fact it is clear that it can be modelled with [[partial ordering]]. Then, by definition, the set of tasks constitute a [[Lattice (order)|lattice structure]]. This adds further complication to the multiprocessor scheduling problem.
| |||