英语原文共 13 页
具有并行站的随机拆卸线平衡的多目标优化问题
摘要
在产品回收中执行的主要活动之一是拆卸。拆卸线是拆卸产品最合适的方式。因此，设计和平衡高效的拆卸系统对优化产品回收过程非常重要。在本文中，我们研究了一类具有并行站的随机拆卸线平衡问题的多目标优化问题，提出了一种求解该多目标优化问题的遗传算法（genetic algorithm，GA）。通过使用产品的AND 、OR Graph （AOG），同时优化线平衡和设计成本目标。本文提出的遗传算法考虑两种不同的适应度评价方法、修复算法和多样化策略来生成Pareto最优解。本文对96个测试问题进行了测试，这些问题是使用文献中开发的针对AOG上定义的问题的基准问题生成方案生成的。此外，为了验证算法的性能，提出了目标规划方法和启发式方法，并与遗传算法的结果进行了比较。计算结果表明，从求解质量和CPU时间两方面考虑，遗传算法可以作为求解具有并行站的随机DLBP的一种有效算法。
关键词：拆卸线平衡；并行站；多目标优化；遗传算法；随机性
1 引言
随着技术发展和工业化而来的迅速城市化和种群增长增加了世界各地对环境的压力。随着工业化的发展，生产和营销活动的扩张必然会大量使用自然资源（Gungor amp; Gupta，1999）。由于消费的不断增加而产生的废物由于其数量和有害内容而威胁到环境和人类健康。
由于环境问题日益突出，未来我们将更加注重可持续发展，而不是单纯的经济增长。可持续发展已经越来越多地在世界各地被作为一项优先政策目标。这是为了提高人类的生活水平，同时减少自然资源的使用（Jovane et al.，2008）。它的主要推动力是可持续生产，它将生产与逆向生产相结合，即闭环生产（Yoshikawa，2008）。具有环境意识的生产和回收活动构成逆生产的基础。在这种情况下，这种生产和产品回收过程的目的是防止快速自然资源消耗（Gungor amp; Gupta，1999）。这些过程不仅把废物转化为各种工业的投入，而且让废物提供了额外的价值。
具有环境意识的生产开发新产品的制造方法，从设计阶段到最终交付和最终处理的生命周期（end of life，EOL）产品，以满足环境标准和要求（Ilgin amp; Gupta，2010）。回收的目的是通过回收弃置或过时产品的物料及零件，尽量减少运往堆填区的废物量。这是通过回收和再制造来实现的（Gungor amp; Gupta，1999）。近年来，环境立法更加严格，垃圾填埋场成本增加，公众意识增强等各种因素迫使制造商对EOL产品进行回收和再制造（McGovern amp; Gupta，2007b）。
材料回收被称为回收，其目的是通过进行必要的拆卸、分拣和物理化学操作来回收EOL产品的材料含量（Gungor amp; Gupta，2002）。另一方面，再制造（产品回收）被定义为一个工业过程，在此过程中，产品被完全拆卸，并进行所需的拆卸、分拣、翻新和装配操作，以使磨损的产品恢复到类似的新状态。与回收利用相比，再制造代表了一种更高形式的重用，侧重于增值回收（Guide，2000）。
通过允许有方法地从EOL产品中提取有价值的部件、组件和材料，拆卸在材料和产品回收中扮演着重要的角色（Gupta amp; Taleb，1994）。拆卸后，可重复使用的部件、组件被清洗、翻新、测试，并直接用于再制造作业。可回收的材料可以卖给原材料供应商，而剩余的则被送往垃圾填埋场（McGovern amp; Gupta，2007b）。由于拆卸通过封闭的循环经济促进工业生产的可持续性（Duflou et al.，2008），因此设计和平衡拆卸线能够高效工作至关重要。
在文献中，拆卸线被定义为最适合于拆卸由许多部件组成的大型产品和大量接收的小型产品（Gungor amp; Gupta，2002）。Gungor和Gupta（2001，2002）是研究拆卸线平衡问题的第一人。拆卸线的平衡对于最大限度地减少投入在拆卸上的宝贵资源（如时间和金钱）的使用是至关重要的。它还最大化了拆卸过程的自动化水平，并提高了回收部件或材料的质量（McGovern amp; Gupta，2007b）。
与装配系统相比，拆卸系统可能面临许多独特的挑战（Brennan，Gupta，amp; Taleb，1994；Gungor amp; Gupta，2001；McGovern amp; Gupta，2003a，2007b）。这些挑战包括复杂的库存问题、复杂的流程、与产品质量和结构相关的高度不确定性。由于工作中心的可靠性问题，拆卸任务时间的巨大差异应该添加到列表中（Brennan et al.，1994）。指南（2000）报告说，拆卸作业一般在所需时间方面变化很大。在这种情况下，考虑直线设计（顺序站）和确定的任务时间，无法实现高效灵活的拆卸线设计。因此，受装配线启发的各种生产线配置和平衡技术可以应用于拆卸生产线，以克服这些复杂性，提高拆卸生产线的灵活性。其中一个策略就是并行。在装配线文献中考虑了两种类型的并行。第一种方法称为任务并行，它允许一个任务在多个工作中心中执行，拆卸该任务所需的工具、设备应该放在所有这些工作中心中。第二个称为工作站并行，要求所有并行站具有分配给该工作中心的任务所需的所有工人和工具、设备（Ege，Azizoglu，amp; Ozdemirel，2009）。并行站有几个重要的好处（Bard，1989；Buxey，1974）。一个好处是平衡效率的潜在提高，因为每个重复的站点都有一个周期时间，这个周期时间等于原始的周期时间乘以相同的并行站点的数量（Bukchin amp; Rubinovitz，2003）。Buxey（1974）指出，将并联工作站引入工作中心，在设计装配线时提供了高生产率和灵活性。它也增加了线路的可靠性。在一条直线上，一个工位的故障使整条生产线停止，而一个平行工位的故障使生产线以较低的生产率运行（Bukchin amp; Rubinovitz，2003）。使用并行站在生产线的潜在益处还被Pinto，Dannenbring和Khumawala（1981），McMullen 和 Frazier (1997, 1998)，Simaria和Vilarinho（2001），McMullen和Tarasewich （2003、2006），Akpinar和Bayhan （2011），Cakir，Altıparmak，和Dengiz （2011），Tuncel和Topaloglu （2013）提到。并行站对拆卸线的有效设计至关重要。在拆卸生产线上采用并行站，可提高生产效率，提高回收率，缩短生产周期，提高生产线的可靠性，减少工位闲置时间。高效的回收过程关闭了材料的使用循环（Guide，2000），形成了一个本质上的闭环生产系统。因此，生产的可持续性是用最少的资源来确保的。
传统的线平衡问题的求解方法大多是求给定循环时间内的最小工作中心个数，或求给定工作中心个数的最小循环时间。然而在拆卸系统中，还有许多其他重要的因素需要集成到拆卸线平衡程序中，比如部件的可访问性和需求水平、危险内容以及拆卸方向的变化（Gungor amp; Gupta，2002）。在拆卸文献中，大多数研究涉及多目标DLBP和由上述不同目标组合而成的线性优先级函数的实现。该函数用于确定分配给特定站点的最佳任务，以及当两个解具有相等的值时，通过利用其他目标来实现决胜（Agrawal amp; Tiwari，2008；Gungor amp; Gupta，2002；McGovern amp; Gupta，2003a）。McGovern和Gupta （2007a，2007b）使用优先级排序方法评估解决方案性能。由于平衡是首要考虑因素，因此只有在以后才会考虑其他目标。Ding，Feng，Tan和 Gao（2010）在DLBP文献中首次提出了一种新的多目标蚁群优化算法，在具有确定任务时间的直线拆卸线平衡中获得Pareto最优解。
考虑到并行站作业时间的变化以及并行站作业的优点，提出了一种多目标随机拆卸线平衡问题。拆卸系统被认为是装配系统的反面，通过使用产品的AOG来平衡。DLBP最基本的形式是NP-hard （McGovern amp; Gupta，2007b），它包含随机任务时间、不同的线路设计以及同时考虑冲突目标，增加了复杂性。在DLBP文献中，已经提出了不同的基于元启发式的求解方法来有效地求解它（Agrawal amp; Tiwari，2008；丁等，2010；McGovern amp; Gupta 2006，2007a，2007b）。在本文中，我们提出了一种遗传算法，该算法已成功地应用于生产经营管理中的各种单目标和多目标问题（Altiparmak，Gen，Lin，amp; Paksoy，2006；Aydemir-Karadag，Dengiz，amp; Bolat，2013；Aytug，Khouja，amp; Vergara 2003；Gen amp; Cheng，2000；Rekiek amp; Delchambre，2006）。本文的目的是提出一种求解具有并行站的随机DLBP的Pareto最优解的方法，使决策者能够评估更多的备选解。由于企业对如何有效地分解EOL产品越来越感兴趣，他们研究了如何使产品回收过程有利可图，或者至少以最低成本进行（Erbis，McGovern，amp; Gupta，2004）。成本主要取决于线路的平衡。因此，本文考虑两个目标：（1）优化线路平衡，即所有工作中心的最小工作中心数量和相似的空闲时间；（2）最小化与劳动力和设备需求相关的设计成本。这些目标通过最小化拆卸过程中时间和金钱等宝贵资源的使用（即工作中心的空闲时间和工作中心的数量）来支持产品回收过程。由于将并联工作站安装到工作中心会因设备、工具的重复而产生额外的费用，因此必须考虑第二个目标，即从经济方面评价线路设计。该算法利用AOG作为主要输入，保证了任务之间优先关系的可行性。该方法考虑两种不同的适应度评价方法，生成Pareto最优解。此外，在搜索过程中，采用了三种不同的修复算法和多样化策略来获得高质量的解决方案。一个新的测试问题集是利用Koc、Sabuncuoglu和Erdal（2009）开发的直线AOG上定义的问题和确定性案例的基准问题生成方案形成的，可用于随机情况。对于生成的问题，我们研究了周期时间和三个参数对CPU时间的影响，这三个参数定义了AOG的大小。此外还有属性的影响，即研究了遗传算法的适应度评价方法、修复算法和多样化策略。从目标函数的角度研究了在工作中心引入平行工位代替直线工位的问题。提出了一种分析遗传算法对小规模问题有效性的目标规划方法，并对中规模、大规模问题提出了一种启发式方法。
本文组织如下：第二节概述了相关文献。第三部分描述了问题的特点和数学公式，第四部分对提出的遗传算法进行了全面的说明。第五节包括测试实例和计算结果的生成。此外，第五节还详细介绍了用于比较遗传算法有效性的方法。最后，在第六节中概述了结束语，并强调了未来的研究方向。
2 文献综述
拆卸线平衡问题最早由Gungor和Gupta（2001，2002）提出。在他们的论文（Gungor amp; Gupta，2001）中，他们提出了一种解决方案，该方案采用了装配线平衡问题（ALBP）中采用的最短路径公式，从而将缺陷部件对拆卸线的影响最小化。Gungor和Gupta（2002）提出了一种基于优先级规则和面向工作站的启发式解决方案，在满足回收部件需求的同时最小化工作中心的数量。
组合优化技术最早由McGovern和Gupta （2003a）在DLBP上应用。针对多目标DLBP，提出了一种贪婪、2-opt混合算法，在处理危险和高需求零件的同时，最小化工作中心的数量。McGovern和Gupta（2004）后来比较了用于DLBP的各种组合优化技术。在文献中，即使是一个简单的DLBP也被证明是NP-hard （McGovern amp; Gupta，2007b），求解DLBP大多采用基于种群的元启发式技术，如蚁群优化和遗传算法。McGovern和Gupta（2006）提出了一种基于蚁群周期模型的蚁群算法来求解多目标DLBP。他们提出了一种两阶段优化方法，第一步最小化站点数量，第二步平衡站点的工作负载。Agrawal和Tiwari（2008）使用协同蚁群优化算法求解具有随机任务时间的混合模型U型DLBP。他们同时确定模型的顺序，并将任务序列分配给工作站。不幸的是，没有其他研究DLBP文献考虑其他线配置和随机任务时间。丁等（2010）提出了一种新的多目标蚁群优化算法，并在DLBP文献中首次获得了Pareto最优解。然而，与我们的问题相反的是他们考虑具有确定任务时间的直线拆卸线。McGovern和Gupta（2007b）提出了一种遗传算法来获得多目标DLBP的最优或近似最优解。在上述所有研究中，DLBP都定义为零件优先图（part precedence diagram，PPD）。
在相关文献中，只有两项研究提出整数规划（integer programming，IP）公式来求解DLBP，并使用AOG来定义问题。Altekin，Kandiller，和Ouml;zdemirel（2008）考虑了利润导向的DLBP，提出一种混合整数规划公式，同时解决拆卸找平和线路平衡问题。Koc等人（2009）认为DLBP是已知ALBP的反面。他们提出了两个精确的公式（整数规划公式和动态规划公式）来求解DLBP，目标是使站点数量最小化。他们使用了一种叫做转换AOG（TAOG）的新图表，而不是AOG或PPD，这使得IP公式更有效。在传统的ALBP中，它们也显示了AOG相对于传统任务优先图（TPD）的优越性。
我们的研究与以前的研究在几个方面有所不同。我们认为拆卸系统是装配系统的反面，并使用Koc等人（2009）开发的TAOG。重点研究了基于AOG的随机DLBP算法，并允许工作中心的并行。提出了一种求解DLBP多目标优化问题的Pareto最优解的遗传算法。在ALBP文献中，McMullen
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
