Approximation algorithms for scheduling monotonic moldable tasks on multiple platforms

Fangfang Wu (), Zhongyi Jiang (), Run Zhang () and Xiandong Zhang ()
Additional contact information
Fangfang Wu: Fudan University
Zhongyi Jiang: Changzhou University
Run Zhang: Fudan University
Xiandong Zhang: Fudan University

Journal of Scheduling, 2023, vol. 26, issue 4, No 4, 383-398

Abstract: Abstract 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.

Keywords: Scheduling; Moldable tasks; Multiple platforms; Dual approximation algorithm; Approximation algorithm (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10951-022-00774-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jsched:v:26:y:2023:i:4:d:10.1007_s10951-022-00774-2

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-022-00774-2

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().