Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-28T20:17:02.235Z Has data issue: false hasContentIssue false
  • English
  • Français

Single-machine stochastic scheduling with dependent processing times

Part of: Operations research and management science

Published online by Cambridge University Press:  01 July 2016

K. D. Glazebrook  and
Lyn R. Whitaker
K. D. Glazebrook*
Affiliation:
University of Newcastle upon Tyne
Lyn R. Whitaker*
Affiliation:
Naval Postgraduate School
*
∗Postal address: Department of Mathematics and Statistics, University of Newcastle upon Tyne, Newcastle upon Tyne, NE1 7RU, UK.
∗∗Postal address: Department of Operations Research, Naval Postgraduate School, Monterey, California 93943, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

A single machine is available to process a collection of stochastic jobs preemptively. Rewards are received at job completions. We seek policies for machine allocation which maximize the total reward. Application areas point to the need to study such models for resource allocation when job processing requirements are dependent. To this end, models are developed in which the nature of such dependence is derived from various notions of positive and negative dependence in common usage in reliability. Optimal policies for resource allocation of simple structure are obtained for a variety of such models.

Keywords

ASSOCIATED RANDOM VARIABLESMARKOV DECISION PROCESSOPTIMAL POLICYSTOCHASTIC SCHEDULING

MSC classification

Primary: 90B35: Scheduling theory, deterministic
Type
Research Article
Information
Advances in Applied Probability , Volume 24 , Issue 3 , September 1992 , pp. 635 - 652
Copyright
Copyright © Applied Probability Trust 1992 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

Research supported by the National Research Council.

Research supported by the NPS Research Foundation.

References

Alam, K. and Wallenius, K. T. (1976) Positive dependence and monotonicity in conditional distributions. Commun. Statist. A5, 525–534.CrossRefGoogle Scholar
Barlow, R. and Proschan, F. (1981) Statistical Theory of Life Testing: Probability Models. To Begin With, Silver Spring, Maryland.Google Scholar
Bergman, S. W. and Gittins, J. C. (1985) Statistical Methods for Planning Pharmaceutical Research . Marcel Dekker, New York.Google Scholar
Block, H. W., Savits, T. H. and Shaked, M. (1982) Some concepts of negative dependence. Ann. Prob. 10, 765–772.Google Scholar
Brindley, E. C. Jr. and Thompson, W. A. Jr. (1972) Dependence and aging aspects of multivariate survival. J. Amer. Stat. Assoc. 67, 822–830.CrossRefGoogle Scholar
Bruno, J. and Hofri, M. (1975) On scheduling chains of jobs on one processor with limited preemption. SIAM J. Comput. 4, 478–490.Google Scholar
Emmons, H. and Pinedo, M. (1990) Scheduling stochastic jobs with due dates on parallel machines. Eur. J. Operat. Res. 47, 49–55.Google Scholar
Gittins, J. C. (1989) Multi-armed Bandit Allocation Indices. Wiley, New York.Google Scholar
Glazebrook, K. D. and Fay, N. A. (1987) On the scheduling of alternative stochastic jobs on a single machine. Adv. Appl. Prob. 19, 955–973.Google Scholar
Glazebrook, K. D. and Gittins, J. C. (1981) On single-machine scheduling with precedence relations and linear or discounted costs. Operat. Res. 29, 289–300.CrossRefGoogle Scholar
Hardy, G. H., Littlewood, J. E. and Pólya, G. (1934) Inequalities. Cambridge University Press.Google Scholar
Harris, R. (1970) A multivariate definition for increasing hazard rate distribution functions. Ann. Math. Statist. 41, 713–717.Google Scholar
Johnson, N. and Kotz, S. (1975) A vector multivariate hazard rate. J. Multivariate Anal. 5, 53–66.Google Scholar
Lee, M. L. T. (1985) Dependence by total positivity. Ann. Prob. 13, 572–582.CrossRefGoogle Scholar
Nash, P. (1973) Optimal Allocation of Resources between Research Projects. Ph.D. thesis, Cambridge University.Google Scholar
Nash, P. and Gittins, J. C. (1977) A Hamiltonian approach to optimal stochastic resource allocation. Adv. Appl. Prob. 9, 55–68.Google Scholar
Ritchie, E. M. (1972) Planning and control of R and D activities. Operat. Res. Quart. 23, 477–490.Google Scholar
Ross, S. M. (1970) Applied Probability Models with Optimization Applications. Holden-Day, San Francisco.Google Scholar
Shaked, M. (1975) On Concepts of Dependence for Multivariate Distributions. Ph.D. thesis, University of Rochester, Rochester, NY.Google Scholar
Shaked, M. (1977) A family of concepts of dependence for bivariate distributions. J. Amer. Statist. Assoc. 72, 642–650.Google Scholar
Shaked, M. and Shanthikumar, J. G. (1987) Multivariate hazard rates and stochastic ordering. Adv. Appl. Prob. 19, 123–137.Google Scholar
Yanagimoto, T. (1972) Families of positive dependent random variables. Ann. Inst. Statist. Math. A24, 559–573.Google Scholar