题目：混合模型装配线顺序规划的复杂性模型

（作者：Xiaowei Zhu , S. Jack Hu , Yoram Koren , Ningjian Huang）

摘要

顺序规划是装配线设计中的一个重要问题。它是确定按顺序执行的装配任务的顺序。根据不同的工艺时间、投资成本和产品质量等标准，我们进行了大量的研究，以找到良好的工艺流程。本文讨论了在混合模型装配线上基于产品变化引起的复杂度的最优顺序选择问题。复杂性被定义为操作者选择复杂性，它间接地测量了在多产品、多阶段、手动装配环境中选择零件、工具、夹具和装配程序时的人类绩效。

作者在早期的一篇论文中提出了装配线的复杂度度量及其模型。根据所建立的复杂度模型，装配顺序决定了复杂度的流向。因此，适当的装配顺序规划可以降低复杂性。然而，由于在优化过程中难以处理复杂流的方向，基于动态规划，建立并求解了一个转换后的网络流模型。本文所开发的方法扩展了前面关于建模复杂性的工作，并为装配顺序规划提供了解决方案策略，以最小化复杂性。

1. 引言

顺序规划或顺序分析是装配系统设计中的一个重要步骤，它决定了哪项装配任务应该先完成，哪项后面完成。合理确定工序有利于平衡生产线，减少设备投资，保证产品质量。为了找到有效的方法来寻找良好的序列，已经进行了大量的研究。

装配顺序规划（ASP）的过程从装配产品的表示开始，例如，通过图形或邻接矩阵。Bourjault首先引入了一种图，即联络图，以建立组件中各部件之间的关系。联络图是一个图形网络，其中节点表示零件，节点之间的线（或弧）表示联络。每个连接代表两个部分连接的装配特性。实现这种联系或联络的过程称为装配任务。因此，ASP的问题是找到实现联络的适当顺序，即完全组装产品所需的任务序列。

图1

另一种装配表示是优先级图。优先级图是装配任务之间优先关系的网络表示。如图1所示。在图中，节点表示任务，如果任务i是任务j的直接前置任务，则存在弧（i，j）。

优先级图中的两个重要概念是不相关的任务对和传递性。一个任务可以有多个直接前置任务，并且可以在所有直接前置任务完成后立即启动。根据这个定义，如果一个任务有两个或两个以上的直接前置任务，那么每对前置任务都必须是不相关的（即没有优先关系），因为它们都不是另一个前置任务。此外，如果我是j的前任，而j是k的前任，那么显然我是k的前任。在符号学中，我们写下：ilt;j，jlt;k == i k。这种优先关系的性质称为及物性。因此，通过传递性，我们可以从每个任务的直接前辈集合（即从优先级图）中确定一组前辈或任何任务的后续任务集合。我们将在随后的分析中使用上述两个概念。

通常，一个优先级图对应多个序列。利用这些候选序列，根据不同的标准选择最佳顺序。其中一个标准就是平衡这条线。Scholl对装配线平衡进行了彻底的处理。大部分工作都致力于简单的装配线平衡问题与一个同质产品的限制。最近，Scholl和Becker对简单装配线的精确启发式求解过程进行了最新的综合调查。除了平衡生产线之外，其他工程知识也可以纳入序列选择过程，例如，删除不稳定的子组件状态以避免尴尬的装配过程并提高质量；消除再加工和重新定位以降低非增值成本；强制子组件允许P并行处理，等等。

除了关注单一产品外，研究人员还为一组类似产品开发了顺序规划方法。Gupta和Krishnan表明，对一个产品系列进行仔细的装配序列设计有助于创建遗传子组件，从而减少子组件的生产和提供产品品种的成本。Rekek， Lit等人开发了产品系列（包括装配顺序）和混合模型装配系统同时设计的集成方法，使多个产品可以在同一条线上装配。Becker和Scholl认为，混合模型线平衡问题通常与序列问题有关，序列问题必须决定模型单元的组装顺序。例如，Yano和Rachamadugu开发了排序算法，以最小化由于不同模型处理时间不同而导致的工作过载；Merengo等人提出了水平平衡的概念，以使线路平衡时不同型号的站时间平滑；Vilarinho和Simaria考虑了具有并行工作站和分区限制的混合模型装配线的平衡。他们开发了一个两阶段的程序，在给定的周期时间内尽量减少工作站的数量，同时平衡工作区之间和工作区内的工作负载。因此，根据哪个因素对不同设置中的特定线路设计问题至关重要，通常会为最佳装配顺序的选择制定新的标准。

本文讨论了在手工、混合型装配线上，为降低制造复杂度而进行的工序规划。混合模型装配线广泛应用于各种行业（如电器、汽车和航空航天），以处理多个产品模型。这种灵活性有助于分享昂贵的设备投资，并吸收不确定的需求波动。然而，当产品变型数量很大时，混合模型装配过程可能变得非常复杂。这是因为，在生产过程中，需要协调许多小的生产步骤，因为有不同选择的产品使用了许多零件（例如，对于汽车，超过三千个不同的零件）。此外，只有有限的自动化在经济上是可用的，而且过程的很大一部分仍然依赖于手动操作。因此，由于复杂性，装配过程会受到不可预测的人为错误和性能（质量和生产率）下降的影响。为了更好地理解制造复杂性及其对性能的影响，作者开发了一个评估复杂性的定量模型。该模型是基于操作人员必须在一个站点做出的选择，复杂度是作为做出选择的不确定性来衡量的。关于复杂性度量和模型的详细信息将在下一节中回顾。根据对于所开发的复杂度模型，装配顺序决定了复杂度的流向，因此适当的装配顺序规划可以降低复杂度。

本论文的目的是发展找出最佳装配序列以最小化系统复杂度的方法。本文的结构如下。第2节提供了关于复杂性度量和模型的背景信息，并展示了通过装配顺序规划最小化复杂性的机会。第三节讨论了问题的形成和基于整数规划（IP）解决问题的初步尝试。由于IP中约束的处理困难，第4节给出了一个网络流程序公式，将原始问题转化为一个可求解的旅行商问题，并用扩展的优先图表示优先约束。在转换过程中，利用优先级约束的信息简化问题，然后实际解决原始优化问题。然后，采用动态规划的方法，对转换后的问题进行求解。第5节展示了图1所示的十个任务案例研究的数值示例。最后，第六部分对本文进行了总结，并对今后的工作提出了建议。

2.研究背景

在本节中，我们介绍了从早期论文中为混合模型装配线开发的复杂性模型。该模型考虑了人工装配生产线中由产品种类引起的制造复杂性，操作员必须根据零件、工具、夹具和装配程序的不同做出选择。我们提出了一种称为“操作员选择复杂性”（OCC）的复杂性度量方法，用以量化做出选择时的不确定性。OCC采用一种分析形式作为选择过程中平均随机性（不确定性）的信息论熵度量。假设操作者在即将到来的装配任务中选择的内容越重要，复杂度越低，操作者出错的可能性越小。降低复杂性有助于提高装配系统的性能。

事实上，OCC的定义也类似于《希克斯-海曼定律》中对人的行为的重要衡量标准，该法在各种手工装配操作中有广泛的应用。在更一般的情况下，Sivadasan等人将熵定义为描述系统状态所需的预期信息量。通过使用熵定义，他们为供应商-客户系统开发了操作复杂性的度量。复杂性度量考虑了与管理供应商-客户系统中信息和物料流的动态变化（时间或数量）相关的不确定性。

2.1复杂度的度量

本文中复杂性的度量被定义为选择过程熵的线性函数。选择过程包括一系列关于时间的随机选择。然后，选择由随机变量表示，每个变量表示从选择集中选择一个可能的备选方案。

事实上，选择过程可以被视为离散时间，离散状态随机过程X^，={Xt，t=1，2，hellip;}，在状态空间（选项集）{1，2，...，m}，其中t是离散时间段的指数，m是每个时间段内可能选择的备选方案总数。基于上述符号，如果随机序列是独立的、相同分布的（I.I.D.），则选择过程的熵可通过以下h函数计算：

H（X）=H（p1,p2,hellip;hellip;pm）=-C*Sigma;Pm*logPm

式中，C是一个常数，取决于所选对数函数的基数，如果选择了log₂，C=1，熵的单位是 比特（bit）；Pm=P（x=m），（m=1，2，hellip;..，m），这是选择mth选项的概率；（p1，p2，hellip;pm）确定x的概率质量函数，也被称为与选择过程相关的（组件）变量的混合比。混合比反映了混合模型装配过程中的各种信息。

利用一个站点上各种选择过程的已知熵值，通过与选择相关的所有熵值的总和来计算该站点的复杂性。此外，确定与选择相关的多样性位置，即复杂性来源，是计算的关键。现在我们将展示如何在复杂性传播和系统级模型的上下文中计算复杂性。

2.2复杂性传播

基于多阶段制造系统中多样性导致复杂性的观点，我们为每个站点定义了两种类型的复杂性：

bull;Feed复杂性：由当前站点添加的功能变量引起的选择复杂性。

bull;传输复杂性：由先前在上游站添加的功能变体引起的当前站的选择复杂性。

这两种复杂度的传播方案如图2所示，其中，对于站点j，feed复杂度表示为cjj（带有两个相同的下标），传输复杂度表示为cij（带有两个不同的下标来表示上游站点i添加的变量导致的站点j的复杂度）。传输复杂性的存在是因为添加在上游站I上的特征变量已被带到站J，可能影响站J实现其他功能的过程

图2

2.3.系统级复杂性模型

通过定义两种类型的复杂性，我们可以导出系统级复杂性模型，以表征多个顺序排列的站之间的交互。考虑装配线有n个工作站，如图3所示

图3

在图3，每个有向弧表示从站i流到j（Cij 的传输复杂度流Cij可以是零）。因此，站点的总复杂度只是站点的馈送复杂度和所有上游站点的传输复杂度之和。对于站j，总复杂度为：

Cj=cjj Sigma;cij（对所有ilt;j）

根据传输复杂性的定义，如果在站点i添加的组件变量在站点j的组装操作期间引起选择，我们有：

Cij=aij*Hi，其中i=0，1，2，3,hellip;,n-1. J=1,2,3hellip;,n

其中Hi 是在站i添加的组分变体的熵;H0 是基部变体的熵;aij 是站j处的组装操作与站i处添加的变体之间的相互作用系数，即:

aij=0或1

3.问题的形成

在本节中，我们将讨论上述顺序规划问题的假设和公式。此外，还编制了一个整数程序，作为解决这一问题的第一次尝试。

3.1假设：位置独立选择复杂性

基于简单和实用的原因，我们提出了位置独立性对转移复杂性的假设。也就是说，cij和cji的值仅取决于两个任务i和j的相对位置，而不是介于两者之间的任务，也不是它们在装配序列中的绝对位置。虽然这一假设似乎有局限性，但它适用于装配具有高度模块化组件的定制产品，例如汽车、家用电器和电子产品的最终装配过程。由于简化了计算过程，使得求解最优解的计算量大大减少，问题也变得易于处理。

3.2整数规划公式的问题

由于强加的优先约束，可以将程序1等效地视为在优先级图中找到覆盖链（或游览）的节点。图。1最小的有效复杂度总和从节点i流向j，其中i j。因此，整数程序可以如下公式化。

≺

4. 网络流程序公式

首先，我们假设每对组装任务之间的传输复杂性值是已知的。它们在如图5所示的阵列中进行选择。但是，由于优先级限制，数组中的某些单元格是不可接受的，即，如果任务i不能先于任务j，则将单元格（i，j）表示为不可接受的，并为其指定infin;复杂性值。找到所有这些不可接受的细胞并清除它们可以大大简化最初的问题。因此，下面制定了一个程序。

4.1不合格细胞清除程序

步骤1：对于行i，在第j列中为所有j标记X，其中j Ji = {j | i j}（Ji是与节点i具有优先关系的节点集，包括隐式传递关系）。

步骤2：对于行i，如果第j行未标记，则{i，j}是一对不相关的元素。 无关对的含义是任务i可以在任务j之前分配，反之亦然。 这两种情况的复杂性分别为Cij或Cji。 找出单元格（i，j）和（j，i）并用Y标记它们。图6显示了步骤1和2之后的结果数组。

步骤3：到目前为止，所有未标记的细胞都是不可接受的细胞。 用infin;标记它们并用适当的下标恢复相应的成本系数到其余的单元格，并对用X标记的单元进行着色以供以后使用（该步骤的结果未在图中明确示出）。

4.2等效网络流模型

观察到非阴影单元中的复杂度值成对形成; 在每个可行解决方案中，它们中的一个且仅一个是活动的并且在总系统复杂度成本函数中计数。 相反，阴影单元格中的复杂度值是由优先约束强加的，无论是明确的还是隐含的; 因此，在所有可行的解决方案中，所有这些都被计算在内。

上述观察意味着在不改变原始问题的情况下简化复杂性成本数组的方法之一。 也就是说，我们只需将所有阴影单元设置为零，参见图7.然后，程序2中原始优化问题的目标函数的唯一变化是常数，这不会影响最优解。 实际上，简化的等价论证是如果优先约束要求i明确地或隐含地（通过转移性）在j之前，则将复杂度从i设置为零，即ij的Cij = 0。

图7中表示复杂度成本的单元是形成无关对的单元。 在如图1所示的原始优先级图上，如果{i，j}是这样的无关对，则在两个方向上在i和j之间绘制有向的虚线弧，并且分别将流量值Cij，Cji分配给相关的弧。 获得扩展优先级图，如图8所示。请注意，实弧上的流是具有显式优先关系的两个任务之间的复杂度值，由于前一段中的简化，所以它们都为零。 然而，虚线弧上的流是每个不相关的任务对之间的复杂度值，其可以采用非零值。

a

b

每个可行解决方案对应于在扩展优先级图中满足以下属性的路径。

1.路径是指向的，即行程必须遵循箭头的方向;

2.该路径必须访问每个节点一次且仅一次;

3.该路径必须具有向前指向的

英语原文共 10 页

资料编号：[4346]