查 靚，田 行

(三峽大學 機械與材料學院，湖北 宜昌 443002)

0 引言

混合流水線是指在不降低流水線效率的前提下，在一條流水線上實現(xiàn)具有相似特征的多個產(chǎn)品或者是一個產(chǎn)品系列的不同品種的混合生產(chǎn)，與單一產(chǎn)品流水線相比，能夠在保持較低庫存水平的情況下更加柔性的應對顧客個性化和多樣化的需求?；旌狭魉€平衡是混合流水線優(yōu)化設計的重要問題之一。這是因為混合流水線平衡有利于:(1)消除生產(chǎn)瓶頸，減少架線成本，提高生產(chǎn)效率。(2)提升員工士氣，穩(wěn)定產(chǎn)品質量。(3)加快物流周轉，縮短生產(chǎn)周期，減少或消除物料及半成品周轉場所。

混合產(chǎn)品流水線平衡遠比單一產(chǎn)品流水線平衡復雜，現(xiàn)有研究多采用遺傳算法、蟻群算法、粒子群算法等智能算法進行求解。張則強等［1］提出了一種帶信息素總合規(guī)則和混合搜索機制的蟻群算法進行求解。徐煒達和肖田元［2］研究了帶有跨工位操作，且作業(yè)完成時間為隨機量的混合裝配線平衡問題，結合隨機模擬和遺傳算法設計了混合遺傳算法進行求解。Reakook Huang 和Hiroshi Katayama［3］設計了兩階段遺傳算法求解多目標U 型混合流水線平衡問題。凌文曙［4］利用遺傳算法解決了某車橋混合裝配線平衡問題。但是，智能算法計算復雜，耗時較長，基于規(guī)則的啟發(fā)式算法計算簡單快捷［5］，容易為生產(chǎn)實踐者理解和掌握，在單一產(chǎn)品流水線平衡實際應用較多，但對混合流水線平衡優(yōu)化精度不高，特別是對不同產(chǎn)品在每個工作站的作業(yè)時間均衡效果不佳。因此，本文提出一種將啟發(fā)式算法和仿真分析相結合的方法，首先將多產(chǎn)品的作業(yè)優(yōu)先次序圖轉化為單一產(chǎn)品綜合作業(yè)優(yōu)先次序圖，然后利用基于規(guī)則的啟發(fā)式算法求得初始平衡方案，接著根據(jù)混合流水線運行特點建立仿真模型，通過仿真分析，辨識存在的問題并進行改進，從而得到最終優(yōu)化平衡方案。

1 混合流水線平衡問題的描述

根據(jù)流水線上加工產(chǎn)品品種的多少，流水線平衡問題可分為單一產(chǎn)品、多產(chǎn)品和混合產(chǎn)品流水線平衡問題。其中，單一產(chǎn)品流水線上只生產(chǎn)一種產(chǎn)品，多產(chǎn)品流水線上以一定的批量輪番進行多種產(chǎn)品的生產(chǎn)，例如生產(chǎn)100 個產(chǎn)品A 后再生產(chǎn)100 個產(chǎn)品B，混合品種流水線上是以一個最小比例集輪番進行多種產(chǎn)品的混合生產(chǎn)，例如以(A，B)為最小比例集重復生產(chǎn)100 次。

混合流水線平衡問題是指:給定加工多個產(chǎn)品的作業(yè)優(yōu)先次序圖，包括作業(yè)集合、作業(yè)加工時間以及作業(yè)間的優(yōu)先次序關系等信息，將作業(yè)組合分配到工作站，要求每個作業(yè)都被分派且只能被分派到一個工作站，每個工作站的作業(yè)時間不大于節(jié)拍，滿足作業(yè)間的優(yōu)先次序要求，并使得某些指標達到優(yōu)化。

2 混合流水線平衡問題向單一產(chǎn)品流水線平衡問題轉化

混合流水線由于需要完成多個產(chǎn)品的加工，因此對應了多個產(chǎn)品的作業(yè)優(yōu)先次序圖，為了能利用單一產(chǎn)品流水線平衡方法來求解，第一步應該是如何將多個作業(yè)優(yōu)先次序轉化為一個作業(yè)優(yōu)先次序圖。

令第p 個產(chǎn)品的作業(yè)優(yōu)先次序圖用有向圖Gp =(Tp，Pp，tp)表示。則PN 種產(chǎn)品的綜合作業(yè)優(yōu)先次序圖為)G = ()T，)P，)t)。其中:

= {(i，j)| )Ti必須在)Tj完工后才能開始}

由于Tp?)T，因此定義δpi表示Tp中是否包括作業(yè)i(i ∈)T)，如果包括δpi= 1，否則δpi= 0。計劃期內(nèi)第p 個產(chǎn)品的需求數(shù)量為dp，總產(chǎn)品數(shù)為)d，則計算出每個作業(yè)元素的加權平均作業(yè)時間為:

3 啟發(fā)式算法

在一個有向網(wǎng)絡圖中，從起點開始，按照作業(yè)順序，連續(xù)不斷地到達終點的一條通路稱為一條網(wǎng)絡路線。其中，完成每一作業(yè)需要時間最長的路線稱為關鍵路線，關鍵路徑上的作業(yè)的松弛時間為0，松弛時間= 作業(yè)最遲開始時間－作業(yè)最早開始時間－作業(yè)時間。正因為關鍵路徑?jīng)Q定了完成所有作業(yè)需要的最長作業(yè)時間，因此盡可能早的開始執(zhí)行關鍵路徑上的作業(yè)越有利于減少所需要的總工作站數(shù)。關鍵路徑可以利用運籌學中的網(wǎng)絡前向分析和后向分析，然后根據(jù)松弛時間為0 計算得到［6］。

雙向啟發(fā)式算法的特點是［7］，同時從第一個工作站和最后一個工作站開始，從前向后和從后向前同時試分配可行的候選作業(yè)到前向工作站和后向工作站，在分配過程中優(yōu)先分配關鍵路徑上的作業(yè)，如果試分配的前向工作站的空閑時間小于試分配的后向工作站的空閑時間，說明前向工作站的試分配方案優(yōu)于后向的，接受前向工作站試分配方案，放棄后向的，否則接受后向工作站試分配方案，放棄前向的。接著進行下一工作站的試分配，直到所有作業(yè)均被分配到工作站。

計算步驟如下:

第一步:計算關鍵路徑作業(yè)集合Scp，非關鍵路徑作業(yè)集合Scp= S－Scp。

第二步:初始化。所有作業(yè)均未分配到工作站Su= S，Sa= φ，同時從第一個工作站和最后一個工作站開始分配作業(yè)，因此令首工作站為當前前向工作站，末工作站為當前后向工作站，即i = 1，j = 1。

第三步:創(chuàng)建兩個臨時前向工作站和后向工作站作業(yè)集合，初始為空，F(xiàn)Si= BSj= φ。

第四步:試分配。篩選可行的候選作業(yè)集合，即未分配的，且不存在未分配的前序作業(yè)可分配到當前前向工作站i，如果候選作業(yè)集合中存在關鍵路徑上的作業(yè)，首先分配到臨時前向工作站FSi，然后按照最長作業(yè)時間等規(guī)則依序分配候選作業(yè)集合里的作業(yè)直到FSi的總作業(yè)時間超過節(jié)拍C 為止。同理，如果存在未分配的且不存在未分配的后序作業(yè)可分配到當前后向工作站j，如果候選作業(yè)集合中存在關鍵路徑上的作業(yè)，首先分配到臨時后向工作站BSj，然后按照最長作業(yè)時間等規(guī)則依序分配候選作業(yè)集合里的作業(yè)直到BSj的總作業(yè)時間超過節(jié)拍C 為止。

第五步:確定分配方案。對于臨時工作站集合FSi和BSj，如果FSi的空閑時間小于BSj的空閑時間，即Wf ≤Wb，說明當前前向工作站i 的臨時分配方案優(yōu)于后向工作站j 的，因此接受FSi的分配方案成為固定分配方案，放棄BSj，即i = i +1，Sa= Sa∪FSi，Sa= Su－FSi，F(xiàn)Si= BSj= φ。如果Wf ＞W(wǎng)b，說明后向工作站j 的臨時分配方案優(yōu)于前向工作站i 的，接受BSj的分配方案成為固定分配方案，放棄FSi，即j = j +1，Sa= Sa∪BSj，Sa= Su－BSj，F(xiàn)Si= BSj= φ。

第六步:如果Su= φ 說明所有作業(yè)都已分配到工作站，程序結束，輸出分配方案，否則，返回第四步繼續(xù)執(zhí)行。

算法流程圖如圖1 所示。

圖1 啟發(fā)式算法的計算流程圖

4 評價指標

4.1 單一產(chǎn)品流水線平衡指標

單一產(chǎn)品流水線平衡效果常采用生產(chǎn)線平衡效率p 作為評價指標，如下式:

其中m 代表工作站數(shù)，Ti代表工作站i 的平均作業(yè)時間，C 為節(jié)拍。p 值越大說明平衡性越好，生產(chǎn)效率越高。對于p 值，文獻［8］給出了推薦的評定標準，如表1 所示。

表1 單一產(chǎn)品流水線平衡性評價標準

4.2 混合流水線平衡指標

由于混合流水線上加工的是多個產(chǎn)品，在一個周期的不同階段每個工作站實際加工的產(chǎn)品會發(fā)生變化，每個工作站的實際作業(yè)時間也隨之發(fā)生變化，盡管按照啟發(fā)式方法得到的初始方法平衡效率p 值高，但不同階段的工作站實際作業(yè)時間仍存在不平衡現(xiàn)象，甚至出現(xiàn)超過節(jié)拍的現(xiàn)象。

通常采用兩種方法解決:一是調(diào)整生產(chǎn)節(jié)拍C，使流水線節(jié)拍大于或等于最長工作站作業(yè)時間，這種方式降低了生產(chǎn)速度，無法滿足客戶需求;二是保持節(jié)拍C 不變，采取補救措施(如設置線外工作站修補)完成，采取這種方式時，每個工作站作業(yè)時間超過節(jié)拍的程度也稱超負荷量對生產(chǎn)效率影響大，總的超負荷量越大，線外補救的工作就越多，需要的趕工成本越大。此外，工作站負荷不均衡，有的工作站作業(yè)時間很長，有的工作站作業(yè)時間很短，也會對產(chǎn)品質量和員工士氣產(chǎn)生很大影響。

因此，最長作業(yè)時間、總的超負荷量以及負荷均衡指數(shù)對于混合流水線的最優(yōu)化設計至關重要，本文選擇這三個指標作為混合流水線平衡效果的評價指標。

總的超負荷量的計算如式(2)所示。

如果a ≥0 則pos(a)= a;否則pos(a)= 0。

負荷均衡指數(shù)的計算如式(3)所示。

利用平均作業(yè)時間和啟發(fā)式算法得到的初始平衡方案無法保證這三個指標的最優(yōu)性，因此需要根據(jù)混合流水線特點建立仿真模型，進而提出改善方案。

下面通過一個案例來說明和驗證本文所提方法的有效性。

5 案例應用

5.1 案例背景介紹

某客車空調(diào)生產(chǎn)企業(yè)原先客戶少，生產(chǎn)品種數(shù)少，隨著技術能力的增強，為擴大利潤，開發(fā)了一些新的客戶，針對客戶需求研發(fā)了幾個系列的新產(chǎn)品，這些新產(chǎn)品利潤高，品種多，但單一品種客戶需求數(shù)量少，為了節(jié)省架線成本和運行成本，受精益生產(chǎn)思想的影響，公司擬針對系列產(chǎn)品采用混合裝配流水線進行生產(chǎn)，因此需要設計一條新的混合流水線。

選定A(內(nèi)置式)、B(全頂置式)、C(半頂置式)三種產(chǎn)品，根據(jù)市場調(diào)研與預測，每個月三種產(chǎn)品的需求分別為200、200 和400 臺，該企業(yè)每周工作6 天(一個月26 個工作日)，每日工作8 小時，需求節(jié)拍CT 為:

根據(jù)需求節(jié)拍CT 的值，考慮一定的寬放系數(shù)混合流水線的生產(chǎn)節(jié)拍設計為15 分鐘。

5.2 綜合作業(yè)優(yōu)先次序圖

三種產(chǎn)品的作業(yè)優(yōu)先次序圖如圖2、3、4 所示。其中，作業(yè)間的優(yōu)先次序是根據(jù)產(chǎn)品裝配工藝的要求繪制的，每個作業(yè)的作業(yè)時間是根據(jù)模特法，并考慮一定的評比系數(shù)和寬放系數(shù)后預訂的標準作業(yè)時間。

圖2 產(chǎn)品A 的作業(yè)優(yōu)先次序圖

圖3 產(chǎn)品B 的作業(yè)優(yōu)先次序圖

圖4 產(chǎn)品C 的作業(yè)優(yōu)先次序圖

根據(jù)每個月三種產(chǎn)品的需求得到綜合產(chǎn)品作業(yè)優(yōu)先次序圖如圖5 所示。

圖5 綜合作業(yè)優(yōu)先次序圖

5.3 求解單一產(chǎn)品流水線平衡問題

按照基于關鍵路徑的雙向啟發(fā)式算法，首先計算關鍵路徑作業(yè)集合為Scp= {1，3，6，7，8，10，12，14，15}，然后按照圖1 所示的流程將作業(yè)分配到工作站的分配過程如下表2 所示。得到的作業(yè)分配方案如表3 所示。平衡有效性指標

根據(jù)表1 的評價標準，p ≥90% 可以認定該單一產(chǎn)品流水線平衡方案是優(yōu)的。

表3 初始作業(yè)分配方案

5.4 仿真分析

一個月內(nèi)三種產(chǎn)品的需求為200、200 和400，需求比例為1:1:2，為了確保零件消耗的均衡性，采用比例倒數(shù)法確定在一個循環(huán)內(nèi)三種產(chǎn)品投放的順序為CBAC，據(jù)此建立仿真模型。仿真結果表明，在一個周期的四個階段內(nèi)五個工作站中出現(xiàn)的產(chǎn)品及工作站作業(yè)時間如表4 所示，工作站實際負荷如圖6 所示。

表4 改善前一個周期內(nèi)工作站加工產(chǎn)品及作業(yè)時間

圖6 改善前工作站負荷

最長工作站作業(yè)時間為20，遠超過節(jié)拍15 的要求。工作站1 在第3 階段，工作站4 在第3、4 階段，工作站5 在第2、3 階段，作業(yè)時間較長，成為瓶頸工作站，超出節(jié)拍，而工作站4 在第一階段的作業(yè)時間只有7，工作站5 在第4 階段的作業(yè)時間只有8，遠小于節(jié)拍，存在空閑時間。總的超負荷量為4000，負荷均衡指數(shù)為0.95。

由此可以看出，雖然初始方案針對以加權平均作業(yè)時間為參數(shù)的單一產(chǎn)品流水線而言平衡效率為優(yōu)，但考慮了每個產(chǎn)品實際的作業(yè)時間后的混合流水線上，由于排序方案的不同使得每個工作站出現(xiàn)的產(chǎn)品不同，使得工作站作業(yè)時間不同，從而出現(xiàn)不平衡現(xiàn)象，甚至超出節(jié)拍需求，在有些時間段內(nèi)個別工作站無法完成作業(yè)，需要在工作站上增加額外的活動工人來完成超出的負荷，才能使流水線正常運行。因此有必要尋求更好的平衡方案較少超負荷量水平，從而減少線外工作站的修補工作量，提高生產(chǎn)效率，提高質量。

5.5 優(yōu)化方案

工作站1 對A 的作業(yè)時間為19 分鐘，超負荷明顯，而工作站2 中對A 產(chǎn)品沒有超負荷現(xiàn)象，所以考慮對工作站1 進行拆分，與工作站2 中作業(yè)進行重新分配;工作站4 與工作站5 的超負荷現(xiàn)象更加明顯，C 產(chǎn)品在工作站4 中作業(yè)時間超過節(jié)拍，而在工作站5 的作業(yè)時間只有8 分鐘，遠小于節(jié)拍;A、B 產(chǎn)品在工作站5 中作業(yè)時間超過節(jié)拍，而在工作站4的作業(yè)時間較小，所以考慮對工作站4、5 進行拆分，對其中的作業(yè)重新分配。改進后的平衡方案如表5 所示。

針對改進的平衡方案，加入排序方案后，產(chǎn)品以投入順序CBAC 循環(huán)進入生產(chǎn)線，重新構建仿真模型，仿真結果表明在一個周期的四個階段內(nèi)五個工作站中出現(xiàn)的產(chǎn)品及工作站作業(yè)時間如表6 所示，工作站實際負荷如圖7 所示。

表6 改善后一個周期內(nèi)工作站加工產(chǎn)品及作業(yè)時間

圖7 改善后工作站負荷圖

改善后最長工作站作業(yè)時間為15，滿足節(jié)拍15的要求，不存在工作站作業(yè)時間超過節(jié)拍的情況，CH= 0，負荷均衡指數(shù)為0.47，大大小于初始方案，改進后的平衡效果優(yōu)。

6 結束語

混合流水線的平衡過程是實現(xiàn)勞動生產(chǎn)率、設備利用率和滿足市場需求三者之間平衡的過程，混合流水線平衡效果直接影響到流水線的生產(chǎn)效率。本文針對混合流水線設計與運行的特點，采用啟發(fā)式算法和仿真分析相結合的方法求解混合流水線平衡問題，通過對某客車空調(diào)生產(chǎn)企業(yè)三種產(chǎn)品混流生產(chǎn)線的設計發(fā)現(xiàn)，經(jīng)過平衡優(yōu)化后，能夠減少最長工作站作業(yè)時間，避免工作站實際負荷超節(jié)拍的情況，大大減少工作站間負荷不均衡，達到提高生產(chǎn)效率，降低生產(chǎn)成本，提升員工士氣，穩(wěn)定產(chǎn)品質量等目的。

［1］張則強，程文明，鐘斌，等. 混合品種裝配線平衡問題的一種混合搜索機制的蟻群算法［J］. 機械工程學報，2009，45(5):95－101.

［2］徐煒達，肖田元. 可跨工位操作的隨機混流裝配線平衡問題研究［J］. 系統(tǒng)仿真學報，2009，21(18):5896－5901.

［3］Reakook Hwang，Hiroshi Katayama. A multi-decision genetic approach for workload balancing of mixed-model U-shaped assembly line systems［J］. International Journal of Production Research. 2009，47(14):3797－3822.

［4］凌文曙. 基于遺傳算法的混流裝配線工作站平衡［J］.合肥工業(yè)大學學報，2008，31(8):1287－1291.

［5］Armin Scholl，Christian Becker. State-of-the-art exact and heuristic solution procedures for simple assembly line balancing［J］. European Journal of Operational Research，2006，168(3):666－693.

［6］李榮鈞. 運籌學導論［M］. 北京:科學出版社，2009.

［7］Din-Horng Yeh，Hsiu-Hsueh Kao. A new bidirectional heuristic for the assembly line balancing problem［J］. Computers ＆ Industrial Engineering，2009，57(4):1155－1160.

［8］吳隆，余海明，吳媛媛. 基于Lingo 的汽車裝配線建模與平衡優(yōu)化［J］. 工業(yè)工程與管理，2008(6):74－77.