ON THE GENERAL-SOLUTION FOR A CLASS OF EARLY TARDY PROBLEMS

We 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, we 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. We also highlight the computational limitations of the proposed methodology (or, for that matter, any methodology) in solving certain members of the class under consideration, and discuss its extensibility to a broader class of early/tardy problems.