混合离散差分进化算法求解自动化制造系统双目标调度问题研究

摘要

本文研究问题针对自动化制造系统周期调度问题，以最小化周期时间和物料搬运机器人运作成本为双目标进行优化，求解问题的帕累托近似最优解集。但本文采用不同的研究思路和方法。首先建立了基于给定的机器人搬运作业排序的问题线性规划模型。由于模型的数学性质，可利用基于图论的多项式算法求解。由此，对于一组给定的机器人搬运作业排序，可在多项式时间内计算获得对应的最小周期时间和最小机器人运作成本。因此，将问题求解转化为对搬运作业排序的枚举。为此，本文提出混合离散差分进化算法求解问题的非支配解集。该算法直接采用机器人搬运作业排序作为种群个体编码，并采用Pan,Wang和Qian(2009)提出的求解无等待flowshop双目标离散差分进化算法基本框架(包含:变异交叉算子、选择机制等)搜索问题的非支配搬运作业排序。在算法设计中，首先根据问题特征计算出自动化制造系统中最大在制工件(work-in-process,WIP)数Kmax，并依此将问题全局解空间划分为Kmax个子空间。为了保证非支配解的多样性，在初始化种群产生中，将种群划分为Kmax个子种群，并根据每个种群k值(k=1、2、...、Kmax)产生具有相同在制工件数k的初始个体。在种群进化过程中，对于变异交叉后产生的不可行个体，提出了基于图论的修复算子，避免了早熟收敛。同时在进化过程中，为了保证各子种群同时向帕累托前沿收敛，算法动态监测各子种群个体数，并且提出了子种群个体数动态增补机制。最后通过五个基准案例和大量随机算例的测试，并与Feng,Che和Wang(2013)提出的。约束法双目标算法(FCW最优算法)和Pan,Wang和Qian(2009)提出的双目标离散差分进化算法(PWQ)进行对比测试分析。实验结果表明，本文提出的算法在求解基准案例和随机算例中，计算时间明显优于FCW最优算法，求解的非支配解质量优于PWQ算法。