Single Machine Scheduling to Minimize Total Late Work

Operations Research · 1992 · Volume 40 · Issue 3

Abstract

In the problem of scheduling a single machine to minimize total late work, there are n jobs to be processed for which each has an integer processing time and a due date. The objective is to minimize the total late work, where the late work for a job is the amount of processing of this job that is performed after its due date. For the preemptive total late work problem, an O ( n log n ) algorithm is derived. The nonpreemptive total late work problem is shown to be NP-hard, although efficient algorithms are derived for the special cases in which all processing times are equal and all due dates are equal. A pseudopolynomial dynamic programming algorithm is presented for the general nonpreemptive total late work problem; it requires O ( n UB) time, where UB is any upper bound on the total late work. Computational results for problems with up to 10,000 jobs are given.

Keywords

production/scheduling: single machine scheduling, programming, integer, algorithms: dynamic programming

Enable JavaScript for citation tools and additional paper interactions.