Single-machine scheduling with deadlines to minimize the total weighted late work

Abstract

We consider scheduling a set of jobs with deadlines to minimize the total weighted late work on a single machine, where the late work of a job is the amount of processing of the job that is scheduled after its due date and before its deadline. This is the first study on scheduling with the late work criterion under the deadline restriction. In this paper, we show that (i) the problem is unary NP-hard even if all the jobs have a unit weight, (ii) the problem is binary NP-hard and admits a pseudo-polynomial-time algorithm and a fully polynomial-time approximation scheme if all the jobs have a common due date, and (iii) some special cases of the problem are polynomially solvable.