On the general solution for a class of early/tardy problems (Q1207204): Difference between revisions

The non-preemptive scheduling of \(n\) jobs with a common due date \(d\) on a single machine is considered. The objective is to find a schedule that minimizes \(\sum^ n_{j=1} | C_ j- d|^ r\), where \(C_ j\) is the completion time of job \(j\) and \(r\) is a positive integer. By generalizing known results for \(r=1\) and \(r=2\), various structural properties of an optimal solution are derived. These structural properties are used to derive a pseudopolynomial dynamic programming algorithm. Prior to applying this algorithm, it is assumed that the processing times and the due date are suitably scaled using an integer scaling factor so that optimal completion times of jobs are integers.