一种条件结构的调度算法

操作调度是高级综合中的最重要的任务。本文提出了一种条件结构的调度算法，该算法以一种自低向上的途径将一个具有嵌套条件结构的控制数据流图转化为一个不包含条件结构的等价的控制数据流图，采用一种传统的调度算法产生后者的一个调度，然后从这个调度再导出前者的一个调度，它最大限度地利用了操作之间的潜在的资源共享，当控制数据流图中含有大量的嵌套条件结构时，该算法非常有效     

一种循环结构的折叠调度算法

操作调度是高级综合中的重要任务。本文提出了一种采用循环折叠对循环结构进行调度的调度算法。该算法可处理具有迭代间数据依赖的循环结构，复杂度低，采用它可获得具有最小迭代时间的循环结构的调度。经实验证明，该算法具有简单易懂且运行速度快的特点，特别适合数字信号处理应用。本文还对有关定理进行了证明     

一种新的操作调度算法

操作调度是高级综合中的主要任务。本文对当前大多数高级综合系统所采用的调度算法进行分析之后，针对它们的全局性差，计算复杂度大的不足之处，提出了一种新的操作调度算法，经实验证明，该算法具有高效，复杂度低的特点，并且能够产生全局优化解，当用在高级综合系统中时，能极大地提高所产生的设计的质量。     

强时间约束条件下的调度优化算法

强时间约束是指控制数据流图CDFG的延迟时间无法满足的时间约束。为了使CDFG的延迟时间能够满足强时间约束,本文提出了对CDFG的优化(压缩)算法。该算法根据操作的结合律和兮配律,在满足硬件资源约束的条件下,将CDFG关键路径上的操作转换到相关的非关键路径上去,使关键路径上的操作个数减少(即CDFG的延迟时间减少),从而使CDFG的延迟时间满足强时间约束。该算法在不改变CDFG语义的前题下,重新安排CDFG中的各个操作,尽量减少关键路径上的操作个数。该算法已经加入到我们所完成的DBS调度算法的控制策略中,使得DBS调度算法能够在强时间约束条件下进行调度。     

基于免疫萤火虫算法的RFID仓储车辆动态调度

针对物流配送实时仓储车辆调度问题,提出了一种基于RFID技术的免疫萤火虫车辆动态调度框架。建立了基于配送成本的带约束条件车辆路径问题数学模型,运用免疫萤火虫优化算法求解该模型,免疫萤火虫优化算法将萤火虫优化及免疫克隆技术融合,采用多层进化模式,在低层萤火虫操作中及高层免疫操作中分别引入多态子种群自适应机制和全局极值筛选策略,以提高算法全局收敛效率,在此基础上设计了仓储车辆动态调度框架,将车辆动态调度过程分为车辆调度任务控制和路径优化两个阶段,给出了车辆动态调度任务处理流程。实验仿真表明,该车辆动态调度算法能够有效地解决大规模动态物流车辆调度问题。     

基于浓度扩散的调度算法

本文介绍了一个适用于高层次综合系统的、新的调度算法:基于浓度扩散的调度算法.该算法不仅可以在硬件资源(如芯片面积)约束条件下或在时间约束条件下进行调度,而且可以在这两种约束条件下进行折衷调度.它支持多周期操作与链式操作到非流水线功能部件与流水线功能部件的调度.我们的算法在较小的时间复杂度下得到了与以前发表的几种算法相似甚至更好的结果.     

柔性Job shop集成化计划调度模型及其求解算法

考虑不同加工工艺路径的成本因素，从集成化的角度研究了柔性Job shop计划和调度问题，针对问题的结构特点，建立了两层混合整数规划模型，提出门槛接受，遗传算法与启发式规则相结合的混合求解算法，综合考虑各层次决策问题进行求解，实例计算表明，该算法可迅速求得问题的近优解，表现出良好的求解性能。     

基于遗传算法的作业车间调度优化

将遗传算法和启发式调度规则相结合，研究了具有柔性加工路径的作业车间的智能优 化调度问题，调度规则的引入使该算法具有较高的搜索效率，遗传算法的引入保证了解的全 局最优性，对照算例，表明该算法在求解性能和效率两方面均具有显著的优势．     

学习路由器模型及路由算法研究

在分析比较现有的两种路由器模型基础之上，结合目前路由器设计中的新技术提出了一种学习路由器模型，并结合工业控制网络的特点对路由表的查找技术和算法作了研究，对路径寻优算法作了改进使其能实现多路径路由，从而满足工业控制网络高可靠性的要求；对路由表采用哈希 技术以提高路由器查表速度；对路由器各端口队列采用了优先级调度算法以满足工业控制网络高实时性的要求，路由器对各端口采用轮转调度算法以体现公平性。     

带后继位级跟踪的抢先位级调度

本文论述多处理机的最佳调度算法.对于相关任务,文中提出了“PSLT——带后继位级跟踪的抢先位级调度算法”.为实现PSLT调度算法编制了操作原语,并对该算法的最佳性进行了分析.     

基于关键路径知识的任务调度遗传算法

基于遗传算法提出了一种新颖的多处理器任务调度算法CPGS。该算法利用任务系统的关键路径知识,构造了性能良好的初始种群。借助第三方测试数据集,将CPGS算法同其他类似算法进行了对比。实验结果表明,CPGS算法性能优于已有的同类算法。     

多AGV调度系统中的两阶段动态路径规划

为缩短AGV系统的研发周期、降低研发成本,寻求能适应不同地图的通用调度策略以及增强对实际调度任务和故障的鲁棒性,提出了一种两阶段动态路径规划策略．对多AGV调度系统应用两阶段控制策略: 采用动态路径规划进行路径生成,实时对多个AGV同时规划其路径,并通过启发式算法实现路径优化．通过系统仿真证明,该策略很好地提高了AGV调度系统的柔性,是一种能适用于不同地图的通用调度策略．     

交通信息物理系统中的车辆协同运行优化调度

运输成本及温室气体的排放是衡量智能交通系统的重要指标，有效的运输调度可以降低运输成本和环境损害.针对路网中集成环保型货车的运输问题，本文提出一种基于交通信息物理系统（Transportation cyber physical system，TCPS）的大规模车辆协同调度及合并方案，以最大限度地降低运输成本和碳排放量.首先，采用局部调度策略，结合领队车辆选择算法及聚类分析，构建可合并车辆集合；然后，通过数学规划方法，实现每个车队集合中车辆路径与速度的改进优化处理；最后，通过突发情况的简易处理说明本文调度策略的可扩展性.仿真实验表明，用本文方法将车辆编组合并成车队行驶，较固定路径合并策略可显著降低路网中货运车辆的整体油耗.     

基于关键路径链和PACGA的网络总线资源调度方法研究

针对传统工业控制网络总线资源调度算法在节点数量逐渐增加时收敛速度慢和搜索精度不高,且准确度及效率低等问题,提出了一种基于关键路径链和多态蚁群遗传算法(PACGA)的资源调度方法,采用关键路径链的调度算法获取需求调度的节点,不同节点间采用多态蚁群遗传算法进行资源的调度,依据照工业控制网络资源调度的特征,用自适应调整挥发系数增强节点的全局搜索性能,通过候选节点集方法缩小搜索区域提高算法的搜索效率,完成工业控制网络总线资源的高效调度;仿真实验说明,该种方法在工业控制过程中任务数量较多的情况下仍然具备较高的运行效率和精度,并且具有较低的运行时间,具有较强的应用价值。     

基于GSPN和人工免疫算法的并行测试任务调度研究

针对ATS中并行测试任务调度复杂、难以优化的问题,提出了一种广义随机Petri网和人工免疫算法相结合的任务调度优化算法.首先对并行测试系统建立广义随机Petri网(GSPN)模型,然后将激发的变迁序列集作为并行测试任务调度路径;将免疫克隆选择算法(ICSA)应用到并行测试系统任务调度问题中,并提出一种自适应克隆选择算子,搜索最优任务调度路径,得到以测试时间最短为目标的最优任务调度方案.用某型雷达接收机并行测试系统对该算法进行仿真验证,结果表明,与改进的混合遗传算法(IHGA)相比,该算法能够便捷地得到任务调度最优序列,且测试效率更高.     

A Transaction Model for XML Databases

The hierarchical and semistructured nature of XML data may cause complicated update behavior. Updates should not be limited to entire document trees, but should ideally involve subtrees and even individual elements. Providing a suitable scheduling algorithm for semistructured data can significantly improve collaboration systems that store their data—e.g., word processing documents or vector graphics—as XML documents. In this paper we show that concurrency control mechanisms in CVS, relational, and object-oriented database systems are inadequate for collaborative systems based on semistructured data. We therefore propose two new locking schemes based on path locks which are tightly coupled to the document instance. We also introduce two scheduling algorithms that can both be used with any of the two proposed path lock schemes. We prove that both schedulers guarantee serializability, and show that the conflict rules are necessary.     

基于动态关键路径的仿真网格资源调度算法

从仿真系统工作流的关键路径分析，确定关键路径上的联邦成员节点，使网格资源调度方面优先获得保证。簦于仿真网格系统运行的复杂性和不确定性，引入了随机规划理论，提出了仿真网格的动态关键路径概念以及基于动态关键路径的资源调度算法，共同解决当资源有限以及任务相关情况下仿真网格的资源调度问题。具体实现，主要使用遗传算法以及MCP算法。仿真实验结果表明，基于动态关键路径的资源调度算法能够优化仿真网格资源的调度。     

一种基于PID反馈控制的分时调度算法

近年来，在实时操作系统的研究中，已开始将反馈控制融人操作系统的任务调度，将这一想法与分时操作系统相结合，提出一种基于PID反馈控制的分时调度算法，它能根据任务对CPU带宽的个性化需求，并考虑开放的分时系统中CPU占用率的不确定动态变化特性，动态地分配CPU带宽，使CPU对任务集的处理效果始终处于最佳状态，性能分析实验结果表明，它不仅兼容传统的分时调度架构，还具有良好的动态、静态特性及鲁棒性，且引入的调度费用较低。     

可回退抢占的设备驱动综合调度算法

针对基于拟关键路径法的综合调度算法按路径长度确定工序的调度次序,形成工序组间的并行处理, 使设备产生较多空闲时间的问题,提出可回退抢占的设备驱动综合调度算法. 该算法以每次工序加工结束作为一次可调度工序的寻找事件,若此时新出现的可调度工序具备抢占能力,则产生回退事 件进行重调度;若不产生回退事件,如果可调度工序唯一,则调度此工序;如果可调度工序不唯一, 选择父结点路径长的工序;如果父结点最长路径相同,选择用时长的工序. 由于该算法在调度工序时形成工序间的并行处理,缩小基于拟关键路径的综合调度算法形成的并行处理单位,进而减少加工过程中产生较多的设备空闲时间,提高设备利用率;同时,由于采用抢占式的回退调度策略,优先调度对调度结果有重要影响的长路径工序,达到对拟关键路径法的扬长避短,进一步提高设备利用率.     

Joint Algorithm of Message Fragmentation and No-Wait Scheduling for Time-Sensitive Networks

Time-sensitive networks(TSNs)support not only traditional best-effort communications but also deterministic communications,which send each packet at a deterministic time so that the data transmissions of networked control systems can be precisely scheduled to guarantee hard real-time constraints.No-wait scheduling is suitable for such TSNs and generates the schedules of deterministic communications with the minimal network resources so that all of the remaining resources can be used to improve the throughput of best-effort communications.However,due to inappropriate message fragmentation,the realtime performance of no-wait scheduling algorithms is reduced.Therefore,in this paper,joint algorithms of message fragmentation and no-wait scheduling are proposed.First,a specification for the joint problem based on optimization modulo theories is proposed so that off-the-shelf solvers can be used to find optimal solutions.Second,to improve the scalability of our algorithm,the worst-case delay of messages is analyzed,and then,based on the analysis,a heuristic algorithm is proposed to construct low-delay schedules.Finally,we conduct extensive test cases to evaluate our proposed algorithms.The evaluation results indicate that,compared to existing algorithms,the proposed joint algorithm improves schedulability by up to 50%.