Abstract
The principle of forwards induction is that jobs, or parts of a job, are scheduled in decreasing order of the expected reward per unit time which they yield. Alternatively, each job, or part of a job, may have an associated priority index, and be scheduled accordingly. This paper explores the wide class of stochastic scheduling problems for which forwards induction leads to optimal policies, and the priority indices which are also optimal for these problems.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
R.E. Bellman (1957) Dynamic Programming, Princeton University Press, Princeton.
S.W. Bergman, J.C. Gittins (1982) The Uses of Statistical Methods in the Planning of New-Product Chemical Research, to appear.
W.L. Black (1965) Discrete sequential search. Inform, and Control 9, 159–162.
Y.S. Chow, H. Robbins, S. Siegmund (1971) Great Expectations, the Theory of Optimal Stopping, Houghton Mifflin, New York.
S. Gal (1980) Search Games, Academic Press, New York.
J.C. Gittins (1979) Bandit processes and dynamic allocation indices. J. Roy. Statist. Soc. Ser. B 14,148–177.
J.C. Gittins (1980) Sequenctial Resource Allocation: Progress Report, obtainable from the author.
J.C. Gittins, K.D. Glazebrook (1977) On Bayesian models in stochastic scheduling. J. Appl. Probab. 14, 556–565.
J.C. Gittins, P. Nash (1977) Scheduling, queues, and dynamic allocation indices. Proc. EMS, Prague, 1974, Czechoslovak Academy of Sciences, Prague, 191–202.
K.D. Glazebrook (1976) Stochastic scheduling with order constraints. Internat. J. Systems Sci. 7, 657–666.
K.D. Glazebrook (1976) A profitability index for alternative research projects. Omega 4, 79–83.
K.D. Glazebrook (1978) Some ranking formulea for alternative research projects. Omega 6, 193–194.
K.D. Glazebrook (1979) Stoppable families of alternative bandit processes. J. Appl. Probab. 16, 843–854.
K.D. Glazebrook (1980) On single-machine sequencing with order constraints. Naval Res. Logist. Quart. 27, 123–130.
K.D. Glazebrook (1981) On non-preemptive strategies in stochastic scheduling, Naval Res. Logist. Quart. 28, 289–300.
K.D. Glazebrook (1980) On non-preemptive strategies for stochastic scheduling problems in continuous time. Unpublished manuscript.
K.D. Glazebrook (1980) Methods for the evaluation of permutations as strategies in stochastic scheduling problems. Management Sci., to appear.
K.D. Glazebrook (1981) On a sufficient condition for super-processes due to Whittle. J. Appl. Probab., to appear.
K.D. Glazebrook, J.C. Gittins (1981) On single-machine scheduling with precedence relations and linear or discounted costs. Oper. Res. 29, 161–173.
G.J. Hall (1978) Nonstationary stochastic gold-mining: a time-sequential tactical allocation problem. Naval Res. Logist. Quart. 25, 81–93.
J.M. Harrison (1975) Dynamic scheduling of a multiclass queue: discount optimality. Oper. Res. 23, 270–282.
J.B. Kadane, H.A. Simon (1977) Optimal strategies for a class of constrained sequential problems. Ann. Statist. 5, 237–255.
F.P. Kelly (1979) Contribution to the discussion of [5]. J. Roy. Statist. Soc. Ser. B 41, 167–168.
E.L. Lawler (1978) Sequencing problems with series parallel precedence constraints. Proc. Summer School in Combinatovial Optimization, Urbino, 1978, to appear.
M. Lehnerdt (1980) On the Structure of Discrete Sequential Search Problems and of their Solutions, Doctoral dissertation, University of Hamburg.
I. Meilijson, G. Weiss (1977) Multiple feedback at a single server station. Stochastic Process. Appl. 5, 195–205.
I. Meilijson, U. Yechiali (1977) On optimal right-of-way poli-ciesat a single-server station when insertion of idle times is permitted. Stochastic Process. Appl. 6, 25–32.
P. Nash (1973) Optimal Allocation of Resources between Research Projects, Ph.D. thesis, Cambridge University.
P. Nash, J.C. Gittins (1977) A Hamiltonian approach to optimal stochastic resource allocation. Adv. in Appl. Probab. 9, 55–68.
J.B. Sidney (1975) Decomposition algorithms for single machine sequencing with precedence relations and deferral costs. Oper. Res. 23, 283–293.
A. Simonovits (1973) Direct comparison of different priority queueing disciplines. Studia Sci. Math. Hungar. 8, 225–243.
L.D. Stone (1975) Theory of Optimal Search, Academic Press, New York.
P. Whittle (1980) Multi-armed bandits and the Gittins index. J. Roy. Statist. Soc. Ser. B 42, 143–149.
P. Whittle (1981) Arm acquiring bandits. Ann. Probab. 9, 284–292.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1982 D. Reidel Publishing Company
About this paper
Cite this paper
Gittins, J.C. (1982). Forwards Induction and Dynamic Allocation Indices. In: Dempster, M.A.H., Lenstra, J.K., Rinnooy Kan, A.H.G. (eds) Deterministic and Stochastic Scheduling. NATO Advanced Study Institutes Series, vol 84. Springer, Dordrecht. https://doi.org/10.1007/978-94-009-7801-0_7
Download citation
DOI: https://doi.org/10.1007/978-94-009-7801-0_7
Publisher Name: Springer, Dordrecht
Print ISBN: 978-94-009-7803-4
Online ISBN: 978-94-009-7801-0
eBook Packages: Springer Book Archive