Sensor scheduling in continuous time

Let N be the number of available sensor sources. Noisy observations of an underlying state process are available for these N sources. We consider the continuous time sensor scheduling problem in which N₁ of these N sources are to be chosen to collect data at each time point. This sensor scheduling problem (with switching costs and switching constraints) is formulated as a constrained optimal control problem. In this framework, the controls represent the sensors that are chosen at a particular time. Thus, the control variables are constrained to take values in a discrete set, and switchings between sensors can occur in continuous time. By incorporating recent results on discrete valued optimal control, we show that this problem can be transformed into an equivalent continuous optimal control problem. In this way, we obtain the sensor scheduling policy as well as the associated switching times.     

Multi-armed bandits with switching penalties

The multi-armed bandit problem with switching penalties (switching cost and switching delays) is investigated. It is shown that under an optimal policy, decisions about the processor allocation need to be made only at stopping times that achieve an appropriate index, the well-known “Gittins index” or a “switching index” that is defined for switching cost and switching delays. An algorithm for the computation of the “switching index” is presented. Furthermore, sufficient conditions for optimality of allocation strategies, based on limited look-ahead techniques, are established. These conditions together with the above-mentioned feature of optimal scheduling policies simplify the search for an optimal allocation policy. For a special class of multi-armed bandits (scheduling of parallel queues with switching penalties and no arrivals), it is shown that the aforementioned property of optimal policies is sufficient to determine an optimal allocation strategy. In general, the determination of optimal allocation policies remains a difficult and challenging task     

Single versus hybrid time horizons for open access scheduling

Difficulty in scheduling short-notice appointments due to schedules booked with routine check-ups are prevalent in outpatient clinics, especially in primary care clinics, which lead to more patient no-shows, lower patient satisfaction, and higher healthcare costs. Open access scheduling was introduced to overcome these problems by reserving enough appointment slots for short-notice scheduling. The appointments scheduled in the slots reserved for short-notice are called open appointments. Typically, the current open access scheduling policy has a single time horizon for open appointments. In this paper, we propose a hybrid open access policy adopting two time horizons for open appointments, and we investigate when more than one time horizon for open appointments is justified. Our analytical results show that the optimized hybrid open access policy is never worse than the optimized current single time horizon open access policy in terms of the expectation and the variance of the number of patients consulted. In nearly 75% of the representative scenarios motivated by primary care clinics, the hybrid open access policy slightly improves the performance of open access scheduling. Moreover, for a clinic with strong positive correlation between demands for fixed and open appointments, the proposed hybrid open access policy can considerably reduce the variance of the number of patients consulted.     

模糊动态抢占调度算法

针对不确定任务特征，提出应用模糊理论进行动态抢占调度，用语言模糊集来描述任务的不确定特征和不同的优先级等级，利用最大隶属度原理确定任务的优先级等级，采用优先调度高优先级等级任务的调度策略提高重要任务的调度成功率，实现具有不确定任务特征的抢占调度，与传统的EDF和LSF算法相比较，仿真表明，所提算法能够提高重要任务的调度成功率，并降低重要任务的截止期错失率；同时，任务间的平均切换次数大大小于LSF的平均切换次数，而与EDF保持相当，该方法可应用于计算机控制系统的控制任务调度，并借鉴于其它具有不确定任务特征或具有有限优先级等级的实时调度问题研究中。     

Fuzzy scheduling strategy for generalized switched server systems and its robustness over system heterogeneity

Generalized switched server system, a discretely controlled continuous‐time system, in which N tanks are used to represent N parallel entities, respectively, can be employed to address a class of load‐balancing problems. A tank‐pair model is a system that consists of two tanks and a single input single output controller, which regulates the inflows of the two tanks to acquire the two uniform levels under the specified inflow constraints. According to a quantized observation of the N tank levels, some discrete events are generated, and based on certain event feedback strategy, switching the location of the tank‐pair can control all the N tanks in a time‐sharing manner to acquire the N levels uniformity. Different from some existing scheduling strategies, this study proposes a fuzzy scheduling strategy (FSS) for such generalized switched server systems. Special measures are taken to reduce the N‐inputs two‐outputs fuzzy inference to a two‐inputs one‐output one, which greatly facilitates fuzzy scheduler design. Simulation results show that the proposed FSS strategy outperforms over the three existing scheduling strategies as a whole, and they also show that the proposed FSS strategy demonstrates high robustness over system heterogeneity. © 2009 Wiley Periodicals, Inc.     

高性能交换与调度仿真平台的设计与实现

仿真实验已成为交换结构和调度策略性能评价的重要手段,而目前存在的交换结构与调度策略的仿真软件在可继承性与可扩展性方面还存在缺陷.基于Crossbar交换结构,建立数学模型,引入系统级设计方法,采用面向对象技术,设计并实现了用于研究交换结构和调度策略的仿真平台——SPES(switching performance evaluation system).该平台集成了输入排队、输出排队、联合输入输出排队、联合输入交叉点排队等多种交换结构以及相应调度策略.设计上实现了业务流、交换结构和调度策略三者之间的分离,具有良好的可继承、可扩展特性.用户通过与仿真平台之间的简单交互,完成模块的添加与仿真环境参数的配置,在支持变长业务、区分服务质量模型和多交换平面仿真方面具有良好的特性.通过简单扩展。该平台还可以实现网络级性能仿真.最后给出了基于该平台,在CICQ(combined input and crosspoint queuing)交换结构下,对所提出的支持DiffServ模型的分布式调度策略DS(DiffServ supporting algorithm)在不同业务流模型下的性能测试结果,并与输入、输出排队交换结构进行了比较,展示了DS良好的性能,验证了仿真平台的合理性.     

一种新型实时调度算法研究

在许多片上特定应用系统中，任务多且切换频繁，任务切换开销大，有时甚至严重影响系统的可调度性．研究了动态可抢占门限调度算法，它通过初始门限值、动态门限值的计算和优化线程分配，实现了在处理器高利用率下，有效降低任务切换开销的目的，并相应地减少了对内存的需求．动态可抢占门限调度算法是将静态抢占门限算法与动态调度算法有机地结合在一起。完成了由静态到动态无缝转换．     

Optimal scheduling of two competing queues with blocking

Consideration is given to the problem of optimal scheduling for two queues for service at a single station, where the queues have finite capacities and the service rate is class-dependent. The cost structure is linear in the number of holding customers in the queues, combined with blocking costs incurred whenever arrivals encounter a full queue. The authors derive the optimal policy minimizing this criterion when the blocking cost is larger than the holding cost for each queue. Then they show that the optimal policy is of the switching type. Numerical results are included to support the analytical findings     

Randomized control of T-policy for an M/G/1 system

We study an M/G/1 queueing system with a server that can be switched on and off. The server can take a vacation time T after the system becomes empty. In this paper, we investigate a randomized policy to control a server with which, when the system is empty, the server can be switched off with probability p and take a vacation or left on with probability (1 − p) and continue to serve the arriving customers. For this system, we consider the operating cost and the holding cost where the operating cost consists of the system running and switching costs (start up and shut down costs). We describe the structure and characteristics of this policy and solve a constrained problem to minimize the average operating cost per unit time under the constraint for the holding cost per unit time.     

Web集群服务器的分离式调度策略

主要用排队论方法讨论了Web集群整体性能与请求调度策略之间的关系，所获得的结论是：在Web集群非过载情况下，一部分后端服务器仅处理静态请求而另一部分后端服务器仅处理动态请求的分离式调度策略要好于所有后端服务器既处理静态请求又处理动态请求的混合式调度策略。用SPECweb99测试工具所做的实际测试更进一步证明：当负载参数为120个连接时，采用分离式调度策略的Web集群服务器可完成63个连接，而采用混合式调度策略的Web集群服务器仅能完成36个连接，性能提高了22.5%。