作　　者： ;

机构地区： 南开大学信息技术科学学院

出　　处： 《南开大学学报（自然科学版）》 2005年第4期86-89,共4页

摘　　要： 讨论了工件权值与加工时间成正比、完工时间与公共交货期绝对偏差权和最小化单机调度问题(简记为PTD问题).1997年,Alidaee和Dragan证明了PTD问题LPT(LargestProcessingTime)调度最优.并给出一个简单证明;还讨论了加工时间随机的情形,指出依加工时间似然比单减得到的工件调度最优. The problem of minimizing total weighted absolute deviations of job completion times from a common due date on a single machine with proportional job weights （PTD） is considered. Alidaee and Dragan in 1997 showed that LPT （largest processing time） job schedule is optimal for this problem. In this paper, a simple proof of the result of PTD problem is given. Moreover, the stochastic counterpart of the PTD problem with random processing times （SPTD） is also discussed, and the job schedule in decreasing order in the sense of likelihood ratio is shown optimal.

关 键 词： 调度 单机 正比权值 随机加工时间 似然比

领　　域： [经济管理]