Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-09T11:53:10.612Z Has data issue: false hasContentIssue false
  • English
  • Français

Variance Minimization – Relationship between Completion-Time Variance and Waiting-Time Variance

Published online by Cambridge University Press:  17 February 2009

S. Zhou  and
X. Cai
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

The completion-time variance (CTV) and the waiting-time variance (WTV) are two performance measures which are commonly used in optimization of single-machine scheduling systems. This paper shows that when the number of jobs is large the two measures are nearly equivalent in a probabilistic environment.

Information

Type
Research Article
Information
The ANZIAM Journal , Volume 38 , Issue 1 , July 1996 , pp. 126 - 139
Copyright
Copyright © Australian Mathematical Society 1996

References

[1]Bagchi, U., “Simultaneous minimization of mean and variation of flow time and waiting time in single machine systems”, Opns Res. 37 (1989) 118–125.CrossRefGoogle Scholar
[2]Baker, K. R. and Scudder, G. D., “Sequencing with earliness and tardiness penalties: a review”, Op Res. 38 (1990) 22–36.CrossRefGoogle Scholar
[3]Cai, X., “Minimization of agreeably weighted variance in single machine systems”, Euro J of Op Res. (1993), to appear.Google Scholar
[4]Cheng, T. C. E. and Gupta, M. C., “Survey of scheduling research involving due date determination decisions”, Euro J of Op Res. 38 (1989) 156–166.CrossRefGoogle Scholar
[5]De, P., Ghosh, J. B. and Wells, C. E., “On the minimization of completion time variance with a bi-criteria extension”, Op. Res. 40 (1992) 1148–1155.CrossRefGoogle Scholar
[6]Eilon, S. and Chowdhury, I. G., “Minimizing waiting variance in the single machine problem”, Mgmt Sci. 23 (1977) 567–575.CrossRefGoogle Scholar
[7]French, S., Sequencing and Scheduling (Wiley, New York, 1982).Google Scholar
[8]Gerchak, Y. and Magazine, M. J., “Some remarks about the ‘equivalence’ of performance measures in scheduling problems”, Euro J of Op Res. 70 (1993) 432–435.CrossRefGoogle Scholar
[9]Ibarra, O. H. and Kim, C. E., “Approximation algorithms for certain scheduling problems”, Math. Opns Res. 3 (1978) 197–204.CrossRefGoogle Scholar
[10]Kan, A. H. G. Rinnooy, “An introduction to the analysis of approximation algorithms”, Discrete Appl Math. 14 (1986) 171–185.CrossRefGoogle Scholar
[11]Kan, A. H. G. Rinnooy, Machine scheduling problems: classification, complexity and computations, Volume 14, 1976, (Martinus Nijhoff, Dordrecht, 1986) 171–185.CrossRefGoogle Scholar
[12]Karp, R. M., “Probabilistic analysis of partitioning algorithms for the travelling-salesman problem in the plane”, Math. Opns Res. 2 (1977) 209–224.CrossRefGoogle Scholar
[13]Lawler, E. L., “Fast approximation algorithms for knapsack problems”, Math. Opns Res. 4 (1979) 339–356.CrossRefGoogle Scholar
[14]Merten, A. G. and Muller, M. E., “Variance minimization in single machine sequencing problems”, Mgmt Sci. 18 (1972) 518–528.CrossRefGoogle Scholar
[15]Schrage, L., “Minimizing the time-in-system variance for a finite jobset”, Mgmt Sci. 21 (1975) 540–543.CrossRefGoogle Scholar
[16]Vani, V. and Raghavachari, M., “Deterministic and random single machine sequencing with variance minimization”, Opns Res. 35 (1987) 111–120.CrossRefGoogle Scholar