基于MAS协作机制的动态计算资源调度模型

针对网格环境的自治性、动态性、分布性和异构性等特征.提出基于多智能体系统(Mutil Agent System,MAS)博弈协作的资源动态分配和任务调度模型,建立了能够反映供求关系的网格资源调度模型和任务求解算法,证明了资源分配博弈中Nash均衡点的存在性、唯一性和Nash均衡解,该方法能够利用消费者agent的学习和协商能力,考虑和引入消费者的心理行为,使得消费者的资源申请和任务调度具有较高的合理性和有效性.实验结果表明,资源调度算法不但可以有效减少不必要的延迟,而且在响应时间的平滑性、吞吐率及资源利用率方面比传统算法要好,从而使得整个资源的供需合理、负载均衡.     

基于移动Agent技术的网格负载均衡调度方法

为了实现网格计算资源的动态自适应性管理和负载均衡调度,将移动Agent技术引入网格资源管理,并提出了一种基于Agent的网格资源调度模型.在该模型基础上,采用遗传克隆算法解决网格计算中的任务调度问题.仿真实验表明该算法不仅充分发挥了Agent的智能性、自主性,还具有良好的扩展性,提高了网格资源调度的效率.     

分层混合局部搜索策略异构多核系统调度

针对遗传算法解决异构多核系统的任务调度问题容易产生早熟现象及其局部寻优能力较差的缺点,将局部搜索算法与遗传算法相结合,创新性地提出一种求解异构多核系统的任务调度问题的分层混合局部搜索遗传算法。该算法提出一种新的分层优化策略以产生初始种群,在变异操作中,对部分个体设计3-opt优化变异,对种群中的优秀个体用改进的Lin-Kernighan算法进行优化。仿真实验结果表明,分层混合局部搜索遗传算法求解异构多核系统的任务调度问题时可以高效获得高质量的解。     

城市道路交通信号实时控制的数学模型与算法研究

研究了交通信号的实时配时控制问题.建立了在已有交通设施条件下,控制信号具有线性约束的非线性实时配时系统优化模型,设计了与模型相适应的实时CLY系列算法.重点讨论了点控制问题,建立了相应的数学优化模型,设计了CLY-Point1算法求解.还对线控制问题和面控制问题,建立了多层优化控制模型,并设计CLY-Point2、CLY-Line和CLY-Area算法进行求解.数值模拟结果表明,CLY系列算法具有很强的实时性,车辆平均等待时间比固定配时减少了约20%.     

基于物流AGV的“货到人”订单拣选系统任务调度研究

基于物流AGV的“货到人”订单拣选模式由于其高效率和灵活性,逐渐成为电商物流配送中心订单拣选系统发展趋势。本文通过对基于物流AGV的电商物流配送中心订单拣选作业流程分析,提出多拣选台同步拣选和多拣选台异步拣选两种作业模式。然后对基于物流AGV的订单拣选任务调度问题进行描述,以物流AGV完成所有任务的时间最短为目标,分别建立同步和异步两种拣选模式下物流AGV任务调度模型;针对物流AGV任务调度问题特性,对共同进化遗传算法粗粒度模型进行改进用于模型求解。最后,通过改进前后算法的对比,验证了改进共同进化遗传算法在求解物流AGV任务调度问题中的有效性;通过在求解速度和优化结果上对多拣选台同步拣选和异步拣选两种作业模式进行比较,得出同步拣选优于异步拣选的结果。     

基于机器学习的智能TWAP和VWAP算法的研究及应用

TWAP与VWAP算法为两类较常见的经典交易算法.传统的VWAP算法在TWAP算法的基础上,大多使用预测日内成交量分布的方法指导算法下单.传统成交量分布的预测效果严重依赖于市场交易惯性,但交易量分布受到日内诸多突发因素的影响,导致算法对市场突发状况的应对能力较弱.本文对传统TWAP与VWAP算法进行改进,利用滚动的1分钟粒度高频实时资金博弈数据,基于Logistic分类器训练量价模型,以该预测结果为入参构建最优化期望执行均价模型,求出当下各个价格档位对应委托数量的最优解.通过相对高频的分钟级价格预测机制,保证算法实时跟踪市场行情走势并寻求相对优势的交易机会.该算法经测试可以稳定地跑赢市场均价,具备推广应用的可行性.     

拟一致无迹卡尔曼滤波算法北大核心CSCD

针对一般的非线性系统,研究了无迹卡尔曼滤波(UKF)算法的一致性问题.通过对传统UKF算法的修正,提出了拟一致UKF(QCUKF)算法,同时给出了修正参数的选取准则,并且在理论上证明了所提算法的拟一致性.当算法具有拟一致性时,估计精度可被实时评估.最后,通过仿真实例说明了所提算法的可行性以及拟一致性.     

拟一致无迹卡尔曼滤波算法

针对一般的非线性系统,研究了无迹卡尔曼滤波(UKF)算法的一致性问题.通过对传统UKF算法的修正,提出了拟一致UKF(QCUKF)算法,同时给出了修正参数的选取准则,并且在理论上证明了所提算法的拟一致性.当算法具有拟一致性时,估计精度可被实时评估.最后,通过仿真实例说明了所提算法的可行性以及拟一致性.     

一种基于序列图像的单镜头测距方法

针对于监视区域目标参数的测量问题,在考虑到被动式实时监控定位与便携性要求的前提下,提出了基于标定点的序列图像单镜头测距算法,并实现了核心测距算法.     

一种基于在线训练的交通信息实时预测快速算法

对于实时交通信息预测,预测精度与预测时间效率始终是一对难以解决的矛盾.重点研究如何提高预测时间效率问题.以精确在线支持向量回归算法(AOSVR)为基础,提出了基于云模型的sigmoid核函数简化计算方法,建立了改进的AOSVR交通信息实时预测模型.该模型应用于实际的交通流实时预测,预测结果表明,由于简化了计算,以损失较小回归精度的代价,显著提高AOSVR模型预测效率.     

实时系统中单处理器调度算法的优化设计研究

研究实时系统的建模与调度问题是运筹与控制领域研究的热点问题, 对实时系统中的单处理器的调度算法进行了分析与研究, 特别是对其中的单调速率算法和最早时间限优先算法进行了深入的研究, 指出单调速率算法是一种典型的静态调度算法, 并且证明了单调速率算法是单处理器最优的静态优先级调度算法, 同时还指出最早时间限优先算法是一种典型的动态优先级调度算法,证明了最早时间限优先算法是单处理器的最优的动态优先级调度算法. 最后, 为了更好地进行实时系统的建模与调度, 引入了一种新的对任务执行行为进行抽象的方法--T-LET平面方法, 利用这种方法建立了单处理器流调度模型和BLREF调度算法, 并指出这种模型和算法都具有很强的几何背景.     

环形路网上带有服务时长的在线TSP问题

为了提高快递揽件的时效性,需要对快递车辆进行有效调度。针对环形路网上服务时长以及需求无法预知的揽件问题,本文提出了以服务总时间尽可能短为目标的环形路网上带有服务时长的在线旅行商问题。用在线算法分析了此问题竞争比的下界,设计了两个在线算法并分析了各自的竞争比,结果表明服务时长可以改善在线车的性能。最后通过简单算例对两个算法进行说明,本文研究结论可以为环形路网上的快递车辆实时调度提供指导。     

A 2.79 COMPETITIVE ON-LINE ALGORITHM FOR TWO PROCESSOR REAL-TIME SYSTEMS WITH UNIFORM VALUE DENSITY

We consider the problem of competitive on-liae scheduling in two processor real-timesystems. In our model all tasks have common value density. Each task has a release time. an exe-cution time and a deadline. The scheduler is given no information about a task until it is released.And the value will be achieved if and only if the task is completed by its deadlirte. Moreover. wesuppose that migratbn is not allowed. The goal of the scheduler is to obtain as much value as pos-sible. In this paper we show that the competitive multipber of Safe-Risky-fixed Algorithm irt [4]is really 3 and presents a modified algorithm (Safe-Risky-unfixed Algorithm) that achieves a com-petitive mukiplier of 2. 79.     

带机会约束的警务调度模型及其解法

研究在紧急情况发生时,城市中不同交巡警服务平台的警务人员封锁指定区域的最优调度问题.把交巡警服务平台到达指定要道的时间视为满足正态分布的随机变量,从而建立了满足机会约束的警务调度模型并将该模型等价地转化为极小极大模型.给出了模型的求解算法及其计算复杂度.最后,通过一个数值例子来说明算法的有效性.     

Optimizing winter road maintenance operations under real-time information

This paper introduces a real-time optimization model that can be used by maintenance managers to develop and evaluate alternative resources allocation plans for winter road maintenance operations. The model takes into account a wide range of road and weather condition factors such as road network topology, road class, weather forecasts, and contractual service levels, and produces a vehicle dispatch schedule that is optimal with respect to operating costs and quality of service. The model is then used in an analysis on a realistic case to illustrate the potential impact of improved information on winter maintenance operations.     

突发事件情景下串联式需求系统应急物资协同调度研究

针对突发事件情景下串联式需求系统遭受破坏问题,分析了突发事件情景下串联式需求系统应急物资协同调度的特征。在对系统提供应急物资进行修复的基础上,以串联式需求系统修复的时间最短及成本最小为目标,分别构建了纵向配送的应急物资调度模型和纵向配送与横向转运相结合的应急物资协同调度模型,并设计一种遗传算法对两种模型进行求解。最后通过算例分析,求解得到两种模式下串联式需求系统应急物资调度的最优配送方案,比较解的结果,得出纵向配送与横向转运相结合的应急物资协同调度模式优于一般的应急物资纵向配送模式的结论,验证了该应急物资协同调度模式的有效性和可行性。     

Approximation algorithms for a vehicle routing problem

In this paper we investigate a vehicle routing problem motivated by a real-world application in cooperation with the German Automobile Association (ADAC). The general task is to assign service requests to service units and to plan tours for the units such as to minimize the overall cost. The characteristics of this large-scale problem due to the data volume involve strict real-time requirements. We show that the problem of finding a feasible dispatch for service units starting at their current position and serving at most k requests is NP-complete for each fixed k ≥ 2. We also present a polynomial time (2k − 1)-approximation algorithm, where again k denotes the maximal number of requests served by a single service unit. For the boundary case when k equals the total number |E| of requests (and thus there are no limitations on the tour length), we provide a -approximation. Finally, we extend our approximation results to include linear and quadratic lateness costs.     

Real-time dispatch of trams in storage yards

Real-time dispatch problems arise when preparing and executing the daily schedule of local transport companies. We consider the daily dispatch of transport vehicles like trams in storage yards. Immediately on arrival, each tram has to be assigned to a location in the depot and to an appropriate round trip of the next schedule period. In order to achieve a departure order satisfying the scheduled demand, shunting of vehicles may be unavoidable. Since shunting takes time and causes operational cost, the number of shunting movements should be minimized without violation of operational constraints. As an alternative, we may serve some round trips with trams of type differing from the requested type. In practice, the actual arrival order of trams may differ substantially from the scheduled arrival order. Then, dispatch decisions are due within a short time interval and have to be based on incomplete information. For such real-time dispatch problems, we develop combinatorial optimization models and exact as well as heuristic algorithms. Computational experience for real-world and random data shows that the derived methods yield good (often optimal) solutions within the required tight time bounds. This revised version was published online in June 2006 with corrections to the Cover Date.     

Queueing analysis of a mobile trunked system with mixed traffic and finite population

In trunk mobile systems, telephone lines are interfaced with the radio system at the repeaters which serve dispatch type mobile subscribers and telephone line users. We study a trunked mobile system which serves two different types of communication traffic (i) dispatch traffic which has short average service time and (ii) interconnect traffic of telephone line users. Both types of users are assumed to arrive from finite population. The dispatch users are allowed to access all repeaters while interconnect users can occupy only a fixed number of repeaters. A sharing service algorithm to derive blocking probabilities of dispatch and interconnect users and average dispatch delay is proposed.     

Automated self-organising vehicles for Barclays Cycle Hire

Self-organisation is a distributed and asynchronous process in which global pattern or behaviour emerge from local components of the system. Neither central control nor external intervention is necessary during this process. Self-organising systems are adaptive and robust, which are appealing properties from a design and engineering point of view. In this paper, we present an innovative self-organisation approach for a dynamic vehicle routing problem, the Barclay Cycle Hire truck dispatch. In addition, we introduce an evolutionary algorithm capable of automatically configuring the “self-organising trucks”. Experimental results show the evolutionary algorithm improves the overall fitness of the self-organising trucks; and we observe global emergent behaviour in the way trucks self-organise.