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.