What question did this study set out to answer?

This research aims to optimize scheduling by minimizing late work and managing resource consumption effectively.

February 6, 2026Open Access

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

Key Points

This research aims to optimize scheduling by minimizing late work and managing resource consumption effectively.
Analyzed two single-machine scheduling problems with late work criterion
Explored processing times as decreasing convex functions of resource consumption
Developed preemptive scheduling strategies that allow job interruptions and resumptions
Demonstrated solutions for both scheduling problems can be achieved in strongly polynomial time
Achieved significant reductions in both late work and resource consumption through proposed methods

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.

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

Key Points

Abstract

Cite This Study

Also Consider

Also Consider