@Misc{macau_mods_00001806, author = {Jansen, Klaus}, title = {A (3/2+ɛ) approximation algorithm for scheduling malleable and non-malleable parallel tasks}, year = {1992}, publisher = {Institut f{\"u}r Informatik}, address = {Kiel}, volume = {1203}, abstract = {In this paper we study a scheduling problem with malleable and non-malleable parallel tasks on {\$}m{\$} processors. A non-malleable parallel task is one that runs in parallel on a specific given number of processors. The goal is to find a non-preemptive schedule on the {\$}m{\$} processors which minimizes the makespan, or the latest task completion time. The previous best result is the list scheduling algorithm with an absolute approximation ratio of {\$}2{\$}. On the other hand, there does not exist an approximation algorithm for scheduling non-malleable parallel tasks with ratio smaller than {\$}1.5{\$}, unless {\$}P=NP{\$}. In this paper we show that a schedule with length {\$}(1.5 +{\backslash}epsilon) OPT{\$} can be computed for the scheduling problem in time {\$}O(n {\backslash}log n) + f(1/{\backslash}epsilon){\$}. Furthermore we present an {\$}(1.5 + {\backslash}epsilon){\$} approximation algorithm for scheduling malleable parallel tasks. Finally, we show how to extend our algorithms to the variant with additional release dates.}, issn = {2192-6247}, url = {https://macau.uni-kiel.de/receive/macau_mods_00001806}, file = {:https://macau.uni-kiel.de/servlets/MCRFileNodeServlet/macau_derivate_00003032/tr-1203-bericht.pdf:PDF}, language = {en} }