We consider the problem of scheduling tasks on a set of dedicated processors, where each task requires a subset of two processors be simultaneously available for a given processing time. The objective is to determine a nonpreemptive schedule with minimum completion time. By means of a graph theoretical formulation, we show that instances with up to 4 processors can be solved in polynomial time. With m = 2s + 1 processors (for s = 2, 3,...) and a minimum of m task types, we prove that the problem is NP-hard. Moreover, for this class of NP-hard instances, a simple O(m) approximation algorithm, whose performance ratio is bounded by 3s/(2s + 1), is given. The bound is shown to be tight.

Dell'Olmo, P., Giordani, S., & Speranza, M. (1997). An approximation result for a duo-processor task scheduling problem. INFORMATION PROCESSING LETTERS, 61(4), 195-200 [10.1016/S0020-0190(96)00196-2].

An approximation result for a duo-processor task scheduling problem

GIORDANI, STEFANO;
1997

Abstract

We consider the problem of scheduling tasks on a set of dedicated processors, where each task requires a subset of two processors be simultaneously available for a given processing time. The objective is to determine a nonpreemptive schedule with minimum completion time. By means of a graph theoretical formulation, we show that instances with up to 4 processors can be solved in polynomial time. With m = 2s + 1 processors (for s = 2, 3,...) and a minimum of m task types, we prove that the problem is NP-hard. Moreover, for this class of NP-hard instances, a simple O(m) approximation algorithm, whose performance ratio is bounded by 3s/(2s + 1), is given. The bound is shown to be tight.
Pubblicato
Rilevanza internazionale
Articolo
Sì, ma tipo non specificato
Settore MAT/09 - Ricerca Operativa
English
Con Impact Factor ISI
Approximation algorithms; Coloring; Computational complexity; Parallel processing; Scheduling
http://dx.doi.org/10.1016/S0020-0190(96)00196-2
Dell'Olmo, P., Giordani, S., & Speranza, M. (1997). An approximation result for a duo-processor task scheduling problem. INFORMATION PROCESSING LETTERS, 61(4), 195-200 [10.1016/S0020-0190(96)00196-2].
Dell'Olmo, P; Giordani, S; Speranza, M
Articolo su rivista
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: http://hdl.handle.net/2108/52233
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 5
social impact