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-01-01
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.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.
