In this study, we examine the single-machine scheduling problem aimed at minimizing the total weighted completion time, focusing on how a job's processing time is a convex function of its allocated continuous resource. The computational complexity of this problem remains an open question, as it is currently unknown whether it is solvable in polynomial time or NP-hard. While we do not fully resolve this complexity issue, we provide several insights into the problem's approximability.
On the positive side, we present a polynomial-time $e \approx 2.718$-approximation algorithm, along with a quasi-polynomial approximation scheme for instances where the largest parameter value is polynomially bounded by the instance size. On the negative side, we show that simple sorting rules, which are optimal for certain special cases in the literature, cannot guarantee a constant-factor approximation for the general case.
Blogger's Review: This study offers new perspectives on the complexity issues in scheduling and advances the understanding of controllable processing times through the introduction of approximation algorithms. Although the complexity remains unresolved, it lays a foundation for future research. This area deserves ongoing attention.