Recently, a new approximation algorithm for the nonpreemptive scheduling of independent jobs on m identical parallel processors has appeared in the literature. The algorithm, named MPS (MultiProcessor Scheduling), combines partial solutions which satisfy suitable properties. Its performance ratio is bounded by (z+1)/z − 1/(mz), where z represents the number of initial partial solutions provided by the algorithm. This note presents an advanced estimate of z and, consequently, an improved worst-case performance ratio of the MPS algorithm.

A short note on an advance in estimating the worst-case performance ratio of the MPS algorithm

PALETTA G;VOCATURO F
2010

Abstract

Recently, a new approximation algorithm for the nonpreemptive scheduling of independent jobs on m identical parallel processors has appeared in the literature. The algorithm, named MPS (MultiProcessor Scheduling), combines partial solutions which satisfy suitable properties. Its performance ratio is bounded by (z+1)/z − 1/(mz), where z represents the number of initial partial solutions provided by the algorithm. This note presents an advanced estimate of z and, consequently, an improved worst-case performance ratio of the MPS algorithm.
multiprocessor scheduling; approximation algorithm; worst-case performance ratio
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/20.500.11770/158936
 Attenzione

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

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