Optimal restricted due date assignment in scheduling

In classical scheduling problems it is common to assume that the due dates are predefined parameters for the scheduler. In integrated systems, however, due date assignment and scheduling decisions have to be carefully coordinated to make sure that the company can meet the assigned due dates. Thus, a huge effort has been made recently to provide tools to optimally integrate due date assignment and scheduling decisions. In most cases it is common to assume that the assigned due date(s) are not restricted. However, in many practical cases, assigning due dates too far into the future may violate early agreements between the manufacturer and his customers. Thus, in this paper we extend the current literature to deal with such a constraint. This is done by analyzing a model that integrates due date assignment and scheduling decisions where each job may be assigned a different due date whose value cannot exceed a predefined threshold. The objective is to minimize the total weighted earliness, tardiness and due date assignment penalties. We show that the problem is equivalent to a two stepwise weighted tardiness problem, and thus for a large set of special cases it is strongly NP-hard, even when the scheduling is done on a single machine. We then provide several special cases that can be solved in polynomial time, and present approximation results for a slightly modified (and equivalent) problem on various machine settings.