简单直线和U型装配线平衡中的改进阶位法

焦玉玲， 邢小翠， 朱春凤， 徐良成， 邹连慧

(1.吉林大学 交通学院，吉林 长春 130021；2.吉林建筑大学 土木工程学院，吉林 长春 130021)

生产线平衡是对生产线的全部工序进行负荷分析，通过调整工序间的负荷分配使各工序达到能力平衡的技术与方法，消除各种等待浪费，提高生产线的整体效率.装配线平衡是装配线工作站作业分配均衡性技术，是一种典型的NP-hard问题[1]，随着生产加工作业元素数量的增加，平衡问题的复杂度呈几何级数增加[2]，求解过程复杂且困难.随着客户需求逐渐变为多品种，小批量的客户定制化和产品多样化，生产制造企业需要提高装配线机动性、柔性，引起装配线上作业元素与产品种类的增加，装配线平衡问题的解决方案数量急剧增加.相对于客户需求的变化，传统的直线型装配线缺乏柔性，任务分配重新调整困难，U型装配线的布局克服了这个缺点.

U型装配线上的工作站相距较近，不仅简化了物料的运输，而且柔性较高，在外部需求发生变化时，通过增加或减少操作人员的数量实现装配线节拍调整达到新的平衡，分配作业元素时，选择的范围更大，分配效果一般比直线型装配线好[3].

装配线平衡算法是学术界和实践界关注的热点问题.1955年Salveson[4]第一次提出用解析法求解装配线平衡问题，并用一个简单的实际案例求解装配线平衡的过程.随着对装配线问题研究的深入以及现代智能算法的发展，装配线平衡问题得到有效解决，Lapierre等[5]利用禁忌搜索算法，在当工作站的时间超过生产节拍时，调整可行解空间和目标函数求解范围，通过结合实际工业的数据验证了算法的有效性.Ozcan、Kellegoz和Toklu[6]对作业元素时间随机的混流装配线平衡与排序问题，采用遗传算法求解，结合具体的U型装配线实例对于算法的有效性和作业时间的随机性进行了研究.Jonn-alagedda[7]对于给定工作站数，最小化生产节拍的U型装配线平衡问题，采用遗传算法求解.求解装配线平衡问题的人工智能算法[8-10]，如遗传算法、禁忌搜索法和粒子群算法等，其编码方式复杂，计算空间复杂度较高，可能会出现局部收敛情况.

基于特定搜索规则的启发式算法，其计算简单，计算效率高.Kucukkoc和Zhang[11]运用阶位法规则解决装配线平衡问题，本文选用基于改进阶位法规则的启发式算法求解装配线平衡问题，即确定节拍下求工作站数尽可能少的装配线平衡，并结合越野车实验算例，求解并验证算法有效，比较了直线型、单U型和双U型装配线平衡效果.

1 改进阶位法

1.1 阶位法简介

阶位法[12](ranked positional weight technique)是1961年由Helgeson和Birnie提出的.阶位法是求出作业元素的时间及其后续作业元素时间之和称为时间阶位(也称为时间权值)，根据求得时间权值大小分配作业，并没有考虑作业元素的后续作业量个数.

改进阶位法(modified ranked positional weight technique,MRP)综合考虑作业元素时间阶位和作业元素后续作业量阶位，得到作业元素的综合阶位，再根据综合阶位的大小排序赋值，得到作业元素的综合阶位值.每个作业元素的时间阶位是其本身的作业时间与后续所有作业元素时间之和，作业元素的作业量阶位是该作业元素及后续的作业元素个数之和.

改进阶位法是综合考虑时间权重和后续作业量权重来获得综合阶位值.作业元素后续作业量的多少影响着流水线上的作业均衡.

1.2 作业元素优先关系

在作业元素优先关系图中，元素之间的关系由优先关系集合Pset和优先关系矩阵P来表示.如果作业元素i在作业元素j之前完成，称作业元素i是作业元素j的先行作业，作业元素j是作业元素i的后继作业.可以用一个有序数对(i，j)表示，有先后关系的所有作业元素都用有序数对表示，构成优先关系集合Pset.

对于有序数对(i，j)，当作业元素i、j直接相邻时，称作业元素i是j的紧前作业，作业元素j是i的直接后继作业；当作业元素i、j不相邻时，称作业元素i是j的间接先行作业，作业元素j是i的间接后继作业.作业元素的优先关系具有传递性，即如果作业元素i、j满足有序数对(i，j)，作业元素j、q满足有序数对(j，q)，则作业元素i、q满足有序数对(i，q).

作业元素之间的优先关系也可以用优先关系矩阵来表示.对于优先关系图中有n个作业元素，该优先关系矩阵为n×n方阵P.其中优先关系矩阵P中的元素Pij(i=1,2,…,n;j=1,2,…,n)的取值取决于作业元素i和j的优先关系，即

1.3 确定作业元素的综合阶位值

依据有向图理论[13]和优先关系矩阵P求解综合阶位值[14]，求解步骤如下：

(1) 计算作业元素i的作业量阶位Rhi

Hi=count{Fi}

式中：Hi表示作业元素的后续作业元素个数;Fi为作业元素i的后续作业元素集合.

根据Hi值按升序排列所有的作业元素，对于Hi值最小的作业元素赋予后续作业量阶位Rhi=1，对于Hi值次小的作业元素赋予后续作业量阶位Rhi=2，如果作业元素Hi值相同的，则被赋予相同的后续作业量阶位Rhi.此类推，直到所有作业元素都被赋予一个特定Rhi.

(2) 计算作业元素i的时间阶位Rti

式中：Ti表示作业元素i的作业时间与全部后继作业元素时间之和,q为Fi集合里的作业元素.

按Ti值升序排列所有作业元素，对于Ti值最小的作业元素赋予时间位置阶位Rti=1，对于Ti值次小的作业元素赋予时间位置阶位Rti=2，如果作业元素Ti值相同，则被赋予相同的时间阶位Rti.依此类推，直到所有作业元素都被赋予一个特定的Rti值.

(3) 计算作业元素i的综合阶位值Ri

Ri=Rhi×Rti

2 建立装配线平衡数学模型

2.1 参数定义

定义的常量和决策变量见表1.

表1 参数定义Tab.1 Parameters definition

2.2 U型装配线平衡问题数学模型

目标函数：

式中:E为装配线平衡率.

约束条件：

(1)

(2)

(3)

(4)

(5)

Wk+1≤Wk,k=1,2,…,m0-1

(6)

(7)

(8)

装配线平衡率最大化为目标函数.约束条件(1)表示对于某一个作业元素i只能采用一种方式来分配，即按照从前到后的顺序或者按照从后往前的顺序，且只能被分配到一个工作站中；约束条件(2)表示第k个工作站中的总作业时间之和不超过生产节拍C；约束条件(3)表示如果作业元素j按照从前向后的顺序分配，那么作业元素j的紧前作业元素都要按照从前向后的顺序分配；约束条件(4)表示如果作业元素j按照从后向前的顺序分配，那么作业元素j的紧前作业元素都要按照从后向前的顺序分配；约束条件(5)表示如果某个工作站中有作业元素，那么这个工作站就要开启.

当约束条件(1)～(2)中的yik取值为0时，数学模型为直线型装配线平衡问题，约束条件(1)表示每个作业元素必须分配到唯一的工作站；约束条件(2)表示工作站k中的总作业时间之和不超过生产节拍C；约束条件(6)保证直线型装配线上顺序排列的m0个工作站中，如果第(k+1)个工作站开启，那么前面的第k个工作站必须开启；约束条件(7)表示如果第k个工作站中有作业元素，那么第k个工作站必须开启；约束条件(8)表示作业元素之间的优先关系约束.

3 改进阶位法求解模型

改进阶位法求解模型是依据作业元素的综合阶位值对U型装配线平衡.

3.1 基于改进阶位法分配作业

根据作业元素i的综合阶位值Ri，从第一个工作站开始分配，装配线上可分配的作业元素由当前设置的工作站形式决定，工作站形式有常规工作站和交叉工作站.

检查分配作业的原则是：作业未被分配；作业没有紧前(紧后)作业，或者它的所有的前任作业(后任作业)都被分配，并且作业是按照优先关系图表的前后关系所分配的；当前工作站的剩余时间足够执行该作业.

当一个作业元素被分配到工作站时，可分配作业列表就会更新一次，选择另一个新的作业并且分配给当前工作站，一直持续到当前工作站没有时间来执行其他作业元素，同时保证工作站的总时间要小于等于节拍.当从优先关系图起点开始分配作业元素时，选择综合阶位值最大的作业元素分配到工作站，当从优先关系图后部开始分配作业元素时，选择综合阶位值最小的作业元素分配到工作站，同时必须兼顾工作站被分配的作业元素时间总和小于等于节拍，或者使当前工作站的闲置时间尽可能小，满足目标函数.

U型装配线和直线型装配线的作业元素分配方式不同.对于U型装配线，将作业元素分配到工作站时，既可以按照装配线的加工方向从前到后分配或者从后到前分配，同时也可以两个方向上同时进行，这样U型装配线平衡问题的求解难度增大，但是U型和双U型装配线平衡效率有所提高.而在直线型装配线上，分配作业元素到工作站时按照单方向进行，降低了作业元素之间的组合搭配的交叉性，会导致直线型装配线生产效率降低.双U型装配线可以同时装配2件同类型的产品.

3.2 装配线平衡效果评价

装配线平衡的效果采用平衡率E和平滑系数S[15]评价.平衡率衡量整个装配过程中装配线平衡和对时间利用效率的指数.平滑系数衡量装配线负荷的均匀程度.平衡率越高说明装配线对于时间的利用程度越好，平滑系数越低说明装配线各工作站负荷越均匀，整个装配线效率和装配产品的稳定性越高.因此，装配线平衡率提取目标函数结果，平滑系数，计算如下：

式中：T(k)表示第k个工作站中作业时间总和，maxT(k)表示最大的工作站时间.

4 算例1

Bomman问题[16]的作业元素优先关系图，如图1，图中圆圈里的数字表示该作业元素的序号，作业元素圆圈上方数字表示该作业元素的作业时间.作业元素的总时间为75，装配线的生产节拍设定C=26，确定最小工作站数.

图1 Bomman问题的优先关系Fig.1 Precedence relationship of Bomman problem

4.1 综合阶位值

Bomman问题的作业元素的优先关系集合为：Pset={(1,2)，(2,3)，(2,4)，(3,5)，(4,6)，(5,7)，(6,8)，(7,8)}.优先关系集合Pset中有8对直接的优先关系，不含有间接的优先关系，其间接优先关系可以根据作业元素之间优先关系的传递性得到.优先关系矩阵P的三元组表示：A=[(1,2,1),(2,3,1),(2,4,1),(3,5,1),(4,6,1),(5,7,1),(6,8,1),(7,8,1)].

由优先关系矩阵和作业元素时间计算作业元素综合阶位值，得到Bomman问题作业元素的综合阶位值矩阵Ri=[48,35,24,12,15,6,4,1].

4.2 改进阶位法求解结果及评价

改进阶位法(MRP)依据作业元素的综合阶位值对装配线平衡问题数学模型求解，将作业元素分配到直线型装配线和U型装配线，实现装配线平衡的优化.并将结果与分支定界法(Branch and Bound,简称BB)的结果进行对比，见表2.

表2 分配结果Tab.2 Allocation results

从表2可见，简单直线型装配线布置4个工作站，线平衡率为72.12%，,平滑系数19.87和17.06.U型装配线布置3个工作站，节约了一个工作站，线平衡率为96.15%，且平滑系数为2.24和3.00，U型装配线的平衡率比直线型的平衡率高出24%，且装配线平滑系数降低了79.8%，流水线上的作业均衡效果好.基于改进阶位法规则的启发式算法的平滑系数优于分枝定界法的结果，说明U型装配线的平衡效果好于简单直线型，且各工作站负荷均匀.

5 实验算例2

在流水生产实验中，对于工序多、流程复杂装配线平衡问题研究和分析，提高其平衡效果乃至提高流水生产效率，提出运用改进阶位法求解单U和双U型装配流水线.如图2所示，选取装配实验的车模(局部)，进行结构分析和工序时间测定，得到装配流程图，如图3所示，作业元素15个，总时间是208 s，设定4个工作站，最小化节拍，以时间阶位和改进阶位法分别进行直线、单U型和双U型装配线平衡.

图2 车模(局部)结构Fig.2 Vehicle model (partial) structure

图3 车模装配流程Fig.3 Vehicle model assembly flow

5.1 车模装配线平衡结果布局

按照算例1计算过程，对算例2采用时间阶位法和改进阶位法两种方法分别平衡装配线，平衡结果绘制成装配线布局图，如图4～图6.

图4 直线型装配线平面布局Fig.4 Simple line assembly line layout

图5 单U型装配线平面布局Fig.5 Single U-shaped assembly line layout

5.2 比较平衡效果指标

计算车模的时间阶位法、改进阶位法分配方案的节拍、平衡率和平滑系数等指标，见表3.

从表3结果可见，车模简单直线型装配线平衡的时间阶位法、改进阶位法和遗传算法求解结果虽然差别不大，节拍、平衡率和平滑系数都相等，但U型装配线节拍减小了，单U型的平衡效果最好，比较双U型时间阶位和改进阶位的求解结果，改进阶位法的平滑系数好，验证了改进阶位法求解双U型装配线平衡问题的优越性.

图6 双U型装配线平面布局Fig.6 Double U-shaped assembly line layout表3 车模平衡效果指标比较Tab.3 Car model balance effect index comparison

线型算法平衡效果指标C/sE/%S直线型时间阶位5791.2212.73遗传算法5791.2312.73单U型改进阶位5594.554.899双U型时间阶位5594.569.798改进阶位5594.569.487

6 结论

结合算例，已知作业元素时间和作业元素优先关系图，建立了装配线平衡的数学模型，计算作业元素综合阶位值，应用改进阶位法对数学模型求解，得到直线型和U型(单U和双U型)装配线平衡结果，比较装配线的平衡效果，得出以下结论：

(1) 依据作业元素时间和优先关系计算各作业元素的综合阶位值，提出了改进阶位法，求解了装配线平衡问题，结果合理有效，为企业装配线平衡与优化提供有效的新方法.

(2) 改进阶位法求解的U型装配线平衡效果优于分枝定界法的结果，与直线型装配线比较，平衡率提高了24%，平滑系数降低了79.8%，提高了装配线效率和设备使用效率，使装配线负荷程度更为均匀，为流水装配线方案设计提供了有效方法.

(3) 结合实验室实际车模(局部)实验，对流水线实验设计双U型装配实验方案，改进阶位的结果与时间阶位法进行对比，改进阶位法的平滑系数降低了.对于小型结构的流水线平衡问题，改进阶位法优势并不明显，但在计算零件多结构复杂的大型产品的装配线平衡问题时，改进阶位法平衡效果明显且易于操作.