Content deleted Content added
m →Minimizing the maximum completion time (makespan): Fix typo in name |
m Open access bot: url-access=subscription updated in citation with #oabot. |
||
| (7 intermediate revisions by 5 users not shown) | |||
Line 13:
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|last1=Horowitz|first1=Ellis|last2=Sahni|first2=Sartaj|date=1976-04-01|title=Exact and Approximate Algorithms for Scheduling Nonidentical Processors
* 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|Polynomial-time approximation schemes]], 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.
Lenstra, Shmoys and Tardos<ref>{{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|s2cid=52867171 |issn=1436-4646|url-access=subscription}}</ref> presented a polytime 2-factor approximation algorithm, and proved that no polytime algorithm with approximation factor smaller than 3/2 is possible unless P=NP. Closing the gap between the 2 and the 3/2 is a long-standing open problem.
Verschae and Wiese<ref>{{Cite journal|last1=Verschae|first1=José|last2=Wiese|first2=Andreas|date=2013-11-10|title=On the configuration-LP for scheduling on unrelated machines|url=https://link-springer-com.mgs.ariel.ac.il/article/10.1007/s10951-013-0359-4|journal=Journal of Scheduling|volume=17|issue=4|pages=371–383|doi=10.1007/s10951-013-0359-4|s2cid=254694965 |issn=1094-6136|arxiv=1011.4957}}</ref> presented a different 2-factor approximation algorithm.
Glass, Potts and Shade<ref>{{Cite journal|date=1994-07-01|title=Unrelated parallel machine scheduling using local search|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=
=== Minimizing the average completion time ===
Line 28:
Minimizing the ''weighted average'' completion time, '''R||'''<math>\sum w_j C_j</math> (where ''w<sub>j</sub>'' is the weight of job ''j''), 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|s2cid=10956951 |issn=0004-5411|doi-access=free}}</ref>
Schulz and Skutella<ref>{{Cite journal |last1=Schulz |first1=Andreas S. |last2=Skutella |first2=Martin |date=2002-01-01 |title=Scheduling Unrelated Machines by Randomized Rounding |url=https://epubs.siam.org/doi/abs/10.1137/S0895480199357078 |journal=SIAM Journal on Discrete Mathematics |volume=15 |issue=4 |pages=450–469 |doi=10.1137/S0895480199357078 |issn=0895-4801|url-access=subscription }}</ref> present a (3/2+ε)-approximation algorithm using [[randomized rounding]]. Their algorithm is a (2+ε)-approximation for the problem with job release times, '''R|<math>r_j</math>|'''<math>\sum w_j C_j</math>.
=== Maximizing the profit ===
Bar-Noy, Bar-Yehuda, Freund, Naor and Schieber<ref>{{Cite journal|last1=Bar-Noy|first1=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|s2cid=12329294 |issn=0004-5411|url-access=subscription}}</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 ===
Line 38:
== 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|url-access=subscription}}</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
* <math>\sum_{i=1}^m z_{i,j} = 1</math> for every job ''j'' in 1,...,''n;''
* <math>\sum_{
* <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
* <math>\sum_{c\in C_i(T)}x_{i,c} = 1</math> for every machine ''i'' in 1,...,''m;''
Line 55:
== 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|last1=Lin|first1=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|url-access=subscription}}</ref>
== Extensions ==
Kim, Kim, Jang and Chen<ref>{{Cite journal|date=2002-06-01|title=Unrelated parallel machine scheduling with setup times using simulated annealing|url=https://www.sciencedirect.com/science/article/abs/pii/S0736584502000133|journal=Robotics and Computer-Integrated Manufacturing|language=en|volume=18|issue=3–4|pages=223–231|doi=10.1016/S0736-5845(02)00013-3|issn=0736-5845|last1=Kim |first1=Dong-Won |last2=Kim |first2=Kyong-Hee |last3=Jang |first3=Wooseung |last4=Frank Chen |first4=F. |url-access=subscription}}</ref> extend the problem by allowing each job to have a setup time, which depends on the job but not on the machine. They present a solution using [[simulated annealing]]. Vallada and Ruiz<ref>{{Cite journal|date=2011-06-16|title=A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times|url=https://www.sciencedirect.com/science/article/abs/pii/S0377221711000142|journal=European Journal of Operational Research|language=en|volume=211|issue=3|pages=612–622|doi=10.1016/j.ejor.2011.01.011|issn=0377-2217|hdl-access=free|hdl=10251/35412|last1=Vallada |first1=Eva |last2=Ruiz |first2=Rubén }}</ref> present a solution using a [[genetic algorithm]].
== External links ==
| |||