On the Complexity of the Single Machine Scheduling Problem Minimizing Total Weighted Delay Penalty

We consider a single machine scheduling problem for a fixed penalty function f. For this problem every job j has a priority wj, and a processing time pj and the goal is to find an order on the given jobs that minimizes ?wff(cj), where cj is the completion time of job j. This paper studies the complexity of this problem for various classes of penalty functions.