ON THE MINIMIZATION OF COMPLETION-TIME VARIANCE WITH A BICRITERIA EXTENSION

被引:92
作者
DE, P
GHOSH, JB
WELLS, CE
机构
关键词
D O I
10.1287/opre.40.6.1148
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
We discuss a single-machine scheduling problem where the objective is to minimize the variance of job completion times. To date, the problem has not been solved in polynomial time. This paper presents a dynamic programming algorithm that is pseudopolynomial in complexity. We also propose a fully polynomial approximation scheme and derive a lower bound that is useful in its implementation. Furthermore, we show that the dynamic programming solution is easy to extend to a bicriteria version of the problem in which it is desired to simultaneously minimize the mean completion time.
引用
收藏
页码:1148 / 1155
页数:8
相关论文
共 12 条