基于候鸟迁徙算法的批量流混合流水车间调度方法研究
发布时间：2020-07-18 11:02
【摘要】：混合流水车间调度问题(Hybrid Flowshop Scheduling Problem,HFSP)的研究具有重要的学术价值和工程意义。为满足带批处理的多品种小批量生产模式,本文致力于将批量流(Lot Streaming,LS)引入HFSP中。考虑静态和动态的车间环境,基于两种分批策略(等量一致分批和不等量一致分批),本文分别构建了静态调度和重调度模型,研究了问题特征知识和调度规则,并以候鸟迁徙算法(Migrating Birds Optimization,MBO)为主要技术手段,提出了与问题特征相结合的调度算法。最后,通过实际工程案例的应用和分析,验证了所提模型和算法的有效性和优越性。主要研究工作如下:针对等量一致分批的批量流混合流水车间静态调度问题(Equal Lot Streaming Hybrid Flowshop Static Scheduling Problem,ELS_HFSP),建立了以总流经时间为目标的混合整数规划模型(Mixed Integer Linear Programming,MILP),并提出了基于MBO的求解算法EMBO(Effective MBO)。在算法中,结合分批特征与目标特点,基于批次序列,提出了“子批优先”、最短等待时间及右移与插入等启发式规则决定各批次的调度顺序。结合MBO算法独有的V形种群结构,提出了联合邻域搜索以及种群竞争机制,增强算法的协同搜索能力;结合MBO算法独有的分享和受益机制,提出一种动态解接受准则来保证种群的多样性;提出一种基于Glover和局部搜索算法的探索机制,帮助算法跳出局部最优。最后,通过与CPLEX和其它算法的对比实验,验证了所提算法的有效性和优越性。针对等量一致分批的批量流混合流水车间重调度问题(Equal Lot Streaming Hybrid Flowshop Rescheduling Problem,ELS_HFRP),考虑机器故障这一随机扰动,基于ELS_HFSP原调度方案,以总流经时间和子批开工时间偏差为目标,建立了多目标优化模型。基于EMBO和问题的多目标特性,通过引入多属性决策方法-TOPSIS,评估解的适应度值,提出了MMBO算法(Multi-objective MBO)。在算法中,基于ELS_HFSP的解码策略,提出了针对机器故障扰动的动态解码方案,并提出一种改进机制缩短子批开工时间偏差;基于Glover操作进行种群初始化以利用ELS_HFSP原始解含有的信息;在竞争机制中,引入种群重排和快速非支配排序技术来调整V形种群结构,并利用种群繁殖策略进一步提高种群质量;在探索机制中,基于Pareto特性,提出一种局部搜索算法来提升替代解的质量。最后,通过与其它多目标算法的对比实验,验证了所提算法的有效性和优越性。针对不等量一致分批的批量流混合流水车间静态调度问题(Inequal Lot Streaming Hybrid Flowshop Static Scheduling Problem,ILS_HFSP),以总流经时间为目标,建立了MILP模型。为了同时解决批次序列及批量分割的集成优化问题,设计了两层编码机制,并提出了相应的初始化方法。基于EMBO和两层编码机制,改进了变邻域下降搜索(Variable Neighborhood Descent,VND)以保证解空间的充分搜索,提出了VMBO算法(VND-based MBO)。在算法中,针对批量分割,验证了“批次优先”比“子批优先”更加有效,并调整了SWT规则;在竞争机制和探索机制分别设计了批量选取操作以及基于块交换的扰动操作。最后,通过与CPLEX和其它算法的对比实验,验证了所提算法的有效性和优越性。针对不等量一致分批的批量流混合流水车间重调度问题(Inequal Lot Streaming Hybrid Flowshop Rescheduling Problem,ILS_HFRP),考虑机器故障这一随机扰动,基于ILS_HFSP原调度方案,以总流经时间、子批开工时间偏差以及平均子批批量调整量为目标,建立了多目标优化模型。基于问题的三目标特性及VND搜索特性,通过引入分解策略,提出了MMBO/D算法(MMBO Based on Decomposition)。在算法中,基于ILS_HFSP编码及ELS_HFRP解码和改进机制,考虑批量分割,分别给出了动态解码方案及改进机制;基于分解策略,提出一种全新的分享和受益机制,保证了过程的高效性,并提出一种变权重策略和全局更新机制执行解的更新;在竞争机制中,应用一种基于相似子问解的协同搜索进一步提升种群质量;在探索机制中,基于变权重策略,引入一种新的判断解是否陷入局部最优的判定准则。最后,通过与其它多目标算法的对比实验,验证了所提算法的有效性和优越性。针对国内某汽车生产公司机械加工车间的实际工程案例,将本文提出的理论和方法应用到该车间的实际生产调度中。根据该车间批量转运的实际情况,将问题归结为ELS_HFSP和ILS_HFSP模型,并分别利用CPLEX和本文所提算法进行求解,验证了模型和算法的有效性;针对机器故障这一随机扰动事件,将问题归结为ELS_HFRP和ILS_HFRP模型,并利用本文所提算法进行求解,验证了模型及算法的有效性。最后,对全文的成果以及创新之处进行了总结,并展望了未来的研究方向。
【学位授予单位】：华中科技大学
【学位级别】：博士
【学位授予年份】：2019
【分类号】：TP18;O224
【图文】：
图 1-3 V 形队列结构MigratingBirdsOptimization,MBO）由 Duma发式算法，该算法受到候鸟在迁徙过程保持 V 仅能够节省鸟群在飞行过程中的能量消耗，以避免相互碰撞。生物学家研究表明，如图 1-个：每只鸟的翅尖与前一直鸟翅尖之间的横向距间的纵向距离（depth）以及 V 字形的开度角度表征解与解之间的关联，由一个领导解和位于了一种独特的分享和受益机制来模拟飞行中的N1N2N3左分享集合L1N1N2NkN3S1S2N1N+2SsNk-s更新左队列跟随解1
2 5 10 20500 800 1000 150030 50 80 100表 2-3 正交矩阵以及响应值 参数 响应值ps t L r25 2 500 30 5187625 5 800 50 5180325 10 1000 80 5158925 20 1500 100 5195851 2 800 80 5189351 5 500 100 5160251 10 1500 30 5183651 20 1000 50 5152381 2 1000 100 5177481 5 1500 80 5172581 10 500 50 5184981 20 800 30 51934101 2 1500 50 52164101 5 1000 30 52388101 10 800 100 52155101 20 500 80 52207
表2-12 在 30下的对比结果MBO IMBO MMBO GA GARD0.39(0.21) 0.32(0.14) 1.46(0.53) 1.06(0.56) 1.11(0.57) 0.30.63(0.29) 0.44(0.16) 2.28(0.76) 1.16(0.50) 1.45(0.76) 0.50.97(0.44) 0.61(0.26) 2.47(0.97) 1.87(0.95) 2.36(1.10) 0.70.58(0.32) 0.45(0.20) 2.17(1.05) 1.54(0.79) 1.68(0.87) 0.50.87(0.33) 0.72(0.27) 6.48(2.40) 0.83(0.42) 2.42(0.67) 4.42.24(0.58) 2.28(0.43) 6.84(2.84) 2.59(0.77) 3.66(1.31) 4.32.28(0.57) 2.02(0.41) 7.05(2.79) 2.32(0.48) 3.63(1.21) 5.12.51(0.67) 2.24(0.43) 7.01(2.80) 2.74(0.61) 3.69(1.10) 5.22.07(0.55) 1.99(0.50) 6.62(3.62) 1.91(0.35) 3.79(1.26) 3.12.52(0.84) 2.34(0.56) 6.62(3.98) 2.37(0.50) 5.12(1.20) 9.62.86(0.92) 2.41(0.69) 5.55(3.99) 2.68(0.74) 5.47(1.39) 4.92.14(1.05) 2.41(0.78) 4.88(4.09) 2.85(0.70) 6.46(1.74) 4.42.81(0.77) 2.37(0.59) 4.23(3.93) 2.34(0.46) 5.87(1.47) 5.12.82(0.95) 2.30(0.62) 6.72(4.83) 2.43(0.46) 5.88(1.36) 5.12.70(1.07) 2.92(0.94) 5.45(4.60) 3.13(0.80) 7.11(1.41) 4.53.40(1.19) 2.95(0.95) 5.28(4.20) 3.11(0.71) 7.60(1.58) 3.53.22(0.92) 2.68(0.70) 4.13(4.62) 2.49(0.45) 6.86(1.52) 5.43.71(1.22) 3.04(0.83) 5.24(4.41) 2.77(0.52) 7.63(1.26) 4.03.97(1.49) 3.35(1.00) 4.50(2.47) 3.18(0.60) 9.16(1.71) 4.03.06(1.26) 2.63(1.08) 4.99(0.69) 2.95(0.74) 8.87(1.92) 5.7.29(0.78) 2.02(0.58) 5.00(2.98) 2.32(0.61) 4.99(1.27) 4.0
本文编号：2760804
【学位授予单位】：华中科技大学
【学位级别】：博士
【学位授予年份】：2019
【分类号】：TP18;O224
【图文】：
图 1-3 V 形队列结构MigratingBirdsOptimization,MBO）由 Duma发式算法，该算法受到候鸟在迁徙过程保持 V 仅能够节省鸟群在飞行过程中的能量消耗，以避免相互碰撞。生物学家研究表明，如图 1-个：每只鸟的翅尖与前一直鸟翅尖之间的横向距间的纵向距离（depth）以及 V 字形的开度角度表征解与解之间的关联，由一个领导解和位于了一种独特的分享和受益机制来模拟飞行中的N1N2N3左分享集合L1N1N2NkN3S1S2N1N+2SsNk-s更新左队列跟随解1
2 5 10 20500 800 1000 150030 50 80 100表 2-3 正交矩阵以及响应值 参数 响应值ps t L r25 2 500 30 5187625 5 800 50 5180325 10 1000 80 5158925 20 1500 100 5195851 2 800 80 5189351 5 500 100 5160251 10 1500 30 5183651 20 1000 50 5152381 2 1000 100 5177481 5 1500 80 5172581 10 500 50 5184981 20 800 30 51934101 2 1500 50 52164101 5 1000 30 52388101 10 800 100 52155101 20 500 80 52207
表2-12 在 30下的对比结果MBO IMBO MMBO GA GARD0.39(0.21) 0.32(0.14) 1.46(0.53) 1.06(0.56) 1.11(0.57) 0.30.63(0.29) 0.44(0.16) 2.28(0.76) 1.16(0.50) 1.45(0.76) 0.50.97(0.44) 0.61(0.26) 2.47(0.97) 1.87(0.95) 2.36(1.10) 0.70.58(0.32) 0.45(0.20) 2.17(1.05) 1.54(0.79) 1.68(0.87) 0.50.87(0.33) 0.72(0.27) 6.48(2.40) 0.83(0.42) 2.42(0.67) 4.42.24(0.58) 2.28(0.43) 6.84(2.84) 2.59(0.77) 3.66(1.31) 4.32.28(0.57) 2.02(0.41) 7.05(2.79) 2.32(0.48) 3.63(1.21) 5.12.51(0.67) 2.24(0.43) 7.01(2.80) 2.74(0.61) 3.69(1.10) 5.22.07(0.55) 1.99(0.50) 6.62(3.62) 1.91(0.35) 3.79(1.26) 3.12.52(0.84) 2.34(0.56) 6.62(3.98) 2.37(0.50) 5.12(1.20) 9.62.86(0.92) 2.41(0.69) 5.55(3.99) 2.68(0.74) 5.47(1.39) 4.92.14(1.05) 2.41(0.78) 4.88(4.09) 2.85(0.70) 6.46(1.74) 4.42.81(0.77) 2.37(0.59) 4.23(3.93) 2.34(0.46) 5.87(1.47) 5.12.82(0.95) 2.30(0.62) 6.72(4.83) 2.43(0.46) 5.88(1.36) 5.12.70(1.07) 2.92(0.94) 5.45(4.60) 3.13(0.80) 7.11(1.41) 4.53.40(1.19) 2.95(0.95) 5.28(4.20) 3.11(0.71) 7.60(1.58) 3.53.22(0.92) 2.68(0.70) 4.13(4.62) 2.49(0.45) 6.86(1.52) 5.43.71(1.22) 3.04(0.83) 5.24(4.41) 2.77(0.52) 7.63(1.26) 4.03.97(1.49) 3.35(1.00) 4.50(2.47) 3.18(0.60) 9.16(1.71) 4.03.06(1.26) 2.63(1.08) 4.99(0.69) 2.95(0.74) 8.87(1.92) 5.7.29(0.78) 2.02(0.58) 5.00(2.98) 2.32(0.61) 4.99(1.27) 4.0
本文编号：2760804
本文链接：https://www.wllwen.com/kejilunwen/zidonghuakongzhilunwen/2760804.html
