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