数据中心网络流量调度的研究进展与趋势

近年来,流量调度已经发展成为网络领域的热点研究问题.该问题主要决定何时以及以多大速率传输网络中的每条数据流,其对网络性能和应用性能都具有十分重要的影响.然而,在托管着许多大规模互联网应用的数据中心中,流量调度问题正面临着流量矩阵多变、流量种类混杂、以及流量突发等与流量模型相关的挑战.此外,随着数据中心规模的不断壮大,流量调度问题还面临着网络带宽动态化、网络拥塞随机化、以及网络目标多样化等与网络模型相关的挑战.为了进一步提升对数据中心流量调度的关注和理解,推动流调度技术在实际应用中的不断发展,本文分别从调度目标、调度方式和调度对象这三个维度对数据中心网络流调度的相关研究工作进行了分析和对比,并概括出如下结论:现有研究主要以分布式、集中式或混合式的调度方式对数据中心内、数据中心间或数据中心与用户间的流进行高效地调度,从而达到带宽保障、时限保障、最小化流完成时间、最小化Coflow完成时间、公平性保证、最小化流传输成本等目标.本文最后还指出了四个数据中心流调度的未来发展方向,并相应提出尚未解决的研究问题.     

并行机成组调度问题的启发式算法

研究了优化目标为总拖后/提前时间最小化的并行机成组调度问题,提出了一种三阶段启发式近似求解算法。首先把并行机问题看成单机问题,以最小化总拖后时间为优化目标排列工件的加工次序;然后将工件按第一阶段所求得的次序指派到最先空闲的并行的机器上;最后采用改进的GTW算法对各机器上的工件调度插入适当的空闲时间。计算表明该算法能够在很短的时间内给出大规模调度问题的近似最优解。     

改进人工蜂群算法求解分布式柔性作业车间调度问题

针对分布式柔性作业车间调度问题的特点,提出一种改进人工蜂群算法.首先,建立以最小化最大完工时间为优化目标的分布式柔性作业车间调度优化模型;然后,改进基本人工蜂群算法以使其适用于求解分布式柔性作业车间调度问题,具体的改进包括设计一种包含三维向量的编码方案,结合问题特点针对性地设计多种策略用于种群初始化,在雇佣蜂改良搜索操作中设计多种有效的进化操作算子,并在跟随蜂搜索操作中引入基于关键路径的局部搜索算子以提升算法的局部搜索能力;最后,利用扩展柔性作业车间通用测试集得到的测试数据设计实验验证算法性能,使用正交试验法优化算法参数设置.仿真实验结果表明,改进后的人工蜂群算法能有效求解分布式柔性作业车间调度问题.     

多AGV和机器集成的多目标柔性作业车间调度研究

为解决智能制造环境中具有多时间和多AGV约束的柔性作业车间调度问题,构建了以最小化最大完工时间、最小化总延期、最小化设备总负荷为目标的机器/AGV双约束多目标调度模型,模型中综合考虑加工时间、工件到达时间、交货期等多时间因素,进行了多AGV和机器集成调度。为求解该模型,设计了新的AGV调度规则和改进的NSGA-算法,算法中提出了基于工序的扩展染色体编码方式和基于AGV分配的贪婪式解码策略,同时设计了不同参数控制的多种群二元锦标赛选择和分段交叉变异策略以及基于Pareto级的去重精英保留策略,以促进个体协同优化搜索。通过实例实验,分析了不同AGV数量任务分配方案下的模型有效性,对4个案例的仿真测试和同类算法比较解也验证了改进NSGA-算法求解该模型的有效性。     

基于AGV的管道加热器柔性作业车间调度方法研究

针对基于AGV约束的管道加热器柔性作业车间调度问题,以最小化最大完工时间和最小化车间总负载为目标,提出改进麻雀搜索算法求解调度方案;建立合理的编解码方式表示调度方案;为解决多目标优化问题,引入Patero排序;考虑麻雀搜索算法求解离散优化问题时无效解较多、易陷入局部最优等缺陷,提出引入交叉变异算子、设置精英种群、设计自适应种群比例因子等改进措施;根据标准算例数据及实际车间生产数据对算法可行性进行验证,结果表明改进算法可有效求解合理的调度方案,相比于车间原生产方案,生产效率提高19.6%,且有效降低了车间总负载。     

面向柔性作业分布式车间的分层调度模型研究

针对多车间分布式制造系统调度优化问题,结合车间实际生产情况,提出一种基于目标级联法和遗传算法的层次调度模型。模型将生产调度过程划分为生产计划层、车间调度层和零件规划层,并将整体时间最短的优化目标划分到各个层次,通过层层优化达到时间最优后反馈至上层,以实现整体调度时间最优。以3个制造车间协调调度问题为例,验证了该模型在零件分配和零件的工艺路线选择上的合理性和有效性。     

求解区间数分布式流水线调度的混合离散果蝇优化算法

分布式调度是制造系统领域的前沿研究,而不确定调度问题的研究更具现实意义.针对不确定分布式置换流水线调度问题,采用区间数表示工序加工时间,以最小化区间最大完工时间为目标,利用问题特性在果蝇优化框架内提出一种混合离散果蝇优化算法.首先,通过改进启发式方法和随机方法混合初始化种群;然后,基于概率协同多搜索操作执行嗅觉搜索.为了平衡算法的全局探索与局部开发能力,设计基于学习机制的双种群协同搜索环节.为了进一步提升种群性能,针对优良解设计基于切换机制的双模式局部搜索.基于大量算例的仿真结果与统计对比,表明所提出算法能更有效求解区间数分布式流水线调度问题.     

双种群混合遗传算法求解具有预防性维护的分布式柔性作业车间调度问题

在实际生产过程中,生产调度和设备维护相互影响,因此两者应该统筹优化.为研究具有预防性维护的分布式柔性作业车间调度问题,以最小化最大完工时间为目标,提出一种双种群混合遗传算法.结合问题特性,设计三维编码以及对应的机器解码方案,采用不同的策略初始化种群以均衡一部分工厂负载,为双种群设计不同的交叉变异算子提高算法的多样性,并利用交换精英解的方法实现两个种群的协作优化,同时针对关键工厂和预防性维护操作设计相应的局部搜索.最后对比现有算法,在同构和异构工厂的算例上进行实验,使用正交试验法优化算法参数设置.实验结果验证了局部搜索以及种群协作的有效性和双种群混合遗传算法求解具有预防性维护的分布式柔性作业车间调度问题的优越性.     

面向多停泊基地的港口拖轮调度优化研究

拖轮调度是典型的多处理器任务调度问题,针对多停泊基地和不同作业模式下的拖轮调度,以最大完工时间和总作业油耗最小化为目标,建立了拖轮调度多目标优化模型。采用演化策略算法对多停泊基地拖轮调度优化问题进行计算,提出一种基于轮盘赌概率分配的编码和解码方法。计算结果表明了演化策略算法的有效性和可行性,优化后的最大完工时间最小值相比仿真运行结果取得较大的改善,不同作业模式下均减少了约16%;计算结果还表明不同作业模式对拖轮调度结果会产生较大影响。     

基于多维EDA算法的低碳分布式装配流水车间调度

针对低碳分布式装配置换流水车间调度问题(LC_DAPFSP),建立以同时最小化总能耗和总完工时间为优化目标的数学模型,进而提出一种多维分布估计算法(MEDA)以进行求解.首先,采用随机方法和启发式算法共同生成初始化种群;其次,建立基于矩阵立方体的概率模型,用于合理学习并积累优质解的块结构信息和序关系信息,同时设计有效采...     

基于最小机器数的柔性作业车间调度研究

针对期望以最小机器数完成生产的柔性作业车间调度问题,建立了最小化最大完工时间为内层目标,最小机器数为外层目标的双层优化模型,即在满足交货期、最小化最大完工时间的条件下,尝试减少机器数量,以寻求车间调度的最少机器数.依据模型、算法特点,设计了一种基于大变异策略的遗传算法,该算法采用二维染色体编码、顺序选择策略,同时运用优...     

求解加热炉调度的改进修复式约束满足算法

针对钢铁生产中加热炉调度问题,考虑炉容受限的情况,以最小化板坯的Makespan和最小化总在炉加工时间为目标建立问题的多目标优化模型,将其归结为多旅行商问题。针对问题的NP-难特性,提出一种改进的修复式约束满足算法求解。松弛炉容约束得到初始调度,在检测冲突变量并构造冲突板坯的可替换加热炉集合的基础上,以开工时间偏移最小规则为冲突板坯重新指派加热炉,得到可行的调度方案。数据实验验证了模型和算法的可行性和有效性。     

基于深度强化学习的随机资源受限多项目动态调度策略

目前对于随机工期的分布式资源受限多项目调度问题（SDRCMPSP）的研究较少且大多数为静态调度方案,无法针对环境的变化实时地对策略进行调整优化,及时响应频繁发生的动态因素。为此建立了最小化总拖期成本为目标的随机资源受限多项目动态调度DRL模型,设计了相应的智能体交互环境,采用强化学习中的DDDQN算法对模型进行求解。实验首先对算法的超参数进行灵敏度分析,其次将最优组合在活动工期可变和到达时间不确定两种不同条件下对模型进行训练及测试,结果表明深度强化学习算法能够得到优于任意单一规则的调度结果,有效减少随机资源受限多项目期望总拖期成本,多项目调度决策优化提供良好的依据。     

基于遗传算法的多工序多机器调度优化研究

随着人民生活质量的提高,消费者对定制化生产提出了更高的要求,此外,在新的经济环境下,降本增效对于提升制造企业的发展能力具有重要的意义,基于此,本文提出了基于遗传算法的多工序多机器调度优化研究。首先,设计了基于完工时间最小化的多工序多机器加工约束的生产调度优化模型;其次,采用遗传算法设计了求解上述生产调度优化模型的算法;最后,通过案例验证了本文构建的优化模型及设计的优化算法,并绘制了以最小化完工时间为优化目标的生产调度甘特图。研究结果表明,本文构建的模型及设计的算法具有一定的实用性,可指导企业制定较优的生产调度方案。     

融合局部搜索与Pareto支配的多目标任务调度模型

为了解决复杂任务群调度过程中资源利用不均、任务完成时间较长等问题,以最小化资源负载均方差和最小化任务群完成时间为目标构建复杂任务群资源调度模型,提出一种融合局部搜索和Pareto支配的多目标优化算法BRLSN（multi-objective optimization based on boundary range local search and NSGA-Ⅱ,BRLSN）。该算法采用有效的编码方式与交叉变异算子进行迭代寻优,并利用基于边界区域局部搜索的精英保留策略扩大算法搜索范围,保存种群优良个体。实验结果表明BRLSN相较于其他多目标算法在收敛性和多样性上有显著的提升,同时算法收敛速度更快,种群质量更高,明显优化了最终目标函数的结果值。     

混合并行机调度问题的多目标优化模型及算法

针对生产工序的合并造成一种串并联共存的生产布局,研究了一种特殊的混合并行机调度问题,并考虑以最小化总流水时间和最小化总延迟工件数量为目标的多目标调度问题,建立了混合整数规划模型.针对模型特点,设计了一种改进的非支配排序遗传算法进行求解,采用基于启发式方法的初始种群生成方式以提高种群的质量和多样性,并引入一种局域搜索策略以改善求解算法所获得的非支配解的质量及分布性.通过对大量数值算例进行仿真实验,并与典型的多目标优化算法进行比较,结果表明所提出的模型和算法在收敛性、分布性及极端点质量方面均具有优势,能够较好的解决多目标混合并行机调度问题.     

蜜蜂交配优化算法在车间作业调度中的应用

为了解决车间作业调度问题,在对其进行分析描述的基础上,提出了采用蜜蜂交配优化算法的求解方法。该方法把由多个作业调度方案组成的集合作为蜂群,以最小化加工时间作为算法的优化目标,通过模拟蜂群交配繁衍培养蜂王的优化过程来获得最优作业调度方案。采用车间作业调度测试案例在Matlab平台上进行实验,实验结果表明,该方法不仅能够有效地求解车间作业调度问题,而且能够取得了比传统优化方法更好的优化结果。     

一种面向网络边缘任务调度问题的多方向粒子群优化算法

任务调度是云计算及网格计算环境中的重要问题,已有的调度算法往往仅致力于最小化任务的总执行时间而不设置其他约束条件,以致难以实现多种性能指标的同时优化。所提出的面向网络边缘任务调度问题的多方向粒子群优化算法,用于解决并发任务在网络边缘服务节点中的分布式调度问题,调度的目标是在任务执行的资源开销不超过阈值的情况下,最小化任务完成的总时间。该方法与现有的离散粒子群优化算法相比同时降低了任务的总完成时间及资源开销,且在合理预设资源开销上限的情况下,其计算复杂度实现了较大程度优化。仿真表明,所提出的方法比现有的离散粒子群优化算法的任务总完成时间缩短约10.52%~13.23%,资源开销减少约10.32%~13.29%。同时,在合理降低资源开销阈值的情况下,该方法的程序运行时间比现有的粒子群调度方法明显缩短。     

基于改进遗传算法的分布式电源并网优化配置

随着国家电网对分布式电源并网市场的开放,将分布式电源集成到现有配电系统是今后电力系统的发展趋势。以配电网网损和节点电压偏移最小化为优化目标,考虑支路电流约束、分布式发电单元容量和总接入容量等约束条件,构建大规模分布式电源并网优化配置模型。并提出基于均匀设计的改进遗传算法进行寻优计算,避免了遗传算子的盲目试凑,可以较好地兼顾多目标优化Pareto解集的多样性与快速性,有效提高优化精度。算例对比分析结果表明,通过对分布式电源接入配电网的合理优化配置,可以有效降低系统网损,提高配电网电压的稳定性。     

基于作业链的泊位与岸桥协同调度研究

针对泊位与岸桥协同调度问题,引入"链式优化"思路,用作业链的方法分析集装箱装卸作业过程,首先将泊位计划作为开始链单元,采用资源节点优化策略进行分析,以最小化船舶在港总成本为目标建立模型;然后将岸桥卸船作业作为结束链单元,采用任务节点优化策略进行分析,以最小化岸桥最大完工时间为目标建立模型.考虑到作业链的整体性能,设计嵌...