We study a multiprocessor task scheduling problem, in which each task requires a set of P 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 N P-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. (C) 2003 Elsevier B.V. All rights reserved.

Confessore, G., Dell'Olmo, P., Giordani, S. (2003). Complexity and approximation results for scheduling multiprocessor tasks on a ring. In Discrete Applied Mathematics [10.1016/S0166-218X(03)00432-3].

Complexity and approximation results for scheduling multiprocessor tasks on a ring

GIORDANI, STEFANO
2003-01-01

Abstract

We study a multiprocessor task scheduling problem, in which each task requires a set of P 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 N P-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. (C) 2003 Elsevier B.V. All rights reserved.
International Symposium on Combinatorial Optimisation
LONDON, ENGLAND
JUL 12-14, 2000
Rilevanza internazionale
2003
Settore MAT/09 - RICERCA OPERATIVA
English
multiprocessor task scheduling; graph model; acyclic orientations; complexity analysis; approximation results
Intervento a convegno
Confessore, G., Dell'Olmo, P., Giordani, S. (2003). Complexity and approximation results for scheduling multiprocessor tasks on a ring. In Discrete Applied Mathematics [10.1016/S0166-218X(03)00432-3].
Confessore, G; Dell'Olmo, P; Giordani, S
File in 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/2108/52232
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact