在线咨询
中国工业与应用数学学会会刊
主管：中华人民共和国教育部
主办：西安交通大学
ISSN 1005-3085  CN 61-1269/O1
工程数学学报

工程数学学报 ›› 2023, Vol. 40 ›› Issue (3): 355-365.doi: 10.3969/j.issn.1005-3085.2023.03.002

• • 上一篇    下一篇

用于求解两个队伍休假排队网络稳态分布的多重网格算法

杨淑伶,  韩晓卓   

  1. 广东工业大学数学与统计学院，广州 510020
  • 收稿日期:2021-01-20 接受日期:2022-12-25 出版日期:2023-06-15 发布日期:2023-08-15
  • 基金资助:
    国家自然科学基金 (31670391).

Multigrid Algorithm for Solving the Steady State Distribution of Vacation Queueing Networks with Two Queues

YANG Shuling,  HAN Xiaozhuo   

  1. School of Mathematics and Statistics, Guangdong University of Technology, Guangzhou 510020
  • Received:2021-01-20 Accepted:2022-12-25 Online:2023-06-15 Published:2023-08-15
  • Supported by:
    The National Natural Science Foundation of China (31670391).

PDF (PC)

45

摘要：

休假策略刻画了工程系统和管理系统中服务进程的中断。休假排队网络可用来模拟这些复杂系统，在实际中具有广泛的应用；由于休假排队网络的稳态分布显式解很难得到，对其数值求解方法的研究有非常重要的意义。提出了一个用于求解包含两个M/M/2队伍的休假排队网络稳态分布的代数多重网格法。根据稳态方程的系数矩阵所特有的拟三对角结构，基于循环约化算法构造了多重网格法的延伸算子和限制算子。这些根据线性系统系数矩阵构造出的算子可以在更粗的网格上保持原有系数矩阵的特征，从而提高了计算的收敛速度。最后通过数值实例验证了所提算法的优越性。

关键词: 排队网络, 休假, 拟生灭过程, 多重网格算法, 循环约化

Abstract:

Vacation policy describes the interruption of service process in engineering systems and management systems. Vacation queueing networks can be used to simulate these complex systems and have a wide range of applications in practice. Since the analytic formulas of the steady state distribution of vacation queueing networks are difficult to obtain, it is of great importance to study the numerical solution method. An algebraic multigrid algorithm is proposed for solving the steady state distribution of vacation queueing networks including two M/M/2 queues. With the special quasi-tridiagonal structure in the steady state equation, the prolongation and restriction operators of the multigrid algorithm are constructed by the cyclic reduction strategy. They are dependent on the coefficient matrix of linear system and therefore can maintain its characteristics on the coarser grid level, thus improving the convergence speed of the numerical algorithm. Finally, numerical examples show the superiority of the proposed algorithm.

Key words: queueing networks, vacation, quasi-birth-death process, multigrid algorithm, cyclic reduction

中图分类号: