Günter Rote and Gerhard J. Woeginger:

Minimizing the number of tardy jobs on a single machine with batch setup times

Acta Cybernetica 13 (1998), 423-429.


This paper investigates a single-machine sequencing problem where the jobs are divided into families, and where a setup time is incurred whenever there is a switch from a job in one family to a job in another family. This setup only depends on the family of the job next to come and hence is sequence independent. The jobs have due-dates, and the objective is to find a sequence of jobs that minimizes the number of tardy jobs.

The special case of this problem where in every family the jobs have at most two different due dates is known to be NP-complete [Bruno and Downey 1978]. The main result of this paper is a polynomial time algorithm for the remaining open case where in every family all the jobs have the same due date. This case may be formulated as a dual resource allocation problem with a tree-structured constraint system, which can be solved to optimality in polynomial time.

  PostScript file (gzippedpdf file (gzippedTeX .dvi file (gzipped)
other papers about this subject