遗传算法在多资源优化调度问题中的应用

多资源项目调度中优化资源使用问题是在满足项目中活动之间的时序约束和资源约束条件下 ,使资源充分使用的调度方案 .针对资源均衡使用的优化目标建立了非线性数学规划模型 ,利用遗传算法进行求解 .仿真实例表明方法的有效性     

基于拓扑排序资源约束下多项目调度优化算法

多项目调度存在着工期和资源的竞争,调度时要考虑时序关系和资源受限两方面约束,启发式串行调度算法在每调度一个任务时都必须搜索项目的任务空间,为此提出了一种基于拓扑排序的多项目串行调度优化算法。此算法利用拓扑排序序列的特点保证任务时序关系,缩小调度时搜索空间,结合项目权重、向后影响度以及关键路径等优先规则进行资源分配和任务调度。通过具体实例验证了此算法可以求得项目调度的最优解并且能够有效地缩短调度计划生成时间。     

多模式资源受限项目调度问题的优化方法

为求解多模式资源受限项目调度问题,提出了一种结合粒子群优化算法（PSO）和基因表达式编程（GEP）的混合优化算法。其中,PSO用来提供活动执行模式组合,GEP用来构造在给定活动执行模式下的调度规则。调度规则由项目状态和活动属性构成,与其他优化方法相比,这是一种新的编码方式与求解方法,也更符合实际应用。对于粒子所表达的不可行活动模式的组合,设计了粒子调整算法,以满足项目调度中可更新资源和不可更新资源总数的约束。最后给出了混合优化算法求解步骤,并采用该算法对项目实例进行了计算与分析,验证了算法的有效性。     

考虑技能水平的多技能资源约束项目调度

针对带有技能水平的一般多技能资源约束项目调度问题进行扩展,将技能水平进行分级并将技能和资源各分为关键和辅助2类,考虑作业执行时间因分配的关键资源具备的技能水平而变.以最小化项目总工期为目标,建立相应的数学优化模型,提出包含双层决策及局部优化策略的混合算法.其中,上层的遗传算法用于决策表示作业执行顺序的优先级列表,下层的关键资源决策启发式算法用以确定作业实际执行时间并对上层列表进行解码得到问题的可行解.在所得可行解的基础上,采用基于关键链的局域搜索算法,调整资源分配以缩短关键链长度,保证算法的求解质量.数据实验表明,所提算法在求解质量和求解速度方面均具有良好性能.     

资源约束下多项目调度的迭代算法

项目实施过程中往往涉及到不同项目之间的资源共享与冲突,因此在资源受限的情况下如何调度项目以满足不同项目的资源要求并缩短各项目工期是一个重要的问题．在对该问题进行分析的基础上,建立了资源约束下的多项目调度问题的数学模型,并在单项目调度迭代算法的基础上进行扩展和改进,设计了多项目调度的迭代算法．该算法结合了串行进度计划生成机制和逆向算法的优点．在保证项目任务紧前关系与资源约束的条件下,能够合理优化多项目的资源分配,从而有效地缩短多项目的总工期．通过具体实例的应用和与其他算法的比较,说明了迭代算法可以得到较好的项目进度计划．     

基于改进智能水滴算法的双资源约束车间调度

为了解决多资源约束下的作业车间调度问题,提出了一种改进智能水滴算法.该算法采用了基于工序与加工机器相融合的两层编码方式建立问题和算法的映射关系,运用随机方法初始化产生可行解,结合精英保留策略加快算法的收敛速度,嵌入迭代局部搜索算法以增强算法的全局搜索能力,并来解决影响车间调度的3个主要成本因素,即最小化延期成本、最小化人工成本和最小化设备运行成本.通过实例的收敛性能对比,证明算法具有优秀的全局开发能力和收敛性.实验表明了该算法能够有效求解双资源约束车间调度问题.     

考虑空间约束的舰载机作业调度模型研究

舰载机的舰面调度是受空间限制的多任务复杂问题,是舰船完成作战效能的重要保证.本文分析了舰载机作业的基本流程以及甲板空间因素对舰载机作业的影响,将舰载机及其相关作业的调运空间和作业空间定义为资源,利用多模式资源受限项目调度问题研究方法,建立了资源受限舰载机机群调度数学模型.基于启发式算法完成了舰载机作业调度计划求解算法设计,并对给定算例进行求解.实例研究结果表明,该模型和算法可以为舰载机作业调度规划提供技术支持.     

一种求解资源受限项目调度问题的遗传算法

提出一种求解使用可更新资源的单模式资源受限项目调度问题的遗传算法．采用遗传算法对项目活动进行调度,在满足紧前关系约束和资源约束的条件下,最小化项目工期．继承了基于排列和基于优先级的编码方案的优点,提出一种新的基于优先权排列的编码方案．采用串行调度方法生成项目计划．使用PSPLIB中的标准问题库对算法进行了充分的数值实验,通过与既有算法进行比较,证明本文算法的有效性．     

资源受限多项目调度的混合遗传算法

针对资源受限多项目调度问题,提出了改进后的混合遗传算法.该算法基于串行进度生成机制,结合多项目任务列表与项目优先权设计了新的染色体,所设计的交叉算子与变异算子均能保证所得新个体满足项目紧前关系约束,从而有效提高算法搜索效率.算法充分利用不同启发式算法构造初始种群,有效扩大种群多样性以避免过早收敛.算法采用正向逆向调度技术对调度方案进行优化,进一步提高了调度方案的质量.与其他多项目调度启发式算法相比,该算法能有效分配资源,显著缩短项目平均总工期.     

云计算环境下多目标约束的虚拟资源动态调度

为了解决静态资源调度所导致的CPU利用率不高的问题,研究了多目标约束的虚拟资源动态调度方法。给出了云计算虚拟资源调度模型,设计了多目标约束的虚拟资源表示方法,采用马尔科夫链对虚拟资源的下一时刻状态进行预测,从而得到可用资源向量;最后,计算任务与可用资源向量之间的匹配向量,将任务分配给匹配向量中具有最大各维分量之和的虚拟资源进行调度,并提出了具体的采用基于马尔科夫链预测的云计算虚拟资源动态调度算法。实验结果表明:该算法能有效解决云环境下多目标约束的虚拟资源动态调度问题,具有较小的负载均衡离差和任务执行跨度,较其它方法具有较大的优越性。     

无等待流水线调度问题的混合优化算法

针对无等待流水线调度问题提出了一种混合离散化粒子群优化算法。通过建立位置矢量编码与调度方案之间的映射关系将连续的粒子群优化算法应用于离散的无等待流水线工件调度问题。为了提高离散粒子群算法的性能,增强算法的探索能力,在粒子群每次迭代之后对全局最优解加入随机扰动并进行变邻域搜索。仿真结果表明,该优化算法具有良好的性能。     

基于能量模型的可分负荷调度算法的研究

为了解决分布式计算系统能量消耗成本高的问题,在具有动态电压调节技术计算处理器的基础上,研究总线型网络环境中可分负荷的能量调度问题.根据能量与处理器速度的N次幂关系,在忽略网络延迟和给定运行时间的前提下,以最小化能量消耗为优化目标,建立可分负荷调度问题模型.采用非线性规划方法和Kuhn-Tucker条件,提出新的基于能量模型的负荷调度方案,并设计了相应的算法流程.对新方案和其他调度方案进行了对比和分析,结果显示新方案能耗率减少了10%～30%,验证了新方案在节能方面的有效性和优越性.     

JIT意义下极大化顾客满意数的并行多机问题

随着JIT(Just-In-Time)生产管理技术的出现和发展,考虑到以往极大化顾客满意数问题的研究只限于单机问题,而实际的生产调度和计划管理中绝大多数情况是并行多机问题,提出了一个在JIT意义下, 极大化顾客满意数的并行多机问题,并在分析相应的单机问题最优排序的基础上,构造出一个求解其多机问题的启发式算法,该算法的构思新颖,计算复杂性低,适用求解多机问题,具有工程实用价值的有效算法.最后给出了一个数值例子.     

用节约法解带有时间窗的车辆调度问题

车辆调度问题是物流配送系统的重要问题,对于提高物流配送系统的效率和效益有重要影响.建立带有时间窗的非满载车辆优化调度的数学模型,并利用节约算法对带时间窗的非满载车辆调度问题模型进行研究,并应用此算法对带有时间窗的车辆调度问题进行仿真,得到最优解,证明此算法的优越性.     

一种独立任务调度问题的相对量化模型

在分布式处理领域,独立任务调度问题是一个NP难题.现有各种调度模型普遍采用基于运行时间的任务量化方式,这使得异构系统调度问题较同构系统更为复杂,因为异构系统中同一任务在不同节点上的运行时间不等.该文提出了一种独立任务调度问题的相对量化模型,该模型采用一种相对量化方案来量化任务的载荷量和计算节点的负载能力及负载状况.基于该模型,可用LPT、AI之类的同构调度算法解决异构调度问题,从而使异构调度问题的复杂度降到与同构调度问题相当.理论分析与实验研究证明了新模型的有效性和良好的工程实用性.     

网格任务调度模型的研究

网格任务调度是采用适当的调度策略把应用程序分配到异构的计算节点上进行高效的执行并返回正确结果的过程。本文研究了经典网格任务调度模型,分析了各自的优缺点,并提出了一种包含有树形全局调度模型和局部调度模型的两层结构模型,此树形全局调度模型通过负载从根节点自上而下的迁移,能够很好地实现网格系统的负载平衡。通过二叉树的节点删除算法能够很好地解决模型中节点的失效问题,因此具有很好的安全性和可靠性。     

基于多目标拆分优化思维的拥塞网络数值调度方法

针对网络拥塞数值调度中存在的盲目性问题,提出了一种基于多目标拆分优化的网络拥塞数值调度方法.将拥塞网络的数值调度问题进行模型化表示,并将拥塞过程调度的最优问题分解为多个目标同时优化问题:即信道最优任务分配问题和路由拥塞调度问题.根据粒子群算法,对信道分配问题的最优解进行计算,同时设计约束模型并利用遗传算法求解拥塞调度问题,实现了在拥塞状态下的网络数值调度.结果表明,所提出算法获得的拥塞调度方案具有较好的可执行性.     

求解调度问题的粒子群算法编码方法研究

利用粒子群算法求解调度问题的关键是建立有效的粒子编码结构。介绍了作业车间、流水车间和并行机调度等3类典型调度问题的特点,阐述了求解调度问题的粒子群算法结构,指出设计粒子群算法编码方法需要考虑的3个关键问题。提出3种求解不同调度问题的粒子群算法编码方法,并从生成调度解的可行性和有效性、粒子群计算模型的适用性和解码过程的复杂性等几个方面对粒子编码方法进行分析。以作业车间调度问题为例,验证了所提粒子编码方法的有效性。     

用基于模拟退火机制的多种群并行遗传算法解Job-Shop调度问题

应用一种新型的遗传算法——基于模拟退火机制的多种群并行遗传算法对Job-Shop调度问题进行求解.通过仿真表明此算法不仅具有较强的全局收敛性,而且有更快的寻优速度,是求解复杂调度问题的有效算法.     

智能蚁群算法解决公交区域调度问题研究

针对多条运营线路的公交区域调度问题，给出了人员调度问题的改进模型，模型的目标是在满足工作时间、跨度时间、换班要求等相关约束的条件下使人员完成任务的间隔时间最小。论文对已有蚁群算法解决车辆路径优化问题的算法进行了改进。对算法中相应的转移规则和轨迹更新规则进行了重新设定，改进了算法转移策略和信息素更新策略。给出了算法的实现步骤。通过仿真，对模型的正确性进行了验证。证明了改进蚁群算法解决公交调度问题的高效性和较强的适用性。