arXiv:2607.22133 · v2
Approximate Total Weighted Completion Time with Convex Controllable Processing Times
摘要
We study the single-machine scheduling problem with controllable processing times to minimize the total weighted completion time, focusing on the setting where a job's processing time is a convex function of its allocated continuous resource. The computational complexity of this problem represents a long-standing open question, as it is currently neither known to be polynomial-time solvable nor NP-hard. While we do not fully resolve this complexity question, we provide several insights into the problem's approximability. On the positive side, we present a polynomial-time $e \le 2.719$-approximation algorithm, alongside a quasi-polynomial approximation scheme for instances where the largest parameter value is polynomially bounded by the instance size. On the negative side, we demonstrate that simple sorting rules, which are optimal for certain special cases in the literature, cannot guarantee a constant-factor approximation for the general case.
作者备注：The results of this manuscript are superseeded by the paper "Dual Techniques for Scheduling on a Machine with Varying Speed" by Megow and Verschae, SIDMA 2018