Single-Machine Scheduling with Preemption: Minimizing Weighted Late Work and Compression Costs

This study investigates a single-machine scheduling problem with preemption, where the processing time of each job can be linearly reduced by allocating additional resources. It is further assumed that the weights assigned to all jobs are distinct. The objective is to minimize the sum of the total weighted late work and the total compression cost. By establishing optimality conditions for the problem, we reduce it to a shortest path problem and develop a polynomial-time algorithm for efficient solution. Single-machine scheduling problems have been extensively studied with a focus on either controllable processing times or late work individually. However, the integration of controllable processing times with the weighted late work criterion is novel in the relevant literature, and this paper contributes to advancing research in this area.