@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} }