• CN:11-2187/TH
  • ISSN:0577-6686

机械工程学报 ›› 2019, Vol. 55 ›› Issue (13): 160-174.doi: 10.3901/JME.2019.13.160

• 数字化设计与制造 • 上一篇    下一篇

多行设备布局的一种多目标差分进化算法和线性规划混合方法

管超1,2, 张则强1,2, 李云鹏1,2, 贾林1,2   

  1. 1. 西南交通大学机械工程学院 成都 610031;
    2. 西南交通大学轨道交通运维技术与装备四川省重点实验室 成都 610031
  • 收稿日期:2018-08-01 修回日期:2019-01-14 出版日期:2019-07-05 发布日期:2019-07-05
  • 通讯作者: 张则强(通信作者),男,1978年出生,博士,教授,博士研究生导师。主要研究方向为制造系统与智能优化。E-mail:zzq_22@163.com
  • 作者简介:管超,男,1994年出生,博士研究生。主要研究方向为设施布局优化。E-mail:17175371524@163.com;李云鹏,男,1994年出生,硕士研究生。主要研究方向为设施布局优化。E-mail:741048765@qq.com;贾林,男,1993年出生,硕士研究生。主要研究方向为设施布局优化。E-mail:1210107281@qq.com
  • 基金资助:
    国家自然科学基金(51205328,51675450);教育部人文社会科学研究青年基金(18YJC630255);四川省科技计划(2019YFG0285)资助项目。

Combining Multi-objective Differential Evolution Algorithm and Linear Programming for Multiple Row Facility Layout Problem

GUAN Chao1,2, ZHANG Zeqiang1,2, LI Yunpeng1,2, JIA Lin1,2   

  1. 1. School of Mechanical Engineering, Southwest Jiaotong University, Chengdu 610031;
    2. Technology and Equipment of Rail Transit Operation and Maintenance Key Laboratory of Sichuan Province, Southwest Jiaotong University, Chengdu 610031
  • Received:2018-08-01 Revised:2019-01-14 Online:2019-07-05 Published:2019-07-05

摘要: 针对现有对多行设备布局研究中预先固定布置行数和未考虑行间距约束的不足,在满足最小间隙约束条件下,构建了优化物料流成本、布局行数和布局占地面积的多目标多行设备布局模型,并运用数学规划软件Lingo对模型进行了精确求解。基于所提问题的多目标、多约束、混合优化特性,提出一种基于Pareto解集的多目标差分进化算法和线性规划混合优化方法。该方法采用四列表直接编码方法表示可行解;提出一种结合改进换行策略的解码方式,该解码方式可以在满足边界约束条件的同时对所有可行的布局方案进行确定;为获得收敛性、分布性良好的多目标布局结果,采用Pareto思想、NSGA-Ⅱ拥挤距离机制筛选外部档案中的非劣解。应用所提算法求解不同规模多行设备布局问题测试算例,比较分析3种差分进化模式对所提方法在求解质量和求解效率方面的影响。最后,将所提模型和求解方法应用至两个布局实例中,不同算法的对比试验表明了所提方法的有效性、优越性。

关键词: 差分进化算法, 多目标优化, 多行设备布局问题, 改进换行策略, 混合整数非线性规划

Abstract: In order to overcome the shortcomings of fixed row number and ignoring spacing constraints between rows in the existing research on multiple row facility layout problem, a multi-objective multiple row facility layout problem model is constructed to optimize material flow cost, layout row number and layout area under the condition of minimum gap constraints, and the model is solved accurately by using Lingo, a mathematical programming software. Based on the multi-objective, multi-constraint and mixed optimization of the proposed problem, a hybrid optimization method of multi-objective differential evolution algorithm and linear programming based on Pareto solution set is proposed. This method uses four-list directly coding method to represent feasible solution, and proposes a decoding method combined with improved line-breaking strategy, which can determine the layout scheme of all possible rows while satisfying boundary constraints. In order to obtain a multi-objective layout result with good convergence and distribution, Pareto method and NSGA-Ⅱ congestion distance mechanism are used to screen external files. The proposed algorithm is applied to solve multiple row facility layout problem with different scales. The effects of three differential evolution modes on the solution quality and efficiency of the proposed method are compared and analysed. Finally, the proposed model and method are applied to two layout examples. The comparative experiments of different algorithms show the effectiveness and superiority of the proposed method.

Key words: evolution algorithm, improve line-wrapping strategies, mixed-integer nonlinear programming, multi-objective optimization, multiple row facility layout problem

中图分类号: