Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) No edit summary |
||
Line 4:
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 '''R||'''<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 '''R||'''<math>\sum w_i C_i</math>.
In a third variant, the goal is to ''maximize'' the ''minimum'' completion time, " '''R||'''<math>C_\min</math>" . This variant corresponds to the problem of [[Egalitarian item allocation]].
== Algorithms ==
=== Minimizing the average completion time ===▼
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 is NP-hard even on ''identical'' machines, by reduction from the [[knapsack problem]].'''<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>''' 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>▼
=== Minimizing the maximum completion time (makespan) ===
Minimizing the ''maximum'' completion time is NP-hard even for ''identical'' machines, by reduction from the [[partition problem]].
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:
* 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).
Line 24 ⟶ 21:
Glass, Potts and Shade<ref>{{Cite journal|date=1994-07-01|title=Unrelated parallel machine scheduling using local search|url=https://www.sciencedirect.com/science/article/pii/0895717794902054|journal=Mathematical and Computer Modelling|language=en|volume=20|issue=2|pages=41–52|doi=10.1016/0895-7177(94)90205-4|issn=0895-7177|doi-access=free}}</ref> compare various [[Local search (optimization)|local search]] techniques for minimizing the makespan on unrelated machines. Using computerized simulations, they find that [[tabu search]] and [[simulated annealing]] perform much better than [[Genetic algorithm|genetic algorithms]].
▲=== Minimizing the average completion time ===
▲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 is NP-hard even on ''identical'' machines, by reduction from the [[knapsack problem]].'''<ref name=":0"
=== Maximizing the profit ===
Bar-Noy, Bar-Yehuda, Freund, Naor and Schieber<ref>{{Cite journal|last=Bar-Noy|first=Amotz|last2=Bar-Yehuda|first2=Reuven|last3=Freund|first3=Ari|last4=(Seffi) Naor|first4=Joseph|last5=Schieber|first5=Baruch|author5-link=Baruch Schieber|date=2001-09-01|title=A unified approach to approximating resource allocation and scheduling|url=https://doi.org/10.1145/502102.502107|journal=Journal of the ACM|volume=48|issue=5|pages=1069–1090|doi=10.1145/502102.502107|issn=0004-5411}}</ref> consider a setting in which, for each job and machine, there is a ''profit'' for running this job on that machine. They present a 1/2 approximation for discrete input and (1-''ε'')/2 approximation for continuous input.
=== Maximizing the minimum completion time ===
{{Main|Egalitarian item allocation}}
Suppose that, instead of "jobs" we have valuable items, and instead of "machines" we have people. Person ''i'' values item j at ''p<sub>i,j</sub>''. We would like to allocate the items to the people, such that the least-happy person is as happy as possible. This problem is equivalent to unrelated-machines scheduling in which the goal is to maximize the minimum completion time. It is better known by the name ''egalitarian'' or [[Max-min item allocation|''max-min item allocation'']].
== Extensions ==
| |||