Scheduling jobs for a common due window to minimize weighted sum of earliness and tardiness penalties

This paper studies a single machine scheduling problem in which all jobs have a common due window. Each job incurs a job dependent early (tardy) penalty if it is early (tardy) with respect to the common due window. The objective is to find an optimal sequence and an optimal common due window location such that the weighted sum of earliness and tardiness penalties of jobs is minimized. It is shown that the problem is NP-Complete in an ordinary sense and a method by dynamic programming in pseudo-polynomial time is presented so that the boundary of this kind of problem is clearer.