基于进化优化的多目标批量流水线调度

发布时间：2018-10-09 09:35

【摘要】：批量流水线调度问题是指,在加工过程中,每个工件可以分割为若干小批量,每个小批量加工之后,才能传送到下游的机器继续加工。通过这种加工方式,能够缩短工件的最大完工时间和机器空闲时间,加速生产流程,增加资源利用率,以及提高用户满意度。因此,该问题广泛应用于制造系统、装配线、信息服务设施、化学、纺织、塑料和半导体等工业生产中。批量流水线调度问题有时优化一个目标函数,有时优化多个相互冲突的目标函数;有时决策变量不需要满足额外的约束,有时需要满足一或多个约束;有时调度问题的所有参数均为确定值,有时至少存在一个参数是不确定的。已有研究表明,含有约束的调度问题,在多项式时间内,不能得到问题的最优解。那么,不确定约束多目标批量流水线调度问题的求解,就更具有挑战性。尽管已有多种求解批量流水线调度问题的智能优化方法,但是,这些方法仅适用于确定的单目标批量调度问题,还无法用于求解多目标、多约束以及参数具有不确定的批量流水线调度问题。鉴于此,本文针对上述3大问题,构建了多目标批量、多目标阻塞批量、加工时间不确定以及机器故障的多目标阻塞批量流水线调度问题的数学模型,提出相应的高效进化求解方法。具体研究内容如下:首先,建立多目标批量流水线调度问题的数学模型,提出求解该问题的INSGA-II(Improved Nondominated Sorting Genetic Algorithm II,NSGA-II)优化方法。该方法主要包含如下3个方面:(1)基于NEH(Nawaz,Enscore and Ham)启发式方法产生若干性能优越的初始解,显著提高初始种群质量;(2)将概率分布估计算法和基于插入和交换的变异算子,分别代替传统的交叉和变异算子,加速算法的收敛速度;(3)当种群的多样性小于某一给定阈值时,提出一种简单有效的重启策略,提高种群多样性。其次,将阻塞约束加入到上述模型中,建立多目标阻塞批量流水线调度问题数学模型,提出求解该问题的混合人工蜂群方法。该方法主要包含如下3个方面:(1)基于MME(combination MinMax with NEH)和NEH的启发式方法变体,产生多个高质量的初始解;(2)利用非支配解信息,提出了改进的相似工件顺序交叉和相似块交叉算子,并用于产生新解,提高算法的全局探测能力;(3)基于Pareto占优的局部搜索算法,提高算法的局部能力。再次,建立加工时间不确定的多目标阻塞批量流水线调度问题的数学模型,提出求解该问题的进化优化方法。文中主要研究了如下2大问题:(1)利用区间的中点和半径信息,将区间多目标阻塞批量流水线调度问题,转化为传统的多目标优化问题;(2)采用改进差分算子,增强算法的全局探测能力;采用基于理想点辅助的局部搜索算法,提高算法的局部开发能力。然后,建立带机器故障的多目标阻塞批量流水线调度问题的数学模型,提出求解该问题的进化优化方法。该方法主要包含如下2个方面:(1)充分利用已有的非支配调度策略提供的信息,设计交叉算子;(2)基于机器故障特性,提出重调度策略。最后,以某太阳能公司批量电池组件生产为应用对象,对实际的批量流水线调度问题进行了分析,并将前面所提优化理论成果应用到该公司的生产中,通过仿真实验,验证了所提算法的可行性和高效性。上述研究成果不但能够丰富和深化已有的调度理论,也能够推动上述理论与方法在太阳能电池组件生产等车间调度问题的应用,从而直接服务于国民经济和社会发展。
[Abstract]:......
【学位授予单位】：中国矿业大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：TP18;TB497
，

本文编号：2258860