Common due date assignment and single-machine scheduling with release times to minimize the weighted number of tardy jobs

摘要

In just-in-time production, meeting due dates is one of the most important goals. Motivated by a scenario of just-in-time production, this paper considers the single-machine scheduling problem with release times and common due date assignment. 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, and propose a dynamic programming algorithm and a fully polynomial-time approximation scheme.