ON THE MINIMIZATION OF COMPLETION-TIME VARIANCE WITH A BICRITERIA EXTENSION
成果类型：
Article
署名作者：
DE, P; GHOSH, JB; WELLS, CE
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.40.6.1148
发表日期：
1992
页码：
1148-1155
关键词：
摘要：
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.