The single machine batch scheduling problem to minimize the weighted number of late jobs is studied. In this problem, n jobs have to be processed on a single machine. Each job has a processing time, a due date and a weighted. Jobs may be combined to form batches containing contiguously scheduled jobs. For each batch, a constant set-up time is needed before the first job of this batch is processed. The completion time of each hob in the batch coincides with the completion time of the last job in this batch. A job is late if it is completed after its due date. A schedule specifies the sequence of jobs and the size of each batch, i.e. the number of jobs it contains. The objective is to find a schedule which minimizes the weighted number of late jobs. This problem is NP-hard even if all due dates are equal. For the general case, the authors present a dynamic programming algorithm which solves the problem with equal weights in O(n3) time. They formulate a certain scaled problem and show that the dynamic programming algorithm applied to this scaled problem provides a fully polynomial approximation scheme for the original problem. Each algorithm of this scheme has a time requirement of O(n3/∈+n3logn). A side result is an O(nlogn) algorithm for the problem of minimizing the maximum weight of late jobs.
