Single Machine Scheduling to Minimize Total Weighted Late Work

In the problem of scheduling a single machine to minimize total weighted late work, there are n jobs to be processed for which each has an integer processing time, a weight and a due date. The objective is to minimize the total weighted late work, where the late work for a job is the amount of processing of this job which is performed after its due date. An O(n log n) algorithm is derived for the preemptive total weighted late work problem. For non-preemptive scheduling, efficient algorithms are derived for the special cases in which all processing times are equal and in which all due dates are equal. A pseudopolynomial algorithm is presented for the general non-preemptive total weighted late work problem. Also, a branch and bound algorithm in which lower bounds are obtained using the dynamic programming state-space relaxation method is proposed for this general problem. Computational results with the branch and bound algorithm for problems with up to 700 jobs are given. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.