Dynamic scheduling of a system with two parallel servers in heavy traffic with resource pooling: Asymptotic optimality of a threshold policy

DOI10.1214/aoap/1015345343zbMath1015.60080OpenAlexW1974518363MaRDI QIDQ1872431

S. L. Bell, Ruth J. Williams

Publication date: 6 May 2003

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1214/aoap/1015345343

zbMATH Keywords

queueing networksdiffusion approximations

Mathematics Subject Classification ID

Queueing theory (aspects of probability theory) (60K25) Stochastic scheduling theory in operations research (90B36) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items

Scheduling a multi class queue with many exponential servers: asymptotic optimality in heavy traffic. ⋮ Brownian control problems for a multiclass M/M/1 queueing problem with model uncertainty ⋮ On-line service scheduling ⋮ On Vector-Kronecker Product Multiplication with Rectangular Factors ⋮ Asymptotic optimality of maximum pressure policies in stochastic processing networks ⋮ On the asymptotic optimality of the \(c\mu\)-rule in queueing networks ⋮ On scheduling a multiclass queue with abandonments under general delay costs ⋮ An asymptotic optimality result for the multiclass queue with finite buffers in heavy traffic ⋮ Asymptotically optimal control of \(N\)-systems with \(H_2^*\) service times under many-server heavy traffic ⋮ Fluid Models of Parallel Service Systems Under FCFS ⋮ On the Optimal Control of Parallel Processing Networks with Resource Collaboration and Multitasking ⋮ Queueing Network Controls via Deep Reinforcement Learning ⋮ Control of Fork-Join Processing Networks with Multiple Job Types and Parallel Shared Resources ⋮ Near critical catalyst reactant branching processes with controlled immigration ⋮ Optimal buffer size and dynamic rate control for a queueing system with impatient customers in heavy traffic ⋮ Asymptotically optimal control of many-server heterogeneous service systems with \(H_{2}^{*}\) service times ⋮ Optimal buffer size for a stochastic processing network in heavy traffic ⋮ Stability analysis of parallel server systems under longest queue first ⋮ Two‐class constrained optimization with applications to queueing control ⋮ A Fluid-Diffusion-Hybrid Limiting Approximation for Priority Systems with Fast and Slow Customers ⋮ Simple form control policies for resource sharing networks with HGI performance ⋮ Parallel server systems under an extended heavy traffic condition: a lower bound ⋮ Controlled stochastic networks in heavy traffic: convergence of value functions ⋮ Matched queues with flexible and impatient customers ⋮ Many-server scaling of the N-system under FCFS-ALIS ⋮ Asymptotic Analysis of a Multiclass Queueing Control Problem Under Heavy Traffic with Model Uncertainty ⋮ Stability analysis of N-model systems under a static priority rule ⋮ Stability analysis of a two-station cascade queueing network ⋮ Dynamic server allocation for unstable queueing networks with flexible servers ⋮ Dynamic Volunteer Staffing in Multicrop Gleaning Operations ⋮ Scheduling parallel servers in the nondegenerate slowdown diffusion regime: asymptotic optimality results ⋮ A survey on skill-based routing with applications to service operations management ⋮ Resource sharing networks: Overview and an open problem ⋮ Large-deviations analysis of the fluid approximation for a controllable tandem queue ⋮ The ``least flexible job first rule in scheduling and in queueing ⋮ MaxWeight scheduling in a generalized switch: State space collapse and workload minimization in heavy traffic ⋮ Profit maximization in flexible serial queueing networks ⋮ Scheduling control for Markov-modulated single-server multiclass queueing systems in heavy traffic ⋮ TWO-CLASS ROUTING WITH ADMISSION CONTROL AND STRICT PRIORITIES ⋮ Adaptive Matching for Expert Systems with Uncertain Task Types ⋮ Reducing Response Time in Fork-Join Systems under Heavy Traffic Via Imbalance Control ⋮ Performance of service policies in a specialized service system with parallel servers ⋮ Optimal control of parallel server systems with many servers in heavy traffic ⋮ THE N-NETWORK MODEL WITH UPGRADES ⋮ Design heuristic for parallel many server systems ⋮ Optimal Control of a Stochastic Processing System Driven by a Fractional Brownian Motion Input ⋮ Diffusion approximations for controlled weakly interacting large finite state systems with simultaneous jumps ⋮ Pathwise optimality of the exponential scheduling rule for wireless channels ⋮ Throughput maximization for two station tandem systems: a proof of the Andradóttir-Ayhan conjecture ⋮ Asymptotically optimal parallel resource assignment with interference ⋮ Robustness of efficient server assignment policies to service time distributions in finite-buffered lines ⋮ Inventory based allocation policies for flexible servers in serial systems ⋮ Heavy traffic analysis of open processing networks with complete resource pooling: asymptotic optimality of discrete review policies ⋮ DYNAMIC ASSIGNMENT OF DEDICATED AND FLEXIBLE SERVERS IN TANDEM LINES ⋮ Scheduling control for queueing systems with many servers: asymptotic optimality in heavy traffic ⋮ OPTIMAL ROUTING IN OUTPUT-QUEUED FLEXIBLE SERVER SYSTEMS ⋮ A Brownian control problem for a simple queueing system in the halfin--whitt regime ⋮ Asymptotic optimality of the generalized \(c\mu\) rule under model uncertainty ⋮ Control of systems with flexible multi-server pools: a shadow routing approach ⋮ Reliability by design in distributed power transmission networks ⋮ Diffusion approximations for controlled stochastic networks: an asymptotic bound for the value function ⋮ Diffusion approximations for load balancing mechanisms in cloud storage systems ⋮ Heavy Traffic Analysis of a Simple Closed-Loop Supply Chain ⋮ Staff assignment policies for a mass casualty event queuing network ⋮ Pooling is not the answer ⋮ Queuing with future information ⋮ Workload-Dependent Dynamic Priority for the Multiclass Queue with Reneging ⋮ Infinite-Horizon Average Optimality of the N-Network in the Halfin–Whitt Regime ⋮ On the Control of Fork-Join Networks ⋮ Control Policies Approaching Hierarchical Greedy Ideal Performance in Heavy Traffic for Resource Sharing Networks ⋮ Heavy traffic analysis of maximum pressure policies for stochastic processing networks with multiple bottlenecks ⋮ Optimal control of a flexible server ⋮ Large deviations of the long term distribution of a non Markov process ⋮ Diffusion approximation for a heavily loaded multi-user wireless communication system with cooperation ⋮ Optimal Control of Brownian Inventory Models with Convex Holding Cost: Average Cost Case ⋮ A large deviations approach to asymptotically optimal control of crisscross network in heavy traffic ⋮ Dynamic safety-stocks for asymptotic optimality in stochastic networks ⋮ Partial Flexibility in Routeing and Scheduling ⋮ Unnamed Item ⋮ Heavy-Traffic Analysis of Queueing Systems with No Complete Resource Pooling ⋮ Dynamic routing in large-scale service systems with heterogeneous servers

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A critically loaded multirate link with trunk reservation
• An invariance principle for semimartingale reflecting Brownian motions in an orthant
• Diffusion approximations for open multiclass queueing networks: Sufficient conditions involving state space collapse
• Heavy traffic analysis of a system with parallel servers: Asymptotic optimality of discrete-review policies
• Dynamic control of Brownian networks: State space collapse and equivalent workload formulations
• Brownian models of open processing networks: Canonical representation of workload.
• Dynamic routing in open queueing networks: Brownian models, cut constraints and resource pooling
• Scheduling networks of queues: Heavy traffic analysis of a simple open network
• Two-server closed networks in heavy traffic: diffusion limits and asymptotic optimality.
• Dynamic scheduling with convex delay costs: The generalized \(c\mu\) rule
• Convergence to equilibria for fluid models of FIFO queueing networks
• Heavy traffic resource pooling in parallel-server systems
• A Heavy Traffic Limit Theorem for Networks of Queues with Multiple Customer Types
• Dynamic Scheduling of a Four-Station Queueing Network
• Heavy Traffic Convergence of a Controlled, Multiclass Queueing System
• Resource pooling in queueing networks with dynamic routing
• Scheduling Networks of Queues: Heavy Traffic Analysis of a Multistation Closed Network
• Probabilistic Modelling
• Heavy Traffic Analysis of a Controlled Multiclass Queueing Network via Weak Convergence Methods
• Principles on the Benefits of Manufacturing Process Flexibility
• Optimal control of assignment of jobs to processors under heavy traffic
• Scheduling Networks of Queues: Heavy Traffic Analysis of a Two-Station Closed Network
• Scheduling Networks of Queues: Heavy Traffic Analysis of a Two-Station Network with Controllable Inputs
• Convex Analysis
• The Equivalence of Functional Central Limit Theorems for Counting Processes and Associated Partial Sums
• Routing and Singular Control for Queueing Networks in Heavy Traffic