Content deleted Content added
Citation bot (talk | contribs) Alter: journal. Add: volume, isbn, s2cid, authors 1-1. Removed proxy/dead URL that duplicated identifier. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Corvus florensis | #UCB_webform 1199/3500 |
m clean up, removed: ?casa_token=cfGjnQyxD3kAAAAA:zxN-eY-KjIvmmp2jwarxag2Ha2rbmnwAPyddWQ-_aMdz9JXkxjtb17Ivw5yDgx7llGw_gTSgvfk |
||
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''<sub>1</sub>, ''J''<sub>2</sub>, ..., ''J<sub>n</sub>'' 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<sub>i,j</sub>''. In the general case, the times ''p<sub>i,j</sub>'' 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<sub>i</sub>'', and the run-time of job ''j'' on machine ''i'' is ''p<sub>i,j</sub>'' = ''p<sub>j</sub>'' / ''s<sub>i</sub>''.
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.
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>.
==Algorithms==
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
*'''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|last1=Bruno|first1=J.|last2=Coffman|first2=E. G.|last3=Sethi|first3=R.|date=1974-07-01|title=Scheduling independent tasks to reduce mean finishing time|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|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 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]].
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|last1=Horowitz|first1=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:
Line 39:
=== 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|last1=Archer|first1=A.|last2=Tardos|first2=E.|date=2001-10-01|title=Truthful mechanisms for one-parameter agents|url=https://ieeexplore.ieee.org/abstract/document/959924/
* '''Auletta, De Prisco, Penna and Persiano'''<ref>{{Cite journal|last1=Auletta|first1=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=Stacs 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.
| |||