《A hybrid approach for dynamic routing planning in an automated assembly shop》

Robotic and Computer-Integrated Manufacturing/2010

1 摘要

        动态作业车间作业的高度动荡环境影响着车间布局以及制造作业。由于布局变化的动态特性，在重新配置车间布局时，除了考虑材料处理和机器搬迁的成本问题外，还需要考虑诸如对变化的适应性和响应性等基本要求。本文根据不确定性的来源，将车间布局问题分解为两个子问题，并通过重新布局和寻路两个模块进行处理。遗传算法用于改变导致整个车间重新布局的地方，而功能块用于在现有布局的新条件下找到机器人的最佳序列。本文介绍了作者以往工作的最新进展。

2 介绍

        设备布局问题是根据产品的操作路线，在车间中找到机器类型和它们的位置之间的一对一映射。在成本和时间方面，它是显著影响生产效率的关键领域之一。通过最小化物料搬运成本(MHC)，一个有效的设备布局可以将一个行业的运营成本从10%降低到30%，这是设备布局设计的最终目标。

        由于生产不确定性成为21世纪制造环境中最具挑战性的方面之一，下一代智能制造的成功取决于其对生产需求的动态响应能力。在这样的环境下，产品设计、产品结构、产品数量和生产过程的频繁变化会影响生产设施布局以及其他方面。

        制造业的不确定性一般分为两类:内部的和外部的。前者是由内部因素引起的，如设备故障、作业延误、拒绝、返工等;后者是由外部因素引起的，如产品需求(量)、产品价格、产品结构、紧急作业等。

        从实际的角度出发，根据不确定性的程度和重新布局的成本，设计师可以在以下布局类型中选择一种：

（1）动态布局(Dynamic layout):考虑多个生产周期，通过平衡所有周期的物料搬运成本和连续布局中设备搬迁的总成本来确定每个生产周期的布局。

（2）稳健的布局（Robust layouts）:在多个生产周期和低不确定性的不同场景中表现良好。

（3）分布式布局（Distributed layout）:允许工厂适应流水作业模式和数量的未来波动，特别是当需求波动太大而无法使设施重新配置具有成本效益时，尤其是当有大量机器和机器类型时。这种类型的布局可用于快速形成临时(虚拟)单元。

（4）可重构布局（Reconfiguration layout）：与实时企业的概念保持一致，在实时企业中，布局前后的更改随时可用，并且通过使用实时数据进行实时布局调整来保持边缘操作。 

        常见的传统车间布局如下：

（1）功能布局：将可能处理不同零件族零件的相同机器类型组合在单个工作中心中。这导致工作中心之间的路线复杂，生产时间长，在制品水平高，物料搬运成本高。

（2）流水线布局：沿着生产线安排机器类型。对于一个作业车间来说，这通常是不可行的，因为不同的零件组合导致了多条流水线。

（3）单元布局：将具有共同或相似操作序列的零件所需的机器分组，以形成零件族的制造单元。这导致在机器故障或产品组合发生变化的情况下灵活性有限。

        为了克服传统作业车间布局的缺点，提出了虚拟单元形成和混合单元布局的概念。

虚拟单元是动态形成的单元，在其中机器被逻辑地临时配置。虚拟单元是仅在系统控制软件(图1)中的一组机器。它允许物理上分布在属于不同零件族的不同单元中的工作站分时工作。

        混合布局是功能布局和单元布局的组合，类似于虚拟单元的概念。它将相同的机器类型相邻在一起，而不会破坏单元格到零件族的分配。通过组合不同的布局模块扩展了混合单元布局的概念。布局模块如图所示。

          设施布局问题还可能涉及其他因素和设计问题：车间的类型和生产变量、物料搬运系统、机器可分配的楼层数、车间的形状和大小、设施的形状和大小、上下车地点等。考虑到设施布局的不同方面，众所周知这是复杂的NP-hard。

        然而，在处理作业车间的不确定性时，仍然需要尝试基于环境变化在运行时进行分布式决策。针对动荡的分布式制造环境，本研究提出采用功能块(FB)技术来提高系统的适应性和主动响应能力，以便系统能够根据机器人装配车间中的变化自主地建议机器人之间的备选路径。

3 启用FB的装配车间布局规划范围

        不确定性的来源可能是产品组合/数量的变化，也可能是意外事件，如机器故障或紧急任务。产品组合或产量的合理变化应该使其值得重新布局。在现有布局内为紧急任务找到最优机器人序列路径或在机器发生故障时找到最佳替代路径就足够好了。这将把车间布局问题分成两个模块：重新布局和查找路线。为了处理重新布局模块，可以结合任何元启发式方法来找到车间的最优/接近最优的新布局。然而，对于查找路线模块，加入了功能块来建议机器人中满足新条件的最佳路线。下图阐述了本研究中可重构装配车间布局问题的概念：

 4 使用GA重新布局车间

4.1 染色体表示法

        每条染色体具有与车间上分配给机器人的位置数量一样多的基因。如下图4为15个机器人的布局，图5为染色体的编码表示。

 4.2 遗传算法算子

 4.3 适应度函数

 4.4 遗传算法流程图

 5 基于FB的机器人调度

        如上所述，产品数量/组合应发生重大变化，以触发装配车间的重新布局。但是，如果有紧急任务到达或机器人出现故障，可能没有必要改变整个车间的布局。将紧急任务定义为具有主装配路线A-B-A-D和副装配路线F-G-A的产品，如图所示：

        因而，可以在现有车间布局内找到最优/接近最优的机器人(或路线)序列，而无需执行任何实际布局重新配置。

        如下图所示，主装配路径可能有多条路线，在这些可能的路线中，应该确定物料搬运成本方面的最优/接近最优的机器人序列，对于第二条装配线，同理，有多条可能的路径，为了在可能的路径中选择最优但可行的路径，评价标准还必须考虑由于涉及相同类型的机器人的在途生产所造成的时间延迟。

        通过FB的嵌入式算法，可以使用方法论来寻找车间中的最优机器人路线。还可以合并功能块，以便在机器人故障的情况下找到最佳替代机器人/路线(图10)。

6 设计寻路功能块(FR-FB)

        寻路功能模块结构图如下所示：

6.1 输入

        FR-FB的输入数据为：INI_INFO、FR_INFO和RB_INFO。INI_INFO(初始化信息)与初始化事件EI_INI耦合，以接收来自上级监督规划的最新更新和信息，包括：

（1）机器人的位置

（2）无序设备

（3）单位距离物料搬运成本

（4）该机器人与其他机器人之间的物料搬运设备类型

（5）物料搬运设备的速度

        在接收到所有初始化信息后，触发事件输出EO_INI以发出初始化过程完成的信号。

        FR_INFO(查找路由信息)与事件输入EI_FR相结合，包含查找路由算法ALG_FR使用的以下信息：

（1）装配产品的机器人布线(主装配线或辅助装配线)

（2）产品流程；

（3）该机器人接收的物料搬运设备的类型；

（4）机器人完成当前作业的剩余时间。

        在机器人故障的情况下，通过输入事件EI_RB将情况传给功能块，而输入事件EI_RB又触发输出事件EO_RB，将情况传给相同类型的其他机器人以及路线中的前一个和下一个机器人。FR-FB通过事件EI_BD与RB_INFO数据输入一起接收应答。

        备用路由算法ALG_AR使用的RB_INFO(机器人故障信息)包括：

（1）同类型机器人完成当前工作所剩的时间；

（2）机器人的位置

（3）这些机器人的MHE类型。

6.3 输出

        输出数据即RR和AR分别由嵌入式算法ALG_FR和ALG_AR产生。

        RR（robot routing）:

（1）累积物料搬运成本；

（2）表示机器人路线的字符串  

（3）如果机器人是机器人类型-路线中的最后一个，则建议机器人的最佳顺序

        AR（alternative route）:

（1）故障情况下与其他机器人的路径评估；

（2）最佳替代机器人的建议.

算法ALG_FR和ALG_AR完成后，分别发射输出事件EO_FR和EO_BD。下一节将介绍嵌入FR-FB中的两种算法的详细信息。

5.3 Embedded algorithms(嵌入式算法)

        ALG_FR(Find-Route Algorithm)算法负责在许多可能的路径中为紧急任务寻找最佳的机器人路径，如图9所示.路线评估分为主装配线和次装配线。利用双行字符串来表示机器人的类型和ID，以形成机器人序列。此字符串从布线中的第一个自动机类型开始传递给自动机进行处理。成本评估是以方程（2）-（6）为基础的。。由于不同类型的MHE在机器人之间的不同路线上服务，所以方程(3)-(5)被定义为考虑由于MHEs和机器人的不同可能组合而产生的时间成本。

 如图12所示.每个FR-FB接收产品路线的主要和次要装配线的机器人类型布线、先前机器人的ID号、累积的MHC、到目前为止的累积的CT2、CT1和TC。然后，它将其ID添加到其类型下的字符串中，并计算机器人的关联MHC、CT1和CT2，并更新字符串中的这些值。该算法消除了重复的机器人ID，避免了使用相同的机器人进行评估。它还检查无序机器人的ID以忽略它们进行评估。类型路线中的最后一个机器人也会比较总成本，并选择成本最低的最佳机器人序列。