A preemptive single-machine scheduling problem with a late work criterion and convex resource consumption functions
Abstract
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.
Fields of Study & Subjects
Scheduling and Optimization Algorithms
Resource-Constrained Project Scheduling
Real-Time Systems Scheduling
Publication details
- Journal / source
- Optimization Letters
- Volume
- 20
- Issue
- 5
- Pages
- 1025–1042
- Publication date
- 4 February 2026
- Language
- EN