Due date assignment and single machine scheduling with deteriorating jobs to minimize the weighted number of tardy jobs

In this paper, we explore a single-machine scheduling problem in which the processing time of a job is a linear increasing function of its starting time. The objective is to determine the optimal due date and schedule simultaneously to minimize a cost function that includes the weighted number of tardy jobs and the due date assignment cost. We show that the problem is NP-hard in the ordinary sense. In addition, we propose two dynamic programming algorithms and a fully polynomial-time approximation scheme for the problem.