Dynamic allocation indices for restless projects and queueing admission control: a polyhedral approach

DOI10.1007/s10107-002-0362-6zbMath1023.90034OpenAlexW1494403903MaRDI QIDQ1396274

José Niño-Mora

Publication date: 30 June 2003

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-002-0362-6

zbMATH Keywords

Markov decision processstochastic schedulingGittins indexroutingpolyhedral combinatoricsWhittle indexthreshold policyrestless banditsfinite buffersindex policycontrol of queuesachievable performanceextended polymatroidconversation lawsmake-to-stockmulticlass queueadaptive-greedy algorithmKlimov index

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Queueing theory (aspects of probability theory) (60K25) Queues and service in operations research (90B22) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Stochastic scheduling theory in operations research (90B36) Markov and semi-Markov decision processes (90C40)

Related Items

Resource allocation and routing in parallel multi-server queues with abandonments for cloud profit maximization ⋮ Conditions for indexability of restless bandits and an algorithm to compute Whittle index ⋮ Dynamic routing to heterogeneous collections of unreliable servers ⋮ Marginal productivity index policies for scheduling a multiclass delay-/loss-sensitive queue ⋮ Resource capacity allocation to stochastic dynamic competitors: knapsack problem for perishable items and index-knapsack heuristic ⋮ Four proofs of Gittins' multiarmed bandit theorem ⋮ On the optimal allocation of service to impatient tasks ⋮ Admission and routing of soft real-time jobs to multiclusters: design and comparison of index policies ⋮ Dynamic routing in distinguishable parallel queues: an application of product returns for remanufacturing ⋮ Whittle’s Index Policy for Multi-Target Tracking with Jamming and Nondetections ⋮ A fluid approach to large volume job shop scheduling ⋮ On the computation of Whittle's index for Markovian restless bandits ⋮ Towards minimum loss job routing to parallel heterogeneous multiserver queues via index policies ⋮ A Verification Theorem for Threshold-Indexability of Real-State Discounted Restless Bandits ⋮ A conservative index heuristic for routing problems with multiple heterogeneous service facilities ⋮ Dynamic priority allocation via restless bandit marginal productivity indices ⋮ Some indexable families of restless bandit problems ⋮ Marginal Productivity Index Policies for Admission Control and Routing to Parallel Multi-server Loss Queues with Reneging ⋮ Grid Brokering for Batch Allocation Using Indexes ⋮ A Marginal Productivity Index Rule for Scheduling Multiclass Queues with Setups ⋮ Linear programming relaxations and marginal productivity index policies for the buffer sharing problem ⋮ Spinning plates and squad systems: policies for bi-directional restless bandits ⋮ DYNAMIC ROUTING OF CUSTOMERS WITH GENERAL DELAY COSTS IN A MULTISERVER QUEUING SYSTEM ⋮ Resource competition in virtual network embedding ⋮ Unnamed Item ⋮ Time-Constrained Restless Bandits and the Knapsack Problem for Perishable Items (Extended Abstract) ⋮ A Restless Bandit Model for Resource Allocation, Competition, and Reservation