On the Minimization of Completion Time Variance with a Bicriteria Extension

Prabuddha De, Jay B. Ghosh and Charles E. Wells
Additional contact information
Prabuddha De: University of Dayton, Dayton, Ohio
Jay B. Ghosh: University of Dayton, Dayton, Ohio
Charles E. Wells: University of Dayton, Dayton, Ohio

Operations Research, 1992, vol. 40, issue 6, 1148-1155

Abstract: 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.

Keywords: dynamic programming/optimal control: exact and approximate algorithms; production/scheduling: minimizing completion time variance; programming: scheduling with multiple criteria (search for similar items in EconPapers)
Date: 1992
References: Add references at CitEc
Citations: View citations in EconPapers (29)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.40.6.1148 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:40:y:1992:i:6:p:1148-1155

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().