Home | Articles | Past volumes | About | Login | Notify | Contact | Search
 Stochastic Systems > Vol. 6 (2016) open journal systems 


Dynamic scheduling for parallel server systems in heavy traffic: Graphical structure, decoupled workload matrix and some sufficient conditions for solvability of the Brownian Control Problem

V. Pesic, XR Trading
R. J. Williams, Department of Mathematics, UCSD


Abstract
We consider a dynamic scheduling problem for parallel server systems. J. M. Harrison has proposed a scheme for using diffusion control problems to approximately solve such control problems for heavily loaded systems. This approach has been very successfully used in the special case when the diffusion control problem can be reduced to an equivalent one for a one-dimensional workload process. However, it remains a challenging open problem to make substantial progress on using Harrison’s scheme when the workload process is more than one-dimensional. Here we present some new structural results concerning the diffusion control problem for parallel server systems with arbitrary workload dimension. Specifically, we prove that a certain server-buffer graph associated with a parallel server system is a forest of trees. We then exploit this graphical structure to prove that there exists a matrix, used to define the workload process, that has a block diagonal-like structure. An important feature of this matrix is that, except when the workload is one-dimensional, this matrix is frequently different from a choice of workload matrix proposed by Harrison. We demonstrate that our workload matrix simplifies the structure of the control problem for the workload process by proving that when the original diffusion control problem has linear holding costs, the equivalent workload formulation also has a linear cost function. We also use this simplification to give sufficient conditions for a certain least control process to be an optimal control for the diffusion control problem with linear holding costs. Under these conditions, we propose a continuous review threshold-type control policy for the original parallel server system that exploits pooling of servers within trees in the server-buffer graph and uses non-basic activities connecting different trees in a critical manner. We call this partial pooling. We conjecture that this threshold policy is asymptotically optimal in the heavy traffic limit. We illustrate the solution of the diffusion control problem and our proposed threshold control policy for a three-buffer, three-server example.

AMS 2000 subject classifications: Primary 60K25, 68M20, 90B36; secondary 60J70.

Keywords: Stochastic networks, dynamic control, resource pooling, heavy traffic, Brownian Control Problems, state space collapse, threshold policies.

Creative Common LOGO

Full Text: PDF


Pesic, V., Williams, R. J., Dynamic scheduling for parallel server systems in heavy traffic: Graphical structure, decoupled workload matrix and some sufficient conditions for solvability of the Brownian Control Problem, Stochastic Systems, 6, (2016), 26-89 (electronic). DOI: 10.1214/14-SSY163.

References

[1]    B. Ata and S. Kumar. Heavy traffic analysis of open processing networks with complete resource pooling: Asymptotic optimality of discrete review policies. Annals of Applied Probability, 15 (2005), 331–391. MR2115046

[2]    B. Ata and W. Lin. Heavy traffic analysis of maximum pressure policies for stochastic processing with multiple bottlenecks, Queueing Systems, 59 (2008), 191–235. MR2439295

[3]    B. Ata and J. A. Van Mieghem. The value of dynamic resource pooling: Should a service network be integrated or product-focused? Management Science, 55 (2009), 115–131.

[4]    R. Atar, A. Mandelbaum and G. Shaikhet. Queueing systems with many servers: Null controllability in heavy traffic. Annals of Applied Probability, 16 (2006), 1764–1804. MR2288704

[5]    R. Atar and I. Gurvich, Scheduling parallel servers in the nondegenerate slowdown diffusion regime: Asymptotic optimality results, Annals of Applied Probability, 24 (2014), 760–810. MR3178497

[6]    S. L. Bell and R. J. Williams. Dynamic scheduling of a system with two parallel servers in heavy traffic with resource pooling: Asymptotic optimality of a threshold policy. Annals of Applied Probability, 11 (2001), 608–649. MR1865018

[7]    S. L. Bell and R. J. Williams. Dynamic scheduling of a parallel server system in heavy traffic with complete resource pooling: Asymptotic optimality of a threshold policy. Electronic J. of Probability, 10 (2005), 1044–1115. MR2164040

[8]    C. Berge. Graphs, North Hollans, Amsterdam, 1985. MR0809587

[9]    V. Bohm. On the continuity of the optimal policy set for linear programs. SIAM J. Appl. Math., 28 (1975), 303–306. MR0371390

[10]    A. Budhiraja and A. P. Ghosh. A large deviations approach to asymptotically optimal control of crisscross network in heavy traffic. Annals of Applied Probability, 15 (2005), 1887–1935. MR2152248

[11]    A. Budhiraja and A. Ghosh, Controlled stochastic networks in heavy traffic: Convergence of value functions, Annals of Applied Probability, 22 (2012), 734–791. MR2953568

[12]    M. Bramson and R. J. Williams. Two workload properties for Brownian networks. Queueing Systems, 45 (2003), 191–221. MR2024178

[13]    J. G. Dai and W. Lin. Asymptotic optimality of maximum pressure policies in stochastic processing networks, Annals of Applied Probability, 18 (2008), 2239–2299. MR2473656

[14]    J. M. Harrison. Brownian models of queueing networks with heterogeneous customer population. In Stochastic Differential Systems, Stochastic Control Theory and Their Applications, IMA Volume 10, W. Fleming and P. L. Lions (eds.), Springer Verlag, New York, 1988, 147–186. MR0934722

[15]    J. M. Harrison. 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.), Oxford University Press, 1996, 57–90.

[16]    J. M. Harrison. Heavy traffic analysis of a system with parallel servers: Asymptotic optimality of discrete review policies. Annals of Applied Probability, 8 (1998), 822–848. MR1627791

[17]    J. M. Harrison. Brownian models of open processing networks: Canonical representation of workload. Annals of Applied Probability, 10 (2000), 75–103. Correction: 13 (2003), 390–393. MR1765204

[18]    J. M. Harrison and M. J. López. Heavy traffic resource pooling in parallel server systems. Queueing Systems, 33 (1999), 339–368. MR1742575

[19]    J. M. Harrison and J. A. Van Mieghem. Dynamic control of Brownian networks: State space collapse and Equivalent Workload Formulations. Annals of Applied Probability, 7 (1997), 747–771. MR1459269

[20]    J. M. Harrison and L. M. Wein. Scheduling networks of queues: Heavy traffic analysis of a simple open network. Queueing Systems, 5 (1989), 265–280. MR1030470

[21]    J. M. Harrison and R. J. Williams. Workload reduction of a generalized Brownian network. Annals of Applied Probability, 15 (2005), 2255–2295. MR2187295

[22]    F. P. Kelly and C. N. Laws. Dynamic routing in open queueing networks: Brownian models, cut constraints and resource pooling. Queueing Systems, 13 (1993), 47–86. MR1218844

[23]    H. J. Kushner and Y. N. Chen, Optimal control of assignment of jobs to processors under heavy traffic, Stochastics and Stochastics Reports, 68 (2000), 177–228. MR1746180

[24]    H. J. Kushner and P. Dupuis, Numerical Methods for Stochastic Control Problems in Continuous Time, Springer-Verlag, New York, 1992. MR1217486

[25]    H. J. Kushner and L. F. Martins, Numerical methods for stochastic singular control problems, SIAM J. Control and Optimization, 29 (1991), 1443–1475. MR1132190

[26]    C. N. Laws. Resource pooling in queueing networks with dynamic routing. Advances in Applied Probability, 24 (1992), 699–726. MR1174386

[27]    C. N. Laws and G. M. Louth. Dynamic sequencing of a four station queueing network. Probab. Engrg. Inform. Sci., 4 (1990), 131–156.

[28]    C. Maglaras. Continuous-review tracking policies for dynamic control of stochastic networks. Queueing Systems, 43 (2003), 43–80. MR1957806

[29]    A. Mandelbaum and A. L. Stolyar. Scheduling flexible servers with convex delay costs: Heavy-traffic optimality of the generalized -rule. Operations Research 52 (2004), 836–855. MR2104141

[30]    L. F. Martins, S. E. Shreve and H. M. Soner. Heavy traffic convergence of a controlled, multiclass queueing system. SIAM J. Control Optim. 34 (1996), 2133–2171. MR1416504

[31]    V. Pesic and R. J. Williams, Dynamic scheduling of a parallel server system with partial pooling: Heavy traffic analysis of a three-buffer, three-server system, in preparation.

[32]    A. L. Stolyar. MaxWeight scheduling in a generalized switch: State space collapse and workload minimization in heavy traffic. Annals of Applied Probability, 14 (2004), 1–53. MR2023015

[33]    L. Wein. Scheduling networks of queues: Heavy traffic analysis of a multistation network with controlable inputs. Operations Research, 40 (1992), 312–334.

[34]    R. J. Williams. On dynamic scheduling of a parallel server system with complete resource pooling. In Analysis of Communication Networks: Call Centers, Traffic and Performance, D. R. McDonald and S. R. E. Turner (eds.), American Mathematical Society, Providence, RI, 2000, 49–71. MR1788708

[35]    P. Yang. Least controls for a class of constrained linear stochastic systems. Mathematics of Operations Research, 10 (1993), 275–291. MR1250119




Home | Articles | Past volumes | About | Login | Notify | Contact | Search

Stochastic Systems. ISSN: 1946-5238