MaxWeight scheduling in a generalized switch: State space collapse and workload minimization in heavy traffic

DOI10.1214/aoap/1075828046zbMath1057.60092OpenAlexW1999102639MaRDI QIDQ1431548

Publication date: 10 June 2004

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

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

zbMATH Keywords

heavy traffic asymptotic optimality state space collapse resource pooling generalized switch max weight scheduling

Mathematics Subject Classification ID

Stochastic network models in operations research (90B15) Queueing theory (aspects of probability theory) (60K25) Applications of Brownian motions and diffusion theory (population genetics, absorption problems, etc.) (60J70)

Related Items (70)

A Fluid Model for One-Sided Bipartite Matching Queues with Match-Dependent Rewards ⋮ An algorithm for improved delay-scaling in input-queued switches ⋮ Maximum weight matching with hysteresis in overloaded queues with setups ⋮ Dynamic scheduling with reconfiguration delays ⋮ Near optimal control of queueing networks over a finite time horizon ⋮ Justifying diffusion approximations for multiclass queueing networks under a moment condition ⋮ Asymptotic optimality of maximum pressure policies in stochastic processing networks ⋮ Diffusion approximation for an input-queued switch operating under a maximum weight matching policy ⋮ The capacity of QoE for wireless networks with unreliable transmissions ⋮ Greedy primal-dual algorithm for dynamic resource allocation in complex networks ⋮ Control of multi-node mobile communications networks with time-varying channels via stability methods ⋮ Optimal heavy-traffic queue length scaling in an incompletely saturated switch ⋮ A stochastic network with mobile users in heavy traffic ⋮ On scheduling a multiclass queue with abandonments under general delay costs ⋮ A load balancing system in the many-server heavy-traffic asymptotics ⋮ Control of Fork-Join Processing Networks with Multiple Job Types and Parallel Shared Resources ⋮ A fluid approach to large volume job shop scheduling ⋮ Asymptotically tight steady-state queue length bounds implied by drift conditions ⋮ A continuous-time queueing model with class clustering and global FCFS service discipline ⋮ Optimal buffer size and dynamic rate control for a queueing system with impatient customers in heavy traffic ⋮ Log-weight scheduling in switched networks ⋮ Congestion-based leadtime quotation and pricing for revenue maximization with heterogeneous customers ⋮ Applications of fluid models in service operations management ⋮ Switched networks with maximum weight policies: fluid approximation and multiplicative state space collapse ⋮ Randomized scheduling algorithm for queueing networks ⋮ Dynamic Distributed Scheduling in Random Access Networks ⋮ Fluctuation Bounds for the Max-Weight Policy with Applications to State Space Collapse ⋮ Stability and implementation of a cycle-based max pressure controller for signalized traffic networks ⋮ Process Flexibility for Multiperiod Production Systems ⋮ A survey on skill-based routing with applications to service operations management ⋮ Optimal queue-size scaling in switched networks ⋮ Lingering issues in distributed scheduling ⋮ Heavy Traffic Approximations of a Queue with Varying Service Rates and General Arrivals ⋮ Transform Methods for Heavy-Traffic Analysis ⋮ Information and Memory in Dynamic Resource Allocation ⋮ Large deviations of queues sharing a randomly time-varying server ⋮ Stability of Kumar-Seidman networks under longest queue first policy ⋮ Optimal control of parallel server systems with many servers in heavy traffic ⋮ Induced idleness leads to deterministic heavy traffic limits for queue-based random-access algorithms ⋮ Diffusion limit for the partner model at the critical value ⋮ A two-class global FCFS discrete-time queueing model with arbitrary-length constant service times ⋮ Stability and probability. I: Convergence for queueing networks via Lyapunov optimization ⋮ A regression-based smoothing spline Monte Carlo algorithm for pricing American options in discrete time ⋮ Pathwise optimality of the exponential scheduling rule for wireless channels ⋮ Asymptotically optimal parallel resource assignment with interference ⋮ OPTIMAL ROUTING IN OUTPUT-QUEUED FLEXIBLE SERVER SYSTEMS ⋮ Front-office multitasking between service encounters and back-office tasks ⋮ A Paradox for Admission Control of Multiclass Queueing Network with Differentiated Service ⋮ Control of systems with flexible multi-server pools: a shadow routing approach ⋮ Wireless scheduling with partial channel state information: large deviations and optimality ⋮ Dynamic scheduling for switched processing systems with substantial service-mode switching times ⋮ Concave switching in single-hop and multihop networks ⋮ Stationary distribution convergence of the offered waiting processes for \(GI/GI/1+GI\) queues in heavy traffic ⋮ Delay Analysis of the Max-Weight Policy Under Heavy-Tailed Traffic via Fluid Approximations ⋮ Heavy traffic analysis of maximum pressure policies for stochastic processing networks with multiple bottlenecks ⋮ Sufficient conditions for stability of longest-queue-first scheduling: second-order properties using fluid limits ⋮ Queueing and scheduling in random environments ⋮ Diffusion Limit of Fair Resource Control—Stationarity and Interchange of Limits ⋮ Diffusion approximation for a heavily loaded multi-user wireless communication system with cooperation ⋮ Instability of FIFO in a simple queueing system with arbitrarily low loads ⋮ Ranking flexibility structures in queueing systems ⋮ Improved queue-size scaling for input-queued switches via graph factorization ⋮ Dynamic safety-stocks for asymptotic optimality in stochastic networks ⋮ Maximizing queueing network utility subject to stability: greedy primal-dual algorithm ⋮ On the Whittle index of Markov modulated restless bandits ⋮ Diffusion Approximation Analysis of MultihopWireless Networks: Quality-of-Service and Convergence of Stationary Distribution ⋮ Logarithmic heavy traffic error bounds in generalized switch and load balancing systems ⋮ Heavy-Traffic Analysis of Queueing Systems with No Complete Resource Pooling ⋮ Minimal and Locally Edge Minimal Fluid Models for Resource-Sharing Networks ⋮ A Restless Bandit Model for Resource Allocation, Competition, and Reservation

Cites Work

This page was built for publication: MaxWeight scheduling in a generalized switch: State space collapse and workload minimization in heavy traffic