摘要
工件完成时间与交货期差的绝对值加权和最小化单机调度是典型的E/T(Earliness/Tardiness)的调度模型,是NP-hard问题.然而,当工件权值与加工时间成正比时,LPT(LargestProcessingTime)工件调度最优.本文讨论了上述问题具有窗口交货期且工件权值与加工时间成正比的情形,结果表明LPT工件调度仍然最优.
The single machine scheduling problem to minimize total weighted deviations of completion times from a common due date is a typical E/T (Earliness/Tardiness) scheduling model. It is NP-hard. However, the LPT(Largest Processing Time) job schedule is optimal when the job weights are proportional to processing times. In this paper, the case with window due date and proportional weights of this problem is discussed, it is shown that LPT job schedule is also optimal.$$$$
出处
《南开大学学报（自然科学版）》
CAS
CSCD
北大核心
2004年第4期48-53,共6页
Acta Scientiarum Naturalium Universitatis Nankaiensis
