SCHEDULING JOBS WITH PROPORTIONATE EARLY TARDY PENALTIES

We address the problem of scheduling jobs subject to proportionate early/tardy penalties. The problem is known to be NP-complete. We identify interesting special cases,and develop polynomial time procedures for solving them optimally. It is shown that the shortest processing time rule is optimal when due dates are set using the widely known total work content rule or the equal slack rule. If jobs have a common due date, many alternative optimal solutions exist, and the longest processing time rule yields an optimal sequence. Also, a simple formula is provided for determining the optimal start times for jobs in the common due date problem. Our results for the common due date problem generalize and extend earlier research. Further extensions are discussed.