Job shop调度文化进化算法研究

作业车间调度优化问题属典型的NP-hard问题,其求解通常采用智能启发式算法,文化进化算法基于文化算法及文化进化思想,通过上层文化空间的经验知识指导下层个体进化搜索的方向及步长,通过模拟人类社会文化进化的机制实现文化空间的进化与更新,最后将算法应用到Jobshop问题的求解,用matlab编程仿真测试,结果表明此算法解决车间调度优化问题是可行的,而且其搜索性能优于一般GA算法及一种改进的微粒群算法。     

无缝钢管热轧批量调度问题的学习型文化基因算法

针对无缝钢管热轧批量调度问题,考虑生产工艺约束、生产需求优化等因素,以最小化热工具轧辊使用消耗、生产拖期为目标,建立了多目标整数规划模型。分析了无缝钢管批量调度顺序对热工具轧辊消耗的影响,给定了轧制批量顺序下的求解启发式算法,并设计了一种基于多种群进化的学习型文化基因算法。针对目标设计了不同的搜索算子以及算子的自适应学习选择策略来指导种群进化,充分发挥全局搜索和局部搜索能力。仿真实验与常用的带精英策略的快速非支配排序遗传算法和文化基因算法进行了对比,验证了所提模型和算法的有效性。     

基于混合差分进化算法的并行机批处理调度问题研究

考虑到实际生产中产品多、批量小的特点,建立了一种带工艺约束的并行机批处理调度优化模型。为解决调度中的分批问题,提出了一种新的基于产品需求量的批量划分方案及批量染色体编码方式,采用两级差分进化算法来解决批量划分和批次调度问题;针对标准差分进化算法收敛速度慢、易出现早熟现象等问题,引入动态随机搜索和随机变异的局部搜索策略,以增强标准差分进化算法的局部搜索能力。测试算例及调度实例的仿真结果表明,该算法能有效地提高算法收敛速度,平衡其全局搜索和局部探索能力。     

置换流水车间调度的文化量子粒子群算法

针对量子粒子群算法在求解置换流水车间调度问题时容易早熟,提出用文化量子粒子群算法求解置换流水车间调度问题.该算法的主群体空间采用量子粒子群算法,知识空间采用遗传算法.通过影响操作和接受操作,知识空间定期将自己的精英个体贡献给主群体空间,主群体空间也定期将自己的精英个体贡献给知识空间.最后将该算法应用到具体问题的求解,用MATLAB编程仿真测试,仿真结果表明,该算法收敛速度快,且具有较高的求解质量,而且其搜索性能优于一般的量子粒子群算法.     

半导体炉管区批调度问题的粒子群优化算法研究

为改善粒子群算法对大规模问题求解的性能,提出了一种基于文化进化的并行粒子群算法,详细阐述了该算法的原理和具体实施方案.针对半导体炉管区批调度问题,设计了双层粒子群算法,外层应用基于文化进化的并行粒子群算法进行批量计划问题的求解,内层采用传统的粒子群算法求解调度问题.通过对其他文献中的仿真实例进行计算和结果比较表明,该算法优于文献中的启发式算法和蚂蚁算法.     

具有资源约束的项目调度问题中的量子进化算法

为了将量子进化思想应用到具有资源约束的项目调度领域中,提出了一种基于活动对连接关系的调度解表示方法,进而构成新的搜索解空间。利用新表示方法的二值性,给出了量子进化算法。该算法扩展了前向-后向搜索思想,构造出原问题的反向问题,并把原问题和反向问题以同样的方式进行求解,利用反向搜索一个方向上的解群来更新另一个方向上的解群。此外,算法根据分散搜索的思想,利用新搜索解空间中定义的距离来控制搜索的分散性。最后,通过仿真说明了该算法的有效性。     

多生产线作业协调调度的PSOGA混合优化算法

为了求解多目标多生产线调度问题,采用协同进化思想,提出了多种群PSOGA混合优化算法(MC-HPSOGA)。以最小化最大完工时间、最大化生产线利用率和最大化客户满意度为目标函数,建立了多生产线作业协调调度问题的多目标批量调度数学模型,并且设计最小批量动态分批策略,将MC-HPSOGA算法应用于BSPT公司角磨机装配线的多目标多生产线调度问题实例中,通过与粒子群(PSO)和遗传算法(GA)的比较,验证了MC-HPSOGA算法和模型的有效性。     

解决多目标Flow-shop问题的生物免疫调度算法

生产调度是车间自动化的关键问题之一 ,生产调度的优劣对制造系统的运行影响极大。通常的确定性优化方法往往不适合生产调度这类NP完全问题的求解。文章基于生命科学中的免疫概念与理论 ,构造了基于生物免疫机理的生产调度模型 ,并研制了用于求解目标Flowshop问题的智能调度系统 ,克服了当前遗传算法用于求解此类问题时 ,易于出现早熟、搜索效率低及不能很好保持个体多样性等不足 ,大大改进了搜索效率 ,对复杂的多约束、大规模及多目标生产调度问题 ,算法效果显著 ,并且可以轻松地获得满足要求的多个优化解。文章讨论了模型的建立、算法的实现和应用实例 ,测试情况表明 ,以上模型与算法在生产调度实际中将具有广阔的应用前景     

一种求解集成生产计划的混合协同进化算法

讨论了一类带有序列相关的机器调整时间和有限缓冲空间的流水车间批量计划与调度的集成优化问题,给出了该问题的非线性混合整数规划模型,提出了一种求解混合协同进化问题的算法.模型的目标函数是使库存费用、缺货费用和加班费用之和最小,约束函数考虑了库存平衡约束和需求平衡约束.算法采用协同进化算法与遗传算法的并行混合搜索结构,通过迁移算子把协同进化的子种群和独立进化的公共种群有机联系起来,同时算法采用基于邻域的进化策略,以提高算法性能.最后,对三种不同规模的问题进行了数值仿真实验,结果验证了算法的有效性.     

基于置换Flow Shop调度问题的混合量子算法研究

安排合理有效的生产调度是生产活动能井然有序开展,生产资源得到最佳配置,运作过程简明流畅的有力保证。置换Flow Shop调度问题是流水车间的典型问题,同时也是NP-C难题。从问题出发,设计了由量子进化,最佳模式和其他优化技术所构成的混合量子算法(HQA)。HQA模仿量子行为迭代演化,将种群一分为二,种群1在量子作用和其他优化作用下,探索解空间。种群2保留最佳模式,提高了搜索的效率。经计算测试,验证了HQA在求解排序问题中的可行性,测试结果表明HQA具备了求解置换Flow Shop调度问题的能力。     

基于过滤定向搜索的Job-Shop调度算法及评价

对以Makespan最小为目标的Job Shop调度问题进行了研究。首先对Job Shop调度问题进行了描述,在此基础上建立了一种求解Job Shop调度问题的启发式优化算法———基于过滤定向搜索的算法,同时结合实例对算法的优化过程作了具体描述。最后通过不同规模的Benchmark实例对该算法进行了仿真评价,结果表明基于过滤定向搜索的算法搜索效率高,解的性能好,是一种有效的优化算法。     

基于细菌觅食算法车间调度系统的研究

细菌觅食优化算法最早于2002年提出,是一种于基于人体内的大肠杆菌的觅食行为提出来的新的进化计算方法.在本文中,我们改进的基于群体搜索方法是细菌觅食算法的一个重要内容,细菌觅食算法在这里被运用到了车间生产调度系统中来,极大地优化了车间调度系统的加工生产过程.     

带准备时间的柔性流水车间多序列有限缓冲区排产优化问题

针对带准备时间的柔性流水车间多序列有限缓冲区排产优化问题,提出一种改进的紧致遗传算法（Improved compactgenetic algorithm,ICGA）与局部指派规则结合的方法来解决该问题。全局优化过程采用改进的紧致遗传算法,为了克服紧致遗传算法（Compact genetic algorithm,CGA）易早熟收敛的问题,提出一种基于高斯映射的概率模型更新方式,在保持紧致遗传算法快速收敛特性的前提下,扩展了种群中个体的多样性,增强了算法进化活力。为减少生产阻塞和降低准备时间对排产过程的影响,设计了多种局部启发式规则来指导工件进出多序列有限缓冲区的分配和选择过程。采用某客车制造企业中的实例数据进行测试,测试结果表明,改进的紧致遗传算法与局部指派规则配合使用,能够有效解决带准备时间的柔性流水车间多序列有限缓冲区排产优化问题。     

一种动态识别瓶颈机床的启发算法

瓶颈机床是影响车间生产和调度的关键因素。针对Jobshop调度中的瓶颈机床确定问题,提出了动态识别瓶颈机床的搜索算法框架。并详细讨论了算法框架中的工序开始时间窗、搜索空间的概率模型和动态启发算法。最后用算例验证了动态启发算法的有效性。     

基于共同进化算法的多工艺路线决策研究

针对传统单种群进化算法(ConventionalEvolutionaryAlgorithm,CEA)求解CAPP中多工艺路线决策与生产调度集成的不足,提出利用共同进化算法(SymbioticEvolutionaryAlgorithm,SEA)来实现单件小批量生产和面向定单生产的柔性工艺设计和生产调度的集成。并对共同进化中工艺子种群和调度子种群的基因编码、染色体的交叉、变异和共同进化个体的选择做了探讨。最后以算例验证了基于动态资源条件下,共同进化算法能够实现系统的全局优化,表明此算法能够较好地解决CAPP和生产调度的集成。     

基于混合遗传鲸鱼优化算法的柔性作业车间自动导引车融合调度方法

针对柔性作业车间调度问题,考虑自动导引车(AGV)在车间制造过程中只参与装卸和搬运工作,提出一种实现AGV路径规划与柔性作业车间调度集成优化的融合调度模型。采用基于工序排序与机器选择两个子问题的二维向量编码方案,并在解码过程中提出基于最先服务原则的AGV安排策略。对鲸鱼优化算法进行离散化改进,针对性地设计了多种种群初始化策略,引入遗传算法的交叉、变异操作以提升鲸鱼优化算法的全局搜索能力,并嵌入局部搜索算法以达到全局搜索和局部搜索的平衡,构建了一种混合遗传鲸鱼优化算法（HGWOA）来求解该融合调度模型。通过经典测试算例验证了算法性能,并使用正交试验优化了算法参数。研究结果表明,HGWOA算法用于求解柔性作业车间AGV融合调度问题可以获得较好的效果。     

面向Job Shop调度的算法融合方法研究

提出一种算法融合方法,解决单一算法求解Job Shop调度问题存在的不足,提高这类问题的求解质量。在融合方法中,采用遗传算法和蚁群算法进行并行搜索;根据Job Shop调度问题解的特征,提出基于关键工序的邻域选择方法,并将基于这种邻域选择方法的禁忌搜索算法作为局部搜索算法,加强了遗传算法和蚁群算法的局部搜索能力。采用算法融合方法构造的优化算法对13个难解的benchmarks问题实例进行求解,在较短的时间内,得到的十次实验结果的makespan最优值和平均值优于并行遗传算法(PGA)和TS算法。采用算法融合方法构造的优化算法具有较强的搜索能力,说明提出的算法融合方法是有效的。     

混合离散蝙蝠算法求解多目标柔性作业车间调度

针对以最大完工时间、生产成本和生产质量为目标的柔性作业车间调度问题,在研究和分析蝙蝠算法的基础上,提出一种混合离散蝙蝠算法。为了提高求解多目标柔性作业车间调度问题的混合离散蝙蝠算法的初始种群质量,在通过分析初始选择的机器与每道工序调度完工时间两者关系的基础上,提出一种优先指派规则策略产生初始种群,提高了算法的全局搜索能力。同时采用位置变异策略来使得算法在较短的时间内尽可能多地搜索到最优位置,有效地避免了算法早熟收敛。在计算问题的目标值上面,首次提出时钟算法。针对具体实例进行测试,试验数据表明,该算法在求解柔性作业车间调度问题上有很好的性能,是一种有效的调度算法,从而为解决这类问题提供了新的途径和方法。     

多目标批量生产柔性作业车间优化调度

研究批量生产中以生产周期、最大提前/最大拖后时间、生产成本以及设备利用率指标(机床总负荷和机床最大负荷)为调度目标的柔性作业车间优化调度问题。提出批量生产优化调度策略,建立多目标优化调度模型,结合多种群粒子群搜索与遗传算法的优点提出具有倾向性粒子群搜索的多种群混合算法,以提高搜索效率和搜索质量。仿真结果表明,该模型及算法较目前国内外现有方法更为有效和合理。最后,从现实生产实际出发给出多目标批量生产柔性调度算例,结果可行,可对生产实践起到一定的指导作用。     

Hybrid evolutionary algorithm with marriage of genetic algorithm and extremal optimization for production scheduling

This paper presents a hybrid evolutionary algorithm with marriage of genetic algorithm (GA) and extremal optimization (EO) for solving a class of production scheduling problems in manufacturing. The scheduling problem, which is derived from hot rolling production in steel industry, is characterized by two major requirements: (i) selecting a subset of orders from manufacturing orders to be processed; (ii) determining the optimal production sequence under multiple constraints, such as sequence-dependant transition costs, non-execution penalties, earliness/tardiness (E/T) penalties, etc. A combinatorial optimization model is proposed to formulate it mathematically. For its NP-hard complexity, an effective hybrid evolutionary algorithm is developed to solve the scheduling problem through combining the population-based search capacity of GA and the fine-grained local search efficacy of EO. The experimental results with production scale data demonstrate that the proposed hybrid evolutionary algorithm can provide superior performances in scheduling quality and computation efficiency.