We study a multiprocessor task scheduling problem, in which each task requires a set of μ processors with consecutiveness constraints to be executed. This occurs, for example, when multiple processors are interconnected by communication means, and the minimization of communication time may require the processors to be physically adjacent and each multiprocessor task to use only one subset of adjacent processors. In particular, we consider the case in which we have m processors arranged in a ring, and we want to find a schedule with minimum makespan. We investigate problem complexity, showing that the problem is View the MathML source-hard in almost all the possible cases, and provide an approximation algorithm that finds a feasible schedule whose makespan is not greater than two times the optimal value.

Complexity and Approximation Results for Scheduling Multiprocessor Tasks on a Ring / Confessore, G; Dell'Olmo, Paolo; Giordani, S.. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - STAMPA. - 133:(2004), pp. 29-44. [10.1016/S0166-218X(03)00432-3]

Complexity and Approximation Results for Scheduling Multiprocessor Tasks on a Ring

DELL'OLMO, Paolo;
2004

Abstract

We study a multiprocessor task scheduling problem, in which each task requires a set of μ processors with consecutiveness constraints to be executed. This occurs, for example, when multiple processors are interconnected by communication means, and the minimization of communication time may require the processors to be physically adjacent and each multiprocessor task to use only one subset of adjacent processors. In particular, we consider the case in which we have m processors arranged in a ring, and we want to find a schedule with minimum makespan. We investigate problem complexity, showing that the problem is View the MathML source-hard in almost all the possible cases, and provide an approximation algorithm that finds a feasible schedule whose makespan is not greater than two times the optimal value.
2004
Scheduling
01 Pubblicazione su rivista::01a Articolo in rivista
Complexity and Approximation Results for Scheduling Multiprocessor Tasks on a Ring / Confessore, G; Dell'Olmo, Paolo; Giordani, S.. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - STAMPA. - 133:(2004), pp. 29-44. [10.1016/S0166-218X(03)00432-3]
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/47651
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact