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'']].
== Linear programming formulation ==
A natural way to formulate the problem as a linear program is called the ''Lenstra–Shmoys–Tardos<ref name=":2">{{Cite journal|last1=Lenstra|first1=Jan Karel|last2=Shmoys|first2=David B.|last3=Tardos|first3=Éva|date=1990-01-01|title=Approximation algorithms for scheduling unrelated parallel machines|url=https://doi.org/10.1007/BF01585745|journal=Mathematical Programming|language=en|volume=46|issue=1|pages=259–271|doi=10.1007/BF01585745|issn=1436-4646|s2cid=206799898}}</ref> linear program (LST LP)''. For each machine ''i'' and job ''j<sub>,</sub>'' define a variable <math>z_{i,j}</math>, which equals 1 iff machine ''i'' processes job ''j'', and 0 otherwise. Then, the LP constraints are:
* <math>\sum_{i=1}^m z_{i,j} = 1</math> for every job ''j'' in 1,...,''n;''
* <math>\sum_{i=1}^m z_{i,j}\cdot p_{i,j} \leq T</math> for every machine ''i'' in 1,...,''m;''
* <math>z_{i,j} \in \{0,1\}</math> for every ''i'', ''j''.
Relaxing the integer constraints gives a linear program with size polynomial in the input. Solving the relaxed problem can be rounded to obtain a 2-approximation to the problem.''<ref name=":2" />''
Another LP formulation is the [[configuration linear program]]. For each machine ''i'', there are finitely many subsets of jobs that can be processed by machine ''i'' in time at most ''T''. Each such subset is called a ''configuration'' for machine ''i''. Denote by ''C<sub>i</sub>''(''T'') the set of all configurations for machine ''i''. For each machine ''i'' and configuration ''c'' in ''C<sub>i</sub>''(''T''), define a variable <math>x_{i,c}</math> which equals 1 iff the actual configuration used in machine ''i'' is ''c'', and 0 otherwise. Then, the LP constraints are:
* <math>\sum_{c\in C_i(T)}x_{i,c} = 1</math> for every machine ''i'' in 1,...,''m;''
* <math>\sum_{i=1}^m \sum_{c\ni j, c\in C_i(T)}x_{i,c} = 1</math> for every job ''j'' in 1,...,''n;''
* <math>x_{i,j} \in \{0,1\}</math> for every ''i'', ''j''.
Note that the number of configurations is usually exponential in the size of the problem, so the size of the configuration LP is exponential. However, in some cases it is possible to bound the number of possible configurations, and therefore find an approximate solution in polynomial time.
== Special cases ==
| |||