The problem of scheduling moldable tasks on multiprocessor systems with the goal of minimizing the makespan has received significant attention, especially in contexts where tasks have dependence constraints (task graphs) or arrive dynamically (online scheduling). However, the combined setting—online scheduling of moldable task graphs—remains less explored. Prior studies have addressed this problem by designing algorithms specifically tailored to particular speedup models, such as Amdahl, Communication, or Roofline. Although these specialized algorithms achieve constant competitive ratios under their respective models, their applicability is limited in practice: Each requires tasks to adhere to a predefined speedup model. In this paper, we introduce a novel, universal online algorithm capable of handling arbitrary monotonic moldable tasks without assumptions about their speedup behavior. Remarkably, when applied to the specific speedup models previously studied, our algorithm achieves competitive ratios comparable to—or better than—those obtained by the specialized algorithms. For the General and Power Communication models, we further show that the optimal simultaneous time-and-area factor is 2, matching the Amdahl case.
Perotin, Lucas, Verrecchia, Thomas, Raghavan, Padma. Near-optimal universal scheduling for moldable tasks: the Fair algorithm. // Journal of Scheduling. – 2026. – DOI: 10.1007/s10951-026-00897-w. – URL: http://link.springer.com/openurl/fulltext?id=doi:10.1007/s10951-026-00897-w
Perotin, Lucas, Verrecchia, Thomas, Raghavan, & Padma (2026). Near-optimal universal scheduling for moldable tasks: the Fair algorithm. Journal of Scheduling. https://doi.org/10.1007/s10951-026-00897-w
Perotin, et al. “Near-optimal universal scheduling for moldable tasks: the Fair algorithm.” Journal of Scheduling, 2026. doi:10.1007/s10951-026-00897-w.
@article{Perotin2026,
title = {Near-optimal universal scheduling for moldable tasks: the Fair algorithm},
author = {Perotin and Lucas and Verrecchia and Thomas and Raghavan and Padma},
journal = {Journal of Scheduling},
year = {2026},
doi = {10.1007/s10951-026-00897-w},
url = {http://link.springer.com/openurl/fulltext?id=doi:10.1007/s10951-026-00897-w}
}
In this paper, we consider cost-sharing problems defined on rooted trees. We refer to these problems as cost-tree problems and to the induced transferable utility cooperative games as irrigation games. We introduce a formal notion of...
In this paper, we focus on nonlinear programming problems with cardinality constraints that restrict the number of nonzero components of the decision vector. We start with a straightforward mixed-integer programming reformulation....
Portfolio selection is a critical issue in financial management under uncertainty. In this paper, we propose a complex approach for portfolio selection with quantile return approximation. In particular, we propose a practical workflow...
The transcendental logarithmic (translog) production function is recognised as a flexible functional form for modelling production processes. It accommodates varying elasticities of input substitution and diverse types of...
This study investigates mothership-drone route determination using two optimization approaches: a Mixed Integer Linear Programming (MILP) model based on a discrete hexagonal grid, and a Mixed Integer Nonlinear Programming (MINLP) model...