The weighted tardiness with batching (WTB) problem can be briefly described as follows: given n jobs, each with a processing time, a weight, and a due date, and given a batch setup time, find a sequence of batches that minimizes the weighted number of tardy jobs. The authors show that the decision version of WTB is NP-complete, but that it can be solved in pseudo-polynomial time by a dynamic programming algorithm. They also analyze various restricted versions of the problem generated by requiring that one or more of the job parameters (weight, processing time, or due date) is the same for all jobs. For each such version of the problem, the authors prove NP-completeness or provide a polynomial algorithm.
