基于分层混合蛙跳的多头贴片机贴装调度算法

• 论文 •

基于分层混合蛙跳的多头贴片机贴装调度算法

臧明相,杜鑫,李斌

西安电子科技大学计算机学院

收稿日期:2013-11-25 修回日期:2013-11-25 出版日期:2013-11-25 发布日期:2013-11-25

Multi-head surface mounting machine scheduling based on layered shuffled frog-leaping algorithm

ZANG Ming-xiang,DU Xin,LI Bin

School of Computer Science and Technology,Chinese Xidian University

Received:2013-11-25 Revised:2013-11-25 Online:2013-11-25 Published:2013-11-25

摘要/Abstract

摘要： 为了提高贴片机的工作效率,研究了多头动臂式贴片机贴装调度问题,提出一种基于分层混合蛙跳的多头贴片机贴装调度算法。算法在初始化阶段同时考虑元器件布局和类型,采用启发式最近邻类方法优化初始种群;基于混合蛙跳思想,引入分层策略对贴装次序和供料器布置两个子问题进行局部搜索;在全局搜索中利用领域搜索算法进行全局信息交换,以改善种群多样性;引入基于模因概率的淘汰策略更新种群,加快算法收敛速度。运用实际工程中不同元器件规模电路板的贴装仿真实验表明,算法能更快、更精确地收敛于问题的全局最优值,验证了算法的可行性和有效性。

关键词: 混合蛙跳算法, 表面贴装技术, 元件贴装次序, 供料槽布置

Abstract: To improve the efficiency of chip mounter,the multi-head surface mounting machine scheduling problem was studied,and a scheduling algorithm based on layered shuffled frog-leaping algorithm was proposed.To improve initial population quality,a nearest neighbor heuristic was introduced.Based on the idea of shuffled frog-leaping,a layered search strategy was introduced to local search the two sub-problems of component placement sequence and feeder assignment.The neighboring search method was used in global search to exchange the information.Thus the population diversity would be improved.An update strategy based on memetic fitness was used to improve population diversity.The surface mount simulation of Printed Circuit Board (PCB) in different size was carried out.The experimental result showed that the proposed algorithm had a better performance in the convergence rate and the accuracy,as well as the feasibility and the effectiveness were also proved.

Key words: shuffled frog-leaping algorithm, surface mounted technology, component placement sequence, feeder arrangement

中图分类号:

TH166
TP18

臧明相,杜鑫,李斌. 基于分层混合蛙跳的多头贴片机贴装调度算法[J]. .

ZANG Ming-xiang,DU Xin,LI Bin. Multi-head surface mounting machine scheduling based on layered shuffled frog-leaping algorithm[J]. .

参考文献

［1］ZENG Y J,MA D Z,JIN Y,et al.Hierarchical planning for a surface mounting machine placement［J］.Journal of Zhejiang University Science,2004 5(11):1449-1455.
[2]LI S Y,HU C F,TIAN F H.Enhancing optimal feeder assignment of the multi-head surface mounting machine using genetic algorithms［J］.Applied Soft Computing,2008,8(1);522-529.
[3]ZHU Guangyu.Memo triangular probability distribution shuffled frog-leaping algorithm［J］.Computer International Manufacturing Systems,2009,15(10):1979-1985(in Chinese).［朱光宇.模因内三角概率选择混合蛙跳算法［J］.计算机集成制造系统,2009,15(10):1979-1985.］
[4]ZENG Youjiao,YAN Junqi.Feeder assignment problem of placement machine assembling printed circuit board［J］.Journal of Shanghai Jiaotong University,2003,37(11):1719-1722(in Chinese).［曾又姣,严隽琪.贴片机贴装印刷电路板中供料器的分配问题［J］.上海交通大学学报,2003,37(11):1719-1722.］
[5]KLOMP C,KLUNDERT J,SPIEKSMA F C R,et al.The feeder rack assignment problem in PCB assembly;a case study［J］.International Journal of Production Economics,2000,64(1):399-407.
[6]GRUNOW M,GNTHER H O,SCHLEUSENER M,et al.Operations planning for collect-and-place machines in PCB assembly［J］.Computer Industrial Engineer,2004,47(4):409-429.
[7]LIU Jian,BI Yajun,TAO Lan.Application improvement Max-Min Ant system optimization SMT placement sequence［C］//Proceedings of 2011 International Conference on Electric Information and Control Engineering.Washington,D.C.,USA:IEEE,2011;4006-4009.
[8]CHEN Y M,LIN C T.A particle swarlm optimization approach to optimize component placement in printed circuit board assembly［J］.International Journal of Advanced Manufacture Technology,2007,35(5/6):610-620.
[9]WILLIAM H,PING J.A genetic algorithm to optimize the component placement process in PCB assembly［J］.International Journal of Advanced Manufacturing Technology,2005,26(12):1397-1401.
[10]DU Xuan,LI Zongbin,JIA Xiaochen.Component placement process optimization for dual-gantry placement machine based on hybrid genetic algorithm.［J］.Journal of Xi’an Jiaotong University,2009,43(5) 80-84(in Chinese).［杜轩,李宗斌,贾晓晨.基于遗传算法的复合式贴片机贴装过程优化［J］.西安交通大学学报,2009,43(5):80-84.］
[11]WILLIAM H,PING Ji.Integrated component scheduling models for chip shooter machines［J］.Production Economics,2010,123(1):31-41.
[12]CHEN Gonggui,LI Zhihuan,CHEN Jinfu,et al.SFLAlgorithm based dynamic optimalpower flow in wind power integrated system［J］.Automation of Electric Power Systems,2009,25(4):25-30(in Chinese).［陈功贵,李智欢,陈金富,等.含风电场电力系统动态优化潮流的混合蛙跳算法［J］.电力系统自动化,2009,25(4):25-30.］
[13]PAN Yuxia,PAN Quanke,SANG Hongyan.Hybrid discrete shuffled frog-leaping algorithm for lot-streaming flowshop scheduling problem［J］.Computer Integrated Manufacturing Systems,2010,16(6):1265-1671(in Chinese).［潘玉霞,潘全科,桑红燕.批量流水线调度问题的混合离散蛙跳算法［J］.计算机集成制造系统,2010,16(6);1265-1671.］
[14]EUSUFF M,LANSEYK E.Optimization of water distribution network design using the shuffled frog leaping algorithm［J］.Water Resources Planning and Management,2003,129(3):210-225.

[1]	陈于思,孙林夫. 分布式环境下基于混合蛙跳算法的物化视图选择问题[J]. 计算机集成制造系统, 2019, 25(第2): 303-317.
[2]	肖莹莹,李伯虎,庄长辉,柴旭东,林廷宇. 面向用户多品种定制的分布式供应链调度[J]. 计算机集成制造系统, 2015, 21(第3期): 800-812.
[3]	王松,孙振忠,郭建文,张智聪. 基于混合蛙跳算法的复杂产品装配序列规划[J]. 计算机集成制造系统, 2014, 20(12): 2991-2999.
[4]	崔文华,刘晓冰,王伟,王介生. 基于递阶支持向量机的产品族配置性能预测[J]. 计算机集成制造系统, 2013, 19(08 ): 2000-2006.
[5]	靳志宏，刘颖，陈贞，李向军. 多品种小批量环境下的印刷电路板组装切换次数优化[J]. , 2010, 16(09): 0-0.
[6]	朱光宇. 模因内三角概率选择混合蛙跳算法[J]. , 2009, 15(10): 0-0.