On the general solution for a class of early/tardy problems

The authors consider a class of early/tardy problems where the objective is to schedule a set of jobs on a single machine in order to minimize a function of the deviations of job completion times from a common due-date. While some individual members of this class of problems have been studied extensively in the research literature, little has been reported to date on the general solution of the class as a whole. In this paper, the authors describe the properties and concepts necessary for deriving such a solution, and propose a solution methodology, based on dynamic programming, that is pseudo-polynomial in its complexity. They also highlight the computational limitations of the proposed methodology (or, for that matter, any methodology) in solving certain members of the class under considerations, and discuss its extensibility to a broader class of early/tardy problems.