多种群蚁群遗传算法在车间调度中的研究应用

蚁群算法和遗传算法都属于仿生型优化算法,是解决调度问题的强有力的工具。本文针对多目标车间调度问题提出了一种多种群蚁群算法和遗传算法想结合的算法,算法的第一部分用多种群蚁群算法求得各个目标函数的最优解,第二部分把求得的解作为遗传算法的初始种群求得多目标问题的Pareto最优解。仿真结果,该算法有较好的有效性、稳定性和订单适应能力。     

基于正逆序策略求解Job Shop的遗传调度算法

针对标准遗传算法在求解车间作业调度问题中易陷入局部极值点的缺点,提出了一种基于领域知识的动态双种群遗传算法. 由于最优调度必定是活动调度,算法利用活动调度技术来进行空间缩减;两个子种群分别采用正、逆序调度策略来提高种群的多样性. 算法采用一种新的染色体编码来表示活动调度方案,并给出了相应子种群的初始化策略、遗传操作,以及子种群之间的交叉方式. Benchmark算例的仿真实验与分析表明,该算法在计算时间和求解质量上均具有较好的效果.     

云计算中基于遗传算法的任务调度算法研究

为解决云计算中的任务调度问题,提出了一种以遗传算法为基础的任务调度模型.在算法初始化种群产生时通过染色体匹配率来使种群个体均匀分布在解空间上,有效地避免了早熟;引入服务质量标准进行建模以改进适应度函数,充分考虑用户对调度结果的满意程度;采用规则约束的交叉和变异操作,提高个体的质量.仿真实验的结果分析表明:该改进算法能更有效地求解云计算环境下作业调度问题.     

用改进的遗传算法求解作业调度问题

作业调度问题JSP(Job Shop Scheduling Problem)是典型的组合优化问题.文中用改进的遗传算法来解决作业调度问题,在遗传算法中设计了一种调整算子,并证明了算法能够收敛到全局最优解;同时提出一种新的求解JSP问题的双目标函数、双种群遗传算子.每个种群侧重一个目标,各从不同侧面深度挖掘问题的信息,用以优化问题的解,两个种群再通过混合交叉得到更好的解,较大地提高了算法的收敛速度.     

求解作业车间调度问题的一种自适应遗传算法

针对作业车间调度问题，提出了最小化空闲时间的处理过程及其变异算子，设计了一种自适应遗传算法．该算法根据个体的特征确定交叉和变异次数，并根据种群特征不断修正种群．经典的调度基准问题测试表明：自适应措施能够有效保持种群的多样性，可以采用非常小的种群规模；最小化空闲时间的变异算子缩小了算法的搜索空间，大大提高了搜索效率．     

基于协同进化遗传算法的水库群供水优化调度研究

针对水库群供水优化调度问题,介绍了一种改进的协同进化遗传算法。该算法针对求解高维、复杂的水库群优化调度时多约束条件难以处理、计算机时长、易陷入局部最优解等缺陷,建立了相应的罚因子的评价机制,生成了两类进化子种群,运用改进遗传算法同时对不同种群进行操作,并将其应用在滦河下游六水库联合供水优化调度中。实例计算结果表明,用该算法求解水库群供水优化调度问题,结果可靠、合理,计算效率高。     

一种求解工程调度中时间/成本权衡问题的遗传算法

结合工程调度中时间/成本权衡问题的特点,设计了一种有效的求解工程底线问题的遗传算法,基于该遗传算法提出了有效工期/成本曲线的绘制策略·对遗传算法解的编码方式、遗传算子的定义及算法结构进行了描述·通过对大量测试问题的求解实验表明,遗传算法是求解该问题的一种有效算法     

混合蚁群遗传算法在车间作业调度的应用研究

提出了一种解决车间调度最短完成时间的有效的混合算法.将遗传算法与蚂蚁算法的融合,采用遗传算法生成信息素分布,利用蚂蚁算法求精确解,优势互补.应用该算法对Job-Shop车间作业调度问题的解进行编译,通过实例表明该算法是可行有效的.     

作业车间调度双阈值控制结构自适应遗传算法的一种改进

当前,用于求解作业车间调度问题的遗传算法的执行效率非常差,针对这一问题,设计了一种双阈值控制结构的自适应遗传算法。该算法首先利用相似度阈值实现选择性的交叉和变异,然后以适应度阈值作为是否引入新个体的标准,从而保持种群的多样性。利用这种方法解决车间调度问题时,可以避免交叉后产生的优秀个体因变异而遭到破坏。它对典型作业车间调度问题的求解表明,该算法可以极大地提高算法的寻优能力和收敛速度。     

多目标模糊柔性作业车间调度问题优化

为降低柔性作业车间调度中的能耗,针对实际制造车间中工序加工时间和交货期的不确定性,将加工时间和交货期采用模糊数表示,建立以完工时间、平均满意度和最小满意度为柔性作业车间调度问题的多目标函数。同时设计了邻域遗传算法(GANS)求解该问题,算法采用机器选择的方法产生初始种群,并采用工序插入式方法对染色体进行解码;采用动态交叉概率及改进精英保留策略来保证种群的多样性和加快算法的收敛速度;并提出一种基于移动模糊关键工序的邻域结构来加强算法的局部搜索能力。最后通过数值实验验证了模型和算法的有效性和可行性,并对4个基准问题进行测试。结果表明:该算法在求解的精度、鲁棒性和解集的分布性方面与传统算法相比具有一定的优势,是一种有效的求解模糊柔性作业车间调度问题的新方法。     

预制构件生产-运输-装配一体化的建造调度优化

为研究预制构件生产-运输-装配一体化的建造调度优化问题,构建装配式构件全过程的多目标调度优化模型.优化模型将预制构件3个阶段的优化作为一个扩展的生产车间调度优化,并采用改进的双种群遗传算法对模型进行求解.结果表明：改进的双种群遗传算法能够显著提高遗传算法的搜索效率;优化模型能够有效地减少总完工时间和并行机器的总机器成本.     

基于改进遗传算法的车间调度原型系统

为了提高遗传算法求解作业车间调度问题的初始解质量和简化遗传操作过程,提出基于幻方变幻的互换编码规则改进遗传算法;同时利用该算法基于.NET平台建立了车间调度问题和柔性车间调度问题的混合原型系统。实验结果表明:采用幻方变换的互换编码规则,提高了遗传算法的求解能力;基于该算法的原型系统实现方便,求解效率高,能够有效应用于作业车间调度系统的开发。     

无线传感器网络基于改进遗传算法的节点调度

节点调度问题是经典的NP-hard组合优化问题之一。为解决该问题提出了诸如蚁群算法、粒子群算法和遗传算法等智能算法,以遗传算法(genetic algorithm,GA)更为有效,但经典的遗传算法在解决节点调度问题时,其算法自身存在寻优速度慢,容易陷入局部最优。提出一种改进的轮盘赌优化方法,该方法基于适应度比例的选择,即用全部个体的选择概率来计算累计概率,产生完整的子代个体并保留其基因,避免陷入局部最优,进而快速精确地求出节点调度问题的最优解,实验结果表明,经过改进的遗传算法求解的路径长度、收敛性和运行时间等指标均有明显改善。     

基于改进遗传算法的柔性作业车间调度优化

在实际生产中,加工成本愈发成为企业关注的重要因素。本文对以最小化加工成本与完工时间为目标的柔性车间调度问题进行了研究。首先根据实际约束构建调度模型,提出改进遗传算法对模型进行求解,引入质量基因段来增强对染色体适应度值的评价,加速淘汰质量差的个体。为了优化求解质量,提出了基于整体负荷最小与局部负荷最小的种群初始化方法,并设计了精确变异机制来维持种群多样性。最后用标准算例进行测试,相比于其他改进遗传算法,求解速度得到提高,求解质量也得到了提升,验证了此改进遗传算法的有效性。     

面向作业车间调度问题的遗传算法改进

为了获得遗传算法在作业车间调度问题上的最优化解,提高算法的迭代速度,研究了遗传算法的改进方法,以工件的加工时间最短为目标建立调度模型。在算法上提出了基于概率改进的具有自适应能力的交叉与变异算子,以求作业车间调度问题的最优解。在遗传算法上采用精英保留策略方法,并结合改进的自适应算子对问题进行求解。以基准案例LA01和FT06作为实验仿真对象,获得了相应的甘特图以及搜索过程曲线。仿真结果表明,与未改进的算法相比,该算法能够更加快速地获得最优解。改进后的算法在搜索上更加快速有效,在求解作业车间调度问题上具有一定的可行性,更加适合工业加工生产。     

多目标柔性作业车间调度的多交叉策略元胞进化算法*

针对经典Job-shop调度问题的局限性,构建了以加工成本、瓶颈机器负荷、机器总负荷及制造工期为目标函数的柔性作业车间调度多目标优化模型,提出了基于多交叉策略的元胞多目标遗传算法。在分析优化模型的基础上,使用双层编码方式,并采用多个交叉算子协同进化,提出一种多交叉策略的进化算子。针对元胞多目标遗传算法的特点,提出一种改进的精英策略,保证更多的精英个体参与进化,从而提升算法收敛速度。通过2个基准实例求解对比分析,表明所提方法的有效性。将新算法应用于实际生产企业的车间调度问题中,得到了一组Pareto解集,并采用层次分析法得到一种满意度最大的方案。数据结果表明,该算法在解决多目标FJSP的工程有效性。     

用AGLA算法求解一类以TFT为目标的模糊Flow Shop调度问题

针对一类加工时间不确定的以总流经时间(TFT)为目标的置换Flow Shop调度问题,应用模糊数学的方法表示加工时间的不确定性,提出了一种改进的智能算法——异步遗传局部搜索算法(AGLA)。该算法初始种群的一个解由构造型启发式算法产生,其他解随机产生;通过引入一个加强的变邻域搜索机制和一个简单的交叉算子,对种群执行异步进化操作(AE);算法最后加入重启机制防止陷入局部极小。仿真实验结果验证了AGLA解决模糊Flow Shop问题的有效性。     

战时车辆调度问题算法及应用分析

战时车辆调度是精确后勤的核心内容之一,对提高部队机动性和后勤保障能力具有重要作用.对战时车辆调度问题进行分析研究,提出一种快速、高效的算法.对战时多任务车辆调度组合优化问题,即NP-Hard问题进行求解.构造了一个两层搜索结构的遗传禁忌混合算法,该算法充分利用了不同领域搜索方法的优点,增强了算法在解空间中的搜索能力和运行效率.试验分析结果表明:所提算法能有效地解决战时多任务车辆调度问题;与基本遗传算法相比,该算法的优化能力、运行效率、可靠性均得到了提高.     

一种用于车间调度的基于熵的混合遗传算法

为提高车间调度算法的寻优性能,通过对模拟退火遗传算法收敛图的研究,提出了评价算法种群有序性（差异性）的种群熵,基于种群熵,提出了改进的模拟退火遗传算法,该混合算法通过种群熵动态地改变算法的交叉和变异概率,使之适应种群的变化,提高种群的多样性,有效地克服算法的过早收敛,从而达到提高算法寻优性能的目的。仿真实例表明,所提出的算法的寻优性能有了显著的提高。     

An optimizing algorithm of static task scheduling problem based on hybrid genetic algorithm

To reduce resources consumption of parallel computation system,a static task scheduling optimization method based on hybrid genetic algorithm is proposed and validated,which can shorten the scheduling length of parallel tasks with precedence constraints.Firstly,the global optimal model and constraints are created to demonstrate the static task scheduling problem in heterogeneous distributed computing systems(HeDCSs).Secondly,the genetic population is coded with matrix and used to search the total available time span of the processors,and then the simulated annealing algorithm is introduced to improve the convergence speed and overcome the problem of easily falling into local minimum point,which exists in the traditional genetic algorithm.Finally,compared to other existed scheduling algorithms such as dynamic level scheduling(DLS),heterogeneous earliest finish time(HEFT),and longest dynamic critical path(LDCP),the proposed approach does not merely decrease tasks schedule length,but also achieves the maximal resource utilization of parallel computation system by extensive experiments.