摘 要

在资源日渐稀缺的时代背景下，废旧产品的回收以及再利用显得至关重要，因此，如何在考虑资源约束的情况下解决拆卸线平衡问题，对于提升工业生产、增大产品回收利用率和环境保护具有极其重大的意义。本文以最小化工作站数与空余时间为目标，考虑的资源为能量，除了常规的拆卸线约束条件以外，还加入了能量资源约束，即所有工作站的总能量消耗不能超过给定的最大值，该方法最大程度的节省了资源，构建带资源约束的拆卸线平衡问题的数学模型，用目前流行的多目标进化算法NSGA-II，并结合所采用的约束处理方法，即约束占优法求解问题，对上述模型的研究有利于减少能量等资源的消耗且节约成本，具有十足重要的理论和实践意义。

通过Lingo软件将数学模型编码仿真，验证了模型的正确性；查阅资料学习了约束处理和进化算法NSGA-II，并将两者相结合，通过约束占优法处理约束条件，最后运用算法求解该模型，得到实验运行结果图并具体分析了方案3，根据算例结果可以看出，该算法具有比较强大的寻优功能，非常充分地验证了该模型与算法具备有效性以及实用性。

关键词：资源约束；拆卸线平衡；多目标优化；NSGA-II；能量消耗

Abstract

In the era of increasingly scarce resources, the recycling and reuse of waste products is very important. Therefore, how to solve the problem of disassembly line balance in consideration of resource constraints, to improve industrial production, increase product recycling rate and environment Protection is of great significance. In this paper, the goal of minimizing the number of workstations and spare time is to consider the resources as energy. In addition to the conventional disassembly line constraints, energy resource constraints are added, that is, the total energy consumption of all workstations cannot exceed a given maximum value. The method saves resources to the greatest extent, constructs a mathematical model of the resource-constrained disassembly line balance problem, and uses the current popular multi-objective evolutionary algorithm NSGA-II, combined with the constraint processing method, that is, the constraint-dominant method to solve the problem. The research on the above model is beneficial to reduce the consumption of energy and other resources and save costs, and has important theoretical and practical significance.

The mathematical model is coded and simulated by Lingo software to verify the correctness of the model. The constraint processing and evolutionary algorithm NSGA-II are studied and the two are combined. The constraints are processed by the constraint dominant method. Finally, the algorithm is used to solve the problem. The model obtains the experimental operation result graph and analyzes the scheme 3 concretely. According to the results of the example, the algorithm has a powerful optimization function, which fully proves that the model and the algorithm are effective and practical.

Key words:resource constraints;disassembly line balance;multi-objective optimization;

NSGA-II;energy consumption

目录

第1章 绪论 1

1.1 研究目的及意义 1

1.2 国内外研究现状 2

1.2.1 拆卸线平衡问题研究现状 2

1.2.2 进化算法中约束处理的研究现状 3

1.3 研究目标与内容 4

1.3.1研究目标 4

1.3.2 研究内容 4

1.4 采取的研究方法与技术路线 5

1.4.1研究方法 5

1.4.2技术路线 5

1.5 论文结构 6

第2章 带资源约束的拆卸线平衡问题研究 7

2.1 拆卸线平衡问题描述 7

2.1.1 拆卸线平衡问题 7

2.1.2 拆卸优先关系 8

2.2 多目标优化问题 10

2.2.1多目标优化问题概述 10

2.2.2 Pareto最优解集 10

2.3 带资源约束的拆卸线平衡问题数学模型 11

2.3.1 带资源约束的拆卸线平衡问题描述 11

2.3.2 问题假设 12

2.3.3 符号说明 12

2.3.4 模型建立 13

2.4 拆卸线平衡模型仿真分析 14

2.4.1 算例设置 14

2.4.2 仿真结果与分析 14

2.5 本章小结 15

第3章 NSGA-II算法的设计与实验 16

3.1 约束处理方法概况 16

3.1.1 约束处理方法简介 16

3.1.2 约束处理方法 16

3.2 算法整体设计 18

3.3 初始阶段 20

3.3.1 编码设计 20

3.3.2 解码设计 20

3.3.3 种群初始化 21

3.4 快速非支配排序和拥挤度计算 22

3.4.1 快速非支配排序 22

3.4.2 拥挤度算子 22

3.5 遗传算子 23

3.5.1交叉操作 23

3.5.2变异操作 24

3.6 算例测试 25

3.6.1实验设置 25

3.6.2实验结果与分析 25

3.7 本章小结 28

第4章 总结与展望 29

4.1总结 29

4.2展望 29

参考文献 30

致 谢 32

第1章 绪论

1.1 研究目的及意义

在目前资源日渐稀缺的时代背景下，产品回收与再制造因为其优秀的环保与节能特性而受到全世界的瞩目。近年来，许多废弃产品将被淘汰，给资源和环境构成重大威胁，为了解决环境与资源问题，废旧产品的回收以及再利用至关重要，有必要全面考虑资源效率和环境影响，以便报废产品可以减少对环境的危害，而且最大限度地发挥经济和社会效益之间的协同作用，有效及时回收废旧产品，形成循环经济的可持续发展模式。目前形势对中国绿色制造业的发展提出了迫切要求，为了减少废物排放与能源消耗，废品回收企业热切响应国家发出的节能减排的号召，不断优化生产和回收过程。

在资源回收与再利用中，极其重要的因素是拆卸，它已被国内外学者广泛关注和研究，废物的回收和再循环不能与拆卸过程分开，通过拆卸，有价值的零件可以回收再利用，达到绿色制造和可持续发展。产品拆卸是指按照需要将产品与零件、组件或零部件分开，它是零部件和材料回收再循环的重要部分，拆卸时要考虑的因素比装配往往大得多，并且实现过程更加复杂，当前，针对产品拆卸的研究比较少。产品拆卸能够在一个工作单元上或在流水线上根据顺序完成，用于实现产品拆卸任务的流水线即为拆卸线，为了保证流利有效的拆卸，如今的大规模拆卸大多使用拆卸线的作业方式，拆卸线具有节约生产空间、效率好等优点。然而，在拆卸操作过程中，假使分配任务不当，会致使拆卸线平衡问题(Disassembly Line Balaneing Problem ,DLBP)的发生，对于大型废旧品的拆卸与回收，为了促进产品拆卸的标准化与产业化并提高拆卸效率，运用流水线作业方式实施生产组织的拆卸线得到了广泛的关注。因此，不管是在理论研究还是在企业的实际运用里，针对DLBP的研究都具有极其重大的意义。

在拆卸流水线中，诸如能量之类的资源消耗多、花费大，并且降低能量消耗能够直接降低企业的成本。与此同时，在目前建设环境友好型社会与资源节约型的号召下，许多公司已经开始向低能耗方向发展，它们渐渐减少生产中机器人的资源消耗来促进环境保护并寻得更大利润，因此，有必要限制工作站中的资源占用并减少资源的损失。在全国能源消耗中，制造业及其产品的能源消耗大概占了三分之二，鉴于此，研究限制能耗的拆卸线平衡问题，对于拆卸效率与节能减排等都有重大影响。

如今，使用进化算法解决有约束的多目标问题研究还不完善，应该进一步研究以解决带约束的优化问题。为了令算法的最后搜寻结果成为满足这些约束条件的最优解，有必要对约束条件实施处理，有约束的优化问题的解决办法更适合于大量的工程实践问题，所以，对约束处理办法进行研究，具有更实际的指示意义，它能使算法找到更好的最优解，并令最优解更大程度地满足实际条件、更好地利用现有资源。

本文考虑的资源为能量，在资源和优先关系的约束下，以最小化工作站数与空余时间为目标，构造带资源约束的拆卸线平衡问题的数学模型，用目前流行的多目标进化算法NSGA-II并结合约束处理求解问题，对上述模型的研究有利于减少能量等资源的消耗并节约成本，具有十分重要的理论和实践意义。因此，如何在考虑资源约束的情况下解决拆卸线平衡问题，对于提升工业生产、增大产品回收利用率和环境保护具有极其重大的意义。

1.2 国内外研究现状

1.2.1 拆卸线平衡问题研究现状

DLBP是由Gupta和Gungo^[1]第一次正式提出，他们所研究的拆卸是完全的拆卸序列安排问题以及损坏零部件情况下的拆卸顺序规划问题；随后，他们详细回顾并且系统地分析了他们自己和其他人在拆卸和拆卸线上的研究状况，并进行了数据收集和理论论证，以建立拆卸线模型，在2001年，他们分析了拆卸线回收产品在产品、零件、拆卸线、拆卸操作、零件要求和零件危险方面可能面临的挑战。Mcgovern等 ^[2]指出了诸如遗传算法、贪婪算法之类的算法处理了该平衡问题，Lee等学者^[3]为未来拆卸线平衡问题的研究昭示了目标与方向，在处理NP问题时，启发式方法比较好，主要显现在对于大规模NP问题能够快速便捷的解决问题。

Koc等人^[4]建议使用改良的AND/OR图（Transformed AND/OR Graph,TAOG）构建拆卸优先顺序，拆卸被认为是装配的逆过程，采用整数规划与动态规划相结合的方法，充分证实了利用TAOG构造拆卸关系序列的上限即为传统任务优先图的最优解。Gungor和Gupta^[5]表明拆卸线平衡问题事实上属于多目标平衡问题；后继者对多目标优化问题进行了研究，并对比MOEA/D来表明NSGA-II 对解决此问题的时候有长处^[6]。Li, Z等人^[7]在研究的拆卸线平衡问题是双边机器人时，考虑到了节拍时间与能量消耗因素。

在国内，丁立平^[8]建立了一个多目标拆卸线模型，其把最小拆卸线闲置率等作为优化目标，他还运用了一种在Pareto解集基础之上的改良的蚁群优化算法，解决这个问题模型非常的高效。李六柯^[9]构造了 DLBP 的整数规划模型，运用软件得到单目标最优解。赵忠^[10]细致阐述了拆卸线平衡问题中的影响方面，构造了简单的多目标平衡数学模型，提出了一种遗传算法来解决产品拆卸线平衡问题，其以时间平衡指数、需求和危险为目标函数，但是算法的性能并未通过实例验证^[11]。朱兴涛等人^[12]详实地分析了拆卸线，构造并且解决了多目标拆卸线模型，同时比较了其他人的算法性能，取得了良好的效果。在机器人流水线中主要的成本有能耗，将工人用机器人替换必然要考虑到机器人的能耗问题^[13]。

资源约束装配线平衡问题（Resource-constrained ALBP,RCALBP）由Ağpak与 Gökçen^[14]第一次提出，他们给 RCALBP 下了定义，提出的两种资源约束下的 RCALBP 数学模型，是在给定最大站数目与节拍时间的基础上，最后运用GAMS-CPLEX 软件处理构造的0-1整数规划模型。资源约束拆卸线平衡问题（Resource-constrained DLBP,RCDLBP）则由Mete 等人^[15]最先提出，他们把拆卸当作装配的逆过程，处理以最小化全部资源消耗数为优化目标的 RCDLBP，在这篇文献里，资源约束为对全部站能行使的资源进行约束，即全部站能利用的资源总会小于等于一个固定值。针对资源约束问题的研究，另外一种约束为制约在同一时刻能够被占用的额外资源数，在调度问题的研究中有相关内容的探索。

近年以来，相比于国外研究拆卸线平衡问题进行得日新月异，国内研究仍然存在较大差距。中国是一个人口诸多、资源薄缺的国家，更应该全面研究拆卸线，随着中国废旧产品数量的日益增多及对资源需求的不断增加，越来越多的人会更加关注对于拆卸线平衡问题的研究。依照调查及总结目前研究的情况，很多的DLBP 考察的优化目标为最小危害指数、工作站数等，只是使用一些比较常规的约束条件，他们很少提及实际拆卸过程中能量消耗与另外的约束条件。

本文考虑的资源为能量，以最小化工作站数与空余时间为目标，除了常规的拆卸线约束条件以外，还加入了能量资源约束，即所有工作站的总能量消耗不能超过给定的最大值，构建带资源约束的拆卸线平衡问题的数学模型，对上述模型的研究有利于减少能量等资源的消耗并节约成本，具有十分重要的理论和实践意义。

1.2.2 进化算法中约束处理的研究现状

尽管研究无约束优化问题收获了很多成就，但仍然无法很好地处理约束优化问题，因为处理约束条件是当前优化问题中更复杂的方面^[16]。除了实现最优目标之外，还需要考虑某些条件制约，它们制约了搜寻空间的可行解范围，收缩了进化算法的目标函数的自变量区域，因此有必要对约束条件实施处理，随后使用求解无约束优化时的进化算法，令最终结果收敛于可行解范围。当前主要的约束处理方案囊括惩罚函数办法、约束与目标函数分开的办法、把约束优化问题转换为多目标优化问题法、混合约束处理办法等。

1. 惩罚函数法，是一种处理约束的传统方法，施加一些惩罚项于目标函数之中，并据此于不可行解中加上适应度值，就可以转换成为无约束的优化问题，研究的重难点在于惩罚项及参数设计，如果惩罚参数太大，则容易陷进局部最优；如果惩罚参数太小则求解过程变得困难，难以找到全局最优解，这些都限制了惩罚函数法的实践操作性。
2. 把约束转换成目标函数，于是转化成无约束的优化问题。Coello建议根据Pareto排列个体的等级，该方法能够在交叉与变异中通过自适应地设置适应度值，不必引进其他的参数来确保群体多样性，然而其适用于约束少的情形，一旦约束条件变多，将急剧增大算法的性能及计算成本，并且不能完全确保最后解的可行性。
3. 分离约束与目标函数法，如约束占优法是被Deb^[17]研究提出来的，还有随机排序法^[18]则由Yao及Runarsson建议提出的。随机排序方法引进了判别比较目标函数值或约束违规程度的概率，但因为添加了新参数以及参数的设置，都对实验结果有深远的影响；约束占优法是本文使用的解决方案，它的实验结果比较好的，通过某些措施来确保最终结果收敛于可行解范围，而且还不会丢失不可行解也许执行的有用信息，比较适用于处理实际工程问题。
4. 混合约束处理法，由于当前常规的约束处理方法具有各自的优势与短处，因此一些学者建议把新办法与现存的办法联合起来，充分利用现有方法的优点并且改进他们的不完善之处。

在国内，同样有相当部分学者专家研究约束优化的问题的处理方案，比如，以焦李成教授为代表的西安电子科技大学的学者们，一起探索提出了一种进化策略唤作人工免疫反应，其可以用于约束优化，中山大学周育人教授建议依照Pareto强度值排列个体，由此选取合适的个体参加进化。

对于本文所需研究的约束优化问题，是在以运用进化算法NSGA-II为基础来优化目标，采用Deb等人定义的约束占优法则来解决约束条件，并将其与进化算法相结合，使算法可以更加准确有效地求解约束优化问题。

1.3 研究目标与内容

1.3.1研究目标

如何在考虑资源约束的情况下解决拆卸线平衡，对保护环境、增加产品回收利用率以及提高工业生产具有极其重大的意义。本课题针对产品拆卸线的特点，构造了资源约束的拆卸线平衡问题模型，结合相应约束处理算子，并运用一种代表性的进化算法——NSGA-II算法对模型进行求解，给出算法评价数据，最后应用于实际拆卸案例。

1.3.2 研究内容

（1）资源约束的拆卸线平衡问题建模

学习总结如今拆卸线平衡问题的研究资料与成果，重点掌握当今研究的方向与特征。本文考虑的资源为能量，在资源和优先关系的约束下，以最小化工作站数与空余时间为目标，构建本文研究的带资源约束的拆卸线平衡问题的数学模型，并通过Lingo软件将数学模型编码运行，验证模型正确性。

以上是毕业论文大纲或资料介绍，该课题完整毕业论文、开题报告、任务书、程序设计、图纸设计等资料请添加微信获取，微信号：bysjorg。

相关图片展示：