Scheduling malleable parallel tasks: an asymptotic fully polynomial time approximation scheme (Q1879360)

The article treats a scheduling problem with \(n\) jobs on up to \(m\) identical machines, where the processing time of each task is dependend from the number of machines (processors) assigned to the job, whereas the overall sum of machines (processors) assigned at one time is limited by the number of machines \(m\). The dependency is defined very general (i.e., processing time \(pj\) \((k\) processors assigned) \(=fj(j,k)\), where \(fj\) is an arbitrary function for each job \(j)\). The objective is to minimize the makespan. This problem is called ``malleable parallel task scheduling''. As an overall assumption, one want to have a schedule without preemtion. Even the preemtive formulation of the problem is known as NP-hard. Therefore in the paper an algorithm is contructed which provides an approximative solution within a fixed accuracy. The main idea behind the approximation is to use the preemtive problem as a basic to construct non-preemtive solutions and to use data rounding to scale down the problem. As usual for these kind of approximation, the effort increases with the required accuracy of the approximative solution.