×

Near optimal control of queueing networks over a finite time horizon. (English) Zbl 1169.90346

Summary: We propose a method for the control of multi-class queueing networks over a finite time horizon. We approximate the multi-class queueing network by a fluid network and formulate a fluid optimization problem which we solve as a separated continuous linear program. The optimal fluid solution partitions the time horizon to intervals in which constant fluid flow rates are maintained. We then use a policy by which the queueing network tracks the fluid solution. To that end we model the deviations between the queuing and the fluid network in each of the intervals by a multi-class queueing network with some infinite virtual queues. We then keep these deviations stable by an adaptation of a maximum pressure policy. We show that this method is asymptotically optimal when the number of items that is processed and the processing speed increase. We illustrate these results through a simple example of a three stage re-entrant line.

MSC:

90B22 Queues and service in operations research
90B15 Stochastic network models in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adan, I. J. B. F., & Weiss, G. (2005). A two node Jackson network with infinite supply of work. Probability in Engineering and Informational Sciences, 19, 191–212. · Zbl 1097.90010
[2] Adan, I. J. B. F., & Weiss, G. (2006). Analysis of a simple Markovian re-entrant line with infinite supply of work under the LBFS policy. Queueing Systems Theory and Applications, 54, 169–183. · Zbl 1103.60076 · doi:10.1007/s11134-006-0065-4
[3] Anderson, E. J. (1981). A new continuous model for job-shop scheduling. International Journal Systems Science, 12, 1469–1475. · Zbl 0468.90033 · doi:10.1080/00207728108963831
[4] Anderson, E. J., & Nash, P. (1987). Linear programming in infinite dimensional spaces. Chichester: Wiley-Interscience. · Zbl 0632.90038
[5] Avram, F., Bertsimas, D., & Ricard, M. (1995). Fluid models of sequencing problems in open queueing networks: an optimal control approach. In F. P. Kelly & R. Williams (Eds.), IMA volumes in mathematics and its applications: Vol. 71. Stochastic networks (pp. 199–234). New York: Springer. · Zbl 0837.60083
[6] Bellman, R. (1953). Bottleneck problems and dynamic programming. Proceedings National Academy of Science, 39, 947–951. · Zbl 0053.27903 · doi:10.1073/pnas.39.9.947
[7] Bramson, M. (1998). State space collapse with application to heavy traffic limits for multiclass queueing networks. Queueing Systems Theory and Applications, 30, 89–148. · Zbl 0911.90162 · doi:10.1023/A:1019160803783
[8] Chen, H., & Yao, D. (1993). Dynamic scheduling of a multi class fluid network. Operations Research, 41, 1104–1115. · Zbl 0791.90023 · doi:10.1287/opre.41.6.1104
[9] Chen, M., Pandit, C., & Meyn, S. P. (2003). In search of sensitivity in network optimization. Queueing Systems Theory and Applications, 44, 313–363. · Zbl 1033.90037 · doi:10.1023/A:1025130105303
[10] Chen, R. R., & Meyn, S. P. (1999). Value iteration and optimization of multiclass queueing networks. Queueing Systems Theory and Applications, 32, 65–97. · Zbl 0949.90020 · doi:10.1023/A:1019182903300
[11] Connors, D., Feigin, G., & Yao, D. (1994). Scheduling semiconductor lines using a fluid network model. IEEE Transactions on Robotics and Automation, 10, 88–98. · doi:10.1109/70.282534
[12] Dai, J. G. (1995). On positive Harris recurrence of multi-class queueing networks: a unified approach via fluid limit models. Annals of Applied Probability, 5, 49–77. · Zbl 0822.60083 · doi:10.1214/aoap/1177004828
[13] Dai, J. G., & Lin, W. (2005). Maximum pressure policies in stochastic processing networks. Operations Research, 53, 197–218. · Zbl 1165.90359 · doi:10.1287/opre.1040.0170
[14] Dai, J. G., & Lin, W. (2006). Asymptotic optimality of maximum pressure policies in stochastic processing networks. Annals of Applied Probability (submitted). · Zbl 1175.90083
[15] Fleischer, L., & Sethuraman, J. (2003). Approximately optimal control of fluid networks. IBM Research Report · Zbl 1094.90510
[16] Goemans, M. X., & Williamson, D. P. (1996). The primal dual method for approximation algorithms and its application to network design problems. In D. Hochbaum (Ed.) Approximation algorithms (pp. 144–191).
[17] Harrison, J. M. (1988). Brownian models of queueing networks with heterogeneous customer populations. In W. Fleming & P. L. Lions (Eds.), Proceedings of the IMA workshop on stochastic differential systems. Berlin: Springer. · Zbl 0658.60123
[18] Harrison, J. M. (1996). The BIGSTEP approach to flow management in stochastic processing networks. In F. P. Kelly, S. Zachary, & I. Ziedins (Eds.), Royal statistical society lecture note series: Vol. 4. Stochastic networks: theory and applications (pp. 147–186). Oxford: Oxford University Press. · Zbl 0860.60068
[19] Harrison, J. M. (2000). Brownian models of open processing networks: canonical representation of workload. Annals of Applied Probability, 10, 75–103. · Zbl 1131.60306 · doi:10.1214/aoap/1019737665
[20] Harrison, J. M. (2001). A broader view of Brownian networks. Annals of Applied Probability, 13, 1119–1150. · Zbl 1060.90020 · doi:10.1214/aoap/1060202837
[21] Harrison, J. M. (2002). Stochastic networks and activity analysis. In Y. Suhov (Ed.), Analytic methods in applied probability, In memory of Fridrik Karpelevich. Providence: American Mathematical Society.
[22] Harrison, J. M., & Van Mieghem, J. (1997). Dynamic control of Brownian networks: State space collapse and equivalent workload formulations. Annals of Applied Probability, 7, 747–771. · Zbl 0885.60080 · doi:10.1214/aoap/1034801252
[23] Kelly, F. P., & Laws, C. N. (1993). Dynamic routing in open queueing networks: Brownian models, cut constraints and resource pooling. Queueing Systems Theory and Applications, 13, 47–86. · Zbl 0772.60068 · doi:10.1007/BF01158929
[24] Kopzon, A., & Weiss, G. (2002). A push pull queueing system. Operations Research Letters, 30, 351–359. · Zbl 1013.90041 · doi:10.1016/S0167-6377(02)00149-9
[25] Kopzon, A., & Weiss, G. (2007). A push pull system with infinite supply of work. Preprint. · Zbl 1166.60333
[26] Kushner, H. J. (2001). Heavy traffic analysis of controlled queueing and communication networks. Berlin: Springer. · Zbl 0988.90004
[27] Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. H. G., & Shmoys, D. B. (1993). Sequencing and scheduling, algorithms and complexity. In S. C. Graves & A. H. G. Rinnooy (Eds.), Handbooks in operations research and management science: Vol. 4. Logistics of production and inventory. Amsterdam: North Holland.
[28] Maglaras, C. (1999). Dynamic scheduling in multiclass queueing networks: Stability under discrete-review policies. Queueing Systems Theory and Applications, 31, 171–206. · Zbl 0934.90021 · doi:10.1023/A:1019106213778
[29] Maglaras, C. (2000). Discrete-review policies for scheduling stochastic networks: Trajectory tracking and fluid-scale asymptotic optimality. Annals of Applied Probability, 10, 897–929. · Zbl 1083.60520 · doi:10.1214/aoap/1019487513
[30] Meyn, S. P. (2001). Sequencing and routing in multiclass queueing networks. Part I: Feedback regulation. SIAM Journal Control and Optimization, 40, 741–776. IEEE international symposium on information theory. Sorrento, Italy, June 25 – June 30 2000. · Zbl 1060.90043 · doi:10.1137/S0363012999362724
[31] Meyn, S. P. (2003). Sequencing and routing in multiclass queueing networks. Part II: Workload relaxations. SIAM Journal Control and Optimization, 42, 178–217. · Zbl 1061.90047 · doi:10.1137/S036301290138376X
[32] Shah, S., & Nahrstedt, K. (2002). Predictive location-based QoS routing in mobile ad hoc networks. In Proceedings of IEEE international conference on communications.
[33] Pullan, M. C. (1993). An algorithm for a class of continuous linear programs. SIAM Journal Control and Optimization, 31, 1558–1577. · Zbl 0833.90124 · doi:10.1137/0331073
[34] Stolyar, A. L. (2004). MaxWeight scheduling in a generalized switch: State space collapse and equivalent workload minimization under complete resource pooling. Annals of Applied Probability, 14(1), 1–53. · Zbl 1057.60092 · doi:10.1214/aoap/1075828046
[35] Tassiulas, L. (1995). Adaptive back-pressure congestion control based on local information. IEEE Transactions on Automatic Control, 40, 236 -250. · Zbl 0821.90047 · doi:10.1109/9.341781
[36] Wein, L. M. (1992). Scheduling networks of queues: Heavy traffic analysis of a multistation network with controllable inputs. Operations Research, 40, S312–S334. · Zbl 0763.90043 · doi:10.1287/opre.40.3.S312
[37] Weiss, G. (1999). Scheduling and control of manufacturing systems–a fluid approach. In Proceedings of the 37 Allerton conference, Monticello, Illinois 21–24, September 1999, (pp. 577–586).
[38] Weiss, G. (2005). Jackson networks with unlimited supply of work. Journal of Applied Probability, 42, 879–882. · Zbl 1082.60090 · doi:10.1239/jap/1127322036
[39] Weiss, G. (2008). A simplex based algorithm to solve separated continuous linear programs. Mathematical Programming, 115, 151–198. · Zbl 1165.90011 · doi:10.1007/s10107-008-0217-x
[40] Williams, R. J. (1998). Diffusion approximations for open multiclass queueing networks: sufficient conditions involving state space collapse. Queueing Systems Theory and Applications, 30, 27–88. · Zbl 0911.90171 · doi:10.1023/A:1019108819713
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.