混合装配线平衡问题的启发式算法

杨 军

（同济大学 经济与管理学院，上海200131）

混合装配线平衡问题的启发式算法

杨 军

（同济大学 经济与管理学院，上海200131）

在现代制造业中，装配线平衡具有重要意义，它直接影响到整个生产系统的效率.本文首先回顾了装配线平衡问题研究的历史，对主要方法进行了介绍和总结.其次，对实际中广泛应用的混合型装配线，提出了平衡优化数学模型，并给出了较为实用的启发式平衡方法.最后，对需要进一步研究的问题和未来发展趋势作出了展望.

装配线平衡，混合装配线，启发式平衡方法

0 引言

装配线是工业领域广泛存在的一种制造系统，是大批量生产的一种高效组织方式.装配线设计与管理中一个重要内容就是装配线平衡，一个装配线的平衡情况直接影响到整个生产系统的效率.显然，应用已有的装配线平衡研究成果，选择适合企业自身的装配线平衡方法，具有十分现实的意义.

本文首先回顾了装配线平衡问题研究的历史，对主要方法进行了介绍和总结.其次，对实际中广泛应用的混合型装配线，提出了平衡优化数学模型，并给出了一个较为实用的启发式平衡方法.最后，对需要进一步研究的问题和未来发展趋势作出了展望.

1 装配线平衡问题的研究方法

装配线平衡问题 （ALB，Assembly Line Balancing）是与流水线同时出现的.1954年美国的Bryton B在论文Balance of A Continouos Production Line中第一次提出了装配线平衡的问题.他在这篇文章中提出了一个“会聚过程法”［1］，这种方法的搜寻方法较为笨拙，而且仅能够得到局部最优解.1956年，Jackson J R提出了一种解决A L B问题的枚举法.这是一种对于给定的节拍，将工作站数降低到最少的方法，但是完全列举的工作量非常大.Jackson还从数学上证明，他的方法与完全列举法一样，最终一定能求出最优解，可以这样说，Jackson方法的意义在于对各种方法提供了基本性的理论依据［2］.1961年，Helgeson W H和Birnie D P提出了ALB问题的阶位算法或称位置加权法（Ranked Positional Weight Technique）［3］.阶位算法的思想是：阶位高的作业元素应安排在较前的工作站内，唯此才能有效地使工作站数减少.每次分配一个位置权重（阶位）最大的作业元素.各个作业的“位置加权”可由该作业本身及其所有后续作业时间之和来求出.阶位算法的平衡结果是令人满意的，其搜索效率高，是很受欢迎的一种平衡方法.在很多生产管理教材中，都介绍这种装配线的平衡方法.Arcus A L于1966年提出一种ARCUS平衡算法又称COMSOAL法［4］.这种方法综合了计算机、随机抽样、蒙特卡罗等技术.ARCUS法进行1000次模拟，从中挑选最佳者作为装配线平衡的结果.后来，Arcus又将其随机抽样法改为加权抽样法，原来候选作业中各作业被选中的概率是相同的，现在视其所处位置不同，设立不同的候选概率.ARCUS算法对实际中许多复杂情况进行了分析，是一种很有实际价值的方法，它对单一品种装配线、混合装配线的平衡问题都作了进一步的研究.Thomopoulos N T修改了Kilbridge和Wester的方法，提出一种混合装配线的平衡方法［5］，并于1970年运用联合优先图将混合装配线转化为单一装配线来处理，从而可以把单一型装配线的平衡方法运用到混合装配线.1988年，李建中与陈良酞等提出CPLT法［6］.该方法将成组生产线转化为单一品种生产线形式，然后在几种启发式方法的基础上提出了关键路线与最大候选时间优先法.该方法通过实例试算，并与阶位法对比，效果比较满意.1994年Leu，Y.Y.等人运用GA方法求解单一确定型 ALB问题［7］.2001年，Brian J Carnahan在装配线平衡中考虑操作者的生理需要因素，这是第一篇结合人机工程、工效学与装配线平衡的文献［8］，文献设计了三种启发式方法求解多因素（疲劳因素、时间因素）装配线平衡问题.

研究人员己经提出了许多种解决装配线平衡问题的方法.根据这些算法的特点，我们可以做以下分类：

（1）经典算法，包括线性规划、动态规划、整数规划和分支定界等运筹学中的传统算法；

（2）构造型算法，一般用来得到初始可行解；

（3）领域搜索算法，包括爬山法、最陡下降法，模拟退火算法（SA）、遗传算法（GA）、禁忌搜索（TS）、蚁群算法（ACO）等；

（4）基于系统动态演化的算法，如人工神经网络、混沌搜索等；

（5）混合型算法，上述各算法相混合而产生的各种算法.

传统的最优化方法有较大的局限性.它往往要求目标函数是凸的，高阶连续是可微的，可行域是凸集，而且其处理非确定性信息的能力很差.这些弱点使传统优化方法在复杂系统中的应用受到了限制.近年来，智能优化方法发展迅速，它具有全局的、并行高效的优化性能，鲁棒性、通用性强等优点，这些方法包括模拟退火算法、遗传算法、禁忌搜索算法、蚁群算法、人工神经网络等.智能优化对求解问题不一定苛求最优解，强调“满意解”作为评价准则，为许多工程和管理方面的问题提供了有效解决方法，具有强劲的发展前景和重要的研究价值.

2 混合装配线平衡的数学模型与算法

2.1 数学模型

当今制造业的生产方式，已从大批量生产方式向准时制及精益生产方式，并进一步向及敏捷制造方式迅速演变，即由少品种、大批量单一品种流水线生产模式向多品种、小批量混合装配线生产模式转变.混合装配线（Mixed Model Assembly Line，MMAL）可以在一定时间内，在一条生产线上生产出多种型号的产品，产品的品种可以随顾客需求而变化.多品种混合生产装配线的出现使得装配线的柔性增加了，而生产线的柔性以及需求的变化又增加了生产的复杂性和不确定性.目前，混合装配线在工业生产中得到越来越广泛的应用，而其中要解决的关键问题之一就是如何实现该装配线的平衡.

在混合装配线平衡问题中，研究最多的三类问题：

（2）给定装配线的最小工作站数，使装配线的节拍最小.已知工作站数m，确定作业元素集E＝｛1，2，…，n｝的一个划分｛Sk｜k＝1，2，…，m｝，使目标函数

该问题等价于已知m求最小化生产线节拍时间.

（3）在装配线工作站数和节拍得到优化的条件下，使平衡装配线上工作站的负荷最小.在现实的装配系统设计和运行阶段，人们比较关注生产过程的连续性和均衡性.在装配线平衡问题的模型中，我们可以使用平滑性指数可以反映工位时间分布的离散程度：

其中，CT为生产节拍，m为工作站个数，Ti为各个工作站的负荷时间（i＝1，2，…，m），SI是工位作业时间分布的离散状况的衡量指标，其值越小，则工位的作业时间分布偏差越小.平衡的效果应向着尽量减小偏差值的方向努力.

2.2 算法

装配线平衡问题属于NP－hard问题，问题复杂度随任务数的增加而呈几何级数增长.根据经验，在实际中，企业较常采用启发式平衡方法.该方法比较简单实用，切实可行.生产线平衡的启发式算法中，常用的有阶位法，又称为位置加权法，这种方法是首先求出每个作业要素的阶位.所谓阶位是作业要素时间与其所有后续作业要素时间的总计.然后，根据阶位的高低进行作业安排，优先安排阶位高的作业要素，从而尽量减少工作站数.对于混合型装配线的平衡，可以运用联合优先图的方法转换为单一型装配线来处理，从而可以把单一型装配线的方法运用到混合型装配线.阶位法的平衡步骤如下：

Step 1.先分配后续作业最多的作业；

Step 2.先分配位置权数最大的作业，位置权数等于该作业及其所有后续作业的时间总和.程序如下：

（1）确定节拍，求出最小所需工作站数；

（2）从工作站1开始，按顺序给工作站分配作业.作业的分配按作业先后顺序图由左至右进行；

（3）在每一分配前，利用下列标准确定哪些作业够资格分配给下一工作站：

A.所有先行作业都已经被分配；

B.该作业时间不超过该工作站允许的剩余时间；

如果没有够资格分配的作业，继续下一工作站分配；

（4）每当一个工作分配后，计算出该工作站的剩余时间，剩余时间等于节拍减去工作站已分配总的作业时间；

（5）如果出现两个作业都一样的情况，可采用下列方法之一解决：

A.分配加工时间最长的作业；

B.分配后续作业最多的作业；

（6）继续下去直到所有工作都已经被分配；

（7）计算相关指标，生产线平衡率＝各工序时间和／（人数＊CT）＊100%.

启发式平衡方法可用图1所示.

3 结论和展望

经过半个多世纪的发展，装配线平衡问题的研究经历了最优化算法、启发式算法、智能化方法和工业工程方法的发展过程.20世纪50年代到70年代主要是装配线平衡的最优化方法应用时期.尽管最优化方法能找到最优解，但是在实际应用中往往十分烦琐，这时人们开始转向研究启发式方法.从20世纪80年代开始，人们开始研究启发式方法.启发式方法以其简便、易懂赢得了管理人员的欢迎，并被广泛应用于许多领域.启发式方法的主要局限是它的静态性，在平衡过程中使用固定的准则，而产品加工过程、市场需求是动态变化的.人工智能时代从20世纪80年代后半期开始，神经网络、专家系统、遗传算法等人工智能方法成为在有效时间内寻求满意解的可行算法.基于人工智能的搜索算法具有全局的、并行高效的优化性能，鲁棒性、通用性强等优点，具有很好的发展前景和研究价值.应用工业工程的理论和方法为指导，系统化的研究生产线平衡问题是解决此类问题的趋势和发展方向.工业工程方法一般运用工作研究和作业测定方法进行平衡，但对于作业元素较多的问题有一定的局限性.

图1

本文对装配线平衡主要方法做了简要的介绍，指出了各种方法的优缺点和未来的发展方向，并从企业的实际应用出发，给出了一种较为简洁实用的启发式方法.利用计算机对装配线平衡进行仿真，建立可视化的虚拟仿真动态系统将成为一个未来发展方向.现在已经有许多专业的仿真软件如Flexism，eM－plant等可以实现装配线平衡的仿真过程.装配线平衡和设施布局，生产计划排产问题也密切相关，如何把这些问题综合起来研究，作出多目标一体化的全局最优决策，有待于进一步的研究.随着工业工程在我国的逐渐应用和发展，利用工业工程的方法结合智能化方法解决装配线平衡问题也越来越引起学者和企业的重视.

［1］贾大龙，韩玉启等.应用工业工程［M］.北京：北京兵器工业出版社，1993：76－118.

［2］Jackson J R.A computing procedure for a line balancing problem ［J］.Management Science，1956，2（3）：261－270.

［3］Helgeson WH，Birnie DP.Assembly line balancing using the ranked positional weight technique［J］.The Journal of Industrial Engineering，1961，12（6）：394－398.

［4］Arcus A L.COMSOAL－A Computer Method of Sequencing Operations for Assembly Line［J］.International Journal for Production Research，1966，（4）：259－277.

［5］Thomopoulos N T.Line balancing－sequencing for mixed model assembly［J］.Management Science，1967，（14）：859－875.

［6］Leu Y Y，Matheson L A，Rees L P.Assembly line balancing using genetic algorithms with heuristic－generated initial populations and multiple evaluation criteria［J］.Decision Sciences，1994，（25）：581－606.

［7］Brian J C，Bryan A N，Mark S R.Incorporating Physical Demand Criteria into assembly line balancing［J］.IEE Transaction，2001，（33）：875－887.

On Heuristic Algorithm for Assembly Line Balancing

Yang Jun
（School of Economics and Management，Tongji University，Shanghai 200092，China）

In modern manufacturing industry，assembly line balancing is playing a very important role，which can exert direct influences on the efficiency of the whole production system.This paper firstly reviews the history of reserach on assembly line balancing and introduces and summarizes the main research methods.Then for the mixed model assembly line most extensively used in manufacturing industry，we provide a balancing optimal mathematical model and a practicable heuristic balancing method and finally put forward some suggestions for the future further reaserch and the development tendency.

assembly line balancing；mixed model assembly line；heuristic balancing method.

TP301

：A

：1673－1794（2010）05－0013－04

杨 军（1975－），男，工程硕士，研究领域：工业工程。

2010－08－22