查 靚，田 行

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

0 引言

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

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

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

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

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

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

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

令第p 個(gè)產(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。計(jì)劃期內(nèi)第p 個(gè)產(chǎn)品的需求數(shù)量為dp，總產(chǎn)品數(shù)為)d，則計(jì)算出每個(gè)作業(yè)元素的加權(quán)平均作業(yè)時(shí)間為:

3 啟發(fā)式算法

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

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

計(jì)算步驟如下:

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

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

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

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

第五步:確定分配方案。對(duì)于臨時(shí)工作站集合FSi和BSj，如果FSi的空閑時(shí)間小于BSj的空閑時(shí)間，即Wf ≤Wb，說明當(dāng)前前向工作站i 的臨時(shí)分配方案優(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 的臨時(shí)分配方案優(yōu)于前向工作站i 的，接受BSj的分配方案成為固定分配方案，放棄FSi，即j = j +1，Sa= Sa∪BSj，Sa= Su－BSj，F(xiàn)Si= BSj= φ。

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

算法流程圖如圖1 所示。

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

4 評(píng)價(jià)指標(biāo)

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

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

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

表1 單一產(chǎn)品流水線平衡性評(píng)價(jià)標(biāo)準(zhǔn)

4.2 混合流水線平衡指標(biāo)

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

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

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

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

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

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

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

下面通過一個(gè)案例來說明和驗(yàn)證本文所提方法的有效性。

5 案例應(yīng)用

5.1 案例背景介紹

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

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

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

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

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

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

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

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

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

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

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

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

根據(jù)表1 的評(píng)價(jià)標(biāo)準(zhǔn)，p ≥90% 可以認(rèn)定該單一產(chǎn)品流水線平衡方案是優(yōu)的。

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

5.4 仿真分析

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

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

圖6 改善前工作站負(fù)荷

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

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

5.5 優(yōu)化方案

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

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

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

圖7 改善后工作站負(fù)荷圖

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

6 結(jié)束語

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

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

［2］徐煒達(dá)，肖田元. 可跨工位操作的隨機(jī)混流裝配線平衡問題研究［J］. 系統(tǒng)仿真學(xué)報(bào)，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è)大學(xué)學(xué)報(bào)，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］李榮鈞. 運(yùn)籌學(xué)導(dǎo)論［M］. 北京:科學(xué)出版社，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.