基于EDA的绿色零等待作业车间调度问题求解

针对绿色零等待作业车间调度问题,本文提出一种基于分布估计算法(Estimation of Distribution Algorithm,EDA)的多目标优化算法,用于最小化最大完工时间和总能量消耗.采用双种群增加种群的多样性,并加入启发式操作NEH(Nawaz-Enscore-Ham,NEH)来提高初始解的质量.设计自适应学习速率来控制优良解信息在整个算法搜索过程中的引导作用.结合零等待作业车间调度问题的结构性质与解码方式,提出基于前端省略的快速评价方法,同时利用Insert操作构建两种局部搜索策略,进而加强算法的搜索效率和深度.通过仿真实验和算法对比验证所提算法的有效性.

混合EDA求解多目标零等待作业车间调度问题

为了求解最小化问题的最大完工时间(Makespan)和最大延迟时间的多目标零等待作业车间调度问题,提出了一种混合分布估计算法。首先,提出了NEH与随机生成并用的初始化种群机制,从而提高初始解的质量。其次,根据概率矩阵模型生成新的个体并通过非劣解集中的非受支配解更新概率矩阵。然后,在局部搜索部分,设计了一种变邻域的搜索机制,从而加强局部搜索能力,提高算法的搜索性能。最后,在仿真实验部分,通过对不同规模标准测试问题的测试,以及与其他算法的对比结果,验证了混合EDA求解多目标零等待作业车间调度问题的有效性。

考虑模糊质检时间的柔性作业车间动态调度问题

为解决更符合现实情形的模糊质检时间柔性作业车间动态调度问题,以最小化完工时间为目标,立足紧急插单、机器在空载运行时发生故障和机器在加工工件时发生故障的三种故障情形,建立了带模糊质检时间的机器故障、紧急插单重调度模型。设计了基于元胞自动机邻域搜索和随机重启爬坡算法的改进遗传算法求解模型,即针对车间调度问题中存在的订单排序和机器选择双决策问题特征,设计包含工序码和机器码的双层编码方案,并基于遗传算法思想对工序码和机器码设计相应的交叉、变异等遗传操作。同时,将遗传操作应用于基于元胞自动机的邻域搜索算法框架中以增强算法全局搜索能力,整合基于关键工序的随机重启爬坡算法以提高算法局部开发能力。实验选取10个柔性车间调度算例验证了所提算法的有效性,同时,测试1个模糊质检时间柔性车间调度算例验证了模型的有效性。另外,实验也测试了不同故障场景,得出该动态调度方法优于实际场景中常使用的“工件后移”调度策略。

基于改进樽海鞘群算法的多目标柔性作业车间调度问题研究

针对多目标柔性作业车间调度问题,构建了以最小化总能耗、最小化生产成本及最小化惩罚值为优化目标的数学模型,并设计改进的多目标樽海鞘群算法(IMSSA)进行求解。改进算法主要由樽海鞘领导者和樽海鞘追随者两部分构成,其中,领导者位置更新结合正余弦算法来实现,追随者位置更新基于线性微分递减的惯性权重方法来完成。此外,引入食物源存储库用于保留非支配解。最后通过对比实验证明了所提策略及改进算法的有效性。

两机零等待流水车间调度问题的启发式算法

为实现两机零等待流水车间调度问题的总流程时间最小化,结合问题的结构信息提出了一种快速求解近优解的启发式算法。在该类问题中,工件在每台机器上的操作包括调整、加工和移除3部分,且调整和移除时间都与工件的加工时间相互分离。首先分析了该类问题的优化性质,结合优化性质进而构造出求解算法。在中小规模和大规模问题上,将启发式算法的结果分别与最优解和最优解的下界值进行了比较。大量数值计算实验表明了该算法的有效性和解决大规模实际问题的潜力。

新型混合改进遗传算法求解零等待流水车间调度问题

具有零等待约束条件的流水车间调度问题是一类典型的NP难问题,针对该问题提出一种新型混合改进遗传算法进行优化求解。首先,采用改进NEH算法强化初始种群质量,提高种群的多样性。结合关联规则理论挖掘种群中的优势块,借助优势块进行人工染色体组合,以降低问题复杂度。交叉操作采用单段交叉、双段交叉和三段交叉3种交叉机制,改善算法全局搜索能力;变异过程引入水平集和种群分割的思想,将种群分割成两部分,并赋予不同的变异概率,提高算法局部搜索能力。为进一步提高遗传算法的求解性能,提出了基于NEH的邻域搜索机制,增加种群多样性,进一步提高种群质量。最后,通过实验结果和算法比较,验证了所提算法的求解性能。

基于改进灰狼优化算法的柔性作业车间分批调度问题研究

针对以最小化最大完工时间为目标的柔性作业车间分批调度问题(Flexible Job shop Batch Scheduling Problem,FJBSP),提出了一种改进灰狼优化(Improved Grey Wolf Optimization,IGWO)算法,优化对象为工件的分批方案。首次将流体模型应用于FJBSP的求解,提出了一种基于流体模型的解码方法,用于获得更好的子批调度方案;然后改进了狼群的等级制度,避免了算法过早收敛;其次设计了一种全新的适应可变长编码的交叉方法,深入交流2个个体之间的分批信息,增强了算法的搜索能力和稳定性;再次,提出了能够动态更新个体游走率的自适应灰狼游走策略,兼顾了算法的搜索质量和收敛速度;此外,对领头狼使用自适应邻域搜索动态调整每种工件选择各邻域的概率,提高算法的局部搜索能力;最后,设计了9个算例和3组实验,验证了所提出的IGWO算法的有效性和优越性。

基于改进的NSGA-II纺织生产车间柔性作业车间调度问题算法的研究

在纺织生产线调度领域,传统的人工调度方式已难以满足当前对高效利用机器和提升生产效率的迫切需求。鉴于此,本文建立了以最小化最大完工时间和机器总负载为优化目标的多目标柔性作业车间调度问题(flexible job shop scheduling problem,FJSP)数学模型,并提出了一种改进的NSGA-II算法(INSGA-II)用于求解。本文的主要特点是:(1)该算法采用基于工序和机器的两层编码方法;(2)采用混合种群初始化策略,目的是提高种群的初始质量;(3)设计了一种基于迭代次数的变领域搜索策略,在减少无效搜索的同时提高了局部搜索能力。本文在MK01-MK09和abz05-abz09的测试集上,将所提出的算法与其他算法(MOEA/D、MOEA/DD和NSGA-II)进行对比,并通过对14个标准算例的分析,证明了改进个NSGA-II算法在求解FJSP问题中的有效性。

融入概率学习的混合差分进化算法求解绿色分布式可重入作业车间调度

本文针对绿色分布式可重入作业车间调度问题(GDRJSSP),提出一种融入概率学习的混合差分进化算法(HDE PL),以实现最大完工时间和总能耗最小.根据GDRJSSP的问题特点,设计编码和解码规则,并采用差分进化算法执行全局搜索来发现优质解区域.为能更明确地引导全局搜索方向,设计基于贝叶斯网络结构的多维概率模型合理学习和积累优质解(即当前种群中的较优解)的模式信息.结合问题解的结构特征,提出基于关键路径的4种邻域结构来构造局部搜索,并设计基于非关键路径的节能策略来提升算法获取低能耗非劣解的能力.仿真实验和算法对比验证了HDE PL可有效求解GDRJSSP.

协同智能体强化学习算法的柔性作业车间调度方法研究

为提高柔性作业车间调度效率,构建一种具有柔性作业车间调度问题约束条件的马尔可夫决策过程,针对工件与机器的同时选择问题,提出一种协同智能体强化学习方法进行求解。在构建马尔可夫决策过程中,引入析取图表述状态特征,采用两种智能体执行工件与机器的选取,预测不同时刻最小化最大完工时间的差值来映射整个调度过程的奖励参数;求解时,嵌入GIN(graph isomorphic network)图神经网络提取状态,为工件与机器智能体分别设置编码器-解码器构件输出两种动作策略,以PPO(proximal policy optimization)算法与D3QN算法训练工件与机器智能体的决策网络参数。通过正交试验法选取算法超参数,以标准实例与其他文献进行对比,实验结果表明,所提方法在求解FJSP方面明显优于其他算法,进一步验证所提方法的可行性与有效性。

混合粒子群算法求解多目标柔性作业车间调调度度问题

柔性作业车间调度问题是生产管理领域和组合优化领域的重要分支.本文提出一种基于Pareto支配的混合粒子群优化算法求解多目标柔性作业车间调度问题.首先采用基于工序排序和机器分配的粒子表达方式,并直接在离散域进行位置更新.其次,提出基于Baldwinian学习策略和模拟退火技术相结合的多目标局部搜索策略,以平衡算法的全局探索能力和局部开发能力.然后引入Pareto支配的概念来比较粒子的优劣性,并采用外部档案保存进化过程中的非支配解.最后用于求解该类问题的经典算例,并与已有算法进行比较,所提算法在收敛性和分布均匀性方面均具有明显优势.

改进细菌觅食算法求解柔性作业车间调度问题

针对柔性作业车间调度问题的NP难特性,提出一种改进的细菌觅食优化算法。采用集成法策略同时求解柔性作业车间调度问题的机器分配和工序调度子问题。将细菌个体表示为工序串,建立问题和算法的映射关系;分别针对普通细菌个体和当前最优个体设计了多重趋化操作,以增强算法的局部搜索能力;复制操作设置繁殖阈和死亡阈,以提高对历史经验的继承程度;迁移/驱散操作中,结合改进的LPT启发式规则,提出带倾向性的迁移/驱散操作方式。采用正交试验对算法的重要参数进行了优化配置,通过搜索算子优化效果对比实验证明了正交试验的结论;进行了收敛性能对比实验,证明算法具有优秀的全局开发能力和局部探索能力;典型算例实验结果表明,该算法能够有效求解柔性作业车间调度问题。

基于Pareto优化的离散自由搜索算法求解多目标柔性作业车间调度问题

针对多目标柔性作业车间调度问题搜索空间的离散性和求解算法的收敛性,提出一种基于Pareto优化的离散自由搜索算法来求解多目标柔性作业车间调度问题。在建立基于Markov链数学模型的基础上,证明了算法以概率1收敛;引入首达最优解期望时间来分析算法收敛速度,并分析了算法时间复杂度。采用基于工序排序和机器分配的个体表达方式,在多目标柔性作业车间离散域,利用自由搜索算法在邻域小步幅精确搜索和在全局空间大步幅勘测进行寻优;通过自由搜索算法自适应赋予个体各异辨别能力和Pareto优化概念来比较个体优劣性,不仅保留优化个体,而且使个体寻优方向沿多目标柔性作业车间调度问题Pareto前沿逼近。通过对搜索过程中产生的伪调度方案进行可行性判定,以确保调度方案可行。采用10×10FJSP和8×8FJSP问题的实例进行寻优测试,验证了所提算法的可行性和有效性。

解决无等待流水车间调度问题的离散粒子群优化算法

针对以生产周期为目标的无等待流水车间调度问题,提出了一种离散粒子群优化算法。研究了无等待流水车间调度问题的快速邻域搜索技术,并将其分别用于加强粒子、个体极值或全体极值的邻域探索能力,得到了三种改进的离散粒子群优化算法。基于典型算例的试验,表明了上述算法的有效性。

考虑批量装配的柔性作业车间调度问题研究

柔性作业车间调度是生产调度领域中的一个重要组合优化问题,由于取消了工序与加工设备的唯一性对应关系,因而相较于作业车间调度问题,具有更高的复杂度。针对该问题在批量装配方面的不足,考虑将批量因素与装配环节同时集成到柔性作业车间调度问题当中。以成品件的完工时间为优化目标,对该批量装配柔性作业车间调度问题进行了数学建模。针对该模型,提出一种多层编码结构的粒子群算法,并对该算法的各个模块进行了设计。最后,以实例验证了该数学模型的正确性及算法的有效性。

一类解决无等待流水车间调度问题的蚁群算法

针对以最大完成时间为目标的无等待流水车间调度问题,提出了一种蚁群算法。首先,基于复杂度为O(n)的最大完成时间算法简化了适应值的计算;其次,基于当前最优解和轨迹密度的新解构造方法提高了求解质量;第三,基于快速插入邻域算法的多重插入移动提高了搜索效率;最后,基于典型算例的仿真试验,表明了所得调度算法的可行性和优越性。

不确定条件下具有零等待的流水车间免疫调度算法

为了解决不确定条件下具有零等待的流水车间生产调度问题 ,采用三角模糊数来描述不确定的产品处理时间 ,在模糊规划理论的基础上建立了相应的调度模型。通过中间值最大隶属度算法 ,将原来的模糊调度模型转化为单目标的规划模型 ,并借鉴自然界中生物免疫系统的概念和机理 ,提出了解决此类问题的免疫调度算法。在该调度算法中 ,采用字符编码的方式来表示产品的处理顺序 ,每个抗体表示一组可行的具体调度方案 ,用亲和度来衡量抗体与抗原之间以及抗体与抗体之间的匹配程度 ,同时根据抗体的浓度自适应地调节搜索方向。通过仿真试验 。

基于遗传算法的车间作业调度问题求解

文章提出了一个求解车间作业调度问题的完备的、强壮的遗传算法。在分析车间作业调度问题的数学模型的基础上,给出了:(1)采用分段结构的染色体编码思想;(2)生成可行调度的算法;(3)计算调度目标函数的算法;(4)三种遗传算子及其辅助算子———修正算子的设计。最后,通过仿真验证了算法的有效性和稳定性。

求解柔性作业车间调度问题的免疫遗传算法

通过对柔性作业车间调度问题(FJSP)进行分析,借鉴生物免疫机理提出一种求解柔性作业车间调度问题的免疫遗传算法(IGA).该算法在保留基本遗传算法(SGA)随机全局搜索能力的基础上,通过抽取疫苗和接种疫苗等免疫机制,有效改善基本遗传算法的未成熟收敛和局部搜索能力差的不足,显著提高了基本遗传算法对全局最优解的搜索能力和收敛速度.仿真实例表明,免疫遗传算法能有效解决柔性作业车间调度问题.

基于关键路径求解作业车间调度问题的收敛性分析

为深入研究基于关键路径求解作业车间调度问题的算法收敛性理论,在构建状态空间与明确算法收敛性充要条件的基础上划分方案转化途径,在参与转换的工序数量与移动方式方面对Van Laarhoven,Nowicki,DellAmico,Balas与Nasiri,Zhang五种邻域结构的部分性质进行拓展,得到相应推论并明确转化途径与完工时间的关系。将五种邻域结构与状态寻优路径相对比,得出结论:五种邻域结构的应用不能满足算法收敛直接连通性的充要条件,利用五种邻域结构求解作业车间调度问题无法保证收敛。所提方案转化途径与工序在关键工序集与非关键工序集间的移动方式,为基于关键路径的邻域结构设计提供了新的思路。