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

Abstract

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)O(1)-speed 11-approximation algorithm and our numerical experiments show that the speed-scaling ratio required is close to 1.1.