基于混合遗传算法的装配线平衡

作者：陈永卿，潘 刚，李 平 日期：2008-04-23/span> 浏览：4051 查看PDF文档

基于混合遗传算法的装配线平衡
陈永卿，潘 刚，李 平
（浙江大学 信息科学与工程学院，浙江 杭州 310027）

摘 要：针对装配线平衡问题的难点（NPhard），提出了一种基于作业次序编码的混合遗传算法，设计出了特殊的遗传操作算子（单点次序交叉和移位插入变异），成功避免了进化过程中非法个体的产生。并结合Lamarckian进化原理，嵌入局部爬山过程以提供算法搜索能力。仿真算例验证了该算法的有效性和可行性。
关键词：生产系统；装配线平衡；遗传算法；爬山算法

Hybrid genetic algorithm for assembly line balancing
CHEN Yongqing, PAN Gang, LI Ping
(College of Information Science and Engineering, Zhejiang University, Hangzhou 310027, China)

Abstract: Considering the difficulty (NPhard) of the problem, an orderbased hybrid genetic algorithm (GA) was proposed. Special genetic operators (order crossover and insert mutation) were designed to avoid the illegal individuals. Moreover, according to Lamarckian evolutionary principle, an iterative hill climbing method was inserted in order to improve the search ability. The result of simulation experiments shows that the proposed algorithm is efficient.
Key words: production system; assembly line balancing; genetic algorithm (GA); hill climbing algorithm

参考文献(Reference):
［1］GUTJAHR A L, NEMHAUSER G L. An algorithm or the line balancing problem［J］. Management Science,1964,11(2):308-315.
［2］GEN M, CHENG R. Genetic Algorithms and Engineering Optimization［M］. New York: John Wiley & Sons,2000.
［3］JACKSON J R. A computing procedure for a line balancing problem［J］.Management Science,1986,2(3):261-271.
［4］BECKER C, SCHOLL A. A survey on problems and methods in generalized assembly line balancing［J］. European J. Operational Research,2006,168(3):694-715.
［5］GONCALVES J F, ALMEIDA J R. A hybrid genetic algorithm for assembly line balancing［J］. Journal of Heuristics,2002,8(6):629-642.
［6］FALKENAUER E, DELCHAMBRE A. A Genetic Algorithm for Bin Packing and Line Balancing［C］. Proceedings of the 1992 IEEE International Conference on Robotics and Automation, Nice, France,1992:1186-1192.