Content deleted Content added
→Linear programming formulation: The constraints on the total costs of assigning jobs to a given machine should be bounded by T; thus, the summation index should be j, as it should range over the set of jobs. |
m Open access bot: arxiv updated in citation with #oabot. |
||
Line 19:
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}}</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=|last1=Glass |first1=C.A. |last2=Potts |first2=C.N. |last3=Shade |first3=P. }}</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]].
| |||