基于遗传算法的装配序列优化
|
摘要
本文以某公司洗衣机装配一线为研究对象，利用遗传算法搜索并优化装配序列，充分考虑了企业的制造资源，从而使优化结果接近生产实际。首先根据调研期间获得的资料建立问题的数学模型，考虑了装配时间、可装配性和调度成本等指标。然后针对子装配体的模式含义，设计了编码方案和遗传策略，分别讨论了不同生产工况下的单目标、多目标优化问题。由于是一个多目标多约束模型，约束环境极易破坏遗传信息从而出现有效基因缺失和早熟，针对这些问题，提出了基因修补算子，基于代沟信息自适应调整算子等新的遗传策略。同时结合局部搜索算法加快了在最优值附近的收敛速度。对算法的收敛性及其实际意义给予了理论分析。最后将优化结果与海尔采用的方案做了分析比较。
In this thesis, based on the washing machine production line of Haier-Merloni Inc, the genetic algorithms are applied to find the feasible and optimal assembly sequence. The constraints of manufacturing resources are introduced to make the sequence more accurate. According to the information collected from the assembly line, the mathematic model is firstly established, and the optimization criteria such as makespan, accessibility and scheduling cost are concerned. Then the coding scheme and genetic operators are designed through which the static and dynamic optimization is discussed respectively. Because it's a multi-objective and multi-constraint optimization model, the hereditary information is easy to be destroyed by the procedure constraints. Therefore, in the process of optimization, the premature convergence and the fault of effective gene are caused. To resolve this problem, several new genetic operators are proposed, such as gene repairing operator and adaptive operator. Combining with local searching, the hybrid genetic algorithms show great effectiveness. Furthermore, the global convergence of the algorithms is analyzed. At last, the optimal assembly sequence is compared with which adopted in Haier to testify the validity of the proposed approach.
In this thesis, based on the washing machine production line of Haier-Merloni Inc, the genetic algorithms are applied to find the feasible and optimal assembly sequence. The constraints of manufacturing resources are introduced to make the sequence more accurate. According to the information collected from the assembly line, the mathematic model is firstly established, and the optimization criteria such as makespan, accessibility and scheduling cost are concerned. Then the coding scheme and genetic operators are designed through which the static and dynamic optimization is discussed respectively. Because it's a multi-objective and multi-constraint optimization model, the hereditary information is easy to be destroyed by the procedure constraints. Therefore, in the process of optimization, the premature convergence and the fault of effective gene are caused. To resolve this problem, several new genetic operators are proposed, such as gene repairing operator and adaptive operator. Combining with local searching, the hybrid genetic algorithms show great effectiveness. Furthermore, the global convergence of the algorithms is analyzed. At last, the optimal assembly sequence is compared with which adopted in Haier to testify the validity of the proposed approach.
引文
1 王先逵．现代制造技术手册．第1版．长沙：国防工业出版社，2001
2 储林波．面向虚拟装配的装配工艺规划技术研究．哈尔滨工业大学博士论文．2000：54—63
3 朱明铨，张树生．虚拟制造系统与实现．第1版．西安：西北工业大学出版社，2001
4 肖伟．CAPP系统中工序工步排序研究的现状与发展．常德高等专科学校
5 李敏强．遗传算法的基本理论与应用．第1版．北京：科学出版社，2002
6 王小平．遗传算法—理论、应用与软件实现．第1版．西安：西安交通大学出版社，2002
7 王正志．进化计算．第1版．长沙：国防科技大学出版社，2000
8 张佩勤．自动装配与柔性装配技术．第1版．北京：机械工业出版社，1998
9 陈国良．遗传算法及其应用．北京：人民邮电出版社，1999
10 潘美芹．遗传算法的改进与研究．山东科技大学硕士论文．2000．5
11 王凌．车间调度及其遗传算法．第1版．北京：清华大学出版社，2003
12 陈玉琨，王宣武．实用成组技术．北京：机械工业出版社，1992
13 李士勇．模糊控制·神经控制和智能控制论．第2版．哈尔滨：哈尔滨工业大学出版社，1998
14 卢开澄．单目标、多目标与整数规划．北京：清华大学出版社，1999
15 陈炳森．生产系统学．第1版．上海：同济大学出版社，1992
16 李军，边肇祺．用于最优化的计算智能第1版．北京：清华大学出版社，1999
17 薛明志．正交Multi-agent遗传算法及其性能分析．控制与决策．2003(3)：290—294
18 蓝海．一类遗传退火算法的函数优化寻根分析．系统仿真学报．2001(8)：111—113
19 杨圣祥．用遗传算法与自适应神经网络混合方法解Job-shop调度问题．控制与决策．1998(8)：402407
20 [日]玄光男．遗传算法与工程设计．第1版．北京：科学出版社，2000
21 张志涌．精通MATLAB5.3版．第1版．北京：北京航空航天大学出版社，2000
22 周明．遗传算法原理及应用．第1版．北京：国防工业出版社，1999
23 [美]安德鲁·库夏克．智能制造系统．第1版．北京．清华大学出版社，1993
24 [苏]B．B．科希洛夫．装配工艺学原理与自动装配设备．第1版．北京：中国农业机械出版社，1983
25 肖田元．系统仿真导论．第1版．北京：清华大学出版社，2000
26 杨建国．可装配性设计．第1版．上海：中国纺织大学出版社，2001
27 唐恒永．排序引论．第1版．北京：科学出版社，2002
28 张文修．遗传算法的数学基础．第1版．西安：西安交通大学出版社．2000
29 王万良，宋毅．求解作业车间调度问题的双倍体遗传算法与软件实现．计算机集成制造系统．2004(1)：65—69
30 (美)迈克尔斯基．机器学习．第1版．北京：科学出版社，1992
31 张旭堂．刘文剑．机械产品非线性装配顺序规划．计算机集成制造系统．2004(1)：88—93
32 皮兴忠．装配线平衡与仿真技术的研究与应用．上海交通大学硕士论文．2002．1
33 傅仕伟，蒋祖花．基于相关机会约束的生产规划．计算机集成制造系统．2003(10)：858—863
34 张旭堂，刘文剑．机械产品非线性装配顺序规划研究．计算机集成制造系统．2004(1)：88—93
35 刘民，吴澄．带特殊工艺约束的并行机器生产线调度问题的一种遗传算法．自动化学报．2001(5)：381—386
36 左兴权，李士勇．一类自适应免疫进化算法．控制与决策．2004(3)：252—256
37 徐国华，王书振．嫁接共生遗传算法及其在作业调度中的应用．计算机集成制造系统．2004(4)：461—464
38 陈伟达．基于杂合遗传算法的车间作业调度问题研究．东南大学博士论文．2001．12
39 马传秀．排序问题的遗传算法．湖南大学硕士论文．2000．5
40 蒲建，王先逵．工艺规划中的组合优化问题．清华大学学报(自然科学版)．1997(8)：69—71
41 李言，陈祖安．指派问题的遗传算法研究与实现．西安理工大学学报．1996(4)：271—276
42 王宏刚，曾建潮．优良模式自学习遗传算法．自动化学报．1999(5)：375—379
43 B. Lazzerini, F. Marcelloni. A genetic algorithm for generating optimal assembly plans. Artificial Intelligence in Engineering. 2000(14): 319-329
44 Sanjay V. Mchta and Reha M. Uzsoy. Predictable Scheduling of a Job Shop Subject to Breakdowns. IEEE Transactions on Robotics and Automations. 1998. 14(3): 365-377
45 Guido Malone and David Naso. A Genetic Approach for Adaptive Multiagent Control in Heterarchical Manufacturing Systems. IEEE Transactions on System, Man, and Cybernetics. 2003. 33(5): 573-588
46 Sara Baase. Computer Algorithms. Mass: Addison-Wesley Pub, Co, 1978
47 M. F. Sebaaly. A genetic planner for assembly automation. Proceedings of the IEEE Conference on Evolutionary Computation. 1996: 401-406.
48 Bonnevillef, Perrardc. Genetic Algorithm to Generate and Evaluate Assembly plans. IEEE Symposium on Emerging Technology and Factory Automation. 1995(2): 231-239.
49 Eiben A E. Parameter Control in Evolutionary Algorithms. IEEE Transaction on Evolutionary Computation. 1999. 3(2): 124-141
50 E. Zussman, E. Lenz. An Approach to the Automatic Assembly Planning Problem. CIRP Annals. 1990. 39(1): 33-36.
2 储林波．面向虚拟装配的装配工艺规划技术研究．哈尔滨工业大学博士论文．2000：54—63
3 朱明铨，张树生．虚拟制造系统与实现．第1版．西安：西北工业大学出版社，2001
4 肖伟．CAPP系统中工序工步排序研究的现状与发展．常德高等专科学校
5 李敏强．遗传算法的基本理论与应用．第1版．北京：科学出版社，2002
6 王小平．遗传算法—理论、应用与软件实现．第1版．西安：西安交通大学出版社，2002
7 王正志．进化计算．第1版．长沙：国防科技大学出版社，2000
8 张佩勤．自动装配与柔性装配技术．第1版．北京：机械工业出版社，1998
9 陈国良．遗传算法及其应用．北京：人民邮电出版社，1999
10 潘美芹．遗传算法的改进与研究．山东科技大学硕士论文．2000．5
11 王凌．车间调度及其遗传算法．第1版．北京：清华大学出版社，2003
12 陈玉琨，王宣武．实用成组技术．北京：机械工业出版社，1992
13 李士勇．模糊控制·神经控制和智能控制论．第2版．哈尔滨：哈尔滨工业大学出版社，1998
14 卢开澄．单目标、多目标与整数规划．北京：清华大学出版社，1999
15 陈炳森．生产系统学．第1版．上海：同济大学出版社，1992
16 李军，边肇祺．用于最优化的计算智能第1版．北京：清华大学出版社，1999
17 薛明志．正交Multi-agent遗传算法及其性能分析．控制与决策．2003(3)：290—294
18 蓝海．一类遗传退火算法的函数优化寻根分析．系统仿真学报．2001(8)：111—113
19 杨圣祥．用遗传算法与自适应神经网络混合方法解Job-shop调度问题．控制与决策．1998(8)：402407
20 [日]玄光男．遗传算法与工程设计．第1版．北京：科学出版社，2000
21 张志涌．精通MATLAB5.3版．第1版．北京：北京航空航天大学出版社，2000
22 周明．遗传算法原理及应用．第1版．北京：国防工业出版社，1999
23 [美]安德鲁·库夏克．智能制造系统．第1版．北京．清华大学出版社，1993
24 [苏]B．B．科希洛夫．装配工艺学原理与自动装配设备．第1版．北京：中国农业机械出版社，1983
25 肖田元．系统仿真导论．第1版．北京：清华大学出版社，2000
26 杨建国．可装配性设计．第1版．上海：中国纺织大学出版社，2001
27 唐恒永．排序引论．第1版．北京：科学出版社，2002
28 张文修．遗传算法的数学基础．第1版．西安：西安交通大学出版社．2000
29 王万良，宋毅．求解作业车间调度问题的双倍体遗传算法与软件实现．计算机集成制造系统．2004(1)：65—69
30 (美)迈克尔斯基．机器学习．第1版．北京：科学出版社，1992
31 张旭堂．刘文剑．机械产品非线性装配顺序规划．计算机集成制造系统．2004(1)：88—93
32 皮兴忠．装配线平衡与仿真技术的研究与应用．上海交通大学硕士论文．2002．1
33 傅仕伟，蒋祖花．基于相关机会约束的生产规划．计算机集成制造系统．2003(10)：858—863
34 张旭堂，刘文剑．机械产品非线性装配顺序规划研究．计算机集成制造系统．2004(1)：88—93
35 刘民，吴澄．带特殊工艺约束的并行机器生产线调度问题的一种遗传算法．自动化学报．2001(5)：381—386
36 左兴权，李士勇．一类自适应免疫进化算法．控制与决策．2004(3)：252—256
37 徐国华，王书振．嫁接共生遗传算法及其在作业调度中的应用．计算机集成制造系统．2004(4)：461—464
38 陈伟达．基于杂合遗传算法的车间作业调度问题研究．东南大学博士论文．2001．12
39 马传秀．排序问题的遗传算法．湖南大学硕士论文．2000．5
40 蒲建，王先逵．工艺规划中的组合优化问题．清华大学学报(自然科学版)．1997(8)：69—71
41 李言，陈祖安．指派问题的遗传算法研究与实现．西安理工大学学报．1996(4)：271—276
42 王宏刚，曾建潮．优良模式自学习遗传算法．自动化学报．1999(5)：375—379
43 B. Lazzerini, F. Marcelloni. A genetic algorithm for generating optimal assembly plans. Artificial Intelligence in Engineering. 2000(14): 319-329
44 Sanjay V. Mchta and Reha M. Uzsoy. Predictable Scheduling of a Job Shop Subject to Breakdowns. IEEE Transactions on Robotics and Automations. 1998. 14(3): 365-377
45 Guido Malone and David Naso. A Genetic Approach for Adaptive Multiagent Control in Heterarchical Manufacturing Systems. IEEE Transactions on System, Man, and Cybernetics. 2003. 33(5): 573-588
46 Sara Baase. Computer Algorithms. Mass: Addison-Wesley Pub, Co, 1978
47 M. F. Sebaaly. A genetic planner for assembly automation. Proceedings of the IEEE Conference on Evolutionary Computation. 1996: 401-406.
48 Bonnevillef, Perrardc. Genetic Algorithm to Generate and Evaluate Assembly plans. IEEE Symposium on Emerging Technology and Factory Automation. 1995(2): 231-239.
49 Eiben A E. Parameter Control in Evolutionary Algorithms. IEEE Transaction on Evolutionary Computation. 1999. 3(2): 124-141
50 E. Zussman, E. Lenz. An Approach to the Automatic Assembly Planning Problem. CIRP Annals. 1990. 39(1): 33-36.