Uniform-machines scheduling: Difference between revisions

Revision as of 21:01, 19 June 2021

Revision as of 21:22, 19 June 2021

Line 1:

'''Uniform machine scheduling''' (also called '''uniformly-related machine scheduling''' or '''related machine scheduling''') is an [[optimization problem]] in [[computer science]] and [[Operations Research|operations research]]. It is a variant of [[optimal job scheduling]]. We are given ''n'' jobs ''J''₁, ''J''₂, ..., ''J_n'' of varying processing times, which need to be scheduled on ''m'' different machines. The goal is to minimize the [[makespan]] - the total time required to execute the schedule. The time that machine ''i'' needs in order to process job j is denoted by ''p_i,j''. In the general case, the times ''p_i,j'' are unrelated, and any matrix of positive processing times is possible. In the specific variant called ''uniform machine scheduling'', some machines are ''uniformly'' faster than others. This means that, for each machine ''i'', there is a speed factor ''s_i'', and the run-time of job ''j'' on machine ''i'' is ''p_i,j'' = ''p_j'' / ''s_i''.

In the standard [[Optimal job scheduling|three-field notation for optimal job scheduling problems]], the uniform-machine variant is denoted by '''Q''' in the first field. For example, the problem denoted by " '''Q||'''<math>C_\max</math>" is a uniform machine scheduling problem with no constraints, where the goal is to minimize the maximum completion time. 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.

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); it is denoted by '''Q||'''<math>\sum C_i</math>. 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. This is denoted by '''Q||'''<math>\sum w_i C_i</math>.

Line 13 ⟶ 11:

* The '''SPT algorithm''' (Shortest Processing Time First), sorts the jobs by their length, shortest first, and then assigns them to the processor with the earliest end time so far. It runs in time O(''n'' log ''n''), and minimizes the average completion time on ''identical'' machines,<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> '''P||'''<math>\sum C_i</math>.

* '''Horowitz and Sahni<ref name=":0" />''' present an exact algorithm, with run time O(''n'' log ''m n''), for minimizing the average completion time on ''uniform'' machines, '''Q||'''<math>\sum C_i</math>.

**There can be many SPT schedules; finding the SPT schedule with the smallest finish time (also called OMFT - optimal mean finish time) is NP-hard. Sahni<ref name=":3" /> presents an exponential-time algorithm and a polynomial-time approximation algorithm for identical machines.

* '''Horowitz and Sahni<ref name=":0" />''' present an exact algorithm, with run time O(''n'' log ''m n''), for minimizing the average completion time on ''uniform'' machines, '''Q||'''<math>\sum C_i</math>.

* '''Bruno, Coffman and Sethi'''<ref>{{Cite journal|last=Bruno|first=J.|last2=Coffman|first2=E. G.|last3=Sethi|first3=R.|date=1974-07-01|title=Scheduling independent tasks to reduce mean finishing time|url=https://doi.org/10.1145/361011.361064|journal=Communications of the ACM|volume=17|issue=7|pages=382–387|doi=10.1145/361011.361064|issn=0001-0782}}</ref> present an algorithm, running in time <math>O(\max(m n^2,n^3))</math>, for minimizing the average completion time on ''unrelated'' machines, '''R||'''<math>\sum C_i</math>.

=== Minimizing the weighted-average completion time ===

Minimizing the ''weighted average'' completion time is NP-hard even on ''identical'' machines, by reduction from the [[Knapsack problem|knapsack problem.]]'''<ref name=":0" />''' It is NP-hard even if the number of machines is fixed and at least 2, by reduction from the [[partition problem]].<ref name=":3">{{Cite journal|last=Sahni|first=Sartaj K.|date=1976-01-01|title=Algorithms for Scheduling Independent Tasks|url=https://doi.org/10.1145/321921.321934|journal=Journal of the ACM|volume=23|issue=1|pages=116–127|doi=10.1145/321921.321934|issn=0004-5411}}</ref>

'''Sahni<ref name=":3" />''' presents an exponential-time algorithm and a polynomial-time approximation algorithm for ''identical'' machines.

Line 28 ⟶ 25:

=== Minimizing the maximum completion time (makespan) ===

Minimizing the ''maximum'' completion time is NP-hard even for ''identical'' machines, by reduction from the [[partition problem]]. Many exact and approximation algorithms are known.

For ''identical'' machines, the problem is equivalent to [[multiway number partitioning]], where the job lengths are the numbers, the number of machines (denoted here by ''m'') is the number of parts (denoted there by ''k''), and the goal is to minimize the maximum sum. See [[multiway number partitioning#minmax]] for details about exact and approximate algorithms.

'''Graham''' proved that:

* Any [[list scheduling]] algorithm (an algorithm that processes the jobs in an arbitrary fixed order, and schedules each job to the first available machine) is a <math>2-1/m</math> approximation for ''identical'' machines.<ref name=":2">{{Cite journal|last=Graham|first=Ron L.|author-link=Ronald Graham|date=1966|title=Bounds for Certain Multiprocessing Anomalies|url=https://onlinelibrary.wiley.com/doi/abs/10.1002/j.1538-7305.1966.tb01709.x|journal=Bell System Technical Journal|language=en|volume=45|issue=9|pages=1563–1581|doi=10.1002/j.1538-7305.1966.tb01709.x|issn=1538-7305}}</ref> The bound is tight for any ''m''. This algorithm runs in time O(''n'').

* The specific list-scheduling algorithm called '''Longest Processing Time First''' (LPT), which sorts the jobs by descending length, is a <math>4/3-1/3m</math> approximation for ''identical'' machines.<ref name=":1">{{Cite journal|last=Graham|first=Ron L.|author-link=Ronald Graham|date=1969-03-01|title=Bounds on Multiprocessing Timing Anomalies|url=https://epubs.siam.org/doi/abs/10.1137/0117039|journal=SIAM Journal on Applied Mathematics|volume=17|issue=2|pages=416–429|doi=10.1137/0117039|issn=0036-1399}}</ref>{{Rp|sec.5}} It has good asymptotic convergence properties even for ''uniform'' machines.<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> It is also called [[greedy number partitioning]].

'''Sahni'''<ref name=":3">{{Cite journal|last=Sahni|first=Sartaj K.|date=1976-01-01|title=Algorithms for Scheduling Independent Tasks|url=https://doi.org/10.1145/321921.321934|journal=Journal of the ACM|volume=23|issue=1|pages=116–127|doi=10.1145/321921.321934|issn=0004-5411}}</ref> presented several algorithms for ''identical'' machines. In particular:

* A PTAS that attains (1+ε)OPT in time <math>O(n\cdot (n^2 / \epsilon)^{m-1})</math>. It is an FPTAS if ''m'' is fixed. For m=2, the run-time improves to <math>O(n^2 / \epsilon)</math>. The algorithm uses a technique called ''interval partitioning''.

'''Horowitz and Sahni<ref name=":0">{{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>''' presented:

Line 46 ⟶ 32:

* [[Polynomial-time approximation scheme]]<nowiki/>s, which for any ''ε''>0, attain at most (1+ε)OPT. For minimizing the ''maximum'' completion time on two ''uniform'' machines, their algorithm runs in time <math>O(10^{2l} n)</math>, where <math>l</math> is the smallest integer for which <math>\epsilon \geq 2\cdot 10^{-l}</math>. Therefore, the run-time is in <math>O( n / \epsilon^2)</math>, so it is an [[FPTAS]]. For minimizing the ''maximum'' completion time on two ''unrelated'' machines, the run-time is <math>O(10^{l} n^2)</math> = <math>O( n^2 / \epsilon)</math>. They claim that their algorithms can be easily extended for any number of uniform machines, but do not analyze the run-time in this case.

'''Hochbaum and Shmoys'''<ref name=":02">{{Cite journal|last1=Hochbaum|first1=Dorit S.|last2=Shmoys|first2=David B.|date=1987-01-01|title=Using dual approximation algorithms for scheduling problems theoretical and practical results|url=https://doi.org/10.1145/7531.7535|journal=Journal of the ACM|volume=34|issue=1|pages=144–162|doi=10.1145/7531.7535|issn=0004-5411|s2cid=9739129}}</ref> presented several approximation algorithms for any number of [[Identical-machines scheduling|''identical'' machines]]. (evenLater,<ref>{{Cite whenjournal|last=Hochbaum|first=Dorit theS.|last2=Shmoys|first2=David numberB.|date=1988-06-01|title=A ofPolynomial machinesApproximation isScheme notfor fixed)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.

* For any ''r'' >0, an algorithm with approximation ratio at most (6/5+2^−''r'' ) in time <math>O(n(r+\log{n}))</math>.

* For any ''r'' >0, an algorithm with approximation ratio at most (7/6+2^−''r'' ) in time <math>O(n(r m^4+\log{n}))</math>.

* For any ''ε''>0, an algorithm with approximation ratio at most (1+ε) in time <math>O((n/\varepsilon)^{(1/\varepsilon^2)})</math> . This is a [[Polynomial-time approximation scheme|PTAS]]. Note that, when the number of machines is a part of the input, the problem is [[Strong NP-completeness|strongly NP-hard]], so no FPTAS is possible.

**The run-time of this algorithm was later improved to <math>O\left((n/\varepsilon)^{(1/\varepsilon)\log{(1/\varepsilon)}}\right)</math>.<ref>{{Cite journal|date=1989-05-08|title=Bin packing with restricted piece sizes|url=https://www.sciencedirect.com/science/article/abs/pii/0020019089902238|journal=Information Processing Letters|language=en|volume=31|issue=3|pages=145–149|doi=10.1016/0020-0190(89)90223-8|issn=0020-0190}}</ref>

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 the PTAS for uniform machines to handle more general objective functions. Let ''C_i'' (for ''i'' between 1 and ''m'') be the makespan of machine ''i'' in a given schedule. Instead of minimizing the objective function max(''C_i''), one can minimize the objective function max(''f''(''C_i'')), where ''f'' is any fixed function. Similarly, one can minimize the objective function sum(''f''(''C_i'')).

Line 73 ⟶ 52:

[[Category:Optimal scheduling]]

[[Category:Number partitioning]]