张宏林，殷复鹏，2，吴爱华

0 引言

装配线是大批量生产的产品经常采用的一种生产方式，这种生产方式可以最大限度地缩短生产时间和运输路线，提高劳动生产率。装配线平衡是发挥装配线优势的关键，与产量、质量和成本都有很大的关系。在我国，由于装配线不平衡引起的效率低下、成本浪费现象十分严重。因此，装配线平衡问题一直是企业和学术界广泛关注的问题。装配线可以分为单边装配线和双边装配线，双边装配线普遍应用于汽车、装载机等大型产品的生产装配过程中，与单边装配线相比，具有能缩短装配线长度，减少产品的下线时间，降低工具、夹具及物料处理的成本等优点。

从1955年Salveson首次提出装配线平衡问题至今，人们对其进行了大量的研究，针对不同的装配线类型建立了多种模型，并提出最优化方法、启发式方法等多种算法。Nils等详细地对装配线平衡问题进行了分类和总结，并对部分文献进行了归类和比较［1］；Christian等对一般装配线平衡问题及其算法进行了较为详细的总结，并对装配线平衡问题在未来的研究提出了建议［2］。目前，大部分研究都集中于单边装配线平衡问题，对于双边装配线的平衡问题研究较少。Bartholdi首次提出双边装配线的概念，并提出一种启发式算法，此后，Kim，Lee和Lapierre等分别对此问题进行了研究，并各自提出不同的算法［3］。近年来，Uˇgur等针对双边装配线平衡问题，提出了一种禁忌搜索算法［4］；Adil等建立了一种基于启发式算法的蚁群模型来解决双边装配线平衡问题［5］；吴尔飞等对双边装配线的平衡问题进行了深入研究，先后提出了基于位置的任务分配策略的启发式算法［3］，并针对双边装配线第二类问题建立了数学模型，提出一种基于规则的启发式算法［6］。

以上双边装配线平衡问题的研究只是针对装配线一个位置左右各有一个工位（伴随工位）的情况，而实际上装配线上的每一个位置往往有多个工位，如在重型汽车装配线上，一个车位（相当于位置）一般有4～6个工位。对于多个工作的并行作业的装配线平衡问题，一些学者也进行了相应的研究，如Christian等［7］，但这些研究都没有考虑装配线左右方位约束的限制。

本文对双边多工位装配线平衡问题进行分析研究，建立该类问题的数学模型，并提出一种有效的启发式算法，为此类装配线平衡提供参考。

1 问题及其描述

双边多工位装配线是在单边装配线的基础上，将原来的工位分为左右多个工位，工人在各自工位上独立作业。本文采用文献［6］中的概念，用位置来表示原单边装配线的工位，称位置左右的工作区为工位，位置内各工位并行作业。如图1所示，位置1的左边和右边各有2个工位，共4个工位；位置2的左边有3个工位，右边有2个工位，共5个工位。

双边多工位装配线一旦投资建成后，很难再进行大的改动，即装配线的长度和装配线所拥有的工作的数量难以变动。因此，与单边装配线相比，双边装配线平衡需要考虑的约束和要求较多，在平衡时，除了需要满足作业的先后约束关系外，还应该考虑以下影响因素：

（1）作业方位的约束 由于受产品结构、装配线设施等的限制，某些装配作业具有方位约束，即作业只能在装配线的左侧或右侧进行。例如由于油箱、空气过滤器、工具箱等部件位于汽车的一边，在汽车装配线上，这些部件的装配操作应安排在与其对应的装配线一侧。可将方位约束分为左方位约束、右方位约束和无方位约束三种情况。

（2）同位置不同工位的优先关系约束 一般同位置内各工位并行作业，但在分配作业时有可能将具有紧前紧后关系的两个作业要素分配给两个工位，这样就有可能使两个作业中的紧后作业产生等待时间，影响平衡。因此，双边装配线平衡时，不仅要考虑其自身作业时间对平衡的影响，还要考虑其前序作业是否分配给与该工位同在一个位置内的其他工位的影响。

本文研究的双边多工位装配线平衡问题仍然属于第一类平衡问题，具体可描述为：已知装配线位置数及各位置左右两边工位数，给定生产节拍，一组作业集在满足作业顺序优先关系、方位约束的条件下，将作业尽可能均衡地分配到装配线两边的各个工位上，使装配线的长度最短（位置数量最少）、启用的工位数量最少。

2 双边多工位数学模型

2.1 假设

由于现实中装配线的复杂性，本文对装配线平衡的研究仍然建立在一定的假设基础之上。

假设1 装配线上工人的技术水平不存在差异，可以完成任一项作业。

假设2 装配线上同时只生产一种产品。

假设3 一个作业元素的作业时间不依赖于位置和工位。

假设4 装配线的节拍大于作业元素时间中的最大者。

假设5 作业元素可以分配到任何工位，即作业元素没有位置约束。

假设6 一个作业元素只能分配给一个位置和一个工位。

2.2 参数设定

在建立模型之前，首先对模型中出现的参数及其符号进行说明：

C表示装配线的节拍；

Tasks 表 示 作 业 元 素 集 合，Tasks ＝ ｛1，2，…，n｝；

n表示作业元素的个数；

i和j为作业元素的序号，代表作业元素i和j，i，j＝1，2，…，n；

ti表示第i个作业元素的时间，i＝1，2，…，n；

pred表示作业元素的优先关系集合，pred＝｛（i，j）｜作业元素i是作业元素j的紧前作业｝；

n＋1表示在作业元素优先关系图中，作业元素的唯一归宿节点序号；

K表示装配线拥有的位置数；

k表示位置的序号，代表第k个位置，k＝1，2，…，K；

mk表示装配线上第k个位置拥有的工位数，mk＝＋

l表示位置左边工位的序号，代表某一位置的第l个工位；

r表示位置左边工位的序号，代表某一位置的第r个工位；

ail表示左方位约束，ail＝1表示作业元素i需要安排在装配线的左侧，否则ail＝0；

air表示右方位约束，air＝1表示作业元素i需要安排在装配线的右侧，否则air＝0；

aie表示无方位约束，aie＝1表示作业元素i没有方位约束，即可以分配给装配线任何一侧工位，否则aie＝0；

Tk表示位置k上分配的作业集合。

2.3 决策变量

装配线平衡是一个决策过程，决策变量表示各作业元素的具体分配情况和工作地占用情况，符号说明如下：

xik为0－1变量，当作业元素i被分配至第k个位置时，xik＝1，否则xik＝0；

Ak为位置k的指示变量，即

2.4 数学模型

建立如下整数规划模型：

目标函数（1）表示启用的位置数最少；目标函数（2）表示启用的工位数最少。

约束条件（3）表示作业元素只能被分配到一个位置；约束条件（4）表示作业元素只能被分配到一个工位；约束条件（5）表示每一个作业元素只有一个方位约束；约束条件（6）表示每个位置内的作业时间不能超过该位置的可用时间，位置可用时间的多少与该位置所包含的工位数量有关，其值是位置内工位数与节拍的乘积；约束条件（7）表示每个位置内具有左方位约束的作业时间不能超过该位置左边工位的可用时间，位置左边工位的可用时间指该位置内处于装配线左边的工位数与节拍的乘积；约束条件（8）表示每个位置内具有右方位约束的作业时间不能超过该位置右边工位的可用时间，位置右边工位的可用时间指该位置内处于装配线右边的工位数与节拍的乘积；约束条件（9）表示位置内作业元素在满足顺序优先关系的前提下，各工位的作业时间不超过节拍时间；约束条件（10）保证不违反作业元素之间的优先关系；约束条件（11）表示具有左方位约束的作业不能分配给右边工位，具有右方位约束的作业不能分配给左边工位；约束条件（12）表示如果某个位置中有作业元素分派进去，则无论作业元素有多少个，该位置的指示值都为1；约束条件（13）表示如果位置k的左工位中有作业元素分派进去，则无论作业元素有多少个，该工位的指示值都为1；约束条件（14）表示如果位置k的右工位中有作业元素分派进去，则无论作业元素有多少个，该工位的指示值都为1。

3 启发式算法

3.1 算法的整体思路

双边多工位装配线平衡问题是典型的NP问题，很难求得最优解，本文提出一种有效的启发式算法，能够得到较优可行解。算法整体思路分为两个阶段：

阶段1 开启位置k，分配作业元素。从未分配的作业元素中找出可以分配给位置k的作业元素，构成可行作业元素集合W。

阶段2 分配位置k内的各工位。按照不违背作业优先关系、方位约束和工位时间不超过节拍的原则，把W 中的部分或全部作业元素分配到位置k内的各工位上。当位置k所有的工位都启动并无法再分配作业，或W 中的作业元素都已分配给各工位时，开启下一个位置（k＝k＋1），返回阶段Ⅰ。

3.2 阶段1的启发式算法

符号说明：W 为可分配给当前位置的作业元素集；E和S为过程中用到的作业元素集合；Tefi为作业元素i在当前位置上可能的最早完成时间；p为已分配给工位的作业元素个数。

步骤1 读入相关参数，包括装配线节拍C；待平衡的作业元素集Tasks及相关参数n，ti，pred，ail，air和aie；装配线参数K和等。

步骤2 开启装配线上的第1个位置（k＝1，Ak＝1）；令p＝0。

步骤3 令W ＝ ∅，E＝ ∅，Tefi＝0（i＝1，2，…，n）。

步骤4 在Tasks中未分配的作业元素中，找出没有紧前作业或紧前作业已经分配给W 的元素，存于集合E。

步骤5 在E中任选一个ti最小的作业元素j。该元素如果有已经分配给W 的紧前作业i，则计算Tefj＝ max（Tefi）＋tj；否则直接进入步骤6。

步骤6 比较Tefj与C。如果Tefj≤C，则将作业元素j保存在集合S中，并从集合E中将其删除；如果Tefj＞C，则直接从集合E中删除元素j。此时，如果E不是空集，则返回步骤5；否则，直接进入步骤7。

步骤7 判断集合S是否为空集。如果S不是空集，则将S中的元素存入集合W，并令S＝∅，返回步骤4，否则直接进入阶段2。

3.3 阶段2的启发式算法

符号说明：Tesi为作业元素i在当前位置上可能的最早开始时间；Tlsi为作业元素i在当前位置上可能的最晚开始时间；Tefi为作业元素i在当前位置上可能的最早完成时间；A和B为过程中用到的作业元素集合；STm为当前工位上已分配作业元素的时间和。

Tesi，Tlsi和Tefi计算说明：

（1）如果W 中的作业元素j没有紧前作业，则Tesj＝0，Tefj＝tj。

（2）如果W 中的作业元素j有紧前作业，则Tesj＝max（Tefi）。

（3）如果W 中的作业元素i没有紧后作业，则Tlsi＝C－ti，Tlfi＝C。

（4）如果W 中的作业元素i有紧后作业，则Tlsi＝max（Tlsj）－ti。

本阶段启发式算法步骤如下。

首先从阶段1获取W。

步骤1 初始化ml＝0，mr＝0。

步骤2 令A＝∅，B＝∅。在W 中找出没有紧前作业或紧前作业已经分配完的作业元素，存于集合A。如果A为空集，则开启下一个位置，即k＝k＋1，Ak＋1＝1，转阶段1中的步骤3；否则，从A中选取Tlsi最小的作业元素，存于集合B。

如果B中有具有方位约束的作业元素，则按以下规则从B中选取一个作业元素。若所选作业具有左边约束，则直接进入步骤3，否则转步骤4。

如果B中没有具有方位约束的作业元素，则按以下规则从B中选取一个作业元素，并直接进入步骤5。

规则1 选取Tesi最小的作业元素。

规则2 如果有多个Tesi最小的元素，则从中选取ti最大的元素。

步骤3 如果当前位置k有已开启的左边工位，则从开启的工位中选取STm≤Tlsi的工位：

（1）如果有STm≤Tlsi的工位，则从中任选STm最大的一个工位作为当前工位，转步骤6。

（2）如果没有STm≤Tlsi的工位，则分两种情况：①当前位置的左边工位都已开启时，从W 中删除当前作业元素j，返回步骤2；②当前位置的左边工位没有都开启或没有开启时，新开启一个左边工位作为当前工位，转步骤7。

步骤4 如果当前位置k有已开启的右边工位，则从开启的工位中选取STm≤Tlsi的工位：

（1）如果有STm≤Tlsi的工位，则从中任选STm最大的一个工位作为当前工位，转步骤6。

（2）如果没有STm≤Tlsi的工位，则分两种情况：①当前位置的右边工位都已开启时，从W 中删除当前作业元素j，返回步骤2；②当前位置的右边工位没有都开启或没有开启时，新开启一个右边工位作为当前工位，转步骤8。

步骤5 如果当前位置k还没有开启工位，则开启左边第一个工位或右边第一个工位，作为当前工位；如果开启的是左边的工位，则转步骤7；如果开启的是右边的工位，则转步骤8。

如果该位置有已经开启的工位，则从中选择STm≤Tlsi的工位：

（1）如果有STm≤Tlsi的工位，则从中任选STm最大的一个工位作为当前工位，转步骤6。

（2）如果没有STm≤Tlsi的工位，则分四种情况：①ml＜mkl且mr＝mkr，开启左边一个工位，作为当前工位，转步骤7。②ml＝mkl且mr＜mkr，开启右边一个工位，作为当前工位，转步骤8。③ml＜mkl且mr＜mkr，任意开启左边或右边的一个工位，若开启的是左边工位，则直接进入步骤7；若开启的是右边工位，则转步骤8。④ml＝mkl且mr＝mkr，从W中删除作业元素j及其所有的后续作业，转步骤9。

步骤6 将当前的作业元素分配给当前的工位，且p＝p＋1，STm＝max（STm，Tesj）＋tj，从W中删除该作业元素，转步骤9。

步骤7 将当前的作业元素分配给当前的工位，且ml＝ml＋1，p＝p＋1，STm＝STm＋tj；从W 中删除该作业元素，转步骤9。

步骤8 将当前的作业元素分配给当前的工位，mr＝mr＋1，p＝p＋1，STm＝STm＋tj；从W中删除该作业元素，进入步骤9。

步骤9 若W不为空集，则返回步骤2；若W为空集，则分两种情况：①如果p＜n，则新开启一个位置，即k＝k＋1，Ak＋1＝1，转阶段1中的步骤3；②如果p＝n，则线平衡结束。

4 算例

本文以某重型汽车装配线翻车前的装配线平衡为例，对其进行双边装配线平衡。已知生产某种型号汽车的作业优先关系如图2所示，图中节点上方括号内的符号表示方位约束（L为左方位约束，R为右方位约束，E为无方位约束），数字表示作业时间。已知装配线的情况如表1所示。装配线节拍定为360s。该企业装配线（翻转前）左右工位的数量如表1所示。

表1 某企业装配线现状

应用本文提出的启发式算法进行平衡的一种平衡结果如表2所示。

表2中“作业元素”一列中有数字表示该工位被启用，且数字表示分配到该工位的作业元素编号，“无”表示该工位没有被启用。结果显示，共启用6个位置和17个工位。从平衡结果可以看出，大部分工位的作业时间基本接近节拍，且空闲时间较少，只有个别的工位空闲时间较大，这时可以对其进行调整。调整原则根据实际情况较为灵活，调整时从空闲时间较大的工位入手，在不违背作业元素优先关系的前提下，可以对作业元素进行重新组合，以减少工位空闲时间或减少工位数量，优化平衡结果。如本例中，车位4中工位4－4的空闲时间为246s，工位空闲率达到了68.3%，因此需要进行优化调整，可以取消该工位，将其所包含的作业55，37，46调整到车位5，此时车位五中的作业包括55，37，46，40，49，44，41，47，42，39和48，其中具有右方位约束的作业总时间为375s，所有作业的总时间为637s，都没有超出车位5的可用时间。因此，可以对这些作业按照阶段2的启发式算法重新进行组合。调整后车位4、车位5和车位6的作业分配情况如表3所示。调整后，减少了一个工位（工位4－4）。

表2 一种平衡结果

表3 调整后部分位置作业分配情况

5 结束语

装配线平衡问题提出以来，人们对该问题的研究一直没有中断过，并产生了大量的研究成果。但大部分研究都是建立在较为理想的假设基础上，与实际应用之间存在很大差距。作为重型汽车、装载机等大型产品常用的双边装配线的平衡问题，只有少数学者进行了相应的研究，但仍然只是较为简单的两边各有一个工位的情况。本文针对实际装配线一个位置两边通常各有多个工位的情况，对双边多工位装配线平衡问题进行了研究，并建立了该类平衡问题的数学模型，提出一种有效的启发式算法。应用该方法虽然不能得到最优解，但可以较容易地得到一种较优的可行解，仍然能够为解决该类平衡问题提供参考，并能够在企业中应用。

［1］ BOYSEN N，FLIEDNER M，SCHOLL A.A classification of assembly line balancing problems［J］.European Journal of Operational Research，2007，183（2）：674－693.

［2］ BECKER C，SCHOLL A.A survey on problems and methods in generalized assembly line balancing［J］.European Journal of Operational Research，2006，168（3）：694－715.

［3］ WU Erfei，JIN Ye，SHEN Jian，et al.A heuristic algorithm for two－sided assembly line balancing［J］.Journal of Shanghai Jiaotong University，2007，41（11）：1484－1487（in Chinese）.［吴尔飞，金 烨，沈 健，等.双边装配线平衡的启发式算法［J］.上海交通大学学报，2007，41（11）：1484－1487.］

［4］ ÖZCAN U，TOKLU B.A tabu search algorithm for two－sided assembly line balancing［J］.International Journal of Advanced Manufacturing Technology，2009，43（7／8）：822－829.

［5］ BAYKASOGLU A.Two－sided assembly line balancing using an ant－colony－based heuristic［J］.International Journal of Advanced Manufacturing Technology，2008，36（5／6）：582－588.

［6］ WU Erfei，JIN Ye，WANG Zheng.Research on balancing problem of typeⅡ of two－sided assembly line［J］.Computer Integrated Manufacturing Systems，2005，11（11）：1604－1608（in Chinese）.［吴尔飞，金 烨，汪 峥.双边装配线第二类平衡问题研究［J］.计算机集成制造系统，2005，11（11）：1604－1608.］

［7］ BECKER C，SCHOLL A.Balancing assembly lines with variable parallel workplaces：Problem definition and effective solution procedure［J］.European Journal of Operational Research，2009，199（2）：1－16.