混合流水车间插单重调度的超启发式遗传算法

针对带有紧急订单的混合流水车间插单重调度问题,提出了一种双层编码的超启发式遗传算法。针对混合流水车间具有的订单排序和机器选择的双决策特征,在算法低层设计双层编码方案,在个体中表示订单排序和机器选择两类信息,对应一个唯一调度解,进而提出了12种排序和选择启发式对个体进行迭代优化;在算法高层采用自适应遗传算法,用来确定订单排序启发式和机器选择启发式的操作组合以及各组合执行的次序,并设计了自适应变异算子来优化算法的有效性。大规模数据实验的结果表明,该算法具有很好的求解质量和求解效率。

混合遗传算法求解含机器可利用约束的HFSP

针对含机器阻塞和可利用约束的混合流水车间调度优化问题,考虑工件运输时间,以最小化总加权完工时间为优化目标,建立混合整数规划模型,提出一种基于启发式规则的自适应混合遗传算法求解该模型。在传统遗传算法的基础结构上,引入五种启发式规则生成部分初始种群,从而改善部分初始解的质量;设计分段自适应交叉概率和变异概率计算公式,以加快算法收敛;利用局域搜索对得到的调度解进行再次优化,进一步提高算法搜索能力。对不同规模问题进行仿真实验,结果验证了该算法的可行性和有效性。

求解阻塞混流生产机器人制造单元调度问题的分支定界算法

针对阻塞混流生产机器人制造单元调度问题,为了同时优化机器人运行顺序和工件加工顺序,提出了分支定界算法。首先,定义机器人活动,将双排序转化为单排序;其次,构建顺序插入规则生成可行解;最后,依据顺序插入规则,设计了分支过程。通过计算随机生成算例,计算结果表明:工作站个数为3时,分支定界算法得到的目标函数值与CPLEX相同,但平均运行时间比CPLEX降低38.58%,证实了分支定界算法的有效性;工作站个数大于3时,与CPLEX相比,在同等时间内,有85.19%的算例搜索到更好解,因此,对于大规模情形,分支定界算法更有价值。

双层束搜索算法优化机器人制造单元调度问题

针对混流生产阻塞机器人制造单元调度问题,给出了可行机器人运动插入法,构建可行解。依据可行机器人运动插入法,提出双层过滤变宽度束搜索算法进行求解。搜索过程利用局部评价函数和全局评价函数对节点进行两次择优选取。通过计算随机生成算例,仿真结果表明,相对于以分支定界算法产生的可行解进行变邻域搜索、分支定界算法、局部评价函数束搜索算法、全局评价函数束搜索算法和双层过滤定宽度束搜索算法,双层过滤变宽度束搜索算法不但能显著提高搜索效率,而且解的平均改进度分别为3.07%、6.07%、7.79%、12.62%、14.47%。

基于启发式-遗传算法的混合流水车间成套订单问题

针对并行机带工艺约束的混合流水车间环境下的成套订单问题,提出一种基于分批调度策略的启发式遗传算法。首先,以最大化加权成套订单数为目标建立数学模型,对工件分批采用内层遗传算法生成初始调度;再以外层启发式规则转化目标为最大加权成套订单数,设计一种订单评价指标用于突破交货时间瓶颈;最后,内外层算法循环优化,直到不存在瓶颈即得到满意解。实例验证结果显示,启发式遗传算法能在20代以内得到每组最优调度,种群规模大于50时得到最优解的概率达到70%。对比实验结果显示,当问题规模增加到40个工件时,遗传算法求解时间显著增加,在不同问题规模中临界比最小(SCR)规则优化后的加权成套订单数均较启发式遗传算法更少。启发式遗传算法能在实际工程中够将加权成套订单数提高到1.5倍以上,使加工时间平均缩短5.1%。结果表明,启发式遗传算法能够改善成套订单问题在混合流水车间环境下易陷入局部最优的问题,可在大规模复杂混合流水车间的订货型企业中实现计划与生产同步,具有实际意义。

多目标多约束混合流水车间插单重调度问题研究

研究了多目标多阶段混合流水车间的紧急订单插单重调度问题,综合考虑工件批量、刀具换装时间、运输能力等约束.先以最小化订单完工时间和最小化总运输时间为双目标建立静态初始订单调度模型,再针对紧急订单插单干扰,增加最小化总加工机器偏差值目标,建立三目标重调度优化模型,并分别用NSGA-Ⅱ算法与融合基于事件驱动的重调度策略和重排插单策略的NSGA-Ⅲ算法对两个模型进行求解.最后,以某实际船用管类零件生产企业为案例,先对NSGA-Ⅱ算法和NSGA-Ⅲ算法的性能进行评估,得到NSGA-Ⅱ算法更适用于解决双目标优化问题而NSGA-Ⅲ算法在解决三目标优化问题时表现更优的结论,再将所建模型与所提算法应用于该企业的十组插单案例中,所得优化率接近三分之一,验证了实用性和有效性.