Imagine a single machine and several jobs to be completed sequentially on it, each job having a characteristic weight, processing time, and a prescribed due date of completion. Then, the tardiness of a job is defined as the time taken beyond its due date for the job to be completed. The authors present an interesting paper on this scheduling problem in which they provide a fully polynomial-time approximation scheme (FPTAS) that minimizes the total weighted tardiness. The newness of their algorithm stems from the revelation that it works even for separate or distinct (although fixed) due dates. Previous known FPTAS algorithms only worked for common due dates.

The proposed pseudo-polynomial scheme has two broad steps. In the first step, dynamic programming is used to evaluate the completion times of different jobs in the schedule. In the authors’ own words, “only a subset of the jobs is explicitly packed and the rest are left ‘floating’ from their completion time backwards,” producing what the authors call “an abstract schedule.” In the second step, the actual job lengths are distributed by means of a greedy algorithm. The authors’ work is motivated by the work of Kellerer and Strusevich [1].

The authors propose extending their work to an arbitrary number of distinct due dates. I would add that since the time of an operation is itself the weight in some sense, one should regard the processing time as a weighted combination of the operations; hence, this can be combined with the other weight talked about in the paper. We may call the result a “g-weight,” a generalized version of the weights. This puts the problem in its most general form.

I recommend this paper for the target audience, which includes computing science graduates and researchers, especially those interested in algorithms.