Home » Publication » 18348

Dettaglio pubblicazione

2019, JOURNAL OF SCHEDULING, Pages 195-209 (volume: 22)

ILP models for the allocation of recurrent workloads upon heterogeneous multiprocessors (01a Articolo in rivista)

Baruah S. K., Bonifaci V., Bruni R., Marchetti-Spaccamela A.

The problem of partitioning systems of independent constrained-deadline sporadic tasks upon heterogeneous multiprocessor platforms is considered. Several different integer linear program (ILP) formulations of this problem, offering different trade-offs between effectiveness (as quantified by speedup bound) and running time efficiency, are presented. One of the formulations is leveraged to improve the best speedup guarantee known for a polynomial-time partitioning algorithm, from 12.9 to 7.83. Extensive computational results on synthetically generated instances are also provided to establish the effectiveness of the ILP formulations.
Gruppo di ricerca: Combinatorial Optimization
© Università degli Studi di Roma "La Sapienza" - Piazzale Aldo Moro 5, 00185 Roma