Improved Approximation Algorithms for Parallel Task Scheduling and Multiple Cluster Scheduling

Bennet Edler, Klaus Jansen, Felix Ohnesorge +1

In the problem of Parallel Task Scheduling (PTS), we are asked to schedule $n$ jobs, each with a fixed processing time and machine requirement, such that the completion time of the…