论文部分内容阅读
混合流水车间(Hybrid Flowshop,HFS)具有多任务,多工序,多并行机,同一工序不同工件加工时间不同等特点。当混合流水车间中存在可重入生产环节时,会导致制造过程更加复杂,生产负荷成倍增加,设备负载不均衡性增大等问题,这极大增加了混合流水车间排产的难度,可重入混合流水车间排产优化问题(Re-entrant Hybrid Flowshop Scheduling Problem,RHFSP)是一类典型NPhard问题。同时RHFSP排产优化问题广泛存在于半导体生产、客车制造、钢铁冶炼等关键行业中。由于受到实际生产车间的空间和存储设备等条件的制约,生产线上只能设置容量有限的缓冲区。可重入混合流水车间具有执行可重入工序的工件需重新插入到待加工队列中的特点,当工件折返执行重入工序时,与已在上道工序完工的工件争夺缓冲区资源,出现影响整个生产过程的死锁现象。在缓冲区资源受限和可重入工序同时存在的情况下,产生的死锁现象会对生产进程产生严重影响,这更进一步加剧了生产过程的不确定性,极大的增加了企业的生产管理组织的难度。因此研究具有可重入工序的混合流水车间有限缓冲区排产优化问题(Limited Buffer Re-entrant Hybrid Flowshop Scheduling Problem,LB RHFSP)解决方法具有重要的理论和工程应用价值。本文针对LBRHFSP排产优化问题,建立具有可重入工序的混合流水车间有限缓冲区数学规划模型,提出求解LBRHFSP排产优化问题的一种优化方案。当工件折返执行重入工序时,与已在上道工序完工的工件争夺缓冲区资源时,会产生死锁现象,如果缓冲区能够为执行可重入工序的工件提前预留容量,则该工件能顺利折返进入到有限缓冲区中,从而降低生产过程中死锁现象发生的概率,保证了生产进程能够顺利的进行,因此提出一种基于马尔科夫链的可重入缓冲区容量动态预留方法,保证在可重入工序和有限缓冲区同存在的条件下排产过程的顺利进行。同时,采用一种基于高响应比优先调度策略的局部优化方法,在局部指派过程中使工件在工位上分配更加合理,进一步降低了死锁现象发生的概率。采用基于反向学习初始化种群策略的变邻域搜索狼群算法作为全局优化方法,并结合局部指派方法和缓冲区容量动态预留方法,给出一种针对LBRHFSP排产问题的优化方案。本文具体研究内容如下:(1)建立LBRHFSP排产优化问题数学规划模型在标准混合流水车间基础上增加可重入工艺流程的模型元素,并引入了有限缓冲区的约束,给出具有可重入工序的混合流水车间有限缓冲区排产问题数学规划模型,并且运用数学语言描述与分析工件在生产过程中因争夺缓冲区资源而导致的死锁现象。(2)LBRHFSP排产优化问题的全局优化方法研究狼群算法(Wolf Pack Algorithm,WPA)相比其他群体智能进化算法具有收敛速度快、寻优精度较高等优点,因此,本文将狼群算法作为全局优化算法求解这类复杂的排产优化问题。同时,狼群算法也具有容易陷入局部极值等特点。针对狼群算法的缺陷,本文提出四种方法对狼群算法进行改进:①提出一种基于莱维飞行的游猎行为,使探狼可以探查小概率的搜索区域,扩大搜索范围,改善狼群算法寻优能力。②提出一种基于汉明距离的种群动态更新机制,当最优值停滞进化次数超过阈值时,通过汉明距离判断个体间相似度,淘汰与最优个体相似度高的个体同时补充相似度低、差异性大的新个体,从而丰富个体多样性,增强算法跃出局部极值的能力。③提出一种基于变邻域搜索的游猎行为,利用不同的动作构成的邻域结构进行交替搜索,使探狼以大小范围搜索模式相交替的方式探查小概率的搜索区域,扩大搜索范围,增强算法在解空间的搜索性能,进一步提升进化活力。④为进一步提高算法寻优速度,采用基于反向学习的种群初始化策略,扩大初始解在解空间中的搜索范围,确定相对优秀的个体作为初始个体,提高初始解质量,加速了寻优进程。基于上述四种改进方法,本文提出基于莱维飞行的动态狼群算法(Dynamic wolf pack algorithm Based on Levy Flight,LDWPA)和基于反向学习初始化种群策略的变邻域搜索狼群算法(Opposition-based Learning Wolf Algorithm Based on Variable Neighborhood Search,OLVWPA)两种新的改进狼群算法便于更好的求解LBRHFSP排产优化问题。(3)LBRHFSP排产过程中的死锁问题研究为解决可重入工序的混合流水车间排产过程中出现的死锁现象,提出一种基于马尔科夫链的可重入缓冲区容量动态预留方法。通过预测工件将折返执行可重入工序的工位上加工的工件发生变化情况,即该工序所对应缓冲区资源释放概率,在排产过程中为执行可重入工序的工件将要进入的缓冲区动态预留容量,使得工件能够顺利折返进入到有限缓冲区中,降低因工件争夺缓冲区资源而导致严重连续阻塞现象对生产进程的影响,降低排产过程中死锁现象发生的概率,从而保证了排产过程能够顺利的进行。(4)LBRHFSP排产问题的优化方案设计综合上述研究成果,提出一种针对LBRHFSP排产问题的优化方案,采用基于马尔科夫链的有限缓冲区容量动态预留方法,降低死锁现象发生概率,保证排产过程顺利进行。在此基础上,探索该排产问题的优化方法,通过分析对比本文提出的四种狼群算法的改进方法,确定全局优化方法采用OLVWPA算法。局部指派方法采用一种高响应比优先调度策略,确定缓冲区内工件加工优先级,用于控制缓冲区内工件的分配过程,进一步降低死锁现象出现的概率,并与全局优化方法结合获得更好的优化效果。通过实例仿真验证,证明了该方案在求解LBRHFSP排产优化问题时的有效性与可行性。