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.