基于进化计算的多目标流水车间批组调度问题研究

发布时间：2020-06-05 05:59

【摘要】：流水车间批组调度(Flowshop Scheduling with Batching, FSB)问题在实际制造系统中有着广泛的应用背景,比传统的流水车间调度问题更复杂,有效的调度算法可以提高资源的利用率和生产效益。因此,FSB问题的研究具有重要的理论和实用价值。相对于传统的优化方法,进化算法在解决多目标优化问题时具有一定的优势,因此本文采用进化算法解决多目标FSB问题,针对FSB问题的三个分支(带有成组工件的FSB问题、批交付FSB问题以及具有批加工设备的FSB问题)展开研究,取得了较好的结果。主要内容如下：研究带有成组工件的FSB问题,建立了同组工件可拆分条件下的多目标优化模型,设计了多目标混合遗传算法(MOHGA).算法中引入基于累计排序策略和自适应密度评估的适应度计算方式更好地保持群体多样性,并根据问题的特征定义了两种邻域结构进行局部搜索提高算法的收敛速度。基准问题和实际问题的求解结果,验证了所提算法的有效性。应用有限Markov链的有关理论分析了MOHGA的收敛性。构建了批交付FSB问题的多目标优化模型,首先对提前／拖期最小化问题,分析了优化调度的性质,给出了工件排序一定时确定开工时间的最优算法,实验分析了成组技术约束对提前／拖期目标的影响。其次对包含提前／拖期在内的多个目标的高维优化问题,提出了利用权重向量控制进化方向的可控权重进化算法(CWEA)。仿真算例和调度实例的计算结果表明,CWEA能有效克服单纯Pareto排序比较在解决高维优化问题时的困难,对于双目标和目标数目较多的优化问题均能获得较多的分布更均匀的解。针对有不可用时间段约束的FSB问题,提出采用工件的非置换排序以减少机器额外的空闲时间,并研究了机器有固定的不可用时间段和机器不可用时刻基于运转时间两种情况下的调度优化。提出启发式算法生成工件在各机器上的调度,基于改进的可控权重进化算法(ICWEA)优化工件调度的优先级顺序。通过对不同规模的调度实例进行计算,结果表明,ICWEA在求解该类问题时有较好的优化效果。研究具有批加工设备的FSB问题。首先针对混合两工序批调度问题提出顺序分批方法对工件进行分批,采用改进的可控权重进化算法(ICWEA)优化工件调度优先排序。其次对工件有不同尺寸,批加工时间可变的两机批调度问题,设计了多目标混合粒子群优化算法(MOHPSO)进行优化,利用整批对换式邻域进行局部搜索。仿真实验表明,在求解两机批调度问题时,MOHPSO算法性能优于其他几种多目标粒子群优化算法。
【学位授予单位】：大连理工大学
【学位级别】：博士
【学位授予年份】：2011
【分类号】：F273;F425

【引证文献】