×

Dynamic scheduling of a system with two parallel servers in heavy traffic with resource pooling: Asymptotic optimality of a threshold policy. (English) Zbl 1015.60080

The authors consider a queueing system consisting of two buffers and two parallel servers with dynamic scheduling capabilities. One server can process jobs from one buffer, whereas the other server can process jobs from either buffer. The service time distribution may depend on the buffer being served and the server providing service. The system manager dynamically schedules waiting jobs onto available servers. The authors consider a parameter regime in which the system satisfies both a heavy traffic condition and a resource pooling condition. The cost function is a mean cumulative discounted cost of holding jobs in the system. They propose a dynamic threshold control policy and show that it is the same as the optimal cost for the Brownian control problem.

MSC:

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

References:

[1] Billingsley, P. (1968). Convergence of Probability Measures. Wiley, New York. · Zbl 0172.21201
[2] Bramson, M. (1996). Convergence to equilibria for fluid models of FIFO queueing networks. Queueing Systems 22 5-45. · Zbl 0851.90044 · doi:10.1007/BF01159391
[3] Chen, H. and Mandelbaum, A. (1991). LeontiefSystems, RBV’s and RBM’s. In Applied Stochastic Analysis (M. H. A. Davis and R. J. Elliott, eds.) 1-43. Gordon and Breach, New York. · Zbl 0729.90021
[4] Chevalier, P. B. and Wein, L. (1993). Scheduling networks ofqueues: heavy traffic analysis ofa multistation closed network. Operations Research 41 743-758. · Zbl 0782.90037 · doi:10.1287/opre.41.4.743
[5] Dembo, A. and Zeitouni, O. (1998). Large Deviations Techniques and Applications, 2nd ed. Springer, New York. · Zbl 0896.60013
[6] Ethier, S. N. and Kurtz, T. G. (1986). Markov Processes: Characterization and Convergence. Wiley, New York. · Zbl 0592.60049
[7] Harrison, J. M. (1985). Brownian Motion and Stochastic Flow Systems. Wiley, New York. · Zbl 0659.60112
[8] Harrison, J. M. (1988). Brownian models ofqueueing networks with heterogeneous customer populations. In Stochastic Differential Systems, Stochastic Control Theory and Their Applications (W. Fleming and P. L. Lions, eds.) 147-186. Springer, New York. · Zbl 0658.60123
[9] Harrison, J. M. (1996). The BIGSTEP approach to flow management in stochastic processing networks. In Stochastic Networks: Theory and Applications (F. P. Kelly, S. Zachary and I. Ziedins, eds.) 57-90. Oxford Univ. Press. · Zbl 0860.60068
[10] Harrison, J. M. (1998). Heavy traffic analysis of a system with parallel servers: asymptotic optimality ofdiscrete-review policies. Ann. Appl. Probab. 8 822-848. · Zbl 0938.60094 · doi:10.1214/aoap/1028903452
[11] Harrison, J. M. (2000). Brownian models ofopen processing networks: canonical representation ofworkload. Ann. Appl. Probab. 10 75-103. · Zbl 1131.60306 · doi:10.1214/aoap/1019737665
[12] Harrison, J. M. and L ópez, M. J. (1999). Heavy traffic resource pooling in parallel-server systems. Queueing Systems 33 339-368. · Zbl 0997.60108 · doi:10.1023/A:1019188531950
[13] Harrison, J. M. and Van Mieghem, J. A. (1997). Dynamic control ofBrownian networks: state space collapse and equivalent workload formulations. Ann. Appl. Probab. 7 747- 771. · Zbl 0885.60080 · doi:10.1214/aoap/1034801252
[14] Harrison, J. M. and Wein, L. (1989). Scheduling networks ofqueues: heavy traffic analysis ofa simple open network. Queueing Systems 5 265-280. · Zbl 0684.90034 · doi:10.1007/BF01225319
[15] Harrison, J. M. and Wein, L. (1990). Scheduling networks ofqueues: heavy traffic analysis ofa two-station closed network. Oper. Res. 38 1052-1064. JSTOR: · Zbl 0723.90026 · doi:10.1287/opre.38.6.1052
[16] Iglehart, D. L. and Whitt, W. (1971). The equivalence offunctional central limit theorems for counting processes and associated partial sums. Ann. Math. Statist. 42 1372-1378. · Zbl 0226.60028 · doi:10.1214/aoms/1177693249
[17] Jordan, W. C. and Graves, C. (1995). Principles on the benefits ofmanufacturing process flexibility. Management Sci. 41 577-594. · Zbl 0836.90087 · doi:10.1287/mnsc.41.4.577
[18] Kelly, F. P. and Laws, C. N. (1993). Dynamic routing in open queueing networks: Brownian models, cut constraints and resource pooling. Queueing Systems 13 47-86. · Zbl 0772.60068 · doi:10.1007/BF01158929
[19] Kumar, S. (2000). Two-server closed networks in heavy traffic: diffusion limits and asymptotic optimality. Ann. Appl. Probab. 10 930-961. · Zbl 1073.60538 · doi:10.1214/aoap/1019487514
[20] Kushner, H. J. and Chen, Y. N. (2000). Optimal control ofassignment ofjobs to processors under heavy traffic. Stochastics Stochastics Rep. 68 177-228. · Zbl 1033.90148 · doi:10.1080/17442500008834223
[21] Kushner, H. J. and Dupuis, P. (1992). Numerical Methods for Stochastic Control Problems in Continuous Time. Springer, New York. · Zbl 0754.65068
[22] Kushner, H. J. and Martins, L. F. (1990). Routing and singular control for queueing networks in heavy traffic. SIAM J. Control Optim. 28 1209-1233. · Zbl 0718.90029 · doi:10.1137/0328065
[23] 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 · doi:10.1137/S0363012994275592
[24] Laws, C. N. (1992). Resource pooling in queueing networks with dynamic routing. Adv. Appl. Probab. 24 699-726. JSTOR: · Zbl 0768.90029 · doi:10.2307/1427485
[25] Laws, C. N. and Louth, G. M. (1990). Dynamic scheduling ofa four-station queueing network. Probab. Engrg. Inform. Sci. 4 131-156. · Zbl 1134.90408 · doi:10.1017/S0269964800001492
[26] Martins, L. F., Shreve, S. E. and Soner, H. M. (1996). Heavy traffic convergence of a controlled, multi-class queueing system. SIAM J. Control Optim. 34 2133-2171. · Zbl 0866.90061 · doi:10.1137/S0363012994265882
[27] Mitrani, I. (1998). Probabilistic Modelling. Cambridge Univ. Press. · Zbl 0887.60001 · doi:10.1017/CBO9781139173087
[28] Peterson, W. P. (1991). A heavy traffic limit theorem for networks of queues with multiple customer types. Math. Oper. Res. 16 90-118. JSTOR: · Zbl 0727.60114 · doi:10.1287/moor.16.1.90
[29] Puhalskii, A. A. and Reiman, M. I. (1998). A critically loaded multirate link with trunk reservation. Queueing Systems 28 157-190. · Zbl 0908.90134 · doi:10.1023/A:1019151106992
[30] Rockafellar, R. T. (1970). Convex Analysis. Princeton Univ. Press. · Zbl 0193.18401
[31] Roughan, M. and Pearce, C. E. M. (2000). A martingale analysis ofhysteretic overload control. Advances in Performance Analysis 3 1-30.
[32] Teh, Y. C. (1999). Threshold routing strategies for queueing networks. D.Phil. thesis, Univ. Oxford.
[33] Van Mieghem, J. A. (1995). Dynamic scheduling with convex delay costs: the generalized c\mu rule. Ann. Appl. Probab. 5 808-833. · Zbl 0843.90047 · doi:10.1214/aoap/1177004706
[34] Wein, L. (1990). Scheduling networks ofqueues: heavy traffic analysis ofa two-station network with controllable inputs. Oper. Res. 38 1065-1078. JSTOR: · Zbl 0724.90025 · doi:10.1287/opre.38.6.1065
[35] Williams, R. J. (1998). An invariance principle for semimartingale reflecting Brownian motions in an orthant. Queueing Systems 30 5-25. · Zbl 0911.90170 · doi:10.1023/A:1019156702875
[36] Williams, R. J. (1998). Diffusion approximations for open multiclass queueing networks: sufficient conditions involving state space collapse. Queueing Systems 30 27-88. · Zbl 0911.90171 · doi:10.1023/A:1019108819713
[37] Williams, R. J. (2000). On dynamic scheduling ofa parallel server system with complete resource pooling. In Analysis of Communication Networks: Call Centres, Traffic and Performance (D. R. McDonald and S. R. E. Turner, eds.) 49-71. Amer. Math. Soc., Providence, RI. · Zbl 0982.90024
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.