关于具有正比权值完工时间与公共交货期偏差最小化单机调度问题的注记

摘要

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.%讨论了工件权值与加工时间成正比、完工时间与公共交货期绝对偏差权和最小化单机调度问题(简记为PTD问题).1997年,Alidaee和Dragan证明了PTD问题LPT(Largest Processing Time)调度最优.并给出一个简单证明;还讨论了加工时间随机的情形,指出依加工时间似然比单减得到的工件调度最优.