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.
Abstract
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.