基于Wang-Landau算法的动态设施布局方法
|
摘要
动态设施布局问题是设施在车间内多个阶段的布局规划问题。针对动态设施布局问题,国内外学者对离散模型研究较多,而对连续模型的研究却较少。根据连续动态设施布局的特性与需求,构建了不等面积的动态设施布局连续模型,求解该模型的难点在于缺乏一种高效的布局优化方法。通过将Wang-Landau算法与空位点放置策略、外推移动策略、内压移动策略三种启发式策略相结合,提出一种基于Wang-Landau抽样的启发式算法,并以此求解该模型。使用文献中已有的测试算例对提出的算法进行测试,计算结果表明,所提出的算法在求解连续动态设施布局问题上是有效的。
The dynamic facility layout problem is the problem of placing facilities in a certain plant for multiple stages. Nowadays,most of researches for the dynamic facility layout problem focus on the discrete models. According to its characteristics and requirements,this paper established a continual model for the unequal area dynamic facility layout problem. The greatest challenge in solving the dynamic facility layout problem consists in lacking a high-performance optimization method. The Wang-Landau algorithm is an improved Monte Carlo method. By combining the Wang-Landau algorithm,the vacant point strategy,pushing strategy and pressuring strategy,this paper proposed a heuristic Wang-Landau algorithm. The proposed algorithm had been tested on instances from the literature. The computational results show that the heuristic Wang-Landau algorithm is effective method for solving the dynamic facility layout problem.
The dynamic facility layout problem is the problem of placing facilities in a certain plant for multiple stages. Nowadays,most of researches for the dynamic facility layout problem focus on the discrete models. According to its characteristics and requirements,this paper established a continual model for the unequal area dynamic facility layout problem. The greatest challenge in solving the dynamic facility layout problem consists in lacking a high-performance optimization method. The Wang-Landau algorithm is an improved Monte Carlo method. By combining the Wang-Landau algorithm,the vacant point strategy,pushing strategy and pressuring strategy,this paper proposed a heuristic Wang-Landau algorithm. The proposed algorithm had been tested on instances from the literature. The computational results show that the heuristic Wang-Landau algorithm is effective method for solving the dynamic facility layout problem.
引文
[1]Mir M,Imam M H.A hybird optimization approach for layout design of unequal-area facilities[J].Computers&Industrial Engineering,2001,39(1):49-63.
[2]Ulutas B H,Kulturel-Konak S.An artificial immune system based algorithm to solve unequal area facility layout problem[J].Expert Systems with Applications,2012,39(5):5384-5395.
[3]Goncalves J F,Resende M G C.A biased random-key genetic algorithm for the unequal area facility layout problem[J].European Journal of Operational Research,2015,246(1):86-107.
[4]Imam M H,Mir M.Nonlinear programming approach to automated topology optimization[J].Computer-Aided Design,1989,21(2):107-115.
[5]Imam M H,Mir M.Automated layout of facilities of unequal areas[J].Computers and Industrial Engineering,1993,24(3):355-366.
[6]Asl A D,Wong K Y.Solving unequal-area static and dynamic facility layout problems using modified particle swarm optimization[J].Journal of Intelligent Manufacturing,2017,28(6):1317-1336.
[7]Rosenblatt M J.The dynamics of plant layout[J].Management Science,1986,32(1):76-86.
[8]Montreuil B,Venkatadri U.Strategic interpolative design of dynamic manufacturing systems layouts[J].Management Science,1991,37(6):682-694.
[9]Yang T,Peters B A.Flexible machine layout design for dynamic and uncertain production environments[J].European Journal of Operational Research,1998,108(1):49-64.
[10]Dunker T,Radons G,Westkamper E.Combining evolutionary computation and dynamic programming for solving a dynamic facility layout problem[J].European Journal of Operational Research,2005,165(1):55-69.
[11]Jr Mc Kendall A R,Hakobyan A.Heuristics for the dynamic facility la-yout problem with unequal-area departments[J].European Journal of Operational Research,2010,201(1):171-182.
[12]Jolai F,Tavakkoli-Moghaddam R,Taghipour M.A multi-objective particle swarm optimisation algorithm for unequal sized dynamic facility layout problem with pickup/drop-off locations[J].International Journal of Production Research,2012,50(15):4279-4293.
[13]马淑梅,蔡惠森,张一帆,等.不确定需求下的设备动态布局方法[J].中国机械工程,2015,26(11):1494-1502.
[14]郭爽,徐克林,孙立峰.基于遗传算法的动态连续型设备布局方法[J].现代制造工程,2011(11):58-62.
[15]Li Lingling,Li Congbo,Ma Huijie,et al.An optimization method for the remanufacturing dynamic facility layout problem with uncertainties[J].Discrete Dynamics in Nature and Society,2015,2015:article ID685408.
[16]黄君政,李爱平,雷明.基于NSGA-II的多目标设备动态布局方法[J].中国工程机械学报,2014,12(1):1-6.
[17]Wang F,Landau D P.Efficient,multiple-range random walk algorithm to calculate the density of states[J].Physical Review Letters,2001,86(10):2050-2053.
[18]Landau D P,Tsai S H,Exler M.A new approach to Monte Carlo simulations in statistical physics:Wang-Landau sampling[J].American Journal of Physics,2004,72(10):1294-1302.
[19]Seaton D T,Wüst T,Landau D P.Collapse transitions in a flexible homopolymer chain:application of the Wang-Landau algorithm[J].Physical Review E,2010,81(1):95-102.
[20]Liu Jingfa,Song Beibei,Yao Yonglei,et al.Wang-Landau sampling in face-centered-cube hydrophobic-hydrophilic lattice model proteins[J].Physical Review E,2014,90(4):1-8.
[2]Ulutas B H,Kulturel-Konak S.An artificial immune system based algorithm to solve unequal area facility layout problem[J].Expert Systems with Applications,2012,39(5):5384-5395.
[3]Goncalves J F,Resende M G C.A biased random-key genetic algorithm for the unequal area facility layout problem[J].European Journal of Operational Research,2015,246(1):86-107.
[4]Imam M H,Mir M.Nonlinear programming approach to automated topology optimization[J].Computer-Aided Design,1989,21(2):107-115.
[5]Imam M H,Mir M.Automated layout of facilities of unequal areas[J].Computers and Industrial Engineering,1993,24(3):355-366.
[6]Asl A D,Wong K Y.Solving unequal-area static and dynamic facility layout problems using modified particle swarm optimization[J].Journal of Intelligent Manufacturing,2017,28(6):1317-1336.
[7]Rosenblatt M J.The dynamics of plant layout[J].Management Science,1986,32(1):76-86.
[8]Montreuil B,Venkatadri U.Strategic interpolative design of dynamic manufacturing systems layouts[J].Management Science,1991,37(6):682-694.
[9]Yang T,Peters B A.Flexible machine layout design for dynamic and uncertain production environments[J].European Journal of Operational Research,1998,108(1):49-64.
[10]Dunker T,Radons G,Westkamper E.Combining evolutionary computation and dynamic programming for solving a dynamic facility layout problem[J].European Journal of Operational Research,2005,165(1):55-69.
[11]Jr Mc Kendall A R,Hakobyan A.Heuristics for the dynamic facility la-yout problem with unequal-area departments[J].European Journal of Operational Research,2010,201(1):171-182.
[12]Jolai F,Tavakkoli-Moghaddam R,Taghipour M.A multi-objective particle swarm optimisation algorithm for unequal sized dynamic facility layout problem with pickup/drop-off locations[J].International Journal of Production Research,2012,50(15):4279-4293.
[13]马淑梅,蔡惠森,张一帆,等.不确定需求下的设备动态布局方法[J].中国机械工程,2015,26(11):1494-1502.
[14]郭爽,徐克林,孙立峰.基于遗传算法的动态连续型设备布局方法[J].现代制造工程,2011(11):58-62.
[15]Li Lingling,Li Congbo,Ma Huijie,et al.An optimization method for the remanufacturing dynamic facility layout problem with uncertainties[J].Discrete Dynamics in Nature and Society,2015,2015:article ID685408.
[16]黄君政,李爱平,雷明.基于NSGA-II的多目标设备动态布局方法[J].中国工程机械学报,2014,12(1):1-6.
[17]Wang F,Landau D P.Efficient,multiple-range random walk algorithm to calculate the density of states[J].Physical Review Letters,2001,86(10):2050-2053.
[18]Landau D P,Tsai S H,Exler M.A new approach to Monte Carlo simulations in statistical physics:Wang-Landau sampling[J].American Journal of Physics,2004,72(10):1294-1302.
[19]Seaton D T,Wüst T,Landau D P.Collapse transitions in a flexible homopolymer chain:application of the Wang-Landau algorithm[J].Physical Review E,2010,81(1):95-102.
[20]Liu Jingfa,Song Beibei,Yao Yonglei,et al.Wang-Landau sampling in face-centered-cube hydrophobic-hydrophilic lattice model proteins[J].Physical Review E,2014,90(4):1-8.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |