Developing Efficient and Effective Algorithms for Complete Analysis of a Class of Vacation Queueing Models

排队延迟是所有服务系统中最难以忍受，但又不可避免的一个方面。假期排队是现实生活中经常出现的一类主要的排队。它们适用于服务器经常中断的系统（包括优先级系统），更具体地说，用于近似轮询系统——通过访问共享介质提供服务的队列。示例包括：无线局域网、工作站制造部件的处理、交通十字路口控制系统、基于优先级的病人调度、医疗程序（如手术、超声心动图等）以及最近的认知无线电网络。为了提供有效和高效的服务，使成本最小化，同时确保服务质量处于系统用户可接受的水平，管理人员需要数学模型来分析这些系统并估计延迟，以便他们能够减少延迟。假期模型的现有数学模型要么太复杂而无法实现，要么做出不切实际的简化假设，使它们不能真正反映所表示的实际系统。我们的主要目标是在矩阵分析方法的基础上，开发计算上可行、高效和有效的工具来分析这类非常重要的排队模型。我们将构建真正更能代表常见度假系统的模型，并探索数学结构，使解决方案在创建可实现算法方面实际易于处理。这项研究的结果包括为准确研究通信系统中的几类协议提供工具。这将有助于设计更有效率和成本效益更高的通信系统，保证用户所期望的服务质量。研究结果还可以应用于医疗保健、运输和制造业领域。

Queueing delays are one of the most intolerable, yet inevitable, aspects of all service systems. Vacation queues are a major class of queues that occur very frequently in real life. They are applied to systems in which the server is often interrupted (including priority systems), and more specifically used to approximate polling systems - queues in which service is provided through access to a shared medium. Examples include: wireless local area network, processing of manufacturing pieces at a workstation, traffic intersection control systems, and scheduling of patients, based on priorities, for healthcare procedures such as surgery, echocardiogram, etc, and recently cognitive radio networks. In order to provide effective and efficient services that minimize costs while ensuring the quality of service is at an acceptable level to the system users, managers need mathematical models for analyzing these systems and estimating delays so they can work at reducing them. The existing mathematical models for vacation models are either too complex to implement or make unrealistic simplifying assumptions that render them not truly reflective of the actual systems being represented. Our main goal in this proposal is to develop computationally feasible, efficient and effective tools, based on the matrix-analytic methods, for analyzing this very important class of queueing models. We will construct the models that are truly more representative of commonly occurring vacation systems and explore mathematical structures that make the solutions realistically tractable in terms of creating implementable algorithms. The results of this research include providing tools for accurately studying several classes of protocols in communication systems. This will assist in designing more efficient and cost effective communication systems that guarantee users the quality of service they expect. The results can also be applied in the areas of healthcare, transportation and manufacturing.