一种空间多核操作系统容错调度算法

目前计算机系统逐步采用多核处理器来提升性能,空间操作系统如何管理多核资源是发挥处理器性能的关键。在航天等安全关键领域中,采用固定点任务与定期任务混合调度,在保证可靠性的前提下提高效率。现有针对混合任务模型的多核调度算法仅考虑任务分配问题,没有考虑到系统中某一核心出现故障时如何进行容错。FT-RTA算法是一种空间多核操作系统容错调度算法,当一个核心上出现瞬时故障,将故障核心上在故障时间段内的所有任务迁移至正常核心上执行,使计算机系统不会感知到此次核心故障,成功屏蔽故障。经过实际应用中的典型参数验证,算法可以成功屏蔽核心故障,进行系统无感知的容错。

基于状态空间模型序号编码进化算法的航班优化调度

多跑道航班进离港优化调度是将某一时间窗内进离港航班看作一个整体,对进离港航班进行统一优化排序,属于典型的组合优化问题。求解组合优化问题时,采用序号编码比二进制编码和实数编码等方式更直接、更方便。本文提出一种基于状态空间模型序号编码进化算法(OSEA),通过构造状态进化矩阵等操作来实现变异算子的功能,简化了遗传操作,并研究其在航班进离港优化调度中的应用。仿真实验表明:OSEA算法与先到先服务(FCFS)航班排序相比,航班总延误损失降低32.88%,且运算速度更快。

基于改进的状态空间模型进化算法的航班优化调度

单跑道进离港航班优化调度是将某一时间窗内进离港航班看作一个整体,对进离港航班进行统一优化排序,属于典型的组合优化问题。改进的状态空间模型序号编码进化算法(MOSEA)采用序号编码,不使用交叉算子,且通过构造状态进化矩阵来实现基因换位等遗传算子功能,使种群不断地进化,并结合选种池的选择操作实现种群的优胜劣汰。MOSEA算法将问题的解答过程表示为离散状态空间模型的动力学过程,突破了遗传算法的计算模式,简化了遗传操作,并研究了其在航班进离港优化调度中的应用。仿真实验表明:MOSEA算法与遗传算法、先到先服务(FCFS)航班排序相比,航班总延误时间分别降低了22.13%、32.06%,且运算速度更快。

基于多变量的执行体动态调度算法

拟态防御技术致力于从内生安全的角度构建安全可靠的系统来解决网络空间中攻防不对称的问题。作为拟态防御中的重要部件,调度模块的关键问题之一是异构冗余体的量化工作。而现有的研究中对异构冗余体的指标不能全面量化,同时调度算法大多将执行体数量设定为某一固定值,对安全性、动态性以及运行效率造成影响。结合调度算法的特性,分析异构冗余体量化过程中的一些重要指标以及这些指标对动态异构冗余构造带来的收益,提出一种多变量负反馈调度算法。通过对多种因素的量化及计算,并在调度过程中对执行体组的状态进行监控,实现执行体数量根据执行体组情况的动态调整。实验结果表明,执行体数量可动态调整提高了动态异构冗余构造的动态性,保持良好的防御能力的同时具有更高的运行效率。

缩短最大完工时间的船舶分段空间调度算法

针对船舶分段的空间调度,考虑船舶建造过程中的时间和空间两大资源要素,构建了时空利用率模型并以此为评价目标.运用形状相似和工艺相似策略,提出了一种缩短最大完工时间的船舶分段空间调度算法.给出了评价时间和空间等资源利用效率的指标,并利用图论的方法提供了具体空间调度的直观结果.结合船舶建造厂的实际数据进行了数据分析和实例验证,无论空间调度的质量还是效率都取得了令人满意的结果.

基于配置空间理论的启发式空间调度算法

针对船舶分段建造等空间问题,对分段和组立平台进行抽象,建立数学模型,在配置空间理论的基础上提出基于任务优先级和启发式空间布局规则(最大残余空间利用规则、初始配置规则和BL矩形规则)的单场地空间调度算法。在不同规模的实验数据下与传统的基于网格的近似全局搜索算法进行对比,结果表明所提算法在相对短的运算时间内能够获得更优的调度方案。

云计算集群相空间负载均衡度优先调度算法研究

针对云计算集群具有海量节点和高耦合性的特点,将云计算集群中各节点的参数变化投影为相空间上投影点的运动,定义云计算集群的相空间负载均衡度,以其为评估指标建立云计算集群相空间负载均衡度优先调度算法,实现了云计算集群相空间投影在不同负载请求情况下平稳的点状聚集.通过仿真实验利用相空间负载均衡度、广义温度、广义熵等参数和集群的相空间投影对算法的效果进行分析,实验表明,相空间负载均衡度优先算法在大多数调度指标上都优于最小负载优先算法,并且集群规模越大系统的相空间负载均衡度越稳定.

改进粒子群算法的动态空间调度方法

针对船体分段生产调度的多目标性和动态性,提出了一种改进粒子群算法的动态空间调度方法,确定船体分段在工作平台上的加工顺序和空间布局位置.算法以加工完成时间最短和空间利用率最高为目标,采用自适应惯性权重策略保证算法的收敛性,并引入遗传算法中的选择算子和变异算子增强算法的收敛速度和多样性,利用启发式定位策略确定分段的位置.最后,以船厂实际生产数据进行仿真验证.仿真结果表明,所提方法可以大大降低以手工方式制定调度计划的复杂度,并能有效地提高空间利用率达到70%,说明该方法是解决动态空间调度问题的一种有效方案.

动态空间调度的混合遗传算法

提出了一种基于混合遗传算法的动态空间调度方法。首先利用遗传算法产生多个可行的分段调度序列,再采用动态决定分段位置的启发式算法——平均最大空闲矩形策略对遗传算法产生的调度序列进行解码。同时以完工时间和平台利用率的加权和作为适应度函数,充分考虑了空间调度问题所特有的动态性和时空关联性。遗传进化过程收敛后得到近似最优解,实现了调度方案的全局优化。对船厂实际生产数据进行了实证分析以及与其它算法的对比分析,证明了所提方法在空间调度问题上的有效性和实用性。

空间耦合粒子群优化算法及峰谷电价下IES-CCHP区域联合调度

综合能源系统中电力、天然气和热力系统之间的交互影响具有一定的相关性。考虑能源间转换关系以及系统对分时电价的响应,以最小化购售电计划交易成本、燃料成本和排放污染气体所产生的环境成本为目标,建立峰谷电价下冷热电联供(CCHP)系统区域联合环保经济调度模型。为解决粒子群优化算法求解模型时存在的优化效率低、易陷入局部最优、计算结果随机性强等问题,提出一种空间耦合粒子群优化算法。在粒子寻优多维参数空间上,通过引入耦合协调数学模型将各维参数有效耦合,从而使所有参数从总体上同时趋向最优解。仿真结果表明,相比经典粒子群优化算法和改进粒子群优化算法,空间耦合粒子群优化算法有较强的全局搜索能力和更可靠的优化计算结果;所提CCHP系统的联合调度模型能有效促进能源的高效利用、电力的经济调度和节能减排。

基于模型的子空间聚类与时间段蚁群算法的合同生产批量调度方法

针对目前冷轧薄板厂生产流程复杂、大量的多品种小批量合同并线生产,导致难以制定生产计划的问题,本文提出了混合模型子空间聚类(Subspace clustering mixed model,SCMM)方法,以合同中待加工钢卷的宽度、冷轧机组的入口厚度、出口厚度以及合同的交货期为约束,对待生产合同进行组批.依据冷轧厂实际生产过程,将冷轧机组视为核心节点,考虑准时交货、在制品库存和生产流向产能分配的要求,对组批后的生产合同建立全流程合同计划模型,并且利用提出的时间段蚁群算法(Time-section ant colony optimization,TSA),制定合同计划.利用生产过程的实际数据测试,本文的方法优于人工排产,可以满足制定冷轧薄板全流程生产计划的要求.

基于商空间的层次式数据网格资源调度算法

为了解决传统数据网格调度算法在对层次式数据网格调度过程中出现的极易陷入局部最优值和收敛速度过慢的问题,将粒计算的思想引入到网格调度中,提出了一种基于商空间的层次式数据网格资源调度QSHDGRA(quotient space theory based hierarchical data grid resource allocation)算法。首先分析了层次式数据网格的特点,接着提出一种基于业务请求平均等待时间和网络与节点资源利用均衡度的调和函数的调度问题模型,随后设计了基于商空间的层次式最优资源调度算法。该算法的特点是可以在不同粒度上由粗至细地对网格业务进行调度,从而保证不同业务的QoS,并实现系统全局最优资源分配。仿真实验表明,算法可以显著地提升系统整体的吞吐率,具有更快的收敛速度,并具备线性扩展能力。

典型工艺和特殊布位约束下的船舶模块空间调度算法

在深入分析典型模块工艺特性和形状特性,并对模块进行归类的基础上,针对模块的典型工艺约束,以及实际生产中亟需解决的模块特殊布位约束,提出了启发式空间调度策略,实现了以缩短最大完工时间为目标的动态空间调度算法.以时空利用率和工作量平衡差值作为评价指标,利用船厂实际数据范围内的随机数据试验,对比分析了该算法与栅格算法的质量和效率.分析结果验证了该算法的有效性和实用性.

融合目标空间分割的网格任务调度算法

针对网格环境中多个相互独立的任务调度问题,提出一种融合空间分割思想的网格任务调度算法(OSD-GTSA,a Grid Task-Scheduling Algorithm based on Objective-Space-Divided)。算法结合了OSD-MOEA(A Multiple-Objective Evolutionary Algorithm based on the ObjectiveSpace-Divided)算法的目标空间分割的思想,通过对网格中多个相互独立的任务问题进行建模,针对费用和时间权重的不同,进行了3组仿真实验。实验结果表明,OSD-GTSA在算法的收敛性和Pareto解集的分布性上都取得了满意的效果。

船体不规则分段的动态空间调度算法

提出了一种基于遗传算法的针对船体不规则分段的动态空间调度方法.基于遗传算法和临界多边形算法直接对不规则分段进行优化调度,提高空间的利用率。首先,利用遗传算法产生多个可行的分段调度序列。然后,基于临界多边形算法及重心最低策略,根据分段调度序列一一确定各不规则分段的空间位置。充分考虑到空间调度问题所特有的动态性和时空关联性,同时以场地利用率和未延迟加工分段所占比例的综合加权和作为评价函数,实现了调度方案的全局优化。以江苏澄西船厂大型散货船的119个不规则分段作为实验数据,并通过多个算法的比较,发现该动态调度算法可以快速收敛得到较优解,并且在空间利用率和延迟分段指标上有了提高,最终可以得到比较理想的调度结果,证明了所提方法在动态空间调度问题上的有效性和优越性。

多解空间N元非合作性流量切割调度算法研究

给出了包交换网络基于多约束限制的多级并行调度和流量均衡体系模型,根据单节点路由调度任务的非合作性在极小碎片线性映射的假定条件下推导出了路由空间切割调度算法和量化公式,在节点上实现了IP包头重组的并行化计算。实验结果表明,通过量增大、利用率提升,网络在整个路由空间里有良好的时间响应特性。

空间目标监视任务资源调度技术建模分析

针对空间目标监视任务具有环境复杂性、目标动态随机性以及任务高度机动性等特点,建立了一种能够体现监视资源设备个体智能和群体智能的多智能体(Multi-Agent)任务资源调度模型,为了能够快速、准确求解任务资源调度决策方案,通过在基本粒子群算法结合多智能体间的相互引导,分析了基于多智能体模型的粒子群算法。仿真结果表明,针对随机设定的任务要求,所提算法可以计算得到合理有效的调度分配方案。

空间观测任务调度子Agent的底层优化模型及算法

对于采用分层的主从Agent体系结构的航天器自主运行系统而言,各个子Agent可以单独设计,这样就大大减小了设计难度并提高了程序运行效率。对于每个子Agent而言,可以专注于底层模型和算法的设计。空间观测任务调度子Agent的任务是对空间观测任务进行调度,以使在有限的资源下,可观测任务最多,观测价值最大。针对这一子Agent,建立了优化模型来完成最优调度问题的建模。优化模型的目标函数为观测任务的优先级之和最大,优先级与观测任务的价值有关。约束条件包括观测机会约束、航天器资源约束等。采用基于遗传算法的启发式算法进行求解,建立了具有可扩展性的任务调度仿真演示系统,直观的演示了调度后的任务运行情况。

基于二维协调空间的网格工作流调度算法研究

传统的网格工作流模型中分布式工作流管理器之间没有合作,因此可能发生源调度冲突问题,另外,在现有的工作流调度算法中,参与工作流调度的工作流管理器依托于集中或半集中的层次式的资源信息服务体系,导致系统的扩展性差。为了解决这些问题,在文中,提出了一个分布式的协同工作流调度算法。该算法基于二维协调空间来管理网格中的工作流管理器。二维协调空间负责资源发现和协调调度等功能。该算法不仅可以避免性能瓶颈,而且可以增强系统的可扩展性和自主性。

复杂形状船舶分段建造空间调度优化算法

为了提高船舶分段建造场地装焊工场的利用率,提出复杂形状船舶分段的分层嵌套空间调度算法,算法将分段空间调度分为调度序列优化和布局寻优两个过程。针对不同的复杂形状分段提出一种通用的分段布局位置干涉检测方法,在此基础上采用栅格遍历与位置筛选的方法求解分段在装焊工场中的布局优化位置;分段调度序列采用基于优先级和遗传算法的混合排序优化方法,序列优化过程中调用分段布局寻优方法。计算结果表明,该算法可明显提高装焊工场的利用率,是解决分段空间调度的一种有效方法。