云环境下基于双重公平性约束并行调度算法的研究与实现

目前并行调度和资源分配一般只注重效率,但是云计算需要给各用户提供多种不同服务,所以需要高度关注用户需求满足度.提出一种基于云计算环境下的并行作业调度算法,该算法对传统并行作业调度算法仅仅注重效率的特点进行了改进,关注资源分配的公平性、任务的完成效率和用户服务质量以及系统的负载均衡性,能够适应云计算的虚拟化和商业化特性,并实现在云计算环境下的并行作业调度中形成双重公平性约束.在注重效率的同时,突出资源分配的公平性.     

基于启发规则的双向冲压生产线调度研究

根据冲压车间生产的无等待并行流水作业的特点,提出了一种基于启发式规则的双向冲压生产线的调度模型.在该模型中,建立在满足工序约束、机器约束、无等待约束等约束条件下的优化模型,提出了冲压作业的重复、折回和前行等排程规则,解决在冲压作业调度中的机器占用冲突问题,保证得到可行的调度解.并设计嵌入启发式规则的混合遗传算法来进行求解.最后通过一个例子对调度模型和求解算法进行了验证.     

多技能资源投入项目调度问题的建模与优化

以大型工业品移动装配线为实际背景,针对多技能人力资源投入成本问题,建立了以最小化资源投入成本为目标的数学模型.针对该模型,提出了基于全局作业影响的改进调度机制的遗传算法,设计最小费用最大流多技能资源分配算法解决资源分配问题,通过基于全局资源水平影响的作业调度评估策略优化非关键作业的调度位置.最后利用改造的标准算例库PSPLIB进行数值试验,通过与CPLEX和文献算法对比,验证了本文算法的有效性.     

网格系统中的层次化资源分配与任务调度

讨论具有大量任务数的一类应用在网格系统中的资源管理和控制问题．提出了具有层次化结构的资源分配与任务调度模型，它由任务分发器和次级调度器组成．上层的任务分发器根据任务的性质和需求，并参考下层次级调度器的执行情况，将任务分发到相应的次级调度器上；而下层次级调度器负责将分发来的任务进行实际的资源分配及调度工作．模拟分析表明随着次级调度器个数的增加，任务调度的并行性增加，但系统的优化趋势逐步减缓．在实际应用中，合理选择次级调度器个数，可在满足调度性能的同时减少设备投入．     

网格计算环境下基于PERT方法的调度算法

在网格计算的资源分配过程中,一般基于费用-时间的DAG调度算法中的假定作业执行时间是确定的,为了解决这一局限性,提出了在网格计算的资源分配中使用基于计划评审技术的调度算法.采用PERT方法中的三时估计法及GridSim仿真软件包进行算法实现,通过用户任务完成时间的概率分析,证明该算法具有较强的实用性.     

基于BACKFILL的"削足适履"并行作业调度算法

BACKFILL方法在并行作业调度时并不能有效地的利用CPU资源.在BACK-FILL的基础上,提出一种“削足适履”算法.利用CPU的空闲空间作为判断依据,扩展了可参与填充操作作业的数量,“削足适履”算法通过合理修改队列中作业的参数-CPU数量和运行时间,将BACKFILL算法无法处理的作业填充到空闲的CPU空间中,弥补了BACK-FILL算法的不足,提高了并行系统作业调度CPU利用率.     

一种并行的网格资源协同分配方法

针对网格系统中资源协同分配的实时性问题,分析了现有的基于有向无环图的资源映射方法,提出了一种并行资源协同分配算法.该算法采用有向无环图表示每个应用,然后,将所得到的这些图合并成一个有向无环图并对其进行分层,最后,对每层中应用任务的资源分配问题并行处理.分析表明,该并行资源协同分配算法降低了系统中资源调度时间,提高了资源分配的效率,从而能够满足系统实时性要求.     

基于同贝同步装卸的岸桥与集卡联合调度优化模型

为解决岸桥同贝同步装卸时多环节作业协调问题,加速集装箱在码头内部的周转,研究基于岸桥同贝同步装卸作业的岸桥与集卡联合调度问题.以船舶装卸完工时间最短为目标,建立岸桥与集卡联合调度优化模型,优化岸桥与集卡的任务分配及作业序列.岸桥同贝同步装卸增加了集卡作业环节,不同于传统作业时多阶段混合流水车间问题,其模型更加复杂,求解更加困难.针对大规模问题,设计了启发式算法进行求解,并将求解结果与下界值进行对比分析.结果表明,该启发式算法能有效提高岸桥与集卡联合调度模型的求解速度,有助于提高岸桥同贝同步装卸作业效率,为码头实际作业提供依据.     

Hadoop下基于资源感知的调度算法

在大规模的数据中心中,I/O型作业和CPU型作业通常会同时在同一集群上运行,他们之间所需要的资源是互补的.现有的Hadoop调度算法并没有对这两种工作的并行化进行研究,针对这点不足,提出了基于资源感知的调度算法,对作业负载和节点负载进行合理的分类和调度,解决因为资源竞争和不合理调度而影响处理速率的问题.对该算法进行实验及性能分析,在验证了算法在作业完成时间和系统吞吐量方面有很大改进.     

面向异构集群的作业调度与资源分配研究

提出一种面向异构集群的作业调度与资源分配策略,在异构资源实时监控的基础上,实现了作业的有效调度,进而在作业执行阶段,采用基于二部图的最小权匹配的资源分配算法,实现异构资源到执行任务的合理部署与配置.以医学科学计算为背景,搭建了异构云计算环境,并进行了仿真实验.实验结果显示:提出的算法实现了预期的目标,有效弥补了现有同构作业调度算法的缺陷与不足.     

基于虚拟集群在线迁移的虚拟化资源整合算法

针对虚拟集群内部关联性和并行作业的运行特点, 基于虚拟集群在线迁移机制, 提出一种虚拟化资源整合算法. 先对系统建模, 描述云计算环境下的虚拟化资源整合问题; 再使用区域划分法对异构资源分类, 从而初步降低问题的规模和求解难度; 最后提出在同构子域中进行虚拟集群迁移的FFD_grp算法. 采用同种负载和多种资源分配方法模拟多种资源使用情况, 并对该方法进行验证. 实验结果表明,  FFD_grp算法能显著提高资源整合效果, 有利于抑制资源碎片的产生.     

带有学习效应和加工时间可控的排序问题

考虑了带有学习效应和加工时间可控的交货期窗口的单机排序问题。工件的加工时间是关于所分配资源的线性函数或凸函数。其中每一个工件均有一个交货期窗口且窗口大小相同,若工件在窗口之前或之后完工则会产生相应的惩罚,若工件在窗口中完工则无惩罚,目标是通过极小化包括提前,误工工件数、窗口的开始时间、窗口大小和资源消耗的总惩罚函数确定工件的最优排序、最优加工时间和最优资源分配量。在加工时间是线性资源函数的情况下,通过将问题转化为一系列指派问题,构造一个多项式时间算法;在加工时间是凸资源函数的情况下,构造了一个在多项式时间内可解的动态规划算法。     

一个综合性集群监测模型MCM的设计与实现

根据已有的网络监测技术, 提出一个集群系统监测模型MCM. MCM将每个监测任务交给一个监测模块, 并可以灵活地加入和删除这些监测模块, 这种设计使得MCM可以有效地支持对分布式计算资源、 服务以及异常事件的监测. MCM为集群资源管理, 跨域并行作业, 网格资源协同分配和元调度算法提供了资源监测基础设施. 最后, 基于MCM和Platform公司的集群产品EGO, 实现了一个高效的综合性集群监测系统.     

带有准备时间和退化维护的单机排序问题

研究带有可变加工时间、准备时间和退化维护的公共交货期与凸资源分配的单机排序问题.工件的实际加工时间是关于所分配的不可再生资源量和与工件位置有关的退化效应的函数,并且在每个工件加工之前都有一个准备时间,它是有关资源分配的凸函数.为了消除机器的退化,在规划时间内最多允许执行一次维护活动.在资源总量有限的条件下,确定最优工件排序、最优公共交货期、最优维护位置和最优资源分配方案,使得由工件的提前惩罚、延误惩罚、公共交货期和最大完工时间构成的总费用最小.根据优化的相关知识,将问题转化为匹配问题,给出了该问题的启发式算法.     

计算网格多拍卖师系统中的3个关键问题

采用多拍卖师机制, 使用拍卖方式对计算经济网格内的资源分配进行管理. 对拍卖师系统中的3个关键性问题： 防止拍卖师欺骗（包括拍卖师欺骗的判定及处理）、 拍卖师的选择和成交价格的制定进行研究并提出相应的解决方案. 使用网格建模和模拟工具GridSim模拟网格环境, 并运用多拍卖师系统进行资源管理和任务调度实验, 对不同条件下的实验结果进行分析, 验证了计算网格多拍卖师系统的可行性.     

Fermi架构下的SPSO算法加速

利用新的图形处理器架构重新评估利用可编程图形处理器加速标准粒子群优化算法的可行性和有效性. 针对新的图形处理器架构进行系统分析, 在此架构下实现了标准粒子群优化算法的并行版本. 实验结果表明, 通过合理运用新的图形处理器架构, 与其他标准粒子群优化算法的并行版本相比, 取得了良好的加速比.     

一种基于遗传算法的OFDMA系统的跨层资源分配

针对现有的跨层资源分配算法计算量大、复杂度较高的问题,提出了一种基于遗传算法的OFDMA系统的跨层资源分配算法。利用遗传算法隐形并行处理、较好的全局搜索性能、易收敛到最优解的特点,在系统性能一定,且满足各个用户业务要求的条件下,对资源进行优化分配,较好地解决了跨层资源的分配问题。仿真结果表明,在满足用户间公平性的前提下,算法有效提高了系统的频谱利用率及吞吐量,减小了用户的平均等待时延,提高了服务质量,并且随着子载波数和用户数的增加,算法在复杂度方面优势更突出。     

基于CMP的多种并行蚁群算法及比较

基于片上多核处理器(Chip Multi-processor,CMP)的多种并行蚁群算法,包括并行最大最小蚂蚁系统、并行蚁群系统及两者的混合等5个并行算法,提出一种在CMP的每个处理器核心上模拟一个子蚁群,整体蚁群共享同一信息素矩阵,实现信息素隐式交流的方法.用多线程实时优先级实现该算法,并用若干旅行商问题实例进行了测试,分析了不同并行策略的影响.测试结果表明,基于CMP的并行蚁群具有相对于核心数目的线性加速比,异种蚁群混合策略在解的稳定性上更具优势。     

速度相同的具有m-2台通用机的两组工件的LS算法分析

对于实践中存在的具有两组任务的优化排序问题进行了讨论,在经典的LS算法的基础上提出了一种改进的LS算法,利用"首先空闲"准则选择机器,按照工件的到达顺序安排工件,讨论了将两组工件安排在两台速度相同的专用机,m-2台同速度的通用机上的Cm ax问题,其中工件具有准备或到达时间,且工件的准备或到达时间均不超过其加工时间的α倍。目标是在最短的时间内完成所有给定的任务。得到了利用该近似算法所得的解TLS与最优解T*的一个估计(1+α)(2-1/m),并且证明了对任意的α此界是紧的。