×

Discrete-review policies for scheduling stochastic networks: trajectory tracking and fluid-scale asymptotic optimality. (English) Zbl 1083.60520

Summary: 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.

MSC:

60K25 Queueing theory (aspects of probability theory)
90B36 Stochastic scheduling theory in operations research
PDF BibTeX XML Cite
Full Text: DOI Euclid

References:

[1] Athans, M. and Falb, P. (1966). Optimal Control. McGraw-Hill, New York. · Zbl 0196.46303
[2] Atkins, D. and Chen, H. (1995). Performance evaluation of scheduling control of queueing networks: fluid model heuristics. Queueing Sys. 21 391-413. · Zbl 0858.90052
[3] Avram, F., Bertsimas, D. and Ricard, M. (1995). Fluid models of sequencing problems in open queueing networks; an optimal control approach. In Stochastic Networks, Proceedings of the IMA(F. Kelly and R. Williams, eds.) 71 199-234. Springer, NewYork. · Zbl 0837.60083
[4] Bambos, N. and Walrand, J. (1993). Scheduling and stability aspects of a general class of parallel processing systems. Adv. in Appl. Probab. 25 176-202. JSTOR: · Zbl 0768.60083
[5] Bertsekas, D. P. (1995). Dynamic Programming and Optimal Control 1. Athena Scientific, Belmont, MA. · Zbl 0904.90170
[6] Bertsimas, D., GamarnikD. and Sethuraman, J. (1999). Asymptotically optimal solutions for job shop scheduling problems. Technical report, Operations Research Center, MIT.
[7] Bertsimas, D., Paschalidis, I. C. and Tsitsiklis, J. N. (1995). Branching bandits and Klimov’s problem: achievable region and side constraints. IEEE Trans. Automat. Control 40 2063-2075. · Zbl 0844.90030
[8] Bertsimas, D. and Van Ryzin, G. (1991). A stochastic and dynamic vehicle routing problem in the Euclidean plane. Oper. Res. 39 601-615. · Zbl 0736.90027
[9] Bramson, M. (1998). Stability of two families of queueing networks and a discussion of fluid limits. Queueing Sys. 28 7-31. · Zbl 0911.90163
[10] Bryson, A. E. and Ho, Y. C. (1975). Applied Optimal Control. Hemisphere Publishing, NewYork.
[11] Chen, H. (1995). Fluid approximations and stability of multiclass queueing networks: workconserving policies. Ann. Appl. Probab. 5 637-655. · Zbl 0847.60073
[12] Chen, H. and Mandelbaum, A. (1991). Discrete flownetworks: bottleneck analysis and fluid approximations. Math. Oper. Res. 16 408-446. JSTOR: · Zbl 0735.60095
[13] Chen, H. and Yao, D. (1993). Dynamic scheduling of a multiclass fluid network. Oper. Res. 41 1104-1115. JSTOR: · Zbl 0791.90023
[14] Chen, R.-R. and Meyn, S. P. (1999). Value iteration and optimization of multiclass queueing networks. Queueing Sys. 32 65-97. Dai, J. G. (1995a). On positive Harris recurrence of multiclass queueing networks: a unified approach via fluid limit models. Ann. Appl. Probab. 5 49-77. Dai, J. G. (1995b). Stability of open multiclass queueing networks via fluid models. In Stochastic Networks Proceedings of the IMA (F. Kelly and R. Williams, eds.) Springer, NewYork. 71 71-90. · Zbl 0949.90020
[15] Dai, J. G. and Meyn, S. (1995). Stability and convergence of moments for multiclass queueing networks via fluid limit models. IEEE Trans. Autmat. Control 40 1889-1904. · Zbl 0836.90074
[16] Dai, J. G. and Weiss, G. (1996). Stability and instability of fluid models for certain re-entrant lines. Math. Oper. Res. 21 115-134. JSTOR: · Zbl 0848.60086
[17] Dai, J. G. and Weiss, G. (1999). A fluid heuristic for job shop scheduling. Technical report, Dept. Statistics, Univ. Haifa.
[18] Davis, M. H. A. (1984). Piecewise-deterministic Markov processes: a general class of nondiffusion stochastic models. J. Roy Statist. Soc. Ser. B 46 353-388. JSTOR: · Zbl 0565.60070
[19] Eng, D., Humphrey, J. and Meyn, S. P. (1996). Fluid network models: linear programs for control and performance bounds. In 13th World Congress of International Federation of Automatic Control 2 19-24 North-Holland, Amsterdam.
[20] Gans, N. and Van Ryzin, G. (1997). Optimal control of a multiclass, flexible queueing system. Oper. Res. 45 677-693. · Zbl 0902.90063
[21] Harrison, J. M. (1988). Brownian models of queueing networks with heterogeneous customer populations. In Stochastic Differential Systems, Stochastic Control Theory and Applications Proceedings of the IMA (W. Fleming and P. L. Lions, eds.) 10 147-186. Springer, NewYork. · Zbl 0658.60123
[22] Harrison, J. M. (1996). The BIGSTEP approach to flowmanagement in stochastic processing networks. In Stochastic Networks: Theory and Applications (F. Kelly, S. Zachary and I. Ziedins, eds.) 57-90. Oxford Univ. Press. · Zbl 0860.60068
[23] Harrison, J. M. (1998). Heavy traffic analysis of a system with parallel servers: Asymptotic optimality of discrete-reviewpolicies. Ann. Appl. Probab. 8 1-24. · Zbl 0938.60094
[24] Harrison, J. M. and Wein, L. M. (1989). Scheduling network of queues: heavy traffic analysis of a simple open network. Queueing Sys. 5 265-280. · Zbl 0684.90034
[25] Harrison, J. M. and Wein, L. M. (1990). Scheduling networks of queues: heavy traffic analysis of a two-station closed network. Oper. Res. 38 1052-1064. JSTOR: · Zbl 0723.90026
[26] Kelly, F. and Laws, N. (1993). Dynamic routing in open queueing networks: Brownian models, cut constraints and resource pooling. Queueing Sys. 13 47-86. · Zbl 0772.60068
[27] Kumar, P. R. and Seidman, T. I. (1990). Dynamic instabilities and stabilization methods in distributed real-time scheduling of manufacturing systems. IEEE Trans. Autmat. Control 35 289-298. · Zbl 0715.90062
[28] Kushner, H. J. and Martins, L. F. (1996). Heavy traffic analysis of a controlled multiclass queueing network via weak convergence methods. SIAM J. Control Optim. 34 1781-1797. · Zbl 0857.90041
[29] Lu, S. H. and Kumar, P. R. (1991). Distributed scheduling based on due dates and buffer priorities. IEEE Trans. Autmat. Control 36 1406-1416.
[30] Luo, X. and Bertsimas, D. (1996). A newalgorithm for state constrained separated linear programs. Technical report, MIT.
[31] Maglaras, C. (1997). A methodology for dynamic control policy design for stochastic processing networks via fluid models. In Proceedings IEEE Conference on Decision and Control 1208-1214. IEEE, NewYork.
[32] Maglaras, C. (1999). Dynamic scheduling in multiclass queueing networks: stability under discrete-reviewpolicies. Queueing Sys. 31 171-206. · Zbl 0934.90021
[33] Maglaras, C. (2000). Tracking Policies for control of stochastic networks: Brownian models, heavy traffic and asymptotic optimality. Technical report, Columbia University. · Zbl 1083.60520
[34] Newell, G. F. (1971). Applications of Queueing Theory. Chapman and Hall, London. · Zbl 0258.60004
[35] Puhalskii, A. and Reiman, M. (1998). A critically loaded multirate link with trunk reservation. Queueing Sys. 28 157-190. · Zbl 0908.90134
[36] Pullan, M. C. (1993). An algorithm for a class of continuous linear programs. SIAM J. Control Optim. 31 1558-1577. · Zbl 0833.90124
[37] Pullan, M. C. (1995). Form of optimal solutions for separated continuous linear programs. SIAM J. Control Optim. 33 1952-1977. · Zbl 0861.49027
[38] Pullan, M. C. (1996). A duality theory for separated continuous linear programs. SIAM J. Control Optim. 34 931-965. · Zbl 0847.49028
[39] Royden, L. H. (1963). Real Analysis. Macmillan, NewYork. · Zbl 0121.05501
[40] Rybko, A. N. and Stolyar, A. L. (1992). Ergodicity of stochastic processes describing the operations of open queueing networks. Problems Inform. Transmission 28 199-220. · Zbl 0768.60089
[41] Stolyar, A. L. (1995). On the stability of multiclass queueing networks: a relaxed sufficient condition via limiting fluid processes. Markov Processes Related Fields 1 491-512. · Zbl 0902.60079
[42] Tassiulas, L. and Papavassiliou, S. (1995). Optimal anticipative scheduling with asynchronous transmission opprtunities. IEEE Trans. Autmat. Control 40 2052-2062. · Zbl 0845.90057
[43] Weiss, G. (1996). Optimal draining of fluid re-entrant lines: some solved examples. In Stochastic Networks: Theory and Applications (F. Kelly, S. Zachary and I. Ziedins, eds.) 19-34. Oxford Univ. Press. · Zbl 0855.60087
[44] Weiss, G. (1997). Algorithm for minimum wait draining of two station fluid re-entrant line. Technical report, Dept. Statistics, Univ. Haifa. · Zbl 0958.90008
[45] Weiss, G. (1999). Scheduling and control of manufacturing systems via optimal control of multiclass fluid networks. In Proceedings of 37th Allerton Conference on Communications, Control and Computing.
[46] Williams, R. J. (1996). On the approximation of queueing networks in heavy traffic. In Stochastic Networks: Theory and Applications (F. Kelly, S. Zachary, and I. Ziedins, eds.) 35-56. Oxford Univ. Press. · Zbl 0855.60083
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.