This note considers the longest processing time heuristic for scheduling n independent jobs on two uniformparallel machines to minimize the makespan.. A posterior worst-case performance ratio, by depending on the index ofthe latest job inserted in the machine where the makespan takes place, is developed for this heuristic, and some examples demonstrate that the ratio is tight.
A note on longest processing time algorithms for the two uniform parallel machine makespan minimization problem
MASSABO', Ivar;PALETTA, Giuseppe;
2016-01-01
Abstract
This note considers the longest processing time heuristic for scheduling n independent jobs on two uniformparallel machines to minimize the makespan.. A posterior worst-case performance ratio, by depending on the index ofthe latest job inserted in the machine where the makespan takes place, is developed for this heuristic, and some examples demonstrate that the ratio is tight.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.
