We consider a discrete-time system comprising a first-come-first-served queue, a non-preemptive server, and a stationary non-work-conserving scheduler. New tasks arrive at the queue according to a Bernoulli process. At each instant, the server is either busy working on a task or is available, in which case the scheduler either assigns a new task to the server or allows it to remain available (to rest). In addition to the aforementioned availability state, we assume that the server has an integer-valued activity state. The activity state is non-decreasing during work periods, and is non-increasing otherwise. In a typical application of our framework, the server performance (understood as task completion probability) worsens as the activity state increases. In this article, we expand on stabilizability results recently obtained for the same framework to establish methods to design scheduling policies that not only stabilize the queue but also reduce the utilization rate, which is understood as the infinite-horizon time-averaged expected portion of time the server is working. This article has a main theorem leading to two main results: (i) Given an arrival rate, we describe a tractable method, using a finite-dimensional linear program (LP), to compute the infimum of all utilization rates achievable by stabilizing scheduling policies. (ii) We propose a tractable method, also based on finite-dimensional LPs, to obtain stabilizing scheduling policies that are arbitrarily close to the aforementioned infimum. We also establish structural and distributional convergence properties, which are used throughout the article, and are significant in their own right.

0
下载
关闭预览

相关内容

服务器,也称伺服器,是提供计算服务的设备。由于服务器需要响应服务请求,并进行处理,因此一般来说服务器应具备承担服务并且保障服务的能力。
服务器的构成包括处理器、硬盘、内存、系统总线等,和通用的计算机架构类似,但是由于需要提供高可靠的服务,因此在处理能力、稳定性、可靠性、安全性、可扩展性、可管理性等方面要求较高。
Top