Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-23T14:56:10.514Z Has data issue: false hasContentIssue false
  • English
  • Français

On the undiscounted tax problem with precedence constraints

Published online by Cambridge University Press:  01 July 2016

K. D. Glazebrook
K. D. Glazebrook*
Affiliation:
University of Newcastle upon Tyne
*
∗ Postal address: Department of Mathematics and Statistics, University of Newcastle upon Tyne, NE1 7RU, UK.
Get access Rights & Permissions [Opens in a new window]

Abstract

A single machine is available to process a collection of jobs J, each of which evolves stochastically under processing. Jobs incur costs while awaiting the machine at a rate which is state dependent and processing must respect a set of precedence constraints Γ. Index policies are optimal in a variety of scenarios. The indices concerned are characterised as values of restart problems with the average reward criterion. This characterisation yields a range of efficient approaches to their computation. Index-based suboptimality bounds are derived for general processing policies. These bounds enable us to develop sensitivity analyses and to evaluate scheduling heuristics.

Keywords

AVERAGE REWARD OPTIMALITYINDEX POLICYRESTART PROBLEMSTOCHASTIC SCHEDULINGSUBOPTIMALITY BOUNDSWEIGHTED FLOWTIME

MSC classification

Primary: 90C40: Markov and semi-Markov decision processes
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 28 , Issue 4 , December 1996 , pp. 1123 - 1144
Copyright
Copyright © Applied Probability Trust 1996 

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

Bertsimas, D. and Niño-Mora, J. (1994) Conservation laws, extended polymatroids and multi-armed bandit problems: a unified approach to indexable systems. Unpublished manuscript. Google Scholar
Gittins, J. C. (1989) Multi-Armed Bandit Allocation Indices. Wiley, New York.Google Scholar
Glazebrook, K. D. (1976) Stochastic scheduling with order constraints. Int. J. Systems Sci. 7, 657–666.Google Scholar
Glazebrook, K. D. (1982) On the evaluation of suboptimal strategies for families of alternative bandit processes. J. Appl. Prob. 19, 716–722.Google Scholar
Glazebrook, K. D. (1983) Stochastic scheduling with due dates. Int. J. Systems Sci. 14, 1259–1271.Google Scholar
Glazebrook, K. D. (1987) Sensitivity analysis for stochastic scheduling problems. Math. Operat. Res. 12, 205–223.Google Scholar
Glazebrook, K. D. (1991) Strategy evaluation for stochastic scheduling problems with order constraints. Adv. Appl. Prob. 23, 86–104.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, 161–173.Google Scholar
Katehakis, M. N. and Veinott, A. F. (1987) The multi-armed bandit problem: decomposition and computation. Math. Operat. Res. 12, 262–268.CrossRefGoogle Scholar
Klimov, G. P. (1974) Time sharing service systems I. Theory Prob. Appl. 19, 532–551.Google Scholar
Lai, T. L. and Ying, Z. (1988) Open bandit processes and optimal scheduling of queueing networks. Adv. Appl Prob. 20, 447–472.Google Scholar
Nain, P., Tsoucas, P. and Walrand, J. C. (1989) Interchange arguments in stochastic scheduling. J. Appl. Prob. 27, 815–826.Google Scholar
Ross, S. M. (1970) Applied Probability Models with Optimization Applications. Holden-Day, San Francisco.Google Scholar
Ross, S. M. (1983) Introduction to Stochastic Dynamic Programming. Academic Press, New York.Google Scholar
Sidney, J. B. (1975) Decomposition algorithms for single-machine scheduling with precedence relations and deferral costs. Operat. Res. 23, 283–293.Google Scholar
Tijms, H. C. (1986) Stochastic Modelling and Analysis: A Computational Approach.Google Scholar
Tsitsiklis, J. N. (1994) A short proof of the Gittins index theorem. Ann. Appl. Prob. 4, 194–199.Google Scholar
Varaiya, P., Walrand, J. C. and Buyukkoc, C. (1985) Extensions of the multiarmed bandit problem: the discounted case. IEEE Trans. Aut. Control. AC–30, 426–439.Google Scholar
Walrand, J. C. (1988) An Introduction to Queueing Networks. Prentice Hall, Englewood Cliffs, N.J. Google Scholar