具有窗口交货期的单机E/T调度问题

摘要

工件完成时间与交货期差的绝对值加权和最小化单机调度是典型的E/T(Earliness/Tardiness)的调度模型,是NP-hard问题.然而,当工件权值与加工时间成正比时,LPT(Largest Processing Time)工件调度最优.本文讨论了上述问题具有窗口交货期且工件权值与加工时间成正比的情形,结果表明LPT工件调度仍然最优.