Economics at your fingertips  

Marginal productivity index policies for problems of admission control and routing to parallel queues with delay

Peter Jacko and José Niño Mora

DES - Working Papers. Statistics and Econometrics. WS from Universidad Carlos III de Madrid. Departamento de Estadística

Abstract: In this paper we consider the problem of admission control of Bernoulli arrivals to a buffer with geometric server, in which the controller’s actions take effect one period after the actual change in the queue length. An optimal policy in terms of marginal productivity indices (MPI) is derived for this problem under the following three performance objectives: (i) minimization of the expected total discounted sum of holding costs and rejection costs, (ii) minimization of the expected time-average sum of holding costs and rejection costs, and (iii) maximization of the expected time-average number of job completions. Our employment of existing theoretical and algorithmic results on restless bandit indexation together with some new results yields a fast algorithm that computes the MPI for a queue with a buffer size of I performing only O(I) arithmetic operations. Such MPI values can be used both to immediately obtain the optimal thresholds for the admission control problem, and to design an index policy for the routing problem (with possible admission control) in the multi-queue system. Thus, this paper further addresses the problem of designing and computing a tractable heuristic policy for dynamic job admission control and/or routing in a discrete time Markovian model of parallel loss queues with one-period delayed state observation and/or action implementation, which comes close to optimizing an infinite-horizon problem under the above three objectives. Our approach seems to be tractable also for the analogous problems with larger delays and, more generally, for arbitrary restless bandits with delays.

Keywords: Admission; control; Routing; Parallel; queues; Delayed; information; Delayed; action; implementation; Index; policy; Restless; bandits; Marginal; productivity; index (search for similar items in EconPapers)
Date: 2008-12
New Economics Papers: this item is included in nep-cmp
References: View references in EconPapers View complete reference list from CitEc

Downloads: (external link) ... 7d4393a4a2fc/content (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link:

Access Statistics for this paper

More papers in DES - Working Papers. Statistics and Econometrics. WS from Universidad Carlos III de Madrid. Departamento de Estadística
Bibliographic data for series maintained by Ana Poveda ().

Page updated 2024-05-12
Handle: RePEc:cte:wsrepe:ws087225