Uniform-machines scheduling: Difference between revisions

Revision as of 05:37, 30 January 2023

Revision as of 11:26, 16 February 2023

Line 10:

Minimizing the ''average'' completion time can be done in polynomial time:

* 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|lastlast1=Horowitz|firstfirst1=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|s2cid=18693114 |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>.

* '''Bruno, Coffman and Sethi'''<ref>{{Cite journal|lastlast1=Bruno|firstfirst1=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|doi-access=free}}</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]].'''<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|doi-access=free}}</ref>

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

Line 29:

A constant-factor approximation is attained by the [[Longest-processing-time-first scheduling#uniform|Longest-processing-time-first algorithm]] (LPT).

'''Horowitz and Sahni<ref name=":0">{{Cite journal|lastlast1=Horowitz|firstfirst1=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|s2cid=18693114 |issn=0004-5411}}</ref>''' presented:

* Exact [[dynamic programming]] algorithms for minimizing the ''maximum'' completion time on both uniform and unrelated machines. These algorithms run in exponential time (recall that these problems are all NP-hard).

* [[Polynomial-time approximation scheme]]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|doi-access=free}}</ref> presented several approximation algorithms for any number of [[Identical-machines scheduling|''identical'' machines]]. Later,<ref>{{Cite journal|lastlast1=Hochbaum|firstfirst1=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|lastlast1=Epstein|firstfirst1=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|s2cid=12965369 |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'')).

=== Monotonicity and Truthfulness ===

In some settings, the machine speed is the machine's private information, and we want to incentivize machines to reveal their true speed, that is, we want a [[truthful mechanism]]. An important consideration for attaining truthfulness is ''monotonicity''.<ref>{{Cite journal|lastlast1=Archer|firstfirst1=A.|last2=Tardos|first2=E.|date=2001-10-01|title=Truthful mechanisms for one-parameter agents|url=https://ieeexplore.ieee.org/abstract/document/959924/?casa_token=cfGjnQyxD3kAAAAA:zxN-eY-KjIvmmp2jwarxag2Ha2rbmnwAPyddWQ-_aMdz9JXkxjtb17Ivw5yDgx7llGw_gTSgvfk|journal=Proceedings 42nd IEEE Symposium on Foundations of Computer Science|pages=482–491|doi=10.1109/SFCS.2001.959924|isbn=0-7695-1390-5 |s2cid=11377808 }}</ref> It means that, if a machine reports a higher speed, and all other inputs remain the same, then the total processing time allocated to the machine weakly increases. For this problem:

* '''Auletta, De Prisco, Penna and Persiano'''<ref>{{Cite journal|lastlast1=Auletta|firstfirst1=Vincenzo|last2=De Prisco|first2=Roberto|last3=Penna|first3=Paolo|last4=Persiano|first4=Giuseppe|date=2004|editor-last=Diekert|editor-first=Volker|editor2-last=Habib|editor2-first=Michel|title=Deterministic Truthful Approximation Mechanisms for Scheduling Related Machines|url=https://link.springer.com/chapter/10.1007/978-3-540-24749-4_53|journal=STACSStacs 2004|series=Lecture Notes in Computer Science|volume=2996 |language=en|___location=Berlin, Heidelberg|publisher=Springer|pages=608–619|doi=10.1007/978-3-540-24749-4_53|isbn=978-3-540-24749-4}}</ref> presented a 4-approximation monotone algorithm, which runs in polytime when the number of machines is fixed.

*'''Ambrosio and Auletta'''<ref>{{Cite journal|lastlast1=Ambrosio|firstfirst1=Pasquale|last2=Auletta|first2=Vincenzo|date=2005|editor-last=Persiano|editor-first=Giuseppe|editor2-last=Solis-Oba|editor2-first=Roberto|title=Deterministic Monotone Algorithms for Scheduling on Related Machines|url=https://link.springer.com/chapter/10.1007/978-3-540-31833-0_22|journal=Approximation and Online Algorithms|series=Lecture Notes in Computer Science|volume=3351 |language=en|___location=Berlin, Heidelberg|publisher=Springer|pages=267–280|doi=10.1007/978-3-540-31833-0_22|isbn=978-3-540-31833-0}}</ref> proved that the [[Longest processing time|Longest Processing Time]] algorithm is monotone whenever the machine speeds are powers of some c ≥ 2, but not when c ≤ 1.78. In contrast, [[List scheduling]] is not monotone for ''c'' > 2.

* '''Andelman, Azar and Sorani'''<ref>{{Cite journal|lastlast1=Andelman|firstfirst1=Nir|last2=Azar|first2=Yossi|last3=Sorani|first3=Motti|date=2005|editor-last=Diekert|editor-first=Volker|editor2-last=Durand|editor2-first=Bruno|title=Truthful Approximation Mechanisms for Scheduling Selfish Related Machines|url=https://link.springer.com/chapter/10.1007/978-3-540-31856-9_6|journal=STACSStacs 2005|series=Lecture Notes in Computer Science|volume=3404 |language=en|___location=Berlin, Heidelberg|publisher=Springer|pages=69–82|doi=10.1007/978-3-540-31856-9_6|isbn=978-3-540-31856-9}}</ref> presented a 5-approximation monotone algorithm, which runs in polytime even when the number of machines is variable.

* '''Kovacz'''<ref>{{Cite journal|last=Kovács|first=Annamária|date=2005|editor-last=Brodal|editor-first=Gerth Stølting|editor2-last=Leonardi|editor2-first=Stefano|title=Fast Monotone 3-Approximation Algorithm for Scheduling Related Machines|url=https://link.springer.com/chapter/10.1007/11561071_55|journal=Algorithms – ESA 2005|series=Lecture Notes in Computer Science|volume=3669 |language=en|___location=Berlin, Heidelberg|publisher=Springer|pages=616–627|doi=10.1007/11561071_55|isbn=978-3-540-31951-1}}</ref> presented a 3-approximation monotone algorithm.

== Extensions ==

'''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.

'''Static versus Dynamic''': Machine scheduling algorithms are static or dynamic. A scheduling algorithm is '''static''' if the scheduling decisions as to what computational tasks will be allocated to what processors are made before running the program. An algorithm is '''dynamic''' if it is taken at run time. For static scheduling algorithms, a typical approach is to rank the tasks according to their precedence relationships and use a list scheduling technique to schedule them onto the processors.<ref>{{Cite journal|lastlast1=Kwok|firstfirst1=Yu-Kwong|last2=Ahmad|first2=Ishfaq|date=1999-12-01|title=Static scheduling algorithms for allocating directed task graphs to multiprocessors|journal=ACM Computing Surveys|volume=31|issue=4|pages=406–471|doi=10.1145/344588.344618|issn=0360-0300|citeseerx=10.1.1.322.2295|s2cid=207614150 }}</ref>

'''Multi-stage jobs''': In various settings, each job might have several operations that must be executed in parallel. Some such settings are handled by [[Open-shop scheduling|open shop scheduling]], [[flow shop scheduling]] and [[job shop scheduling]].