Linux内核的进程调度原理及改进算法研究

随着Linux在嵌入式操作系统领域的广泛应用,对Linux实时性能增强的研究也越来越多。通过对Linux进程调度依据和进程调度过程的分析,提出了一种改进的Linux进程调度算法。该算法改造了进程调度队列数据结构,去掉了进程调度选择时的遍历步骤,更改为直接得到待选最高优先级进程,同时,该算法改统一的时间片重新分配策略为分散的时间片重算策略。通过Linux进程调度算法与改进算法的时间复杂度对比分析,改进算法将Linux调度算法O(n)级的时间复杂度降低为O(1)级时间复杂度,因此能够更好地满足实时操作系统时间可测度以及低延迟等要求。     

面向多星观测调度的分层迭代算法

提出一种基于分治策略的多星观测分层调度框架,在该框架下,用蚁群优化算法把任务分配至各轨道圈次上,并利用自适应模拟退火算法求解各轨道圈次的调度问题。根据各轨道圈次调度结果的反馈情况,再调整任务分配方案,重复上述过程直到达到算法终止条件。为了提高算法的性能,在设计蚁群算法的启发式信息模型时,应充分考虑卫星调度问题的领域知识;在模拟退火算法中设计两个邻域结构,采用动态选择策略在优化过程中确定最佳邻域搜索结构。仿真实验表明,该方法有效地降低了问题求解的复杂度,尤其在求解大规模多星观测调度问题时表现出优异的性能。     

基于多资源点的装备应急器材调度决策模型

针对装备应急器材调度决策问题,从调度路径优化和调度计划分配2个方面,研究了其多目标优化模型的构建。将资源点划分为若干级别来确定资源点选取的优先次序,通过先求解资源点与需求点之间的最优路径,后求解器材资源分配量的思路,建立了装备应急器材调度决策的广义最优路径模型和运输模型,采用改进的Dijkstra算法对模型进行求解,仿真结果表明:所构建的决策模型及算法是有效的。     

基于NGA算法的舰载机机库出库调度优化

为了在复杂的机库环境中,尽可能缩短舰载机出库时间,优化其出库顺序,对舰载机多机出库调度优化问题进行了研究。首先,对该问题进行分析,建立了适合优化的数学模型。其次,设计了一种适合优化舰载机多机出库调度问题的算法—NGA算法,该算法是在遗传算法(GA)的基础上,对原有交叉和变异策略进行改变以适应所求解问题,并融入执行路径探测和规划的通视图算法后形成的。最后,分别将该方法和枚举法应用于求解尼米兹级航母舰载机多机出库调度优化问题T4。仿真结果为基于NGA算法所得的最短出库时间为801 s,最短移动距离为1 098.3 m;基于枚举法结果为800.4 s和1 097.6 m。由结果可知,NGA算法计算结果与枚举法相差较小,可以应用于求解舰载机多机出库调度问题。     

改进柔性资源约束项目调度模型与粒子群算法

在资源受限项目调度问题中,将可再生资源进一步拓展为具有能力差异的柔性资源,建立考虑能力差异的柔性资源受限的多模式项目调度问题模型,该模型是对传统资源约束项目调度问题(RCPSP)更接近实际的拓展。提出了基于粒子群算法的求解算法,粒子群算法求解该模型的思路为,利用蒙特卡洛方法根据资源-能力矩阵与活动模式-能力矩阵得到活动模式-资源矩阵,将考虑能力差异的柔性资源受限的多模式项目调度问题转换为常规的多模式项目调度问题,然后利用基于任务序列与模式表示的粒子群算法对该多模式项目调度问题进行求解。用数值实例说明了模型的合理性与算法的有效性。     

SpaceFibre星载数据网络低延时确定性调度算法

针对超高速SpaceFibre星载网络中多源数据传输的确定性和实时性应用需求,提出一种分类细粒度低延时确定性调度算法。该算法基于差异化调度策略的思想,将数据流划分为三类。为实现网络资源的细粒度分配,引入扩展时隙。该算法采用无冲突均匀调度方法,降低了数据包的平均排队延时。为适应有效载荷组网的航天应用场景,该算法兼顾网络拓扑结构生成调度方案。为验证算法有效性,在OPNET仿真平台下利用自定义建模技术搭建网络仿真模型。仿真结果表明:相比优先权调度和无冲突连续调度机制,该算法实现了时间敏感数据流的确定性传输;随着时隙数目的增加,网络的延时性能和抗抖动性能显著提升,吞吐量性能得到保证;该算法具有一定的航天工程实用价值。     

保障时间不确定情况下的舰载机航保资源调度

航空母舰舰载机保障环境多变,导致航保资源的保障时间不确定,采用区间数的方法表示保障时间,建立了基于保障时间为区间数的调度模型。根据问题的特点,定义了4种区间数排序规则,并且在模型求解时,直接采用区间数计算。针对调度模型,提出了一种改进的差分进化算法,采用短用时和负载均衡策略以及随机生成的方法初始化编码,解码采取活动调度,改进变异规则,最后通过实验验证了模型和算法的正确性及有效性。     

基于约束满足的多目标对地观测卫星成像调度

EOS(对地观测卫星)成像调度需要根据用户提出的成像任务需求确定卫星成像序列,是一个复杂的组合优化问题。考虑到成像侧视约束条件,建立EOS成像调度的多目标有向无环约束图模型。在此模型的基础上提出了基于SPEA2(strength pareto evolutionary algorithm 2)的多目标成像调度算法,采用约束控制技术设计遗传算子处理成像约束。经过三个实际的多目标成像调度问题测试,表明该算法可以有效地解决EOS成像调度问题。     

基于改进QPSO算法的云计算资源调度策略研究

资源调度问题是云计算研究的一个重要方向。针对传统量子粒子群算法的不足,提出了一种改进量子粒子算法,并将其应用于云计算资源调度策略。首先,建立了云计算资源调度问题的模型,并将资源调度任务完成的时间作为适应度函数。随后采用自适应机制,通过改变粒子位置更新的惯性权值,提高了算法的全局搜索能力,加快了收敛速度。最后通过实验仿真对该算法进行了测试。实验表明,该算法能更好更快地找到云计算资源调度方案,使资源分配更加合理高效。     

卫星数传调度模型研究

卫星数传调度问题是一个具有多时间窗口、多资源约束的优化问题。针对该问题,建立了卫星数传需求模型、任务模型和调度模型。在建模过程中,采用了框架模型形式,把问题中的主要约束封闭于每个数传任务中,这在降低调度模型复杂度的同时,也降低了调度算法设计难度。还提出了调度算法设计思想,并设计了一基于灵活度的调度算法。仿真表明,所建立的模型及算法对解决卫星数传调度问题是可行的。     

一种用于区分服务路由器的crossbar调度算法

宽带路由器一般采用crossbar交换开关。Crossbar交换开关对QoS (QualityofService)的支持十分重要。提出一种支持IETF区分服务 (DifferentiatedService)服务模型的crossbar调度算法———OSP (OutputSerialPolling) ,该算法带宽利用率高 ,支持报文优先级。与目前存在的同类算法相比 ,具有硬件实现简单的优点     

An evaluation of scheduling heuristics for dynamic single-processor scheduling with early/tardy costs

In an endeavor to broaden the application of scheduling models to decisions involving the use of a manager's time we use simulation to investigate the performance of a number of simple algorithms (including eight priority rules and a construction heuristic) in a dynamic setting with tasks arriving (randomly) and scheduling decisions being made, over time. We compare these simple methods relative to a bound that uses an adjacent pairwise interchange algorithm. We model uncertainty in task durations, and costs being incurred for early and tardy task completion (representative of JIT settings). In addition to evaluating the efficacy of the scheduling rules and various preemption strategies (using ANOVA), we highlight the managerial implications of the effects of eight environmental parameters. © 1996 John Wiley & Sons, Inc.     

一种应用于数据通道综合的定向搜索流水调度算法

流水调度是专用数字信号处理器高层综合中一个困难而急待解决的问题。给出了一种定向搜索流水调度算法 ,目标是使全面考虑了运算单元、寄存器和互连的硬件代价最小化。它作为一种利用启发信息的迭代算法 ,一方面克服了确定性算法爬峰能力差、易于陷于局部极值的缺点 ,另一方面启发信息的利用加快了搜索过程。典型设计实例显示算法性能达到或超过了目前流水调度文献报道的最好性能     

考虑航线交叉的救援直升机起飞时序规划方法

为解决多架救援直升机的起飞时序规划问题,以最小化最后一架救援直升机的起飞时间为优化目标,建立多直升机多起降点的数学规划模型。设计了基于任务优先级的快速启发式算法,提出航线交叉点的处理方案,给出起飞时间求解算法。以云南鲁甸6.8级地震的灾后救援为背景,设计了包含24架直升机和12个起飞点的起飞时序规划案例,对模型和算法进行了仿真验证,并对航线交叉的影响与处理措施进行了深入讨论。实验结果表明该模型和方法能有效解决多架救援直升机的起飞时序规划问题。     

A branch-and-bound algorithm to minimize total flow time with unequal release dates

This article examines the single-machine scheduling problem to minimize total flow time with unequal release dates. This problem has been proven to be NP-hard. We present a necessary and sufficient condition for local optimality which can also be considered as a priority rule. On the basis of this condition, we then define a class of schedules which contains all optimal solutions. We present some efficient heuristic algorithms using the previous condition to build a schedule belonging to this subset. We also prove some new dominance theorems, discuss the results found in the literature for this problem, and propose a branch-and-bound algorithm in which the heuristics are used to provide good upper bounds. We compare this new algorithm with existing algorithms found in the literature. Computational results on problems with up to 100 jobs indicate that the proposed branch-and-bound algorithm is superior to previously published algorithms. © 1992 John Wiley & Sons. Inc.     

空间预警系统建立导弹目标优先级的多属性决策

空间预警系统在多传感器多目标的情况下需要传感器调度,而建立目标优先级是有效进行传感器调度的第一步。由星载传感器所得图像对目标特征进行估计具有很大的不确定性,直接影响到导弹目标优先级的建立。首先通过作战分析确定出导弹目标的主要属性,采用层次分析法评价属性的权重,然后在不确定的条件下对属性求期望值,使用3种多属性决策方法评价导弹目标的威胁程度,最后取期望值作为导弹目标的威胁评价。正交实验结果表明算法具有很强的实时性和实用性。     

SpaceFibre网络服务质量时隙资源分配算法

为保证SpaceFibre星载数据网络大量实时数据流的超高速确定性传输,提出一种包含两个子算法的SpaceFibre网络服务质量时隙资源分配算法。形式化描述网络服务质量机制,给出调度矩阵相关定义;创建网络服务质量排队模型,定量分析时隙资源分配对网络时延性能的影响;考虑网络兼容性和算法鲁棒性,给出改进二进制序列调度子算法;采用提高初始种群进化程度和增加遗传算子等方法,给出改进混合单亲遗传调度子算法;利用Opnet网络仿真平台建立网络服务质量仿真模型,对比不同算法下网络时延性能。仿真结果表明,该时隙资源分配算法与其他算法相比,网络平均延时降低,网络性能得到显著改善,对构建低延时SpaceFibre网络具有参考意义。     

支持并行工程的造船分段作业计划系统

针对传统造船模式下,车间作业计划与工艺设计串行工作方式的缺点,基于并行工程的原理,提出了分段作业计划与工艺设计的集成运行模式,为实现造船CAPP系统与PPC系统的集成化和并行化提供了实现的基础。针对集成模式的特点,建立了分段作业计划系统资源优化的数学模型,应用遗传算法解决了针对任意分段装配工艺方案的多资源平衡优化问题,可以得到每项作业最优的开工时间,同时能够给出多种资源的最优分布结果,满足了多工艺方案之间资源利用率的比较。最后,给出了计算实例,计算机模拟结果说明了这一方法的有效性。     

基于目标威胁度的相控阵雷达自适应调度方法

对时间资源的合理安排是相控阵雷达发挥自身优势的关键。将目标威胁度引入调度算法中,与工作方式和任务截止期共同进行综合优先级规划。通过构建目标威胁度的量化模型,使雷达在调度跟踪任务时依目标威胁度大小分配时间。提出了修正价值率和执行威胁率的概念,完善了性能评估指标。通过仿真,全面评价了新算法性能,验证了引入目标威胁度的合理性。结果表明,新算法可以有效提升相控阵雷达对高威胁度目标的处理能力。