资源空窗期及任务可拆分的资源投入问题研究

考虑飞机装配过程中任务可拆分及资源存在空窗期的两大特性,对飞机移动生产线资源投入问题进行模型与算法研究.针对部分任务存在已知拆分模式及拆分惩罚的情形,设计了求解该问题的改进遗传算法,对传统实数交叉操作进行优化,提出了基于染色体适应值的交叉方法,并在数值实验中对相关参数的取值范围进行了敏感性分析;同时,提出了基于任务开始时间选择概率的变异机制.对满足优化条件的任务调度方案,结合空窗期的位置,评判各可拆分任务可否通过选取新的拆分模式重新调度执行,对不同情形进行总结归纳,通过局部操作进一步降低目标资源量.数值实验表明:通过本文算法对求解带资源空窗期的任务不可拆分问题与基本问题的结果对比,得到任务数分别为10、16、30、60、90算例的目标值平均增量达到4.3%;对求解本文问题与任务不可拆分问题的结果对比,平均优化率达3.5%,证明了本文算法的有效性,同时证明将任务拆分纳入考虑资源空窗期的资源投入问题中,可提高问题求解的灵活性,从而获得较好的调度结果.     

带资源空窗期的资源投入型问题的建模与优化

以飞机移动式装配线为背景,在基本资源投入型问题的基础上考虑资源空窗期约束,建立以最小化资源使用总成本为目标的数学模型.针对该模型设计了一种构造启发式算法,并提出了非关键任务优先级决策规则.考虑空窗期约束特点,以连续排入的两个非关键任务间结果最优的启发式规则来确定非关键任务位置,并提出以非关键任务优先级和关键任务开始时间为双链表编码的遗传算法,然后将启发式规则嵌套在遗传算法的解码和评估阶段.最后通过数值实验比较启发式算法和遗传算法与CPLEX在求解该问题时的优劣,证明了两种算法的有效性.     

基于项目拆分决策的多模式资源投入

结合一类实际生产决策需求,提出了基于项目拆分决策的多模式资源投入调度问题,并以资源投入最小化为优化目标,建立了问题的数学模型.针对模型特点,提出了包含项目拆分算法和多模式资源投入型项目调度算法的双层优化算法,其中项目拆分算法通过将作业在不同子项目之间有效移动获得合理的拆分方案,多模式资源投入型项目调度算法通过分析不同作业对时间约束和资源约束的影响来确定优先级规则,进而得到最佳调度方案.应用PSPLIB标准算例进行数据实验,结果证明了算法的有效性和可靠性.     

基于子集模拟的建设工程项目多资源均衡优化算法

为高效、稳定地求解建设工程项目管理过程中的多资源均衡问题,提出一种基于子集模拟的优化算法.多资源均衡问题中,如直接采用工序计划开始时间作为决策变量,在优化算法的实现时易违反工序间的逻辑关系.为避免该问题,本文采用工序计划开始时间的间隔率变量表示(在二者的映射中考虑工序间的逻辑关系),并据此建立间隔率变量表示的建设工程项目多资源均衡优化模型,以简化基于子集模拟的优化算法的操作流程.通过算例验证,与目前应用较广的遗传算法相比,本文提出的优化算法在最优解的获取稳定性上有较大改进.     

基于信任驱动的网格资源调度算法

针对当前网格资源管理中作业与资源匹配的缺陷,基于信任效益函数和作业响应比,提出了同时兼顾性能QoS和信任QoS的资源调度算法.不仅考虑到作业资源对的信任考虑,还考虑到每个作业的性能QoS,解决了长时间等待作业不断被推迟运行的问题.实验表明,该算法较传统的Min-Min算法在总信任效益函数、总执行时间和作业提交失败率方面有较好的综合性能.     

基于网格资源可用度的元任务映射算法

针对Min-Min启发式算法没有充分考虑网格的异构特性,导致资源负载不均衡的问题,提出一种基于资源可用度的启发式映射算法,在元任务与资源映射过程中,先计算资源对元任务的可用度,然后将元任务划分为优先映射与次优先映射两部分,再对这两组元任务分别应用经典Min-Min算法进行映射.采用仿真软件模拟网格异构环境,在元任务与资源一定的情况下,分别模拟这两种算法的元任务与资源的映射过程,得到这两种情况下的任务完成时间.实验结果表明,基于资源可用度的启发式算法在异构的网格环境中任务完成时间更短.     

资源短时占用型作业调度算法

对资源短时占用型作业调度的问题给出了一个数学描述模型 ,并讨论了该问题求解的时间复杂性 .基于该模型提出了对不同情况最佳或近似最佳的实用的联机调度算法 ,并讨论了这些算法在其他类似问题上的应用 .     

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

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

一种实用的启发式资源平衡优化算法的改进

资源平衡优化问题即资源有限项目调度问题,是一个NP难问题,现在商用项目管理软件系统中的资源平衡优化问题多采用基于优先规则的启发式算法.通过定义一个新的作业集合和一个巧妙的修改动态参数的方法,使算法在实现上极大地减少了调度时间,进一步增强了启发式算法的实用性.     

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

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

基于思维进化的集群作业调度方法研究

为了减少不准确的时间估计对作业调度的影响,提出了动态预约调度模式.在该模式中,预约队列中的作业与被预约资源是松耦合的,可根据作业完成情况进行重映射,以减少作业提前完成而产生的资源碎片.基于动态预约模式,将思维进化计算引入到作业调度中,以各种回填算法的调度结果作为初始群体,通过趋同和异化操作,使群体不断向最优解进化,从而产生更优的调度方案.基于真实作业集的仿真结果表明,所提算法的作业平均的等待、延迟时间比最优的基于回填的组合算法分别下降了68.5%和66.95%.     

考虑排班的人力资源投入问题的建模与优化

结合实际生产或项目中的排班情况,提出考虑排班的人力资源投入问题。针对该问题建立了以最小化人力资源投入为目标的数学模型。根据资源投入量与排班约束的性质,将原问题数学模型简化,证明简化后问题的数学模型与原问题最优解一致,并通过CPLEX软件求解过程,说明简化后的数学模型在求解速度上表现出很大的优越性。对于大规模问题,由于排班约束会导致班次间资源占用,使用传统任务列表编码方式难以获得较优的解。为此,提出了一种新型编码方式的遗传算法。该算法采用对作业延迟时间进行编码的方式,对作业开始时间进行搜索。为了提升算法的局部搜索能力,对作业延迟时间和开始时间进行局部优化。最后,通过数值实验与CPLEX和文献的算法比较,表明该算法的有效性。     

基于项目网络拆分决策的多项目协同调度问题建模

以大型工业品资源共享型节拍式流水装配过程为背景,提出基于项目网络拆分决策的多项目协同调度问题.根据装配过程作业的周期性调度需求,将单个项目的作业集合划分成共享资源的多个并行执行的协同子项目,以最小化节拍时间为目标,建立了项目网络拆分与项目调度同时决策的数学优化模型,设计了一种双层循环迭代算法以对模型进行求解.算法的上层是基于有效时序约束数量的作业划分构造型启发式算法,可在多项目网络之间调整作业的从属关系;算法的下层采用基于优先规则的启发式算法对上层拆分后的多项目网络进行求解,并将调度结果反馈至上层,通过循环迭代不断优化项目来调度计划.数据实验结果表明,所提算法能够有效提高资源利用率,且其求解质量和效率较高.     

基于加工资源的零件分类成组研究

多品种、小批量生产模式导致频繁的切换,产生了大量作业切换时间并影响了生产效率.为了缩短作业切换时间,提出一种基于加工资源的零件聚类分组遗传算法.首先对加工零件所需资源进行分类,不同类别资源再划分子类,0-1整数编码表示加工是否需要该项资源;其次根据加工资源对于作业切换时间长短的不同影响,确定核心加工资源和一般加工资源的权重.采用Jaccard系数计算零件间相似度,应用分组遗传算法确定零件的分类成组.最后以M航空紧固件企业零件为例进行验证.结果显示,分组遗传算法比系统聚类极小值法和K-means聚类法更有效地缩短了作业切换时间和提高了生产效率,并减少了单位成本.     

资源短时占用型作业调度算法

对资源短时占用型作业调的问题给出了一个数学描述模型,并讨论了该问题求解的时间复杂性,基于该模型提出了对不同情况最佳或近似最佳的实用的联机调度算法,并讨论了这些算法在其他类似问题上的应用。     

Hadoop平台下基于资源预测的Delay调度算法

针对Delay算法的不合理等待问题, 提出一种基于资源预测的Delay调度算法（RFD）, 该算法基于对资源可用性的预测方法合理地调度作业. 实验结果表明, 在Hadoop机群一般应用场景下, 该调度算法与已有算法相比, 在保证作业本地化计算Map任务比例相近的同时, 将作业平均运行效率提高28.8%, 明显提高了Mapreduce作业的执行效率.     

具有服务优先级别的动态离散泊位调度优化

研究具有不同服务优先级别的船舶动态到达情形下的离散泊位调度问题.以泊位分派和船舶作业开始时间为决策变量,为优化码头作业效率和船公司客户满意度,以最小化船舶总在港时间与加权延迟时间之和为目标建立数学模型.采用基于修改后的先到先服务等规则的启发式算法生成初始解,以此为基础设计结合禁忌深度搜索和模拟退火算法框架的混合算法对问题进行优化求解.不同问题规模下的数据仿真试验表明,该算法可以快速、有效地解决此类问题.     

轨道路径约束的散货卸船机调度优化策略

基于对卸船机调度特征的描述,建立了以最小化卸载作业完成时间为目标的卸船机调度优化模型,设计了混合遗传算法组件以获得问题近似最优解,通过松弛原问题中的难约束,推导了松弛问题的下界并作为原问题的下界.同时,对具有不同规模的问题进行实例计算与分析.结果表明,所设计的混合遗传算法能够在可接受的计算时间内获得合理的解.     

基于蚁群算法的云计算并行机资源调度研究

研究在云计算中服务资源优化管理背景下,基于时间窗口的非等同并行机服务资源调度问题.为达到最大任务处理数,选取任务延误时间作为目标函数建立数学模型,并利用蚁群算法为模型求解.设计了该算法的各项参数,并通过仿真算例证实了该算法的可行性及合理性.结果表明:本算法能够较好地用于解决云计算中的并行机资源调度问题,以较快的收敛速度找到满足约束条件的较优解.     

基于经济模型的网格资源调度算法

建立了基于经济模型的网格作业调度系统,给出了相应的服务质量(QoS)资源调度算法.通过定义资源的多维QoS指标,实现了对计算网格中广域分布和异构资源的统一描述,能很好地适应网格资源的动态性和自治性.采用QoS偏好度排序和欧氏距离的优化策略搜索资源,将用户提出的具有个性化或总体服务需求的作业透明、动态地分配给最适应的资源,优化了资源的统一配置.采用仿真实验比较多种算法的性能,结果说明QoS算法可满足资源的自适应性,较好地实现全局资源调度的目标.