混合裝配線平衡問題的啟發(fā)式算法

楊 軍

（同濟(jì)大學(xué) 經(jīng)濟(jì)與管理學(xué)院，上海200131）

混合裝配線平衡問題的啟發(fā)式算法

楊 軍

（同濟(jì)大學(xué) 經(jīng)濟(jì)與管理學(xué)院，上海200131）

在現(xiàn)代制造業(yè)中，裝配線平衡具有重要意義，它直接影響到整個(gè)生產(chǎn)系統(tǒng)的效率.本文首先回顧了裝配線平衡問題研究的歷史，對主要方法進(jìn)行了介紹和總結(jié).其次，對實(shí)際中廣泛應(yīng)用的混合型裝配線，提出了平衡優(yōu)化數(shù)學(xué)模型，并給出了較為實(shí)用的啟發(fā)式平衡方法.最后，對需要進(jìn)一步研究的問題和未來發(fā)展趨勢作出了展望.

裝配線平衡，混合裝配線，啟發(fā)式平衡方法

0 引言

裝配線是工業(yè)領(lǐng)域廣泛存在的一種制造系統(tǒng)，是大批量生產(chǎn)的一種高效組織方式.裝配線設(shè)計(jì)與管理中一個(gè)重要內(nèi)容就是裝配線平衡，一個(gè)裝配線的平衡情況直接影響到整個(gè)生產(chǎn)系統(tǒng)的效率.顯然，應(yīng)用已有的裝配線平衡研究成果，選擇適合企業(yè)自身的裝配線平衡方法，具有十分現(xiàn)實(shí)的意義.

本文首先回顧了裝配線平衡問題研究的歷史，對主要方法進(jìn)行了介紹和總結(jié).其次，對實(shí)際中廣泛應(yīng)用的混合型裝配線，提出了平衡優(yōu)化數(shù)學(xué)模型，并給出了一個(gè)較為實(shí)用的啟發(fā)式平衡方法.最后，對需要進(jìn)一步研究的問題和未來發(fā)展趨勢作出了展望.

1 裝配線平衡問題的研究方法

裝配線平衡問題 （ALB，Assembly Line Balancing）是與流水線同時(shí)出現(xiàn)的.1954年美國的Bryton B在論文Balance of A Continouos Production Line中第一次提出了裝配線平衡的問題.他在這篇文章中提出了一個(gè)“會聚過程法”［1］，這種方法的搜尋方法較為笨拙，而且僅能夠得到局部最優(yōu)解.1956年，Jackson J R提出了一種解決A L B問題的枚舉法.這是一種對于給定的節(jié)拍，將工作站數(shù)降低到最少的方法，但是完全列舉的工作量非常大.Jackson還從數(shù)學(xué)上證明，他的方法與完全列舉法一樣，最終一定能求出最優(yōu)解，可以這樣說，Jackson方法的意義在于對各種方法提供了基本性的理論依據(jù)［2］.1961年，Helgeson W H和Birnie D P提出了ALB問題的階位算法或稱位置加權(quán)法（Ranked Positional Weight Technique）［3］.階位算法的思想是：階位高的作業(yè)元素應(yīng)安排在較前的工作站內(nèi)，唯此才能有效地使工作站數(shù)減少.每次分配一個(gè)位置權(quán)重（階位）最大的作業(yè)元素.各個(gè)作業(yè)的“位置加權(quán)”可由該作業(yè)本身及其所有后續(xù)作業(yè)時(shí)間之和來求出.階位算法的平衡結(jié)果是令人滿意的，其搜索效率高，是很受歡迎的一種平衡方法.在很多生產(chǎn)管理教材中，都介紹這種裝配線的平衡方法.Arcus A L于1966年提出一種ARCUS平衡算法又稱COMSOAL法［4］.這種方法綜合了計(jì)算機(jī)、隨機(jī)抽樣、蒙特卡羅等技術(shù).ARCUS法進(jìn)行1000次模擬，從中挑選最佳者作為裝配線平衡的結(jié)果.后來，Arcus又將其隨機(jī)抽樣法改為加權(quán)抽樣法，原來候選作業(yè)中各作業(yè)被選中的概率是相同的，現(xiàn)在視其所處位置不同，設(shè)立不同的候選概率.ARCUS算法對實(shí)際中許多復(fù)雜情況進(jìn)行了分析，是一種很有實(shí)際價(jià)值的方法，它對單一品種裝配線、混合裝配線的平衡問題都作了進(jìn)一步的研究.Thomopoulos N T修改了Kilbridge和Wester的方法，提出一種混合裝配線的平衡方法［5］，并于1970年運(yùn)用聯(lián)合優(yōu)先圖將混合裝配線轉(zhuǎn)化為單一裝配線來處理，從而可以把單一型裝配線的平衡方法運(yùn)用到混合裝配線.1988年，李建中與陳良酞等提出CPLT法［6］.該方法將成組生產(chǎn)線轉(zhuǎn)化為單一品種生產(chǎn)線形式，然后在幾種啟發(fā)式方法的基礎(chǔ)上提出了關(guān)鍵路線與最大候選時(shí)間優(yōu)先法.該方法通過實(shí)例試算，并與階位法對比，效果比較滿意.1994年Leu，Y.Y.等人運(yùn)用GA方法求解單一確定型 ALB問題［7］.2001年，Brian J Carnahan在裝配線平衡中考慮操作者的生理需要因素，這是第一篇結(jié)合人機(jī)工程、工效學(xué)與裝配線平衡的文獻(xiàn)［8］，文獻(xiàn)設(shè)計(jì)了三種啟發(fā)式方法求解多因素（疲勞因素、時(shí)間因素）裝配線平衡問題.

研究人員己經(jīng)提出了許多種解決裝配線平衡問題的方法.根據(jù)這些算法的特點(diǎn)，我們可以做以下分類：

（1）經(jīng)典算法，包括線性規(guī)劃、動態(tài)規(guī)劃、整數(shù)規(guī)劃和分支定界等運(yùn)籌學(xué)中的傳統(tǒng)算法；

（2）構(gòu)造型算法，一般用來得到初始可行解；

（3）領(lǐng)域搜索算法，包括爬山法、最陡下降法，模擬退火算法（SA）、遺傳算法（GA）、禁忌搜索（TS）、蟻群算法（ACO）等；

（4）基于系統(tǒng)動態(tài)演化的算法，如人工神經(jīng)網(wǎng)絡(luò)、混沌搜索等；

（5）混合型算法，上述各算法相混合而產(chǎn)生的各種算法.

傳統(tǒng)的最優(yōu)化方法有較大的局限性.它往往要求目標(biāo)函數(shù)是凸的，高階連續(xù)是可微的，可行域是凸集，而且其處理非確定性信息的能力很差.這些弱點(diǎn)使傳統(tǒng)優(yōu)化方法在復(fù)雜系統(tǒng)中的應(yīng)用受到了限制.近年來，智能優(yōu)化方法發(fā)展迅速，它具有全局的、并行高效的優(yōu)化性能，魯棒性、通用性強(qiáng)等優(yōu)點(diǎn)，這些方法包括模擬退火算法、遺傳算法、禁忌搜索算法、蟻群算法、人工神經(jīng)網(wǎng)絡(luò)等.智能優(yōu)化對求解問題不一定苛求最優(yōu)解，強(qiáng)調(diào)“滿意解”作為評價(jià)準(zhǔn)則，為許多工程和管理方面的問題提供了有效解決方法，具有強(qiáng)勁的發(fā)展前景和重要的研究價(jià)值.

2 混合裝配線平衡的數(shù)學(xué)模型與算法

2.1 數(shù)學(xué)模型

當(dāng)今制造業(yè)的生產(chǎn)方式，已從大批量生產(chǎn)方式向準(zhǔn)時(shí)制及精益生產(chǎn)方式，并進(jìn)一步向及敏捷制造方式迅速演變，即由少品種、大批量單一品種流水線生產(chǎn)模式向多品種、小批量混合裝配線生產(chǎn)模式轉(zhuǎn)變.混合裝配線（Mixed Model Assembly Line，MMAL）可以在一定時(shí)間內(nèi)，在一條生產(chǎn)線上生產(chǎn)出多種型號的產(chǎn)品，產(chǎn)品的品種可以隨顧客需求而變化.多品種混合生產(chǎn)裝配線的出現(xiàn)使得裝配線的柔性增加了，而生產(chǎn)線的柔性以及需求的變化又增加了生產(chǎn)的復(fù)雜性和不確定性.目前，混合裝配線在工業(yè)生產(chǎn)中得到越來越廣泛的應(yīng)用，而其中要解決的關(guān)鍵問題之一就是如何實(shí)現(xiàn)該裝配線的平衡.

在混合裝配線平衡問題中，研究最多的三類問題：

（2）給定裝配線的最小工作站數(shù)，使裝配線的節(jié)拍最小.已知工作站數(shù)m，確定作業(yè)元素集E＝｛1，2，…，n｝的一個(gè)劃分｛Sk｜k＝1，2，…，m｝，使目標(biāo)函數(shù)

該問題等價(jià)于已知m求最小化生產(chǎn)線節(jié)拍時(shí)間.

（3）在裝配線工作站數(shù)和節(jié)拍得到優(yōu)化的條件下，使平衡裝配線上工作站的負(fù)荷最小.在現(xiàn)實(shí)的裝配系統(tǒng)設(shè)計(jì)和運(yùn)行階段，人們比較關(guān)注生產(chǎn)過程的連續(xù)性和均衡性.在裝配線平衡問題的模型中，我們可以使用平滑性指數(shù)可以反映工位時(shí)間分布的離散程度：

其中，CT為生產(chǎn)節(jié)拍，m為工作站個(gè)數(shù)，Ti為各個(gè)工作站的負(fù)荷時(shí)間（i＝1，2，…，m），SI是工位作業(yè)時(shí)間分布的離散狀況的衡量指標(biāo)，其值越小，則工位的作業(yè)時(shí)間分布偏差越小.平衡的效果應(yīng)向著盡量減小偏差值的方向努力.

2.2 算法

裝配線平衡問題屬于NP－h(huán)ard問題，問題復(fù)雜度隨任務(wù)數(shù)的增加而呈幾何級數(shù)增長.根據(jù)經(jīng)驗(yàn)，在實(shí)際中，企業(yè)較常采用啟發(fā)式平衡方法.該方法比較簡單實(shí)用，切實(shí)可行.生產(chǎn)線平衡的啟發(fā)式算法中，常用的有階位法，又稱為位置加權(quán)法，這種方法是首先求出每個(gè)作業(yè)要素的階位.所謂階位是作業(yè)要素時(shí)間與其所有后續(xù)作業(yè)要素時(shí)間的總計(jì).然后，根據(jù)階位的高低進(jìn)行作業(yè)安排，優(yōu)先安排階位高的作業(yè)要素，從而盡量減少工作站數(shù).對于混合型裝配線的平衡，可以運(yùn)用聯(lián)合優(yōu)先圖的方法轉(zhuǎn)換為單一型裝配線來處理，從而可以把單一型裝配線的方法運(yùn)用到混合型裝配線.階位法的平衡步驟如下：

Step 1.先分配后續(xù)作業(yè)最多的作業(yè)；

Step 2.先分配位置權(quán)數(shù)最大的作業(yè)，位置權(quán)數(shù)等于該作業(yè)及其所有后續(xù)作業(yè)的時(shí)間總和.程序如下：

（1）確定節(jié)拍，求出最小所需工作站數(shù)；

（2）從工作站1開始，按順序給工作站分配作業(yè).作業(yè)的分配按作業(yè)先后順序圖由左至右進(jìn)行；

（3）在每一分配前，利用下列標(biāo)準(zhǔn)確定哪些作業(yè)夠資格分配給下一工作站：

A.所有先行作業(yè)都已經(jīng)被分配；

B.該作業(yè)時(shí)間不超過該工作站允許的剩余時(shí)間；

如果沒有夠資格分配的作業(yè)，繼續(xù)下一工作站分配；

（4）每當(dāng)一個(gè)工作分配后，計(jì)算出該工作站的剩余時(shí)間，剩余時(shí)間等于節(jié)拍減去工作站已分配總的作業(yè)時(shí)間；

（5）如果出現(xiàn)兩個(gè)作業(yè)都一樣的情況，可采用下列方法之一解決：

A.分配加工時(shí)間最長的作業(yè)；

B.分配后續(xù)作業(yè)最多的作業(yè)；

（6）繼續(xù)下去直到所有工作都已經(jīng)被分配；

（7）計(jì)算相關(guān)指標(biāo)，生產(chǎn)線平衡率＝各工序時(shí)間和／（人數(shù)＊CT）＊100%.

啟發(fā)式平衡方法可用圖1所示.

3 結(jié)論和展望

經(jīng)過半個(gè)多世紀(jì)的發(fā)展，裝配線平衡問題的研究經(jīng)歷了最優(yōu)化算法、啟發(fā)式算法、智能化方法和工業(yè)工程方法的發(fā)展過程.20世紀(jì)50年代到70年代主要是裝配線平衡的最優(yōu)化方法應(yīng)用時(shí)期.盡管最優(yōu)化方法能找到最優(yōu)解，但是在實(shí)際應(yīng)用中往往十分煩瑣，這時(shí)人們開始轉(zhuǎn)向研究啟發(fā)式方法.從20世紀(jì)80年代開始，人們開始研究啟發(fā)式方法.啟發(fā)式方法以其簡便、易懂贏得了管理人員的歡迎，并被廣泛應(yīng)用于許多領(lǐng)域.啟發(fā)式方法的主要局限是它的靜態(tài)性，在平衡過程中使用固定的準(zhǔn)則，而產(chǎn)品加工過程、市場需求是動態(tài)變化的.人工智能時(shí)代從20世紀(jì)80年代后半期開始，神經(jīng)網(wǎng)絡(luò)、專家系統(tǒng)、遺傳算法等人工智能方法成為在有效時(shí)間內(nèi)尋求滿意解的可行算法.基于人工智能的搜索算法具有全局的、并行高效的優(yōu)化性能，魯棒性、通用性強(qiáng)等優(yōu)點(diǎn)，具有很好的發(fā)展前景和研究價(jià)值.應(yīng)用工業(yè)工程的理論和方法為指導(dǎo)，系統(tǒng)化的研究生產(chǎn)線平衡問題是解決此類問題的趨勢和發(fā)展方向.工業(yè)工程方法一般運(yùn)用工作研究和作業(yè)測定方法進(jìn)行平衡，但對于作業(yè)元素較多的問題有一定的局限性.

圖1

本文對裝配線平衡主要方法做了簡要的介紹，指出了各種方法的優(yōu)缺點(diǎn)和未來的發(fā)展方向，并從企業(yè)的實(shí)際應(yīng)用出發(fā)，給出了一種較為簡潔實(shí)用的啟發(fā)式方法.利用計(jì)算機(jī)對裝配線平衡進(jìn)行仿真，建立可視化的虛擬仿真動態(tài)系統(tǒng)將成為一個(gè)未來發(fā)展方向.現(xiàn)在已經(jīng)有許多專業(yè)的仿真軟件如Flexism，eM－plant等可以實(shí)現(xiàn)裝配線平衡的仿真過程.裝配線平衡和設(shè)施布局，生產(chǎn)計(jì)劃排產(chǎn)問題也密切相關(guān)，如何把這些問題綜合起來研究，作出多目標(biāo)一體化的全局最優(yōu)決策，有待于進(jìn)一步的研究.隨著工業(yè)工程在我國的逐漸應(yīng)用和發(fā)展，利用工業(yè)工程的方法結(jié)合智能化方法解決裝配線平衡問題也越來越引起學(xué)者和企業(yè)的重視.

［1］賈大龍，韓玉啟等.應(yīng)用工業(yè)工程［M］.北京：北京兵器工業(yè)出版社，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－），男，工程碩士，研究領(lǐng)域：工業(yè)工程。

2010－08－22