考虑能耗的多目标拆卸线平衡优化与层次分析法决策
|
摘要
针对拆卸过程中能耗浪费和负荷不均衡现象,以最小化拆卸能耗、工作站数目、平滑指数、危害指数和需求指数为优化目标,建立了多目标拆卸线平衡模型。结合拆卸线平衡问题的特点,设计了一种基于Pareto的离散果蝇算法,在嗅觉搜索阶段,采用单点变异操作;在视觉搜索阶段,筛选最优邻域解以更新个体;为了增加算法的全局寻优能力,用两点交叉操作执行全局协作机制。为了提高收敛效果,采用精英保留策略对外部档案中的非劣解进行维护。通过求解不同规模的拆卸算例,并与现有多种算法进行对比,验证了所提算法的有效性。以27项任务的某型电视机为拆卸实例,通过所提算法求得12个非劣解,采用层次分析法对Pareto解集进行排序,筛选最满意解,结果表明了所提方法和模型的可行性和有效性。
Aiming at the phenomenon of energy consumption and workload unbalance during the process of actual disassembly,a multi-objective disassembly line balance model was established to minimize the disassembly energy consumption,workstations number,smoothing index,hazard index and demand index.Combined with the characteristics of disassembly line balance problem,a multi-objective discrete fruit fly algorithm based on Pareto was designed.A single point mutation operation was used in the olfactory search stage,and the optimal neighborhood solution was filtered to update the individual in the visual search stage.To strengthen the global optimization ability of algorithm,the global cooperation mechanism was implemented by performing the two-point crossover operation.To improve the convergence effect,the elite strategy was used to maintain the non-inferior solutions in the external file.The effectiveness of the proposed algorithm was verified by solving the disassembly examples of different sizes and the solving results were compared with the existing algorithms.Through applying the proposed algorithm to solving a certain type of TV disassembly instance involving 27 tasks,12 non-inferior solutions were obtained,and the most satisfactory solution was selected by sorting Pareto solutions with analytic hierarchy process.The results further identified the feasibility and effectiveness of the proposed method and model.
Aiming at the phenomenon of energy consumption and workload unbalance during the process of actual disassembly,a multi-objective disassembly line balance model was established to minimize the disassembly energy consumption,workstations number,smoothing index,hazard index and demand index.Combined with the characteristics of disassembly line balance problem,a multi-objective discrete fruit fly algorithm based on Pareto was designed.A single point mutation operation was used in the olfactory search stage,and the optimal neighborhood solution was filtered to update the individual in the visual search stage.To strengthen the global optimization ability of algorithm,the global cooperation mechanism was implemented by performing the two-point crossover operation.To improve the convergence effect,the elite strategy was used to maintain the non-inferior solutions in the external file.The effectiveness of the proposed algorithm was verified by solving the disassembly examples of different sizes and the solving results were compared with the existing algorithms.Through applying the proposed algorithm to solving a certain type of TV disassembly instance involving 27 tasks,12 non-inferior solutions were obtained,and the most satisfactory solution was selected by sorting Pareto solutions with analytic hierarchy process.The results further identified the feasibility and effectiveness of the proposed method and model.
引文
[1]Ministry of Commerce,et al.Renewable resource recovery system construction medium and long term plan(2015-2020)[J].China Resources Comprehensive Utilization,2015,33(1):3-8(in Chinese).[商务部,等.再生资源回收体系建设中长期规划(2015-2020年)[J].中国资源综合利用.2015,33(1):3-8.]
[2]MCGOVERN S M,GUPTA S M.A balancing method and genetic algorithm for disassembly line balancing[J].European Journal of Operational Research,2007,179(3):692-708.
[3]MCGOVERN S M,GUPTA S M.Combinatorial optimization analysis of the unary NP-complete disassembly line balancing problem[J].International Journal of Production Research,2007,45(18):4485-4511.
[4]MCGOVERN S M,GUPTA S M.Uninformed and probabilistic distributed agent combinatorial searches for the unary NP-complete disassembly line balancing problem[C]//Proceedings of the International Society for Optical Engineering.Bellingham,Washington,D.C.,USA:SPIE,2005:81-92.
[5]AVIKAL S,MISHRA P K,JAIN R.A Fuzzy AHP and PROMETHEE method-based heuristic for disassembly line balancing problems[J].International Journal of Production Research,2014,52(5):1306-1317.
[6]ALTEKIN F T,KANDILLER L,OZDEMIREL N E.Profitoriented disassembly-line balancing[J].International Journal of Production Research,2008,46(10):2675-2693.
[7]KALAYCI C B,POLAT O,GUPTA S M.A hybrid genetic algorithm for sequence-dependent disassembly line balancing problem[J].Annals of Operations Research,2016,242(2):321-354.
[8]KALAYCI C B,GUPTA S M.A hybrid genetic algorithm approach for disassembly line balancing[C]//Processing of the42nd Annual Meeting of Decision Sciences Institute.Boston,Mass.,USA:DSL,2011:713-718.
[9]WANG Kaipu,ZHANG Zeqiang,ZHU Lixia,et al.Pareto genetic simulated annealing algorithm for multi-objective disassembly line balancing problem[J].Computer Integrated Manufacturing Systems,2017,23(6):1277-1285(in Chinese).[汪开普,张则强,朱立夏,等.多目标拆卸线平衡问题的Pareto遗传模拟退火算法[J].计算机集成制造系统.2017,23(6):1277-1285.]
[10]DING L P,TAN J R,FENG Y X,et al.A new multi-objective ant colony algorithm for solving the disassembly line balancing problem[J].International Journal of Advanced Manufacturing Technology,2010,48(5/6/7/8):761-771.
[11]KALAYCI C B,GUPTA S M.A particle swarm optimization algorithm for solving disassembly line balancing problem[C]//Proceedings of the Northeast Region Decision Sciences Institute Conference.Houston,Tex.,USA:DSI,2012:347-357.
[12]KALAYCI C B,GUPTA S M,NAKASHIMA K.A simulated annealing algorithm for balancing a disassembly line[C]//Proceedings of the Design for Innovative Value Towards a Sustainable Society.Berlin,Germany:Springer-Verlag,2012:714-719.
[13]WANG Kaipu,ZHANG Zeqiang,MAO Lili,et al.Pareto artificial fish swarm algorithm for multi-objective disassembly line balance problems[J].China Mechanical Engineering,2017,28(2):183-190(in Chinese).[汪开普,张则强,毛丽丽,等.多目标拆卸线平衡问题的Pareto人工鱼群算法[J].中国机械工程,2017,28(2):183-190.]
[14]PAN Wenchao.Fruit fly optimization algorithm[M].Taipei:Canghai Bookstore,2011(in Chinese).[潘文超.果蝇最佳化演算法[M].台北:沧海书局,2011.]
[15]WANG Ling,LYU Shenxiang,ZENG Yurong.Literature survey of fruit fly optimization algorithm[J].Control and Decision,2017,32(7):1153-1162(in Chinese).[王林,吕盛祥,曾宇容.果蝇优化算法研究综述[J].控制与决策.2017,32(7):1153-1162.]
[16]LIU Zhixiong,WANG Yafen,ZHANG Yu.Multiple population fruit fly optimization algorithm for automatic warehouse order picking operation scheduling problem[J].Journal of Wuhan University of Technology,2014,36(3):71-77(in Chinese).[刘志雄,王雅芬,张煜.多种群果蝇优化算法求解自动化仓库拣选作业调度问题[J].武汉理工大学学报,2014,36(3):71-77.]
[17]YUAN Webin,CHANG Liang,XU Zhoubo,et al.Multiplant assembly sequence planning based on fruit fly optimization algorithm[J].Computer Science,2017,44(4):246-251(in Chinese).[袁文兵,常亮,徐周波,等.基于果蝇优化算法的多工位装配序列规划[J].计算机科学.2017,44(4):246-251.]
[18]LIU Qiong,ZHAO Haifei.Integrated optimization of workshop layout and scheduling to reduce carbon emissions based on a multi-objective fruit fly optimization algorithm[J].Journal of Mechanical Engineering,2017,53(11):122-133(in Chinese).[刘琼,赵海飞.基于多目标果蝇算法面向低碳的车间布局与调度集成优化[J].机械工程学报,2017,53(11):122-133.]
[19]LI J Q,PAN Q K,MAO K.A hybrid fruit fly optimization algorithm for the realistic hybrid flowshop rescheduling problem in steelmaking systems[J].IEEE Transactions on Automation Science&Engineering,2016,13(2):932-949.
[20]ZHANG Qiliang,YU Zuoming.Discrete fruit fly optimization algorithm based on dominant population for solving nowait flow shop scheduling problem[J].Computer Integrated Manufacturing Systems,2017,23(3):609-615(in Chinese).[张其亮,俞祚明.基于优势种群的离散果蝇优化算法求解无等待流水车间调度问题[J].计算机集成制造系统,2017,23(3):609-615.]
[21]ZHENG Xiaolong,WANG Ling,WANG Shengyao.A hybrid discrete fruit fly optimization algorithm for solving permutation flow-shop scheduling problem[J].Control Theory&Applications,2014,31(2):159-164(in Chinese).[郑晓龙,王凌,王圣尧.求解置换流水线调度问题的混合离散果蝇算法[J].控制理论与应用,2014,31(2):159-164.]
[22]HU Yang,WANG Kaipu,ZHANG Zeqiang,et al.Pareto based bacteria foraging optimization algorithm for multi-objective disassembly line balancing problem[J].Computer Application Research,2016,33(11):3265-3269(in Chinese).[胡扬,张则强,汪开普,等.多目标拆卸线平衡问题的Pareto细菌觅食算法[J].计算机应用研究,2016,33(11):3265-3269.]
[23]DEB K,PRATAP A,AGARWAL S,et al.A fast and elitist multi-objective genetic algorithm:NSGA-II[J].IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.
[24]ZHANG Chaoyong,DONG Xing,WANG Xiaojuan.Improved NSGA-Ⅱfor the multi-objective flexible job-shop scheduling problem[J].Journal of Mechanical Engineering,2010,46(11):156-164(in Chinese).[张超勇,董星,王晓娟,等.基于改进非支配排序遗传算法的多目标柔性作业车间调度[J].机械工程学报,2010,46(11):156-164.]
[25]LEI Deming,YAN Xinping.Multi objective intelligent optimization algorithm and its application[M].Beijing:Science Press,2011(in Chinese).[雷德明,严新平.多目标智能优化算法及其应用[M].北京:科学出版社,2009.]
[26]GONG Maoguo,JIAO Licheng,YANG Dongdong,et al.Research on evolutionary multi-objective optimization algorithms[J].Journal of Software,2009,20(2):271-289(in Chinese).[公茂果,焦李成,杨咚咚,等.进化多目标优化算法研究[J].软件学报,2009,20(2):271-289.]
[2]MCGOVERN S M,GUPTA S M.A balancing method and genetic algorithm for disassembly line balancing[J].European Journal of Operational Research,2007,179(3):692-708.
[3]MCGOVERN S M,GUPTA S M.Combinatorial optimization analysis of the unary NP-complete disassembly line balancing problem[J].International Journal of Production Research,2007,45(18):4485-4511.
[4]MCGOVERN S M,GUPTA S M.Uninformed and probabilistic distributed agent combinatorial searches for the unary NP-complete disassembly line balancing problem[C]//Proceedings of the International Society for Optical Engineering.Bellingham,Washington,D.C.,USA:SPIE,2005:81-92.
[5]AVIKAL S,MISHRA P K,JAIN R.A Fuzzy AHP and PROMETHEE method-based heuristic for disassembly line balancing problems[J].International Journal of Production Research,2014,52(5):1306-1317.
[6]ALTEKIN F T,KANDILLER L,OZDEMIREL N E.Profitoriented disassembly-line balancing[J].International Journal of Production Research,2008,46(10):2675-2693.
[7]KALAYCI C B,POLAT O,GUPTA S M.A hybrid genetic algorithm for sequence-dependent disassembly line balancing problem[J].Annals of Operations Research,2016,242(2):321-354.
[8]KALAYCI C B,GUPTA S M.A hybrid genetic algorithm approach for disassembly line balancing[C]//Processing of the42nd Annual Meeting of Decision Sciences Institute.Boston,Mass.,USA:DSL,2011:713-718.
[9]WANG Kaipu,ZHANG Zeqiang,ZHU Lixia,et al.Pareto genetic simulated annealing algorithm for multi-objective disassembly line balancing problem[J].Computer Integrated Manufacturing Systems,2017,23(6):1277-1285(in Chinese).[汪开普,张则强,朱立夏,等.多目标拆卸线平衡问题的Pareto遗传模拟退火算法[J].计算机集成制造系统.2017,23(6):1277-1285.]
[10]DING L P,TAN J R,FENG Y X,et al.A new multi-objective ant colony algorithm for solving the disassembly line balancing problem[J].International Journal of Advanced Manufacturing Technology,2010,48(5/6/7/8):761-771.
[11]KALAYCI C B,GUPTA S M.A particle swarm optimization algorithm for solving disassembly line balancing problem[C]//Proceedings of the Northeast Region Decision Sciences Institute Conference.Houston,Tex.,USA:DSI,2012:347-357.
[12]KALAYCI C B,GUPTA S M,NAKASHIMA K.A simulated annealing algorithm for balancing a disassembly line[C]//Proceedings of the Design for Innovative Value Towards a Sustainable Society.Berlin,Germany:Springer-Verlag,2012:714-719.
[13]WANG Kaipu,ZHANG Zeqiang,MAO Lili,et al.Pareto artificial fish swarm algorithm for multi-objective disassembly line balance problems[J].China Mechanical Engineering,2017,28(2):183-190(in Chinese).[汪开普,张则强,毛丽丽,等.多目标拆卸线平衡问题的Pareto人工鱼群算法[J].中国机械工程,2017,28(2):183-190.]
[14]PAN Wenchao.Fruit fly optimization algorithm[M].Taipei:Canghai Bookstore,2011(in Chinese).[潘文超.果蝇最佳化演算法[M].台北:沧海书局,2011.]
[15]WANG Ling,LYU Shenxiang,ZENG Yurong.Literature survey of fruit fly optimization algorithm[J].Control and Decision,2017,32(7):1153-1162(in Chinese).[王林,吕盛祥,曾宇容.果蝇优化算法研究综述[J].控制与决策.2017,32(7):1153-1162.]
[16]LIU Zhixiong,WANG Yafen,ZHANG Yu.Multiple population fruit fly optimization algorithm for automatic warehouse order picking operation scheduling problem[J].Journal of Wuhan University of Technology,2014,36(3):71-77(in Chinese).[刘志雄,王雅芬,张煜.多种群果蝇优化算法求解自动化仓库拣选作业调度问题[J].武汉理工大学学报,2014,36(3):71-77.]
[17]YUAN Webin,CHANG Liang,XU Zhoubo,et al.Multiplant assembly sequence planning based on fruit fly optimization algorithm[J].Computer Science,2017,44(4):246-251(in Chinese).[袁文兵,常亮,徐周波,等.基于果蝇优化算法的多工位装配序列规划[J].计算机科学.2017,44(4):246-251.]
[18]LIU Qiong,ZHAO Haifei.Integrated optimization of workshop layout and scheduling to reduce carbon emissions based on a multi-objective fruit fly optimization algorithm[J].Journal of Mechanical Engineering,2017,53(11):122-133(in Chinese).[刘琼,赵海飞.基于多目标果蝇算法面向低碳的车间布局与调度集成优化[J].机械工程学报,2017,53(11):122-133.]
[19]LI J Q,PAN Q K,MAO K.A hybrid fruit fly optimization algorithm for the realistic hybrid flowshop rescheduling problem in steelmaking systems[J].IEEE Transactions on Automation Science&Engineering,2016,13(2):932-949.
[20]ZHANG Qiliang,YU Zuoming.Discrete fruit fly optimization algorithm based on dominant population for solving nowait flow shop scheduling problem[J].Computer Integrated Manufacturing Systems,2017,23(3):609-615(in Chinese).[张其亮,俞祚明.基于优势种群的离散果蝇优化算法求解无等待流水车间调度问题[J].计算机集成制造系统,2017,23(3):609-615.]
[21]ZHENG Xiaolong,WANG Ling,WANG Shengyao.A hybrid discrete fruit fly optimization algorithm for solving permutation flow-shop scheduling problem[J].Control Theory&Applications,2014,31(2):159-164(in Chinese).[郑晓龙,王凌,王圣尧.求解置换流水线调度问题的混合离散果蝇算法[J].控制理论与应用,2014,31(2):159-164.]
[22]HU Yang,WANG Kaipu,ZHANG Zeqiang,et al.Pareto based bacteria foraging optimization algorithm for multi-objective disassembly line balancing problem[J].Computer Application Research,2016,33(11):3265-3269(in Chinese).[胡扬,张则强,汪开普,等.多目标拆卸线平衡问题的Pareto细菌觅食算法[J].计算机应用研究,2016,33(11):3265-3269.]
[23]DEB K,PRATAP A,AGARWAL S,et al.A fast and elitist multi-objective genetic algorithm:NSGA-II[J].IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.
[24]ZHANG Chaoyong,DONG Xing,WANG Xiaojuan.Improved NSGA-Ⅱfor the multi-objective flexible job-shop scheduling problem[J].Journal of Mechanical Engineering,2010,46(11):156-164(in Chinese).[张超勇,董星,王晓娟,等.基于改进非支配排序遗传算法的多目标柔性作业车间调度[J].机械工程学报,2010,46(11):156-164.]
[25]LEI Deming,YAN Xinping.Multi objective intelligent optimization algorithm and its application[M].Beijing:Science Press,2011(in Chinese).[雷德明,严新平.多目标智能优化算法及其应用[M].北京:科学出版社,2009.]
[26]GONG Maoguo,JIAO Licheng,YANG Dongdong,et al.Research on evolutionary multi-objective optimization algorithms[J].Journal of Software,2009,20(2):271-289(in Chinese).[公茂果,焦李成,杨咚咚,等.进化多目标优化算法研究[J].软件学报,2009,20(2):271-289.]