Content deleted Content added
Erel Segal (talk | contribs) No edit summary |
Erel Segal (talk | contribs) No edit summary |
||
Line 33:
{{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'']].
== Special cases ==
There is a special case in which ''p<sub>i,j</sub>'' is either 1 or infinity. In other words, each job can be processed on a subset of ''allowed machines'', and its run-time in each of these machines is 1. This variant is sometimes denoted by " '''P|p<sub>j</sub>=1,M<sub>j</sub>|'''<math>C_\max</math>". It can be solved in polynomial time. <ref>{{Cite journal|last=Lin|first=Yixun|last2=Li|first2=Wenhua|date=2004-07-01|title=Parallel machine scheduling of machine-dependent jobs with unit-length|url=https://www.sciencedirect.com/science/article/pii/S0377221702009141|journal=European Journal of Operational Research|series=EURO Excellence in Practice Award 2001|language=en|volume=156|issue=1|pages=261–266|doi=10.1016/S0377-2217(02)00914-1|issn=0377-2217}}</ref>
== Extensions ==
| |||