Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-22T15:11:51.541Z Has data issue: false hasContentIssue false
  • English
  • Français

Monotone stopping-allocation problems

Published online by Cambridge University Press:  01 July 2016

Robert A. Benhenni
Robert A. Benhenni*
Affiliation:
University of California, Los Angeles
*
∗Present address: AT & T Bell Laboratories, IH4A-271, 2000 N. Naperville Road, Naperville, IL 60566, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

Stopping-allocation problems are concerned with how best to allocate observations among some K competing stochastic populations and when to stop the observation process. The goal of the decision-maker is to choose a stopping–allocation rule to maximize the expected value of a payoff function. First the stopping rule is fixed, and the local and global optimality of the myopic allocation rule are derived under some monotonicity conditions. An application is considered, namely the inspection problem and its use in solving a computer scheduling problem. Next, optimization is done with respect to both the allocation rule and the stopping rule. For any given stopping-allocation rule, it is shown that under some monotonicity conditions, the decision-maker can improve on it by using a ‘partial' myopic allocation rule and a generalized one-stage-look-ahead stopping rule; this result is then extended, under the same conditions and other monotonicity requirements, to derive the joint optimality of the myopic allocation rule and the one-stage-look-ahead stopping rule. Finally this latter result is applied to the inspection problem.

Keywords

STOPPING–ALLOCATION RULEMYOPIC ALLOCATION RULEONE-STAGE-LOOK-AHEAD STOPPING RULEINSPECTION PROBLEM
Type
Research Article
Information
Advances in Applied Probability , Volume 23 , Issue 1 , March 1991 , pp. 24 - 45
Copyright
Copyright © Applied Probability Trust 1991 

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.)

References

1. Bechhofer, R. E. and Kulkarni, R. V. (1982) Closed adaptive sequential procedures for selecting the best of k ≧ 2 Bernoulli populations. Proc. 3rd Purdue Symp. Statistical Decision Theory and Related Topics , ed. Gupta, S. S. and Berger, J., Academic Press, New York, 61–108.Google Scholar
2. 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
3. Chow, Y. S., Robbins, H. E. and Siegmund, D. O. (1971) Great Expectations: The Theory of Optimal Stopping. Houghton Mifflin, Boston.Google Scholar
4. Gittins, J. C. and Glazebrook, K. D. (1977) On Bayesian models in stochastic scheduling J. Appl. Prob. 14, 556–565.CrossRefGoogle Scholar
5. Gittins, J. C. and Jones, D. M. (1974) A dynamic allocation index for the sequential design of experiments. In Progress in Statistics , ed. Gani, J. et al. North-Holland, Amsterdam.Google Scholar
6. Glazebrook, K. D. (1980) On stochastic scheduling with precedence relations and switching costs. J. Appl. Prob. 17, 1016–1024.CrossRefGoogle Scholar
7. Glazebrook, K. D. (1982) Myopic strategies for Bayesian models in stochastic scheduling. Opsearch 19, 160–170.Google Scholar
8. Hall, G. J. Jr (1976) Sequential search with random overlook probabilities. Ann. Statist. 4, 807–816.CrossRefGoogle Scholar
9. Kulkarni, K. V. and Jennison, C. (1986) Optimal properties of the Bechhofer–Kulkarni Bernoulli selection procedure. Ann. Statist. 14, 298–314.Google Scholar
10. Weitzman, M. L. (1979) Optimal search for the best alternative. Econometrica 47, 641–654.Google Scholar
11. Wetherill, G. B. and Glazebrook, K. D. (1986) Sequential Methods in Statistics , 3rd edn. Chapman and Hall, New York.Google Scholar