Scheduling of Independent Dedicated Multiprocessor Tasks (Articolo in rivista)

Type
Label
  • Scheduling of Independent Dedicated Multiprocessor Tasks (Articolo in rivista) (literal)
Anno
  • 2002-01-01T00:00:00+01:00 (literal)
Alternative label
  • Bampis E., Caramia M., Fiala J., Fiskin A., Iovanella A. (2002)
    Scheduling of Independent Dedicated Multiprocessor Tasks
    in Lecture notes in computer science
    (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori
  • Bampis E., Caramia M., Fiala J., Fiskin A., Iovanella A. (literal)
Pagina inizio
  • 391 (literal)
Pagina fine
  • 402 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#altreInformazioni
  • Il lavoro in esame ha ricevuto da gennaio 2003 6 citazioni su articoli su riviste internazionali (buon risultato se si pensa che che gli esperti internazionali che lavorano in quest'area sono pochi). Tra i risultati ottenuti per la classe di problemi di scheduling studiata in questo lavoro c'è la migliore approssimazione della soluzione ottima ottenubile in tempo polinomiale. Impact factor delle Lecture Notes in Computer Science nel 2003: 0.8. (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroVolume
  • 2518 (literal)
Rivista
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#descrizioneSinteticaDelProdotto
  • Pubblicazione su rivista internazionale (literal)
Note
  • ISI Web of Science (WOS) (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#affiliazioni
  • Evripidis Bampis, LaMI, CNRS-UMR 8042, Univerite d'Evry, Evry Cedex, France. Massimiliano Caramia, Istituto per le Applicazioni del Calcolo \"M. Picone\" - CNR, Rome - Italy. Jiri Fiala, DIMATIA and ITI, Charles University, Prague, Czech Republic. Aleksei V. Fishkin, Institut fur Informatik und Praktische Mathematik, Universitat zu Kiel, Kiel, Germany. Antonio Iovanella, Dipartimento di Informatica, Sistemi e Produzione, University of Rome \"Tor Vergata\" - Rome, Italy. (literal)
Titolo
  • Scheduling of Independent Dedicated Multiprocessor Tasks (literal)
Abstract
  • We study the on-line version of the well known problem of scheduling a set of $n$ independent multiprocessor tasks with prespecified processor allocations on a set of identical processors in order to minimize the makespan. Recently, it has been proven that even in the off-line case with unit processing time tasks no polynomial time approximation algorithm can be found with approximation factor $m^{{1}/{2}-\eps}$ for any $\eps >0$, unless \NP=\ZPP. We first study simple approximation and on-line algorithms based on the classical first-fit technique. Then, by using a split-round technique, we give a \sqrt{m}$-approximation algorithm for the off-line version of the problem. Finally, we adapt this algorithm to the on-line case, in the paradigm of tasks arriving over time, and show that its competitive ratio is bounded by $(6\sqrt{m}+1)$. Due to the conducted experimental results, which also analyzed here, we conclude that our algorithms can also perform well in practice. (literal)
Prodotto di
Autore CNR
Insieme di parole chiave

Incoming links:


Prodotto
Autore CNR di
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#rivistaDi
Insieme di parole chiave di
data.CNR.it