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
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 diffusio...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Institute for Operations Research and the Management Sciences (INFORMS)
2016-11-01
|
| Series: | Stochastic Systems |
| Subjects: | |
| Online Access: | http://www.i-journals.org/ssy/viewarticle.php?id=163&layout=abstract |
| _version_ | 1818208546251079680 |
|---|---|
| author | V. Pesic R. J. Williams |
| author_facet | V. Pesic R. J. Williams |
| author_sort | V. Pesic |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-12T04:46:32Z |
| format | Article |
| id | doaj.art-4ed87df9c45e4a7baa0bccf860294406 |
| institution | Directory Open Access Journal |
| issn | 1946-5238 1946-5238 |
| language | English |
| last_indexed | 2024-12-12T04:46:32Z |
| publishDate | 2016-11-01 |
| publisher | Institute for Operations Research and the Management Sciences (INFORMS) |
| record_format | Article |
| series | Stochastic Systems |
| spelling | doaj.art-4ed87df9c45e4a7baa0bccf8602944062022-12-22T00:37:36ZengInstitute for Operations Research and the Management Sciences (INFORMS)Stochastic Systems1946-52381946-52382016-11-0161268910.1214/14-SSY163Dynamic scheduling for parallel server systems in heavy traffic: Graphical structure, decoupled workload matrix and some sufficient conditions for solvability of the Brownian Control ProblemV. Pesic0R. J. Williams1XR TradingDepartment of Mathematics, UCSDWe 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.http://www.i-journals.org/ssy/viewarticle.php?id=163&layout=abstractStochastic networksdynamic controlresource poolingheavy trafficBrownian Control Problemsstate space collapsethreshold policies.threshold policies |
| spellingShingle | V. Pesic R. J. Williams 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 Stochastic networks dynamic control resource pooling heavy traffic Brownian Control Problems state space collapse threshold policies. threshold policies |
| title | 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 |
| title_full | 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 |
| title_fullStr | 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 |
| title_full_unstemmed | 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 |
| title_short | 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 |
| title_sort | 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 |
| topic | Stochastic networks dynamic control resource pooling heavy traffic Brownian Control Problems state space collapse threshold policies. threshold policies |
| url | http://www.i-journals.org/ssy/viewarticle.php?id=163&layout=abstract |
| work_keys_str_mv | AT vpesic dynamicschedulingforparallelserversystemsinheavytrafficgraphicalstructuredecoupledworkloadmatrixandsomesufficientconditionsforsolvabilityofthebrowniancontrolproblem AT rjwilliams dynamicschedulingforparallelserversystemsinheavytrafficgraphicalstructuredecoupledworkloadmatrixandsomesufficientconditionsforsolvabilityofthebrowniancontrolproblem |