Approximation algorithms for scheduling monotonic moldable tasks on multiple platforms

We consider scheduling monotonic moldable tasks on multiple platforms, where each platform contains a set of processors. A moldable task can be split into several pieces of equal size and processed simultaneously on multiple processors. Tasks are not allowed to be processed spanning over platforms. This scheduling model has many applications, ranging from parallel computing to the berth and quay crane allocation and the workforce assignment problem. We develop several approximation algorithms aiming at minimizing the makespan. More precisely, we provide a 2-approximation algorithm for identical platforms, a Fully Polynomial Time Approximation Scheme (FPATS) under the assumption of large processor counts and a 2-approximation algorithm for a fixed number of heterogeneous platforms. Most of the proposed algorithms combine a dual approximation scheme with a novel approach to improve the dual approximation algorithm. All results can be extended to the contiguous case, i.e., a task can only be executed by contiguously numbered processors.

Automated summary

We study the scheduling of monotonic moldable tasks on multiple platforms, each with a set of processors. Moldable tasks can be divided and processed simultaneously on multiple processors. The tasks cannot span over multiple platforms. This scheduling model has various applications such as parallel computing, berth and quay crane allocation, and workforce assignment. We propose several approximation algorithms to minimize the makespan, including a 2-approximation algorithm for identical platforms, a Fully Polynomial Time Approximation Scheme (FPATS) for large processor counts, and a 2-approximation algorithm for a fixed number of heterogeneous platforms. These algorithms combine dual approximation schemes with novel approaches to improve performance. The results can be extended to the contiguous case where tasks require contiguous numbered processors.