基于YARN的分布式资源动态调度与协同分配系统

Storm on YARN是目前主流的分布式资源调度框架,但其存在需要人工干预和无法根据资源可用性实时调整系统资源的不足。根据流数据处理的实时延迟计算系统负载情况,在Storm平台上基于YARN设计分布式资源调度和协同分配系统。建立包含系统层和任务层的双层调度模型,系统层通过对流数据处理负载的实时监测进行资源分配预测,任务层利用ZooKeeper和YARN对集群资源的高效管理能力进行动态资源管理。实验结果表明,该系统可以实时调整集群资源分布,有效减小系统延迟。     

基于交替方向乘子法的电力系统完全分布式动态经济调度方法

本文基于交替方向乘子法(alternating direction multiplier method,ADMM)提出了一种完全分布式的跨区域电力系统动态经济调度方法.其中的经济调度模型以整个系统的运行成本最小为目标,并满足各种系统运行约束.为了实现模型的分布式求解,本文利用交替方向乘子法将各区域之间的联系解耦,将整个系统的大型优化问题分解为各个区域内部的子优化问题,通过迭代求解每个区域的子问题即可得到整个系统的最优解.进一步地,本文算法取消了负责乘子更新的数据中心,实现了完全分布式的调度策略.同时,为了兼顾电力系统中时间断面之间的紧密联系,本文的经济调度模型采用了多时段优化方法.最后,本文对基于IEEE标准测试系统的3区域互联系统算例进行了分析,验证了本文的调度策略的有效性.     

分布式实时系统任务与消息综合调度算法研究

分布式实时系统作为一种典型的实时系统应用受到了关注,目前提出了许多分布式实时系统的调度策略。但是,绝大多数策略往往忽略了全局任务调度时的消息调度。本文提出一种综合任务调度和消息调度的算法,提供了一种实时系统调度的新思路。     

分布式WLAN全双工链路加权调度算法

针对分布式无线局域网络带内全双工接入过程的链路调度公平性问题,提出一种基于节点调度权重的全双工链路调度算法(W-FD).通过节点调度权重实现链路负载均衡,从而提升全双工链路的吞吐量,减小节点接入时延.算法基于分布式网络结构,节点按自组织方式获取网络拓扑及邻居节点状态信息,依据节点间数据量、互扰关系和链路调度间隔等参数计...     

分布式测量系统服务窗口动态调度方法研究

在网络制造环境下, 动态时间性能是测量系统的重要指标. 针对基于 CORBA (Common object request broker architecture) 和尺寸测量接口标准 (Dimensional measurement interface standard, DMIS) 的分布式测量系统 (Distributed measurement system, DMS), 根据多用户非抢占优先排队网络静态性能模型, 提出基于无穷小摄动分析的样本轨道划分方法, 建立测量系统服务窗口的动态调度算法, 实现测量系统的时间性能调优. 通过在一个制造工厂中进行的应用实验, 证明了此方法的有效性.     

无线传感器网络分布式调度方法研究

无线传感器网络(Wireless sensor network, WSN)是一个资源受限的网络系统.已提出了多种调度方法来提高网络性能. 本文归纳了WSN分布式调度方法的设计原则和分类方法,并按调度对象对调度方法进行了分类讨论. 详细论述了一些典型调度方法的内在机理,分析了每一类调度方法的特点. 对这些调度方法的设计目标和性能特点进行了对比.最后总结了WSN分布式调度方法的研究现状, 提出了该领域今后发展需要关注的重要因素.     

分布式实时系统中的预测调度算法

对于分布式实时系统中的周期性任务,人们提出了一系列静态分配调度算法,有效地解决了各种特定条件下的任务分配和调度问题.这些算法的主要特点是,它们均要求被调度任务的特征参数为已知条件.然而在很多实时系统中,周期性任务的运行时间或任务数量常常是一些具有一定规律的随机过程,因而上述静态算法的效能将受到限制.在分析了特定应用背景中的处理流程之后,抽象得到两类随机任务模型,针对这两类模型介绍了在分布式实时系统中已经得到应用的静态分配调度算法SAA(static allocation algorithms),进而提出了多任务分配调度的预测算法PAA(predicting allocation algorithm).它根据周期性任务执行时间或子任务数量的统计特性,实现任务参量的合理预测和多任务的动态调度,以提高系统的实时性能.仿真结果表明,对于两类任务模型,PAA算法与SAA算法相比,在任务完成时间、负载均衡度、系统响应时间及任务夭折率等多方面均有显著改善.     

分布式流媒体资源调度技术研究

随着信息技术和网络技术的飞速发展,以多媒体为核心的现代网络流媒体技术得到非常广泛的应用。为了应对流媒体的应用中出现的大量消耗CPU、带宽等资源的问题,单机服务器已经不能承受高并发用户的访问,因此分布式的解决方案应运而生。本文针对分布式流媒体调度技术进行研究,在分布式的流媒体服务子节点的部署环境中,每个子节点均作为流媒体的服务器。为保证流媒体服务的质量,设计了基于蚁群的资源调度算法来获取传输的最佳路径。     

分布式测量系统服务窗口动态调度算法研究

在网络制造环境下,分布式测量系统(Distributed Measurement System,DMS)的负载是动态变化的,需要根据负载情况对测量系统上的资源进行动态调度.针对基于CORBA和DMIS的分布式测量系统,根据多用户非抢占优先排队网络静态性能模型,提出基于无穷小摄动分析(Infinitesimal Perturbation Analysis,IPA)的分布式测量系统服务窗口动态调度算法.算法以DMS系统负载的在线变化为输入,动态调整排队网络系统服务台的窗口数量,从而实现测量用户对动态时间性能的要求.最后在一个制造工厂中进行的应用实验,证明了算法的有效性.     

基于SINR的动态无线网络分布式链路调度

无线信号之间的干扰阻碍了信号的并发传输,降低了无线网络的吞吐量.链路调度是提高无线网络吞吐量、减少信号传输延迟的一种有效方法.因为SINR (signal to interference plus noise ratio)模型准确地描述了无线信号传播的固有特性,能够真实反映无线信号之间的干扰,提出一种在动态无线网络中基于SINR模型的常数近似因子的在线分布式链路调度算法(OLD＿LS).在线的意思是指,在算法执行的过程中任意节点可以随时加入网络,也可以随时离开网络.节点任意加入网络或者从网络中离开体现了无线网络的动态变化的特性. OLD＿LS算法把网络区域划分为多个正六边形,局部化SINR模型的全局干扰.设计动态网络下的领导者选举算法(LE),只要网络节点的动态变化速率小于1/ε, LE就可以在O(log n+log R)ε≤5(1-2^1-α/2)/6,α表示路径损耗指数, n是网络节点的规模, R是最长链路的长度.根据文献调研,所提算法是第1个用于动态无线网络的在线分布式链路调度算法.     

基于消息报告机制的多Agent调度系统研究

针对生产车间调度系统中因资源庞大以及动态变化而引起的监管困难问题,构建了一种 基于消息报告机制的多代理调度系统分层体系结构。根据Agent在调度系统中的作用和角色的不 同,将Agent划分为管理Agent、任务Agent和资源Agent,并通过一个具有消息报告机制的管理Agent 来有效管理和监控系统的运行。实例分析表明,消息报告机制不仅能保证系统的有效运行,而且能提 高系统的工作效率。     

基于Q-learning的高速铁路列车动态调度方法

高速铁路作为国家综合交通运输体系的骨干核心,近十年来取得了飞速蓬勃的发展.其飞速发展的同时也引发了路网复杂化、分布区域广等现象,这些现象对高铁动态调度提出了更高的要求.突发事件的不确定性会对列车造成时间延误影响,甚者时间延误会沿路网传播,造成大面积列车到发晚点.而目前对于此问题的人工调度方式,前瞻性及针对性较差,难以对受影响列车进行迅速调整.针对上述问题,本文建立了以各列车在各车站延误时间总和最小为目标函数的高速铁路列车动态调度模型,在此基础上设计了用于与智能体交互的仿真环境,采用了强化学习中的Q-learning算法对模型进行求解.最后通过仿真实例验证了仿真环境的合理性以及Q-learning算法用于高铁动态调度的有效性,为高铁调度员做出优化决策提供了良好的依据.     

结合通信重排和消息合并的通信调度方法研究

网络通信对于高性能计算机应用至关重要。当前,随着数值模拟应用的复杂化和并行规模的不断提升,应用软件对于缓解拥塞和减少通信协议开销的需求愈发迫切。传统的消息合并方法只以减少通信协议开销和延迟为目标,所以针对小消息进行合并。与之不同的是,从调度算法的角度提出了一种通过消息重排以减缓大消息网络拥塞,并基于优先级合并消息来提高网络有效利用率的算法。实验表明,该算法针对真实应用的通信性能最大可以提升41%,平均对每个应用提升了10%。     

An emergent modelling method for dynamic scheduling

In this paper a modelling method for simulating dynamic scheduling is presented. The basic idea behind the method is to use local attraction fields to direct transporters carrying jobs to particular machines. Emergence is used here to describe the fact that the decision on which job is directed to which machine, i.e. the schedule, is the result of continuously simulated local force fields without a foreseeable global result. The emphasis is thus on the dynamic schedule rather than an optimal schedule. As will be demonstrated, the schedule is capable of continuous adaptation in a turbulent environment.     

到达时间依赖于资源分配的单机排序问题*

研究了具有线性退化及学习效应作用下的单机排序问题,对于工件的到达时间是其资源消耗量的正的严格单调递减函数时,考虑了总资源消耗量限定情形下最大完工时间极小化问题,给出了相应的最优算法;也考虑了满足工件最大完工时间限制的条件下极小化资源消耗的总量问题,提出最优资源分配方案。     

CAN总线中非周期信息的随机动态优先级调度

针对CAN总线中非周期信息传输的“死锁”现象,利用动态优先级提升机制中消息在发送队列的位置随等待时间动态改变的思想,对非周期性信息的传输采用基于随机数的动态优先级调度策略,以解决CAN总线中非周期信息传输的“死锁”问题。     

多阶段人机协同求解动态柔性作业车间调度问题

针对柔性作业车间生产环境中机器故障的动态调度问题, 以最小最大完工时间和最小偏差为目标, 结合车间调度人员的经验建立多阶段人机协同动态调度策略. 在不同阶段该策略的调度人员可参与优化过程, 提高方案的可行性和稳定性. 设计外部精英库中最优解的更新方法, 依据海明距离保留具有相同目标值的多种调度方案. 最后通过实例仿真验证了该模型和算法的有效性、可行性和稳定性, 更便于有效地指导生产实践.

     

数据驱动下的半导体生产线动态调度方法

本文研究了一种数据驱动下的半导体生产线调度框架,该框架基于调度优化数据样本,应用机器学习算法,获得动态调度模型,通过该模型,对于半导体生产线,能够根据其当前的生产状态,实时地定出近似最优的调度策略.在此基础上,利用特征选择和分类算法,提出一种生成动态调度模型的方法,并且具体实现出一种混合式特征选择和分类算法的调度模型:先采用过滤式特征选择方法对生产属性进行初步筛选,然后再采用封装式特征选择和分类方法生成模型以提高模型生成的效率.最后,在某实际半导体生产线上,对在所提出的框架上采用6种不同算法实现的动态调度模型进行测试,并对算法性能数据和生产线性能据进行对比和分析.结果表明,数据驱动下的动态调度方法优于单一的调度规则,同时也能满足生产线调度实时性要求.在数据样本较多的情况下,建议采用本文所提出的方法.     

Applications of machine learning approach on multi-queue message scheduling

Due to limited resource contentions and deadline constraints, messages on the controller area network (CAN) are competing for service from the common resources. This problem can be resolved by assigning priorities to different message classes to satisfy time-critical applications. Actually, because of the fluctuation of network traffic or an inefficient use of resources, these static or dynamic priority policies may not guarantee flexibility for different kinds of messages in real-time scheduling. Consequently, the message transmission which cannot comply with the timing requirements or deadlines may deteriorate system performance significantly. In this paper, we have proposed a controller-plant model, where the plant is analogous to a message queue pool (MQP) and the message scheduling controller (MSC) is responsible to dispatch resources for queued messages according to the feedback information from the MQP. The message scheduling controller, which is realized by the radial basis function (RBF) network, is designed with machine learning algorithm to compensate the variations in plant dynamics. The MSC with the novel hybrid learning schemes can ensure a low and stable message waiting time variance (or a uniform distribution of waiting time) and lower transmission failures. A significant emphasis of the MSC is the variable structure of the RBF model to accommodate to complex scheduling situations. Simulation experiments have shown that several variants of the MSC significantly improve overall system performance over the static scheduling strategies and the dynamic earliest-deadline first (EDF) algorithms under a wide range of workload characteristics and execution environments.