Abstract

We investigate a family of single-machine scheduling problems that combine convex resource consumption with job rejection, where the performance measure is the total completion time of the accepted jobs. Across four natural variants-distinguished by whether the resource consumption cost and rejection cost appear in the objective or as budget constraints-we analyze their computational complexity and develop efficient algorithms. We show that one variant is polynomially solvable, two variants are weakly NP-hard but admit fully polynomial-time approximation schemes (FPTASs), and the remaining variant admits an FPTAS while its exact complexity remains open.