Models and Numerical Algorithms for Queueing and Manufacturing Systems

Markovian models are widely used in modeling and analyzing queuing and manufacturing systems. For the purpose of performance analysis, one requires the solution of the steady-state probability distribution of a large and complex Markov chain. We first develop models for complex manufacturing systems and queuing systems. We then develop fast numerical algorithms for solving linear systems arising from the captured applications. Typical examples are Flexible Manufacturing Systems and queuing systems with batch arrivals and negative customers. Classical iterative methods such as Gauss-Seidel are common solvers for these types of problems. However, their convergence rates are slow in general when the problem size is large. In this project we suggest to develop two types of numerical algorithms: the Preconditioned Conjugate Gradient method and the hybrid algorithm based on the evolutionary algorithm and the successive over-relaxation method. We establish theoretically the convergence rate of the numerical methods and compare them with the classical iterative methods.

Multivariate Markov Chains with Applications

High-dimensional Markov chains are popular tools for many real world applications such as queueing networks, inventory systems and categorical data sequences. Given an irreducible Markov chain, it is well-known that the Perron-Frobenius theorem guarantees the existence of the system stationary distribution which is important in the system performance analysis. In many applications, one has to employ a multivariate Markov chain in a mathematical model. In a conventional model of multivariate Markov chains having s chains, the total number of states will grow exponentially with respect to s. Some approximate first-order models have been proposed to handle this high dimensionality problem. However, they cannot capture the long-range dependence of the data sequences. Here we will propose high-order multivariate Markov chain models. We will also propose simplified models in case the models overfit the practical data. The simplified models can be extended to capture the negative correlations among the data sequences. We will then extend the Perron-Frobenius theory to both the high-order models and the simplified models. Efficient algorithms will be developed for solving the model parameters. The developed multivariate Markov chain models will then be applied to some practical problems including credit risk analysis.

Matrix Approximation Theory For Probabilistic Boolean Networks

Developing mathematical theory and building computational models for genetic regula- tory networks are important research issues in computational systems biology. Boolean Networks (BNs) and its extension Probabilistic Boolean Networks (PBNs) are effective mathematical models for studying genetic regulatory interactions. A PBN is essentially a collection of BNs driven by a Markov chain process and therefore can be studied by using Markov chain theory. On the one hand, the steady-state probability distribution of a PBN gives useful information about the desirable states (attractor cycles) of the underlying genetic network where the attractor cycles have important biological interpretations. On the other hand, it is well-known that the control/intervention of a genetic regulatory network is useful for avoiding undesirable states associated with diseases like cancer. The optimal control problem can be formulated mathematically by using the principle of stochastic dynamic programming. The size of the transition probability matrix of a PBN is 2^n-by-2^n where n is the number of genes in the genetic network, and the problem size grows exponentially with respect to n. We develop matrix approximation theory for approximating both the steady-state probability distribution of a PBN and also the optimal solution of the captured control problem. The matrix approximation methods can reduce the computational cost significantly and still retain the important information of the network. Theoretical results for the error analysis of the approximation method will be established. Numerical experiments based on real genetic networks will also be performed to demonstrate both the efficiency and effectiveness of the proposed methods. Extension to more general and complex PBNs such as PBNs with random gene perturbations and context-sensitive PBNs are also be studied.

Consultant Service

  • Marketing Strategy and Consumer Behavior, a consultant work with PCCW (2002).
  • Implement a New-Gas-Phase Chemistry Solver and Flexible Mechanism Interface for the PATH Modeling System, a consultant work with the Environmental Protection Department, HKSAR Government (2003).
  • Auction and Trading Algorithms, a consultant work with (2003).
  • Evaluation Study of the Portering and Lift Services, a consultant work with Hospital Authority (2006).
  • Trend Analysis for Power Cable Loading and Capacity Planning, a consultant work with China Light and Power Company Limited (2007).