一种任务分配问题的快速剪枝优化算法

任务分配问题是运筹学中的一类规划问题,求解这类问题的比较经典的算法是匈牙利算法,但匈牙利算法在求解大规模任务分配时运算效率不高。文章提出了一种新的求解任务分配问题的方法——剪枝优化算法。算法通过逐步剔除已确定的部分分配方案对应代价矩阵元素,逐次降低分配问题的规模,从而实现快速求解全局任务分配问题。对于n个主体执行n个任务的分配问题,进行(n-1)次操作就可以获得最优解。论文进行了相应的仿真,将文章提出的算法和匈牙利算法做了比较。仿真结果表明,该算法与传统匈牙利算法计算结果一致,但计算耗时远远小于匈牙利算法,即该算法大大提高了任务分配问题的求解速度。     

移动边缘计算时延与能耗联合优化方法

针对移动边缘计算中时延与能耗是关键性能指标,且相互制约的问题,研究了通过在边缘与终端之间进行任务分配,对时延与能耗进行联合优化。首先,建立了能耗与时延联合优化的0-1整数规划模型;其次,设计了对任务进行分配的分支定界算法。仿真结果表明,该方法能够有效降低移动边缘计算能耗与时延。     

快速降阶匈牙利算法的云计算任务分配模型

为了提高云计算任务分配效率,在标准匈牙利算法的基础上,提出一种快速降阶优化算法的云计算任务分配模型.为实现快速求解全局任务分配问题,快速降阶算法不断排除已确定的分配方案对应的代价矩阵元素,从而快速降低矩阵的阶次.并可根据成本矩阵规模将矩阵分解成多个矩阵,使得该算法在任务和计算机不对等的情况下同样适用.论文最后的仿真结果表明,快速降阶匈牙利算法计算耗时远远小于匈牙利算法,并能有效提高计算机的利用率.     

基于动态规划的复合电源能量管理优化

以复合电源能耗和电池组容量损失最小化为目标建立多目标优化模型,将电池组容量损失视为状态变量,将多目标优化问题转化为单目标多状态形式,并应用动态规划进行求解,得到Pareto解集。分析优化结果,提取了数条功率分配规律,并基于此提出基于规则的能量管理策略。对控制策略进行仿真验证,结果表明:与动态规划结果相比,复合电源能耗增加1%,电池容量损失增加0.4%,达到了与动态规划相近的效果,在线能量管理策略同时在两个目标上近似最优。     

基于改进MOSFLA的多机协同任务分配

为解决多机协同任务分配这一多约束组合优化问题,提出了一种基于矩阵二进制编码的改进多目标混合蛙跳算法(multi-objective shuffled frog-leaping algorithm,MOSFLA)的任务分配策略。首先,建立了基于目标剩余价值、战机攻击损耗和航程代价的多目标优化模型;然后,对混合蛙跳算法的位置更新策略进行了改进,以保证更新过程中解的可行性及算法的全局收敛能力;最后,利用改进算法求解多机协同对地攻击任务分配问题,得出问题的Pareto最优解集。仿真实验表明,改进算法能够在较短时间内同时得出多个分配方案,增加决策的灵活性。     

面向效用优化的动态阈值在线任务分配算法

针对任务和工人动态到达场景下的在线任务分配问题，提出一种面向效用优化的两阶段动态阈值在线任务分配算法。第一阶段中，根据历史数据，使用多重采样得出产生最大效用的效用阈值数据，并使用反向传播神经网络进行效用阈值曲线拟合；第二阶段中，先动态计算分配阈值，再根据分配阈值进行在线任务分配。实验结果表明，与基于两阶段的全在线任务分配相比，提出算法显著提升了任务分配的效用。     

一种能耗约束的多核系统任务调度算法

不同的任务调度算法将任务分配在不同的处理单元,会产生不同的能耗。在基于片上网络的多核系统中,将任务分摊到所有处理器核能提高系统利用率,但导致大量的簇间通信,增加数据传输能耗。本文在对系统能耗进行建模的基础上,提出一种能耗约束的任务调度算法。该算法结合任务间依赖关系,动态计算任务分配时产生通信开销最小的簇和系统利用率最大的簇,通过计算在相应簇上产生的系统能耗,选择产生系统能耗小的分配方案以平衡系统利用率和簇间通信开销。仿真实验结果证明,算法在减少了簇间通信开销并提高系统利用率的同时,降低了系统能耗。     

基于车辆边缘计算的用户能耗最小化资源分配研究

考虑车辆时变信道对资源分配策略的影响,构建在保证任务QoS要求下的车载用户终端能量消耗最小化问题。利用车辆信道可预测特性以及李雅普诺夫随机优化理论将原问题分解为计算资源分配和无线资源分配两个子问题。由于计算资源分配子问题是单变量优化问题,因此可以直接得到解决方案。而对于无线资源分配子问题,通过将其转换为单变量优化问题进行求解。基于两个子问题的结果,提出一种联合无线与计算资源分配算法。仿真结果显示,当数据包平均到达速率从20个/时隙增加到40个/时隙时,该算法能耗相较于传统的贪婪算法能耗降低了48.85%。     

共享资源约束下多核实时任务分配算法

为了提高多核实时系统任务分配效率,研究分组固定优先级调度策略下的任务分配算法.通过分析核间任务阻塞对任务最坏情况响应时间产生的影响,提出由于任务间共享资源冲突而引发了任务分配故障问题;指出负载非均衡算法,如First-fit算法、Best-fit算法容易引发任务分配故障.为了避免该问题,提出基于分组与负载均衡的任务分配算法.该算法将存在访问共享资源冲突的任务分配到同一核上,以避免核间任务阻塞;当这些任务无法分配到同一核上时,将这些任务依次分配到当前负载最轻的核上以避免任务分配故障.可调度性分析实验表明,采用该算法可以避免任务分配故障,减少分配任务所需的处理器核数(比Worst-fit算法少10%～40%).     

基于熵矩阵的多目标非线性0-1规划近似算法

为了简化多目标二元匹配问题的求解,将该问题建模为多目标非线性0-1规划模型,该模型将变量约束转移到目标函数中,从而降低了问题求解难度.针对该模型,设计了基于熵矩阵计算的贪心近似算法,该算法通过熵矩阵的熵值计算确定多目标二元匹配度,并根据熵值的大小预先优化匹配顺序,从而使近似解更快速地接近最优解.仿真实验结果证明,对于单目标非线性0-1规划问题,本算法优于已有的近似算法,对于多目标非线性0-1规划问题,本算法在计算时间以问题规模的指数级减少的情况下,近似解能够很好地逼近最优解.因此,本算法与其它近似算法相比,在不增加时间复杂度的前提下,结果更优,近似度更高.     

无人机群变航迹多任务综合规划方法研究

将无人机群作为一个整体,对任务和航线进行综合规划有利于提高效率,减少油耗。为了缩短机群的任务完成时间,减少飞行航程,提出了一种启发式的任务和轨迹综合规划方法。通过将各无人机的任务执行时间趋于均衡以减小机群任务的总完成时间,同时兼顾同一无人机执行的多个任务在路径上的相邻,使得机群的总飞行航程得到缩短,从而减少了油耗。仿真试验表明,任务轨迹综合规划算法与仅考虑航线或任务执行时间的算法相比较,机群的任务完成时间减少了18%左右,提高了无人机群的工作效率,减少了油耗。     

全双工能量受限中继网络的安全波束成形设计

为了解决全双工能量受限中继网络的无线物理层安全问题,提出了一种基于能量和信息联合传输的安全波束成形方法.在满足中继节点和能量收集节点收集能量的约束条件下,通过联合优化能量信号协方差矩阵、波束成形矩阵和功率分配因子,实现了系统安全速率最大化.目标问题是非凸的,采用分步优化方法将原始问题转化为2个子问题.将第1个子问题转化为双层优化问题,外层优化问题采用一维搜索求解,内层优化问题采用半定松弛技术解决;然后通过一维搜索得到第2个子问题的最优解.仿真结果表明,提出的方法显著提高了系统的安全速率.     

高寒地区新建庆哈输油管道生产运行参数优化

对输油管道进行生产运行参数优化,可有效降低运行能耗,提高管道输送的经济效益。针对高寒地区新建庆哈输油管道,以生产运行能耗最低为目标,以温度约束、压力约束、输油泵工作特性约束等为约束条件建立了生产运行参数优化模型。为提高求解效率,采用混合PSO⁃Powell算法对该模型进行求解。优化结果表明,优化后热能损失降低了38.3%,压能损失升高了90.3%,总能耗损失降低了26.3%,节能效果明显。     

基于粒子群优化的无线Mesh网络信道分配算法

多信道多天线（MCMR）广泛被用于提升无线Mesh网络的性能,但现有信道分配算法存在两方面问题:算法的时间太长和空间复杂度过高,无法获得全局最优解;算法可扩展性差,无法适用于大规模的网络。为解决上述问题,该文借鉴粒子群优化算法在收敛快、开销小等方面的优势,以建模无线Mesh网络中的信道分配问题。通过网络信息的交换和干扰模型的定义,以最小化适应度函数为优化目标,以天线、可用信道数量、信号干扰等为约束条件,设计并实现了基于粒子群优化的信道分配算法（PSOCA）。仿真实验表明了算法的可行性,且与同类算法相比,该算法在网络吞吐量和丢包率两个方面具有明显的改善。     

基于最小流量的液压机械臂冗余分解

针对冗余液压机械臂预设轨迹下的能量优化问题,提出基于最小流量的液压机械臂冗余分解方法. 采用D-H参数法推导液压机械臂的运动学方程,构建末端速度与液压缸缸速的映射,建立系统能耗模型. 基于最小缸速范数法求解能量次优的冗余分解以部分降低能耗. 以液压系统流量最小为目标,通过优化加权雅可比矩阵求解能量最优的冗余分解. 为了提高计算效率,提出加权雅可比矩阵权值的动态优化方法,实现在线最优运动规划. 在研制的液压机械臂试验平台对冗余分解方法进行试验验证. 三关节平面运动试验结果表明,相比于现有梯度投影法和最小缸速范数法,所提最小流量优化方法相同末端轨迹的运动能耗降低超过5%.     

云数据中心面向实时任务的节能调度算法

针对云计算环境下的独立实时任务的节能调度问题进行了研究,设计了一种基于松弛时间的任务调度算法,该算法由实时任务的分配、虚拟机资源的动态扩展以及虚拟机的动态整合3个部分组成,通过计算任务的松弛时间保证任务在截止期限内完成,保证任务的时效性. 同时提出了一种基于多阈值的虚拟机整合策略,以平衡系统负载并降低系统完成任务集合的能耗. 实验表明,与其他算法相比,该算法在保证了任务能够按时完成的基础上,有效降低了系统的整体能耗.     

并行产品开发中任务智能分配

为了实现并行开发中任务分配的优化与智能算法.运用任务之间的并行度构造了项目C-DSM模型;通过任务序列分解把项目C-DSM模型所描述的复杂任务序列简化为一个或多个简单任务序列;使用"任务-团队匹配矩阵"实现问题领域遗传算法的二维编码;基于遗传算法的基本原理,运用"任务-团队效率矩阵"、"并行层次深度"、以及"开发团队成本列表",开发了一种面向并行开发任务智能化分配的解决方案.最后通过一个实例对该解决方案进行了可行性验证.     

Voltage island-driven multilevel floorplanning optimization algorithm

Since the existing multiple voltage floorplanning algorithms are slower and generate a higher white space, a voltage island-driven multilevel floorplanning optimization algorithm is proposed. Firstly, an ILP(Integer Linear Programming)-based approach is used to assign the voltage to each module aiming at minimizing power consumption, and all modules are divided into different voltage islands according to their voltage assignment results. Secondly, a rapid method based on enumeration and shape curve adding techniques is proposed to determine the shape and position of each voltage island. Finally, an LP(Linear Programming) model is constructed to solve the wirelength optimization problem by exchanging blocks' positions. Experimental results show that our algorithm outperforms previous methods in runtime and chip area usage ratio.     

异构网络中几乎空白子帧存在时干扰协调方法

针对异构网络中几乎空白子帧存在时用户接入选择和资源分配方法过于复杂的情况,以及吞吐量需求难以得到满足问题,以最大化系统总吞吐量为目标提出一种易于实现的蚁群算法.在考虑不同用户不同需求的前提下,根据微基站用户在几乎空白子帧和正常子帧时受到干扰的不同,把一个微基站划分为两个虚拟基站,将所存在的问题建模为广义分配问题进行求解,同时解决了用户接入选择和资源分配问题.仿真结果表明,所提出方法与参考文献方法及两种增强型小区干扰协调固定配置结果相比,可以有效提高系统总吞吐量,同时兼顾小区边缘用户吞吐量,实现了良好的综合性能,能够更好地满足用户需求并在实际系统中易于实现.