On the fixed interval due-date scheduling problem

We consider the nonpreemptive single machine scheduling problem with multiple due-dates (delivery dates), where the time between two consecutive due-dates is a constant. Given a set of jobs, we are interested in scheduling the jobs such that the sum of the total due-date cost and the total earliness cost is minimized with the constraint that each job must be finished at or before its due-date. We show that this problem is strongly NP-hard in general. We then analyze the problem where the number of due-dates is bounded by a given constant. We describe a pseudo-polynomial dynamic programming algorithm for this restricted problem. A heuristic is also provided and worst-case analysis is performed. An efficient algorithm is developed to solve the special case where all the job processing times are identical.