模糊置换流水车间调度的多目标模型

为了求解同时考虑模糊加工时间和模糊交货期的多目标置换流水车间调度问题,提出一种模糊多目标调度模型。针对目标之一的最大化满意度,考虑决策者偏好,建立基于悲观准则的偏好满意度模型,并在此基础上,兼顾考虑可信度,对满意度模型进行改进;针对Pareto最优解的选取,引入模糊集理论和概率论,运用面积补偿法将最大模糊完工时间去模糊化,便于可行解之间进行比较。最后,采用随机系列算例以及典型算例进行优化计算,计算结果验证了模型的有效性。

分布式装配置换流水车间调度问题研究综述

近几十年来,现代制造业发展迅速,一种趋势是在分布式生产工厂进行工件的加工,待完成后到装配工厂集中装配成最终产品。该模式在带来诸多好处的同时,对资源调度提出了新的挑战。针对分布式装配置换流水车间调度问题(distributed assembly permutation flowshop scheduling problem,DAPFSP),介绍了DAPFSP的背景和存在的主要困难,进而对以最小化最大完工时间为优化目标的DAPFSP,从数学模型、编解码策略、全局和局部搜索算法角度进行探讨,分别综述了以最小化总流程时间等为优化目标,具有零等待等约束,以及考虑准备时间等因素的DAPFSP研究成果。最后,对有待进一步开展的研究工作进行展望。

超启发式人工蜂群算法求解多场景鲁棒分布式置换流水车间调度问题

本文考虑现实中广泛存在的加工时间不确定的分布式置换流水车间调度问题(DPFSP),研究如何建立问题模型和设计求解算法,方可确保算法最终获得的解在多个典型DPFSP场景下,均具有能满足客户期望的较小优化目标值(即makespan值).在问题建模方面,首先,采用场景法构建多个不同典型场景以组成场景集(每个场景对应1个具有不同加工时间的DPFSP),并设定合适的makespan值作为场景阈值,用于在评价问题解时从场景集中动态筛选出“坏”场景子集;其次,在常规优化目标makespan的基础上,结合“坏”场景子集概念提出可实现鲁棒调度的新型优化目标,用于引导算法每代加强对当前“坏”场景子集中每个DPFSP场景对应解空间的搜索;然后,结合所提的新型优化目标,建立基于多场景的鲁棒DPFSP(MSRDPFSP).在算法设计方面,提出一种超启发式人工蜂群算法(HHABC)对MSRDPFSP进行求解.HHABC分为高、低两层结构,其中低层设计6种启发式操作(HO),高层采用人工蜂群算法控制和选择低层HOs来不断生成新的混合启发式算法,从而实现在不同场景对应解空间中的较深入搜索.在不同规模测试问题上的仿真实验与算法对比,验证了HHABC的有效性.

自适应混合粒子群算法求解置换流水车间调度问题

为更有效地解决以最大完工时间最小化为目标的置换流水车间调度问题,提出了一种自适应混合粒子群算法(SHPSO)。该算法结合Q学习设计了参数自适应更新策略,以平衡算法的探索和开发;同时引入粒子停滞判断方法,使用平局决胜机制和Taillard加速算法改进基于迭代贪婪的局部搜索策略,对全局极值进行局部搜索,帮助粒子跳出局部最优。实验结果表明,对比其他四种改进PSO算法,SHPSO算法取得的平均相对百分偏差(RPDavg)至少下降了83.2%,在求解质量上具有明显优势。

基于交叉选择的变邻域蜂群算法求解置换流水车间调度问题

针对置换流水车间调度问题的特性,设计了一种基于交叉选择的变邻域蜂群算法。首先,算法在初始化种群阶段加入了NEH启发式算法,进而提高初始解的质量。在算法迭代的初期引入了差分进化算子进行交叉与选择,从而提高解的多样性。在算法的局部搜索阶段对50%最优个体加入了交换与逆序两种变邻域操作,增强了算法的搜索能力。通过正交实验选择合适的参数,在Car、Rec以及Taillard标准测试集上进行仿真实验,结果表明所提算法优于与之对比的其他群智能算法。最后,以最小化最大完工时间为寻优目标对某公司轮胎产品生产线上的作业排产问题进行求解,求解结果优于对比的算法,进一步验证所提算法在求解PFSP上的有效性。

基于链接学习的生物地理学算法求解置换流水车间调度问题

针对置换流水车间调度问题的特性,提出了一种基于链接学习的生物地理学算法(Biogeography-based optimization based on linkage learning,LLBBO)来对其求解。算法以生物地理学算法为架构,使用反向学习方法(Opposition-based learning,OBL)生成初始解,依据群体适应度值将群体分为优秀群体和劣势群体,使用信息熵的概念以及数理统计方法通过对这两个群体进行统计,分别建立概率矩阵模型以构建一种链接学习模型称为链接区块,使用链接区块依照算法迁移率对群体进行迁移操作实现群体更新。为进一步改善算法的搜寻性,提出一种NEH序列重组法对解序列执行局部搜索以进一步提高适应度。最后运用所提的LLBBO算法通过对基准例题的仿真测试和算法比较验证了所提算法的有效性。

基于激素调节机制改进型自适应粒子群算法在置换流水车间调度中的应用研究

研究以最小化最大流程时间为调度目标的离散型生产作业中的置换流水车间调度问题,将基于激素调节机制的改进型自适应粒子群算法应用到其中。在该算法中,粒子群算法的个体最优初始值不再是随机生成,而是由基于启发式信息的贪婪随机自适应算法得到的工件加工顺序转换而成,同时借鉴激素调节机制,引入激素调节因子,根据单个粒子周围的粒子的信息,对粒子的飞行方程进行改进,以提高搜索效率和搜索质量。对置换流水车间调度实例Rec系列基准问题进行测试,结果验证算法的有效性。

基于深度强化学习的非置换流水车间调度问题

针对传统调度算法不能有效利用历史数据进行学习,实时性较差而难以应对复杂多变的实际生产调度环境等问题,首次提出一种基于时序差分法的深度强化学习算法。该方法综合神经网络和强化学习实时性、灵活性的优势,直接依据输入的加工状态进行行为策略选取,更贴近实际订单响应式生产制造系统的调度决策过程。通过将调度问题转化为多阶段决策问题,用深度神经网络模型拟合状态值函数,把制造系统加工状态特征数据输入模型,采用时序差分法训练模型,把启发式算法或分配规则作为调度决策候选行为,结合强化学习在线评价—执行机制,从而为每次调度决策选取最优组合行为策略。在非置换流水车间标准问题集上的测试结果表明,该算法能够取得低于实例上界的较优解。

基于PSO的置换流水车间调度算法

置换流水车间调度问题(PFSP)是典型的具有工程背景的组合优化问题.对该问题的研究具有重要的理论意义与应用价值.本文针对PFSP问题提出了新的基于粒子群优化(PSO)的调度算法.论文分析了广义粒子群优化(GPSO)模型中信息流动拓扑结构的缺陷,提出新的基于种群的元启发式算法信息共享机制SISM.基于SISM信息共享机制的PSO调度算法利用PFSP问题的邻域知识指导个体的局部搜索.与历史文献中该问题的代表性算法比较,该算法可在调度质量与计算费用之间获得较好的平衡.仿真实例验证了该调度算法的有效性.

改进的粒子群算法求解置换流水车间调度问题

针对置换流水车间调度问题,提出了一种改进的粒子群算法进行求解。改进算法引入了判断粒子群早熟的方法,并在发现粒子群早熟后采用逆转策略对种群最优粒子进行变异,利用模拟退火思想概率接收新的最优粒子。种群最优粒子的改变会引导粒子群跳出局部极值的约束,从而克服粒子群的早熟状态。通过对置换流水车间调度问题中Car系列和Rec系列部分基准数据的测试,证明了该算法的有效性。

基于混合粒子群优化算法的置换流水车间调度问题研究

针对最大完工时间最小的置换流水车间调度问题,提出一种粒子群优化算法与变邻域搜索算法结合的混合粒子群优化(hybrid particle swarm optimization,HPSO)算法。在该混合算法中,采用NEH启发式算法进行种群初始化,以提高初始解质量。运用基于随机键的升序排列规则(ranked-or-der-value,ROV),将连续PSO算法应用于离散置换流水车间调度问题中,提出了一种基于关键路径的变邻域搜索算法,以进一步提高算法的局部搜索能力,使算法在集中搜索和分散搜索之间达到合理的平衡。最后,运用提出的混合算法求解Taillard和Watson基准测试集,并将测试结果与一些代表算法进行比较,验证了该调度算法的有效性。

应用模拟植物生长算法求解置换流水车间调度问题

针对置换流水车间调度问题,提出了一种基于模拟植物生长的调度算法。该算法利用置换流水车间调度的有向图表示,提出了可交换节点集概念,并将其融入模拟植物生长算法中,解决置换流水车间调度问题。采用所提算法对置换流水车间调度问题的基准数据进行测试,并比对标准遗传算法,结果表明算法的有效性。

基于知识进化粒子群算法的模糊交货期流水车间调度问题

针对模糊交货期的流水车间调度问题的特点,提出采用知识进化算法和粒子群优化的混合算法来求解问题。该算法首先在多个群体空间内采用粒子群优化寻找局部最优解,然后利用知识进化算法的猜测操作和反驳操作建立以群体空间知识为基础的一个知识空间,最后通过知识空间的协同进化更新其中的社会知识,从而形成问题的最优解。通过采用所提算法对带模糊交货期的流水车间调度问题的实例进行测试,并比对遗传算法和粒子群优化算法,表明了混合算法的可行性和有效性。

求解置换流水车间调度问题的改进遗传算法

针对置换流水车间调度问题的基本特征和传统遗传算法易早熟的缺陷,设计了改进遗传算法来求解此问题。采用NEH和Palmer启发式算法进行种群初始化,以提高初始解的质量;根据Metropolis准则对染色体进行选择操作,避免陷入局部最优;在变异过程中引入禁忌算法,避免迂回搜索;在算法迭代过程中引入了保优机制,避免丢失优秀染色体的基因信息;采用自适应终止准则,以保证解的质量。基于典型Benchmark算例的仿真实验结果表明,算法在求解质量和收敛速度方面明显优于NEH算法和种群经过初始优化的传统遗传算法。

含有混合中间存储策略的模糊流水车间调度方法

针对中间产品在相邻加工步骤间存在不同存储策略的流水车间调度问题,提出了一种含有混合中间存储策略的流水车间调度模型。在该模型中,考虑无限中间产品存储、有限中间产品存储、无中间产品存储3种策略同时存在的情况下对调度问题的影响,采用三角模糊数来描述生产过程中操作时间的不确定性;通过对三角模糊数的操作,并利用面积补偿的比较方法,将原有的模糊调度模型转化为确定性的调度模型;应用双倍体遗传算法对问题进行优化求解。仿真结果证明了模型和算法的有效性。

求解置换流水车间调度问题的布谷鸟算法

分析了布谷鸟算法的优化机理和特点,针对最小化最大完工时间的置换流水车间调度问题,采用基于最小位置值规则的随机键编码方式,应用布谷鸟算法进行求解.通过选取的标准算例对算法进行了仿真测试,并与萤火虫算法和粒子群算法进行对比,测试结果表明了该算法求解置换流水车间调度问题的有效性和优越性.该方法可作为解决流水线生产调度问题的一种有效方法.

变参数量子进化算法及其在求解置换流水车间调度问题中的应用

针对置换流水车间调度问题的求解,改进了基本量子进化算法,设计了一种变参数量子进化算法,用以求解置换流水车间调度问题。使用量子位极角表示工件排序,缩短了染色体长度。在运算过程中改变变异率和局部寻优次数,以改善全局搜索和局部寻优性能、提高算法的全局最优性。运用变参数量子进化算法求解置换流水车间调度的Benchmark问题,数值实验表明,该算法具有良好的性能。

求解置换流水车间调度问题的改进遗传算法

目前求解置换流水车间调度问题的遗传算法中,加工顺序编码方法导致交叉、变异算子复杂,且子代与父代不相似,算法易陷入局部最优。为解决以上问题,提出了一种基于优先权值编码并含有限优算子的改进遗传算法。利用各工件的优先权值进行编码,避免遗传算子中不合法编码的出现;加入限优算子限制种群中最优个体的繁殖数量,防止种群陷入局部最优点,改善寻优质量。实验结果表明,该算法中的编码方法可行且易于应用于求解紧急工件优先加工的实际问题;同时用基准算例验证了具有限优算子的改进算法求解结果相对误差小且求解稳定性高。

改进微粒群优化求解置换流水车间调度问题

针对置换流水车间调度问题,提出了一种改进微粒群优化的求解算法。首先,由基于启发式信息的贪婪随机自适应算法得到工件加工顺序,个体最优的初始值不再是随机生成的初始值,而是由该工件加工顺序转化而成;然后,对个体最优解进行了交换型局部搜索;最后,通过对Car系列和Rec系列基准的测试,表明了该算法的有效性。

用遗传算法解决一类模糊流水车间调度问题

对同时考虑模糊加工时间和模糊交货期的模糊流水车间调度问题进行了研究 ,模糊加工时间用三角模糊数来表示 ,模糊交货期用梯形模糊数来表示。应用遗传算法搜索最优排序 ,在适应度函数处理中引入模糊数处理方法 ,以平均满意度最大作为优化目标。