We consider the scheduling problem of n independent jobs on m identical parallel processors in order to minimize makespan, the completion time of the last job. We propose a new approximation algorithm that iteratively combines partial solutions to the problem. The worst-case performance ratio of the algorithm is (z+1)/z-1/(mz), where z is the number of initial partial solutions that are obtained by partitioning the set of jobs into z families of subsets which satisfy suitable properties. The computational behavior of our worst-case performance ratio provided encouraging results on three families of instances taken from the literature.

A new approximation algorithm for the non-preemptive scheduling of independent jobs on identical parallel processors

PALETTA, Giuseppe;PIETRAMALA, Paolamaria
2007

Abstract

We consider the scheduling problem of n independent jobs on m identical parallel processors in order to minimize makespan, the completion time of the last job. We propose a new approximation algorithm that iteratively combines partial solutions to the problem. The worst-case performance ratio of the algorithm is (z+1)/z-1/(mz), where z is the number of initial partial solutions that are obtained by partitioning the set of jobs into z families of subsets which satisfy suitable properties. The computational behavior of our worst-case performance ratio provided encouraging results on three families of instances taken from the literature.
optimization ; 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/158090
 Attenzione

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

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 13
  • ???jsp.display-item.citation.isi??? 7
social impact