The authors consider the n-job, non-preemptive, single-machine scheduling problem of minimizing the weighted sum of tardy jobs and earliness-tardiness penalties about a common due date. They study the case of job-dependent penalites under a certain condition on the ratio of processing times and weights. Two instances of the problem, one when the due date is a decision variable and the other when the due date is a given parameter, are considered. The authors provide dynamic programming algorithms to solve both instances. For the special case when the weights are independent of jobs, they propose more efficient algorithms.
