宽容交货加权超前延误单机排序问题

Scheduling Jobs for a Common Due Window to Minimize Weighted Sum of Earliness and Tardiness Penalties

该文研究下述宽容交货加权超前延误排序问题:n个工件具有一共同的宽容交货期,任一工件在宽容交货期内完工不受罚,超前或延误则受罚,惩罚系数依赖于工件.排序目标是找一个最优序和最优宽容交货区间位置使最小化加权超前延误惩罚之和.证明它是NP Completeness的,并给出一伪多项式算法,从而获知所研究问题是一般意义下NP Completeness的,也使该类问题的复杂性界限更清楚.

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.