Scheduling Non-stationary Bursts of Real-time and Non-real-time Traffic in ATM Networks

The problem of scheduling real-time and non-real-time traffic in an ATM switch multiplexor when bursts of either type of traffic occur is studied. The scheduling algorithms studied are: Queue Length Threshold (QLT) and Minimum Laxity Threshold (MLT). Analytic results based on Markov Chains are used. In addition the results are compared with an optimal (but impractical) scheduling determined via dynamic programming. Dynamic programming is used in this paper to show that MLT gives a near optimal performance trade-off between real-time and non-real-time traffic for constant arrival rates. The trade-off QLT allows is not close to optimal. For non-real-time bursts MLT still gives a close to optimal trade-off. For real-time bursts the trade-off MLT allows between real-time and non-real-time traffic is not as close to optimal, but even where the MLT trade-off is not near optimal, the QLT trade-off is much worse than the MLT trade-off.     

双头磁盘系统的实时调度算法

对双头磁盘系统模型和调度算法进行实时化扩展,设计了三种实时调度算法：最早截止期优先（ＥＤＦ）算法,可满足的最早截止期优先（Ｆ－ＥＤＦ）算法和忽视超期限请求（ＩＧＭ－ＥＤＦ）算法．由于这三种算法充分考虑了Ｉ／Ｏ请求的截止期限,使双头磁盘系统能满足更多的实时Ｉ／Ｏ请求．实时调度算法的性能模拟实验表明：实时调度算法比非实时算法能更好地满足实时Ｉ／Ｏ请求的期限要求．三种实时调度算法中,ＩＧＭ－ＥＤＦ的性能最好,它很适用于硬实时应用;Ｆ－ＥＤＦ算法的性能次之,它最适合于软实时应用．     

异构无线网络融合的建模仿真与性能评估

结合IEEE 802.16和IEEE 802.11标准实现移动互联网的接入,设计一种将WiMAX作为Wi-Fi回程支持的异构无线网络融合模型.利用OPNET仿真工具进行建模,采用自相似Pareto分布生成实时、非实时业务的网络流量,并根据不同应用的优先级需求,得出异构无线网络中相应业务的最优配置.分析结果表明:该融合模型与传统模型相比,不仅在实时和非实时业务上的时延抖动和响应时间更优,而且能满足异构无线网络对VoIP,HTTP和FTP等应用的服务质量(QoS)需求.     

基于实时车货信息的港-公调度优化模型

为了解决港区内存在的进出车辆拥挤、货物周转时间长、甚至延误顾客要求到货时间等问题,将港口系统和公路运输系统综合起来进行整体调度优化研究.通过分析港口每艘货船靠港和离港的装卸作业过程,采用线性规划的方法,建立包含港口、公路货运场站和目的地的港-公调度优化模型.该模型在满足港口和所有目的地货物需求的前提下,根据港-公系统信息平台提供的实时车货信息,求解出作业时间最短的公路货运车辆调度方案,这里作业时间既包括装卸车作业时间又包括车辆行程时间.对于每次港口装卸船作业,港-公调度优化模型均能为货运车辆在港口、货物场站和目的地之间提供最优运输路线,从而节省装卸作业时间,提高港-公系统的作业效率.     

一种能量消耗平衡的线性无线传感器网络调度策略分析

考虑应用在公路、桥梁、隧道和地铁等场合的线性无线传感器网络,其线性和多跳传输特征造成能量不平衡消耗,靠近基站的节点需要转发大量数据,因此自身能量很快耗尽导致网络监控失效.以线性网络、均匀部署为研究内容,采用适当的调度策略平衡能量消耗,从而解决能量消耗不平衡问题.将节点转发信息的能量消耗和能量平衡作为约束条件,采用非线性规划方法建立一种线性传感器网络调度策略,通过调整节点到下一跳的距离和转发的数据量来平衡能量消耗,延长网络寿命.对影响网络寿命和节点效率的因素给出了详细分析,对节点之间不同传输距离的能量消耗给予了详细讨论,并进行了仿真.仿真结果表明,通过优化节点间通信距离和流量能够平衡能量消耗,延长网络寿命.     

一种基于粗集的电力系统调度新方法

为满足电力系统实时调度和提高系统抵御风险的能力,基于广义粗糙集理论,提出一种适应动态环境的电力系统调度策略.该方法充分考虑了机组工作、停运、检修及紧急调度等事件发生,研究了实时调度窗口内机组的再选择与再调度策略,建立了一种基于S-粗集和偏序粗集理论的电力系统调度粗模型.仿真计算显示了该方法不仅能适应动态环境,而且能缩小问题求解规模,特别是对动态规划中机组状态数“组合爆炸“问题特别有效,是一种实时调度新方法.     

交换机中周期流优化调度问题的复杂性

研究了交换机中周期流量的优化调度问题,着重讨论了该问题的复杂性.依据呼损率定义了交换机周期流量调度的最优化问题,并对其子问题,嵌套周期流优化调度的复杂性进行了研究.证明了一种受限Max2Sat问题的NP完全性,并通过将该问题多项式归约到交换机周期流量调度的最优化问题,由此证明了仅有1和2周期的交换机周期流优化调度问题是强NPC问题.并利用该结果证明了任意嵌套周期的优化调度问题也是强NPC的.这表明对于任意嵌套周期流优化调度问题不存在伪多项式算法.     

现场硬实时网络调度算法研究

研究了实时任务死线不大于其周期的任务集调度条件与硬实时网络调度算法约束条件，论证了计算时间复杂度，并将单调死线调度方法直接用于非周期任务调度．最后对调度算法的可调度性进行了严格测试．     

单台机器排序问题中工件的预排序

在排序问题中,为了寻找一个工件的加工次序,有时需要对原来工件进行重新编号,即对工件进行预排序.例如用动态规划求解工件有先后约束关系的单台机器排序问题时,需要对工件进行预排序,使得先加工的工件的序号小于它的后继工件的序号,且使得某种指标达到最优.对于工件之间的先后关系呈链状结构的单台机器排序问题,给出了一个算法,并证明了该算法是最优的.对于工件之间的先后关系呈树形结构的单台机器排序问题,也给出了一个算法,并证明了对于某些特殊的树形结构的单台机器排序问题,该算法是最优的.     

基于遗传算法多目标优化的工程项目调度

在建设工程项目管理中,施工周期和项目成本的综合均衡管控是项目调度管理的最重要内容之一。然而,实际中两者的关系即相互关联又矛盾对立,任一目标的优化必然以弱化另一目标为代价。因此,工程项目调度管理问题是一类组合优化问题。为此本文提出了一种基于遗传算法的多目标优化建设项目调度模型。模型为项目管理者制定和评估工程完成最佳时间和成本最小化的的工程施工进度计划。计算模型主要分为三个模块：开发实用的建设项目进程调度模块;计算项目成本的管控模块;多目标搜索和识别项目时间和成本之间最优或接近最优解的权衡模块。最后,应用该模型分析了一个应用实例,并证明了模型的有效性,为项目管理者提供理论参考。     

具有岸桥碰撞和甲板约束的岸桥混合装卸作业调度优化

针对具有岸桥间不可相互穿越及安全距离约束、甲板开闭约束的集装箱码头岸桥混合装卸作业的调度优化问题,分析了岸桥装卸与移动过程中的相关性质,并提出一种基于减小岸桥移动距离和均匀化岸桥负荷的启发式算法.在该算法基础上设计了一种遗传算法,进一步搜索最优解,并推导了问题的一个低界.数据实验表明,所提出算法的解具有良好的质量和较高的时间效率.     

炼钢－连铸最优炉次计划模型与算法

对钢铁厂炼钢－连铸计划与调度中的炉次计划建立了一个最优炉次计划混合整数规划模型．为了用遗传算法求解这一带约束条件的混合整数规划模型，提出了一种染色体的构造策略和交叉、变异方法，解决了迭代过程中满足可行性要求的问题，经用实际数据进行计算，表明所给模型和算法是有效的．     

若干带拒绝费用的分批排序问题研究

首次考虑了工件可拒绝的单机串行分批排序问题.对于问题1,s｜s-batch,rej｜Cmax＋Σ j∈ ej,均给出了最优算法;对于问题1,s｜s-batch,rej｜Σ j∈s Cj＋Σj∈ ej,通过动态规划算法给出了多项式时间的精确算法.研究了问题1｜B〈n,rej｜Σj∈s wjCj＋Σj∈ ej中工件加工时间均相等的特殊情况.     

用于差别服务网络中的业务调度与成形机制

在差别服务网络中,实时业务的延时保证是一个难题,这需要在调度聚集业务的时候能够保存聚集类中每一个单独流的业务特性。针对此问题,该文提出了一种用于差别服务网络的调度与整形相结合的机制——TD2FQ(Token-drivenDelay-sensitiveDynamicFairQueueing)。该机制包括一种新的调度机制——延时相关动态公平队列,以及一种新的"有色令牌"应用模块。TD2FQ可用于进行聚集业务的成形调度,除了能够获得确保的延时上界,还可以维持业务类中不同流间的公平性以及业务流的成形条件,并且保证了输出链路的带宽利用率。该文给出了该算法的理论分析和仿真结果,论证了该算法的优越性。     

空中交通进近排序及优化调度

针对空中交通进近管制地区日益繁忙的交通流量,设计了一种进近排序及优化调度方案。目前的空中交通调度依赖于管制员的经验判断。随着交通流量的增加,管制员的工作负荷越来越重,这就进一步威胁交通安全。管制员通常以牺牲容量为代价来保障安全,结果造成大量的交通延误。该文设计的进近管制排序和优化调度方案能够在充分保证安全运营的情况下最优地使用机场和空域的容量。同时为管制员提供方便直观的决策支持工具,可以进一步减轻管制员的工作负荷。该方案已应用于清华大学国家CIMS中心与华北空管局合作开发的空中交通管制指挥检测系统(ATCCMS)中,得到了管制员的一致好评。     

A Decision Support Method for Truck Scheduling and Storage Allocation Problem at Container

Truck scheduling and storage allocation, as two separate subproblems in port operations, have been deeply studied in past decades. However, from the operational point of view, they are highly interdependent. Storage allocation for import containers has to balance the travel time and queuing time of each container in yard. This paper proposed an integer programming model handling these two problems as a whole. The objective of this model is to reduce congestion and waiting time of container trucks in the terminal so as to decrease the makespan of discharging containers. Due to the inherent complexity of the prob-lem, a genetic algorithm and a greedy heuristic algorithm are designed to attain near optimal solutions. It shows that the heuristic algorithm can achieve the optimal solution for small-scale problems. The solutions of small-and large-scale problems obtained from the heuristic algorithm are better than those from the genetic algorithm.     

多处理器混合实时任务调度

比例公平调度PFair(Proportionate-Fair)算法和边界公平调度BFair(Boundary-fair)是多处理器系统上周期性实时任务的最佳全局调度方法,但在实际的实时系统中,实时任务往往是周期任务和非周期任务混合的任务系统,在研究PFair和BFair调度算法的基础上,提出了基于服务器思想的公平调度方案,实现了对混合实时任务的调度,同时保证了任务公平地使用共享资源,使得公平调度算法适用于多处理器系统中的混合实时任务调度,扩展了其适用范围。     

Approximate Solution to the Scheduling of Flexible Transfer Lines

ＡｐｐｒｏｘｉｍａｔｅＳｏｌｕｔｉｏｎｔｏｔｈｅＳｃｈｅｄｕｌｉｎｇｏｆＦｌｅｘｉｂｌｅＴｒａｎｓｆｅｒＬｉｎｅｓ￥ＹａｎｇＳｈｅｎｇ，ＷｕＣｈｅｎｇ杨盛，吴澄（ＣＩＭＳ－ＥＲＣ，ＴｓｉｎｇｈｕａＵｎｉｖｅｒｓｉｔｙ，Ｂｅｌｉｉｎｇ１０００８４）Ａｂ...     

基于规则组合的Job Shop多目标柔性调度方法

为提高Job Shop模式下多目标柔性调度的实时性,文章利用规则调度计算量小、实现速度快的特点,建立基于双层规则组合的Job Shop多目标柔性调度方法;运用离差最大化原理分析规则调度结果,生成合理的多目标权重,以选择符合现场实时工况的较优调度方案;通过仿真实例验证了该调度方法的有效性。     

柔性制造系统的合作博弈调度

有多个加工和装配设备的柔性制造系统的生产包括零部件的加工和产品的装配过程.为适应敏捷制造,此系统需要有效的实时生产调度.文中就此提出了一种调度方法,首先根据产品装配结构对问题进行分解,得到多个易于调度的简单问题,形成对应的Agent,然后应用合作博弈理论,根据各Agent的重要性和装配约束获得Agent的排序,依此顺序在机器上按照规则进行生产安排,能够得到满足产品加工约束的近似最优调度结果.最后通过实验对所提出的算法进行了验证.