A new constructive heuristic for the scheduling problem of n independent jobs on m identical parallel machines with minimum makespanobjective is described. The proposed algorithm, which is an n log n algorithmas the LPT algorithm of Graham, iteratively combines partial solutions thatare obtained by partitioning the set of jobs in suitable families of subsets. Thealgorithm was tested using different families of instances which were takenfrom the literature and results compared with other well known algorithms.
A new nlogn algorithm for the identical parallel machine scheduling problem
GUALTIERI, Maria Italia;PALETTA, Giuseppe;PIETRAMALA, Paolamaria
2008-01-01
Abstract
A new constructive heuristic for the scheduling problem of n independent jobs on m identical parallel machines with minimum makespanobjective is described. The proposed algorithm, which is an n log n algorithmas the LPT algorithm of Graham, iteratively combines partial solutions thatare obtained by partitioning the set of jobs in suitable families of subsets. Thealgorithm was tested using different families of instances which were takenfrom the literature and results compared with other well known algorithms.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.
