Discrete-review policies for scheduling stochastic networks: trajectory tracking and fluid-scale asymptotic optimality
Open Access
- 1 August 2000
- journal article
- Published by Institute of Mathematical Statistics in The Annals of Applied Probability
- Vol. 10 (3), 897-929
- https://doi.org/10.1214/aoap/1019487513
Abstract
This paper describes a general approach for dynamic control of stochastic networks based on fluid model analysis, where in broad terms, the stochastic network is approximated by its fluid analog, an associated fluid control problem is solved and, finally, a scheduling rule for the original system is defined by interpreting the fluid control policy. The main contribution of this paper is to propose a general mechanism for translating the solution of the fluid optimal control problem into an implementable discrete-review policy that achieves asymptotically optimal performance under fluid scaling, and guarantees stability if the traffic intensity is less than one at each station. The proposed policy reviews system status at discrete points in time, and at each such point the controller formulates a processing plan for the next review period,based on the queue length vector observed, using the optimal control policy of the associated fluid optimization problem. Implementation of such a policy involves enforcement of certain safety stock requirements in order to facilitate the execution of the processing plans and to avoid unplanned server idleness. Finally, putting aside all considerations of system optimality, the following generalization is considered: every initial condition is associated with a feasible fluid trajectory that describes the desired system evolution starting at that point. A discrete-review policy is described that asymptotically tracks this target specification; that is, it achieves the appropriate target trajectory as its fluid limit.Keywords
This publication has 30 references indexed in Scilit:
- Asymptotically Optimal Algorithms for Job Shop Scheduling and Packet RoutingJournal of Algorithms, 1999
- Heavy traffic analysis of a system with parallel servers: asymptotic optimality of discrete-review policiesThe Annals of Applied Probability, 1998
- Stability and convergence of moments for multiclass queueing networks via fluid limit modelsIEEE Transactions on Automatic Control, 1995
- Performance evaluation of scheduling control of queueing networks: Fluid model heuristicsQueueing Systems, 1995
- Branching bandits and Klimov's problem: achievable region and side constraintsIEEE Transactions on Automatic Control, 1995
- Optimal anticipative scheduling with asynchronous transmission opportunitiesIEEE Transactions on Automatic Control, 1995
- Dynamic routing in open queueing networks: Brownian models, cut constraints and resource poolingQueueing Systems, 1993
- Scheduling and stability aspects of a general class of parallel processing systemsAdvances in Applied Probability, 1993
- Distributed scheduling based on due dates and buffer prioritiesIEEE Transactions on Automatic Control, 1991
- Scheduling networks of queues: Heavy traffic analysis of a simple open networkQueueing Systems, 1989