Efficient approximation algorithms for scheduling moldable tasks - ENSAE Paris Access content directly
Journal Articles European Journal of Operational Research Year : 2023

Efficient approximation algorithms for scheduling moldable tasks


Moldable tasks allow schedulers to determine the number of processors assigned to each task, thus enabling efficient use of large-scale parallel processing systems. We consider the problem of scheduling independent moldable tasks on processors and propose a new perspective of the existing speedup models: as the number p of processors assigned to a task increases, the speedup is linear if p is small and becomes sublinear after p exceeds a threshold. Based on this, we propose an efficient approximation algorithm to minimize the makespan. As a by-product, we also propose an approximation algorithm to maximize the sum of values of tasks completed by a deadline; this scheduling objective is considered for moldable tasks for the first time while similar works have been done for other types of parallel tasks.
Fichier principal
Vignette du fichier
WuLoiseau_MoldableTasks_EJOR2023.pdf (471.68 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-04236778 , version 1 (11-10-2023)





Xiaohu Wu, Patrick Loiseau. Efficient approximation algorithms for scheduling moldable tasks. European Journal of Operational Research, 2023, 310 (1), pp.71-83. ⟨10.1016/j.ejor.2023.02.044⟩. ⟨hal-04236778⟩
95 View
45 Download



Gmail Facebook X LinkedIn More