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

SINGLE MACHINE E/T SCHEDULING WITH WINDOW DUE DATE

作　　者：贾春福[1] 孙旭[1] 

机构地区：[1]南开大学信息技术科学学院,天津300071

出　　处：《南开大学学报（自然科学版）》2004年第4期48-53,共6页Acta Scientiarum Naturalium Universitatis Nankaiensis

摘　　要：工件完成时间与交货期差的绝对值加权和最小化单机调度是典型的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.$$$$

关 键 词：单机调度 窗口交货期 E/T(Earliness/Tardiness) 正比权值 

分 类 号：F224[经济管理—国民经济]