A new $nlog(n)$ algorithm for the scheduling problem of $n$ independent jobson $m$ identical parallel machines with minimum makespan objective is proposed andits worst-case performance ratio is estimated. The algorithm iteratively combinespartial solutions that are obtained by partitioning the set of jobs into suitable familiesof subsets. The computational behavior on three families of instances taken from theliterature provided interesting results.
Minimizing the makespan in nonpreemptive parallel machine scheduling problem
CHIASELOTTI, Giampiero;GUALTIERI, Maria Italia;PIETRAMALA, Paolamaria
2010-01-01
Abstract
A new $nlog(n)$ algorithm for the scheduling problem of $n$ independent jobson $m$ identical parallel machines with minimum makespan objective is proposed andits worst-case performance ratio is estimated. The algorithm iteratively combinespartial solutions that are obtained by partitioning the set of jobs into suitable familiesof subsets. The computational behavior on three families of instances taken from theliterature provided interesting results.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.