Common due-date assignment and scheduling for a single processor to minimize the number of tardy jobs

This paper considers the problem of assigning a common due-date to a set of simultaneously available jobs and sequencing them on a single production facility. The objective is to determine the optimal common due-date value and job sequence that jointly minimize a cost function based on the assigned due-date and the number of tardy jobs. It is shown that the optimal due-date coincides with one of the job completion times and ordering jobs in non-decreasing processing times yields an optimal sequence which in general is not unique. An efficient (polynomial-bound) algorithm to find the optimal solution is presented and an illustrative example is provided.