Archivio Istituzionale della RicercaWe consider the problem of minimizing the sum of quadratic completion times on two parallel machines and we discuss the approximation ratio of the generalized shortest processing time (GSPT) priority rule according to which the jobs are sorted in nondecreasing processing time order and the next job on the list is assigned to the earliest available machine. We show that the approximation ratio of the GSPT rule is bounded above by approx. 1.309 and below by approx. 1.290. Extensions to the parallel m-machine problem are also discussed.
A note on minimizing the sum of quadratic completion times on twoidentical parallel machines / DELLA CROCE DI DOJOLA, Federico; C., Koulamas. - In: INFORMATION PROCESSING LETTERS. - ISSN 0020-0190. - 112:(2012), pp. 738-742. [10.1016/j.ipl.2012.06.011]
A note on minimizing the sum of quadratic completion times on twoidentical parallel machines
DELLA CROCE DI DOJOLA, Federico;
2012
Abstract
We consider the problem of minimizing the sum of quadratic completion times on two parallel machines and we discuss the approximation ratio of the generalized shortest processing time (GSPT) priority rule according to which the jobs are sorted in nondecreasing processing time order and the next job on the list is assigned to the earliest available machine. We show that the approximation ratio of the GSPT rule is bounded above by approx. 1.309 and below by approx. 1.290. Extensions to the parallel m-machine problem are also discussed.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
https://hdl.handle.net/11583/2499462
Attenzione
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo