@Misc{macau_mods_00001794,
  author = 	{Dutot, Pierre-Francois
		and Jansen, Klaus
		and Robenek, Christina
		and Trystram, Denis},
  title = 	{A (2+ɛ)-approximation for scheduling parallel jobs in platforms},
  year = 	{1992},
  publisher = 	{Institut f{\"u}r Informatik},
  address = 	{Kiel},
  volume = 	{1217},
  abstract = 	{We consider the problem of {\backslash}textsc{\{}Scheduling parallel Jobs in heterogeneous Platforms{\}}: We are given a set {\$}{\backslash}mathcal{\{}J{\}}={\backslash}{\{}1,{\backslash}ldots,n{\backslash}{\}}{\$} of {\$}n{\$} jobs, where a job {\$}j{\backslash}in{\backslash}mathcal{\{}J{\}}{\$} is described by a pair {\$}(p{\_}j,q{\_}j){\$} of a processing time {\$}p{\_}j{\backslash}in{\backslash}mathbb{\{}Q{\}}{\_}{\{}>0{\}}{\$} and the number of processors {\$}q{\_}j{\backslash}in{\backslash}mathbb{\{}N{\}}{\$} that are required to execute {\$}j{\$}. We are also given a set {\$}{\backslash}mathcal{\{}B{\}}{\$} of {\$}N{\$} heterogeneous platforms {\$}P{\_}1,{\backslash}ldots,P{\_}N{\$}, where each {\$}P{\_}i{\$} contains {\$}m{\_}{\{}i{\}}{\$} processors for {\$}i{\backslash}in{\backslash}{\{}1,{\backslash}ldots, N{\backslash}{\}}.{\$} The objective is to find a schedule for the jobs in the platforms minimizing the makespan, i.e. the latest finishing time of a job. Unless {\$}{\backslash}mathcal{\{}P{\}}={\backslash}mathcal{\{}NP{\}}{\$} there is no approximation algorithm with absolute ratio strictly better than {\$}2{\$} for the problem. We give a {\$}(2+{\backslash}epsilon){\$}-approximation for the problem improving the previously best known absolute approximation ratio {\$}3{\$}.},
  issn = 	{2192-6247},
  url = 	{https://macau.uni-kiel.de/receive/macau_mods_00001794},
  file = 	{:https://macau.uni-kiel.de/servlets/MCRFileNodeServlet/macau_derivate_00003046/tr-1217-bericht.pdf:PDF},
  language = 	{en}
}