Single machine scheduling with assignable due dates

AbstractThis paper introduces a new subclass of machine scheduling problems in which due dates are treated as variables and must be assigned to the individual jobs. A solution then is a sequence of jobs along with due date assignments. In contrast to existing due date assignment models, solutions to the proposed problems do not depend on predetermined rules or the requirement that due dates be assigned in the same order as the sequence. The single machine case is investigated in detail. Complexity results are presented for all common objective functions and processing restrictions. The analysis shows that in a number of instances polynomial time algorithms are available though most problems that are intractable under traditional due date definitions remain so