A new class of scheduling criteria and their optimization

The paper defines a new class of scheduling criteria called over-regular criteria. This class is a subclass of regular criteria. It analyzes the properties of scheduling problems with over-regular criteria. In the literature a lot of effort has been made to solve specific problems. The papers, however, are applicable to several scheduling problems. Using these properties and additional specific ones, it proposes a procedure to optimize an over-regular criterion in single machine case: minimization of total tardiness with generalized due dates. This problem particularly arises in maintenance departments where maintained parts are interchangeable. Computational results about ths procedure are also reported.