In this paper,we define a new class of scheduling criteria called over-regular criteria. This class is a subclass of regular criteria. We analyze the properties of scheduling problems with over-regular criteria. In the literature a lot of effort has been made to solve specific problems, these properties, however, are applicable to several scheduling problems. Using these properties and proving additional specific ones, we propose a procedure to solve the scheduling problem to minimize total tardiness with generalized due dates. This latter problem particularly arises in maintenance departments where maintained parts are interchangeable. Computational results are also reported.