Single machine scheduling with job-dependent convex cost and arbitrary precedence constraints

Rodrigo A. Carrasco, Garud Iyengar, Cliff Stein

Resultado de la investigación: Contribución a una revistaArtículorevisión exhaustiva

7 Citas (Scopus)

Resumen

In this work we combine resource augmentation and alpha-point scheduling techniques, which have resulted in very good performance scheduling algorithms, to compute approximate solutions for a general family of scheduling problems: each job has a convex non-decreasing cost function and the goal is to compute a schedule that minimizes the total cost subject to precedence constraints. We show that our algorithm is a O(1)-speed 1-approximation algorithm and our numerical experiments show that the speed-scaling ratio required is close to 1.

Idioma originalInglés
Páginas (desde-hasta)436-441
Número de páginas6
PublicaciónOperations Research Letters
Volumen41
N.º5
DOI
EstadoPublicada - 2013

Huella

Profundice en los temas de investigación de 'Single machine scheduling with job-dependent convex cost and arbitrary precedence constraints'. En conjunto forman una huella única.

Citar esto