英语原文共 13 页

一种基于波束搜索算法的拆卸线平衡问题求解方法

Suleyman Mete^d, Zeynel Abidin Cil^a,b, KUrsad Agpak^a, Eren Ozceylan³#39;

Alexandre Dolgui

摘要

拆卸线平衡 (DLB) 问题是将一组拆卸任务分配给有序的工作站序列的过程, 以优化某些性能度量 (例如, 周期时间、工作站数量)。由于 DLB 问题属于 NP 硬类, 因此为了在合理的时间内获得可接受的解, 应用了许多启发式和元启发式算法来处理 DLB 问题的复杂性。在本研究中, 提出了一种基于波束搜索 (BS) 的 DLB 问题的方法。将工作站的数量降至最低是一种性能度量。将该算法与已知的真实案例和生成的测试问题的最优解进行了比较。结果表明, 提出的基于 BS 的方法是进一步研究的一个非常有竞争力和前景的工具。

1.介绍

由于严格的环境法规、公众意识的提高和制造责任的扩大, 制造商越来越多地回收和再制造其后消费品。再制造是一个工业过程, 在这个过程中, 降解的产品被恢复到较早的条件下。通过这种方式, 再制造提供了使用过的部件的初始工艺的质量标准。另一方面, 回收是回收废旧和无功能产品材料含量的过程。产品回收要求通过再制造和回收从过时的产品中获取材料和组件, 以最大限度地减少送往垃圾填埋场的废物数量。一个产品有几个步骤来提高产品的恢复能力。拆卸是产品恢复的第一步。它被描述为通过一系列操作系统地将有价值的产品与废弃产品分离。

如果拆卸了某些部件和子组件，则可以部分拆卸；如果完全拆卸了产品，则可以完全拆卸[1]。关于回收、再制造和产品回收的更多细节，可以在ILGIN和Gupta的研究中找到[2]。

由于拆卸在产品回收中的作用，拆卸在文献中得到了合理的重视，并成为一个活跃的研究领域。拆卸系统面临着许多独特的挑战，如复杂的库存问题、退回产品的质量以及结构的高度不确定性[3]。拆卸操作通常在由多个串行工作站组成的拆卸线上进行。由于拆卸线具有较高的生产率和自动化的适用性，因此拆卸线是拆卸操作的适当布局。因此，高效设计和平衡的拆卸线具有显著的环境和工业意义[4]。DLB对于最大限度地利用拆卸过程中投入的宝贵资源（如金钱和时间）以及最大限度地提高拆卸过程的自动化水平以及开发回收部件和材料的质量至关重要[5]。

DLB是一个与装配线平衡（ALB）有关的问题，近年来一直受到研究者的关注[6-9]。尽管DLB中存在许多子问题，但线平衡是最重要的。

一般来说，DLB问题可以通过满足优先级关系和优化性能度量来将分解任务分配给工作站。DLB和ALB问题在技术和操作方面存在一定差异，例如与零件质量、需求来源和优先关系复杂性相关的不确定性[10]。DLB问题首先由Gungor和Gupta[1,4]描述，并且由McGovern和Gupta[11]在数学上证明它是NP困难的，这使得实现最优平衡的目标的计算代价很高。详尽搜索为小规模的测试用例提供了最佳的解决方案，但由于问题的复杂性，它在大规模问题上的适用性很难。因此，为了在合理的时间内平衡拆卸线，需要提出适合工作站任务分配的启发式/元启发式方法。因此，在DLB问题文献中使用元启发式技术的趋势越来越大，如蚁群优化[12]、遗传算法[5]和模拟退火[13]。

本文提出了一种基于BS算法的拆卸线平衡求解方法。BS算法在结构上类似于分支定界法。它已经应用于解决文献中的各种组合优化问题（见表2）。分支定界法用回溯技术检验所有解。与此相反，BS算法只在确定的点上搜索一个解，并使用“前进”来加快解的搜索速度[14]。本研究的目的是提出一种基于BS技术的解决DLB问题的方法，以最小化拆卸工作站的数量。虽然BS已经用于不同的问题，但这是DLB问题的第一个应用程序。在目标函数（工作站数）和速度（CPU时间）方面，将BS的性能与Hezer和Kara[15]提出的最短路径模型进行了比较。此外，通过使用Koc等人开发的基准问题生成方案，形成了一组新的测试问题。〔16〕。将所提出的BS算法与GAMS-CPLEX解算器12.3和随机搜索（RS）算法进行了比较。

论文的其余部分组织如下。在第二节中，对DLB和BS进行了文献综述。在第3节中，Koc等人提出的DLB问题的数学模型。[16]已提交。在第4节中，解释了BS算法。它的适用性在第5节的实际案例和测试问题中得到了证明。最后，结论和未来的方向在第6节给出。

2. 文献综述

本节首先简要回顾了有关 DLB 的最新相关文献, 然后介绍了 BS 的相关文献。

2.1审查关于拆卸线平衡问题的文献

DLB是ALB问题的一个相关问题，近年来引起了研究者的兴趣[7]。虽然在反汇编中有许多子问题，但是行平衡是最重要的。一般来说，DLB问题可以说是将拆卸任务分配给工作站，以优化性能度量，同时满足优先级关系[10]。

有一些数学模型[16,39]来解决DLB问题。然而，在McGovern和Gupta[11]证明了DLB的NP硬性质之后，也开发了不同的启发式/元启发式方法[1,5,10,40]，并应用于在合理时间内得到一个很好的解，这是由于精确模型的问题规模随着问题规模的增大而呈指数增长的结果。

在目标功能方面，尽量减少工作站数量[16]是最理想的性能指标，其次是尽早移除危险和高需求部件[1,4,40,41,42]。表1总结了相关的DLB文献，并对目标函数和解决方法进行了区分。

根据表1，没有使用BS解决DLB问题的纸张。我们选择BS的动机是，当前最先进的ALB问题方法之一的关键算法部分强烈基于BS[21]。由于ALB和DLB问题的相似性，本文对BS在DLB问题上的潜在成功进行了思考和测试。本文的贡献有三个方面：（i）BS算法在DLB问题中的应用；（i i）产生新的DLB测试问题；（i i i）将所提出的BS方法与基于网络的最短路径模型和RS进行比较。

2.2光束搜索算法文献综述

Lowerre[17]首先将BS技术应用于人工智能领域。后来，这种技术被用于许多领域，如柔性制造系统[14]、数据挖掘[18]、人工智能[19]、装箱[20]、ALB[21]问题等。表2给出了BS技术的一些变化和应用领域。BS是分支定界方法在结构上的一种改进。分支定界法用回溯技术检验所有解。与此相反，BS算法只在确定的点上搜索一个解，并使用“前进”加速搜索。

在标准版本的BS中，梁独立进行。如果在BS算法的局部搜索中使用元启发式方法，则这种算法称为混合BS。如果增强工具集成到标准BS中，例如回溯机制和前瞻技术，则该算法被视为改进的BS算法。最后，对滤波后的BS算法进行了扩展和改进。使用过滤机制的目的是减少计算时间，因为它有助于在全局评估之前消除某些节点[22]。

如表2所示，据我们所知，本研究是BS技术在解决DLB问题上的首次应用。

3.问题定义

本文提出了一种基于BS算法的拆卸线平衡求解方法。将工作站数量最小化用作性能度量。Koc等人开发的任务进度图（TPD）。本文中使用了[16]。和/或图是描述将产品完全分解为其基本组件的所有可能方法的图。AOG图显示了将产品完全分解为其基本组件的所有可能方法。参考文献[63]中可以找到AOG表示的详细特征。此外，Koc等人[16]证明使用和/或图代替优先图可以更好地解决传统的ALB问题。虽然和/或图显示了所有可能的子部件，但它没有提供有关分解任务之间优先级关系的信息。因此，Koc等人[16]提出了一种新的图表，称为转换和/或（TAOG），以克服这个问题。TAOG是和/或图（AOG）的一个修改版本，它包含有关所有反汇编树上任务之间优先级关系的特定信息。在本研究中，转换和/或图形被用作优先图。

与子部件相对应的AOG中的每个节点由人工节点（AK）对称。任务在图中用普通节点（bj）表示。表1显示和/或图的转换。

表1：关于DLB问题的最新文献综述

带正常节点（b1，b2-）的样品产品。.b24）和人工节点（a0、a1...a12）如图1所示。一个人工节点（子组件）可以由多个正常节点（任务）前置或后继。但是，只能处理其中一个前置任务和一个后继任务。TAOG中有两种不同类型的弧（以及类型和或类型）。弧型表示正优先级关系，弧型表示可选的可行路径。或型指示器用一条小曲线表示（见图1），以表示两种类型之间的差异。关于TAOG表示的更详细描述，见Koc:等人。〔16〕。

在TAOG中，定义问题大小有三个参数。TAOG中每个级别的人工节点数用A表示，每个人工节点的任务数（普通节点）用T表示，部件数用N.A表示。

图1给出了13个人工节点和24个正态节点的PLE TAOG。样本图的参数设置如下：a=3，t=2，n=6。图1中的曲线描述了或类型关系的指示器。这意味着只有一个前任和一个继任者必须被选中。根据示例（见图1），拆卸程序从三

您可能感兴趣的文章

• 射频通信与传感融合研究综述外文翻译资料
• 具有磁性和电性的单体硅纳米筒的光学光谱分析外文翻译资料
• 水下彩色图像质量评价指标外文翻译资料
• 基于圆柱形纳米金属粒子阵列的高灵敏度生化传感器外文翻译资料
• 基于接收信号强度的RFID室内定位系统外文翻译资料
• 波分复用光通信网络：进展与挑战外文翻译资料
• 一种基于Android客户端的新型电动自行车电池监测系统外文翻译资料
• 租赁电动自行车充电站的微电网结构设计外文翻译资料
• 电动自行车低成本无线充电器的设计与实现外文翻译资料
• 无参考图像清晰度评估自回归参数空间外文翻译资料