On the performance of Smith's rule in single-machine scheduling with nonlinear cost

min-sum objective. Given some continuous,
non-decreasing cost function, we aim at computing a schedule
minimizing the total weighted completion time cost. This problem is
closely related to scheduling a single machine with nonuniform
processing speed. We show that for piecewise linear cost functions the
problem is strongly NP-hard. Moreover, we give a tight analysis of the
approximation guarantee of Smith's rule under any particular convex or
concave cost function. More specifically, for these wide classes of
cost functions we reduce the task of determining a worst case problem
instance to a continuous optimization problem, which can be solved by
standard algebraic or numerical methods. For monomial cost functions
x^k, we show that the tight approximation factor is asymptotically
equal to k^((k-1)/(k+1)). To overcome unrealistic worst case
instances, we also give tight bounds for the case of integral
processing times that are parametrized by the maximum and total
processing time. This is joint work with Tobias Jacobs.