A preemptive single-machine scheduling problem with a late work criterion and convex resource consumption functions

Abstract We consider two single-machine scheduling problems with the late work criterion, where each job’s processing time follows a decreasing convex function of the resource consumption amount, and each job can be interrupted and resumed later. The first objective is to minimize the sum of late work and resource consumption amount, while the second objective is to minimize the total late work with a constraint on the total resource consumption amount. We show that both problems can be solved in strongly polynomial time.