Optimal Control of Non-Conventional Queueing Networks: A Simulation-Based Approximate Dynamic Programming Approach

This dissertation considers stochastic modeling and optimization problems associated with a type of queueing network later defined as non-conventional queueing networks. Unlike their conventional counterparts, where only external arrival and service-related dynamics in the networks are modeled, non-conventional queueing networks not only admit general inter-arrival and service time distributions but also allow the modeling of other types of recurring events within a network. As a result, a non-conventional queueing network becomes much more appropriate for modeling realistic systems. For queueing networks, one of the main research problems is to find a good control policy so that networks can work within stable and efficient regions. In this study, we consider one of these problems, known as sequencing control, which involves prioritizing waiting customers or jobs in the network so that the overall throughput of the network can be improved. To optimize sequencing control problems in non-conventional queueing networks, an analytic and tractable approach is needed. To achieve this, a model approximation method based on the use of phase-type (PH) distributions is investigated in this study. Here, the use of PH distributions admits a tractable Markov model of the problem so that an optimization problem can be associated with the network. One then attempts to solve this optimization problem and hopes that an optimal solution can be obtained for the corresponding network. This is not quite true, as there usually exist certain mismatches between the real process and its approximated mathematical model. These mismatches would generally suggest two types of model parameter uncertainties with the problem. The first type can be associated with the problem's cost structure in reflecting correct objectives for the problem to be optimized, and the second type can be associated with the underlying parameters of the model in reflecting the correct dynamics of the process, e.g., the transition matrix. In particular, the latter type can be often incurred during the model approximation steps. Three practical challenges are then identified in this work with model approximation steps for nonconventional queueing networks, corresponding to 1) simultaneous approximation, 2) event concurrency, and 3) state space expansion. It is also found that the first two challenges will usually lead to biases or deviations in the underlying model parameters and thus create parameter uncertainties. This becomes even more severe when model approximation is carried out with higher-order moment-matching algorithms. The last challenge raises the classic computational tractability issue, known as the "curse of dimensionality." To overcome these challenges and ameliorate the effects of model parameter uncertainties, a heuristic solution is proposed and investigated in this work. This heuristic approach is based on the use of what we call a nominal-optimal policy set. To proceed with the development of this heuristic approach, optimality equations and structural properties for optimal sequencing control problems are first presented and discussed. These results are utilized later, along with proper parameterization of the problem's cost structure, to help explore and evaluate differenterent control policies. To further facilitate and promote this approach, an integrated framework called the extended actor-critic is presented, with the main focus and discussion on its structural and convergence properties. Later, numerical studies and results are also presented and discussed to validate the use of this framework.