考慮生產(chǎn)線平衡的多目標混流裝配線排程問題研究*

黃 健，劉亮，齊二石

(天津大學 管理與經(jīng)濟學部，天津 300072)

0 引言

在大規(guī)模定制模式下，越來越多的制造商開始引入混流裝配線以實現(xiàn)把產(chǎn)品定制和大批量生產(chǎn)結(jié)合起來，在降低成本、保證質(zhì)量的同時，高效率地滿足客戶的個性化需求［1］?；炝餮b配線(Mixed Model Assembly Lines，MMALs)是指可同時對產(chǎn)品結(jié)構(gòu)相似、工藝路線接近的不同型號產(chǎn)品(同一產(chǎn)品族)進行裝配的柔性裝配生產(chǎn)線，在基本不改變生產(chǎn)線的前提下，生產(chǎn)不同數(shù)量、不同類型的產(chǎn)品。因此，在該裝配線上既可以按照單一品種大批量的福特式生產(chǎn)方式生產(chǎn)，也可以進行多品種小批量生產(chǎn)，具有較高的靈活性和適應性。

排序問題是決定混流裝配線能否高效運作的關(guān)鍵問題之一，國內(nèi)外已有很多學者從不同角度研究了混流裝配線的產(chǎn)品排序問題。1963 年Wester 和Kilbridge［2］首次提出混流裝配線的排序問題(Mixed Model Sequencing Problem，MMSP)，MMSP 已被證明為典型的NP 難題。隨著研究的深入，研究者普遍運用人工智能算法，Mansouri［3］用遺傳算法對JIT 生產(chǎn)線的兩個常見目標進行產(chǎn)品排序;Hyun 等［4］考慮三個目標并設計改進的遺傳算法和選擇機制(Pareto stratum-niche cubicle)來求解排序問題，并證明得到結(jié)果優(yōu)于現(xiàn)存的遺傳算法;曹振新等［5］針對兩個目標運用Pareto 理論和小生境單元的適應度函數(shù)及選擇算子構(gòu)建遺傳算法解決排序問題;Kim 等［6］提出一種改進的進化算法針對三個目標對U 型混流裝配線的平衡和排序進行研究。宋華明和馬士華［7］證明工作站中不同產(chǎn)品操作時間的差異性對排序結(jié)果有顯著影響;蘇平等［8］對兩個目標采用改進混合遺傳算法求得最優(yōu)排序方案，有效解決了GA 收斂過早的缺點;朱華炳等［9］考慮兩個目標采用改進多目標粒子群優(yōu)化算法和仿真結(jié)合的方法來對模型進行求解。

目前大多文獻都集中在對生產(chǎn)系統(tǒng)的建模分析運用智能算法求解，然而在實際的生產(chǎn)過程中，生產(chǎn)系統(tǒng)一般都屬于復雜的離散事件系統(tǒng)，具有不確定性、動態(tài)性、復雜性等特點，依靠傳統(tǒng)的解決方案進行分析求解，很難做到真實反映生產(chǎn)系統(tǒng)的諸多特性?；炝骶€的平衡和排序問題是設計混流裝配線必須要考慮的，但很多學者都把這兩方面問題孤立開來研究，在實際應用中很可能不能實現(xiàn)裝配線整體優(yōu)化。

針對上述研究的不足和更加準確、客觀地反映企業(yè)的生產(chǎn)實際狀況，本文在研究排序問題時考慮了生產(chǎn)線平衡，盡可能在讓排序所得結(jié)果滿足生產(chǎn)線平衡條件而不產(chǎn)生忙閑不均的情況，把遺傳算法和系統(tǒng)仿真結(jié)合起來，綜合優(yōu)化得到最優(yōu)解。仿真模型中的各參數(shù)設置可按照生產(chǎn)實際作相應調(diào)整，具有較強的通用性。

1 數(shù)學模型的建立

1.1 混流轉(zhuǎn)配線模型描述

假設一條混流裝配線上需加工M中產(chǎn)品，每種產(chǎn)品的需求量記作D1，D2，...，DM，生產(chǎn)采用最小生產(chǎn)循環(huán)(Minimal Production Set，MPS)模式:設g為D1，D2，...，DM的最大公約數(shù)，那么一個MPS中M種產(chǎn)品的生產(chǎn)數(shù)量整個生產(chǎn)過程投放g次MPS即可完成，混流裝配線的排序問題就是確定一個MPS中產(chǎn)品的投產(chǎn)順序。該裝配線有S個工作站，每個工作站的長度是固定的且是封閉的，操作工不能越過自己的工位。假設不同類型產(chǎn)品之間不存在零部件共享，且生產(chǎn)線平衡問題已經(jīng)解決。

s表示工作站編號，共有S個工作站;

n表示產(chǎn)品編號，共有N個產(chǎn)品;

k表示產(chǎn)品類別編號，共有K類產(chǎn)品;

xnk是一個0，1 變量，表示排產(chǎn)序列中第n個產(chǎn)品是否為第k類產(chǎn)品，如果變量值為1 ，則表示排產(chǎn)順序中第n個產(chǎn)品種類為k，否則不是第k種產(chǎn)品;

vc表示傳送帶的恒定的運行速度;

Ls表示第s個工作站的長度;

w表示兩相鄰產(chǎn)品的距離;該值等于產(chǎn)品投放時間間隔CT與傳送帶速度vc的乘積，因為CT是恒定的，我們可以認為w也是恒定不變的;

dk表示生產(chǎn)計劃中第k種產(chǎn)品的需求量;

Uns表示排產(chǎn)順序中第n個產(chǎn)品在s工作站上因超載而需額外補充的工作量，用超載的作業(yè)時間來衡量這里的工作量;

SPns表示投產(chǎn)順序中的第n個產(chǎn)品在第s個工作站上的起始位置;

tsk表示第k類產(chǎn)品在工作站s上的裝配時間;

xnkr表示排產(chǎn)順序中第n和(n +1)個產(chǎn)品的種類是否分別為k品種和r品種，如果是則值為1，否則值為0;

tskr表示在s工作站上產(chǎn)品由k品種切換到r品種所需要的準備時間。

1.2 零部件消耗速率保持均勻模型

生產(chǎn)的均衡化，是在準時制生產(chǎn)方式JIT 中，為了實現(xiàn)“將必需的物品，在必需的時候，僅生產(chǎn)必需的數(shù)量”這樣的準時生產(chǎn)理念最重要的必要條件。也就是說為了消除不必要的零部件的庫存和不必要的產(chǎn)品庫存，以及避免因產(chǎn)品裝配線和零部件組裝線發(fā)生生產(chǎn)線停線所需要的多余勞動時間所產(chǎn)生的勞務費浪費，作為前提而必須滿足的核心必要條件［10］。對于當下許多實施豐田生產(chǎn)方式企業(yè)來說，保持零部件和原材料使用量的均勻消耗是首先要考慮的目標。參照Miltenburg 等提出的生產(chǎn)均衡化模型，得到最終裝配線上物料消耗波動最小模型［11］:

1.3 工作站超載量最小化模型

在一次計劃排序問題中，每個工作站工作的時間長度為Ls/vc，裝配線上的工作站可能會出現(xiàn)如下兩種情況，一種情況是一單位產(chǎn)品加工完成后，下一單位的產(chǎn)品尚未進入工作站，操作工回到工作站起點等待產(chǎn)品到來，產(chǎn)生閑置，造成資源浪費;另一種情況是操作工尚未完成一個單位產(chǎn)品的加工，下一單位產(chǎn)品就已進入工作站，這時需要線外工人來幫助完成，產(chǎn)生超載，必將引起成本增加，所以我們要設法減少這樣的情況產(chǎn)生。此過程我們可以用圖1 表示。

圖1 閑置和超載示意圖

目標函數(shù)2 是為使各工位上超載時間最小化。其中式(6)是為確定投產(chǎn)序列中的第(n +1)個產(chǎn)品在第s個工作站上的起始位置;式(7)為排產(chǎn)順序中第n個產(chǎn)品在s工作站上因超載需額外補充的工作量。

1.4 總調(diào)整變換時間最小化模型

在實際生產(chǎn)中，總的切換時間往往跟產(chǎn)品的投放順序有關(guān)，一般組內(nèi)調(diào)整時間少，組間調(diào)整時間大。過于頻繁的產(chǎn)品切換將導致操作工出錯的可能性變大、生產(chǎn)效率降低等問題。所以這也是很多制造型企業(yè)在混流裝配線中考慮的一個因素，建立模型如下:

目標函數(shù)三是使切換時間最小化。式(10)限定每一工作站對應唯一在制品;式(11)、(12)是為了確保每個MPS 中產(chǎn)品都按照相同的投產(chǎn)順序進行生產(chǎn);式(13)是為了滿足需求量dk。

最后采用加權(quán)法將三個獨立的目標函數(shù)聯(lián)合起來進行優(yōu)化。根據(jù)企業(yè)自身的情況不同，對各目標函數(shù)分配不同的權(quán)重系數(shù)w1w2w3，經(jīng)歸一化后得到優(yōu)化模型:

該目標函數(shù)的約束為綜合以上三個目標函數(shù)約束。

2 仿真的建立運行與優(yōu)化求解

2.1 生產(chǎn)線模型構(gòu)建

對某500 強企業(yè)進行調(diào)研，該企業(yè)主要生產(chǎn)先進的高、中壓開關(guān)設備以及滿足中國快速發(fā)展的輸電網(wǎng)絡市場對高品質(zhì)開關(guān)設備的需求。本文將針對該公司的中壓開關(guān)裝配線展開研究。企業(yè)生產(chǎn)是按照訂單進行的，基本實現(xiàn)了定制化。由于產(chǎn)品種類過多，為簡化研究過程，假定在一個計劃期內(nèi)，總裝線上需要加工的開關(guān)柜有CCF、CFC、CCVV、CCCCF、CCCCCC 五種型號，產(chǎn)量分別為120 臺、120 臺、80 臺、160 臺和40 臺。目前裝配線上共有4 個工作站，分別為內(nèi)部裝配(包括背板焊接)、氣密耐壓試驗、側(cè)板裝配、總裝。

混流裝配線仿真模型建立如圖2 所示，裝配線由內(nèi)裝、背板焊接、側(cè)板裝配、總裝四個工作站組成，每個工作站旁都有相應的線邊協(xié)作區(qū)，分別為S1、S2、S3、S4。工件在各工作站停留時間是固定的，為實現(xiàn)這一要求，工件從進入工作站就流向相應的傳送帶，分別為Line、Line4、Line1、Line2，工件在傳送帶上流動時間即為在此工作站停留時間，生產(chǎn)工人必須再次時內(nèi)完成本工位操作，如果不能實現(xiàn)，將由線邊協(xié)作人員幫忙完成，以避免裝配線停線。由于個工作站之間的距離是相等的，模型中工作站之間緊挨著，即產(chǎn)品在上一工位加工完成后緊接著就流向本工位。假定傳送帶的速度vc=0.1m/s，各裝配站長度為12，14，12，11。

圖2 仿真運行界面

在該模型中，安排生產(chǎn)的產(chǎn)品共有5 種，一個MPS中有15 件產(chǎn)品，其中的產(chǎn)品數(shù)可以在全局變量Innumber 中根據(jù)不同的生產(chǎn)計劃安排自由設定。產(chǎn)品按照模型中表格Schedule 安排的順序以固定間隔時間50s進入裝配線，BF1、BF2、BF3、BF4 表示線邊暫存區(qū)，產(chǎn)品從傳送帶上流入到暫存區(qū)BF 中等待工作站出現(xiàn)空閑，進入工作站加工。不同類型產(chǎn)品在各工作站上需要的切線準備時間在A1Setup、A2Setup、A3Setup、A4Setup 中設定。對應的每種產(chǎn)品在各工作站上的生產(chǎn)裝配時間及工作的長度如下表所示，后分別記錄在Assembly1、Assembly2、Assembly3、Assembly4 中，線邊作業(yè)人員操作時間根據(jù)超載時間在程序中設定。在Method 對 象 BF1in-BF4in，BF1out-BF4out，A1OUTA4OUT、S1in-S4in 等中編寫的程序，控制各個產(chǎn)品按照設定的邏輯在各工作站中的流動加工，并將加工信息記錄在TableFile0、TableFile1、TableFile2、TableFile3中，然后根據(jù)所建立的數(shù)學模型和統(tǒng)計的信息求得以上三模型的目標函數(shù)值。

表1 工作站裝配時間和工作站長度

表2 各工作站準備時間

2.3 遺傳算法的設計

在本文研究中采用數(shù)字串表示基因，每個數(shù)字表示各個不同型號的產(chǎn)品。在此例中有A、B、C、H、P 五種型號產(chǎn)品，一個MPS 中各型號數(shù)量分別選用(A，B，C，H，P)=(3，5，2，4，1)共15 個，在該實驗中，一個染色體由15 個基因組成，并分別用數(shù)字1～15 表示。初始種群的產(chǎn)生采用完全隨機方法。

適應度是個體選擇過程中的評價標準，具有高適應度的個體在進化過程中被保留下來。根據(jù)第三部分建立的目標函數(shù)模型，根據(jù)數(shù)學模型在Method、UT 和setuptime 對象中編寫SimTalk 程序語言，生成相應的統(tǒng)計數(shù)據(jù)，然后得到需要的目標函數(shù)值，根據(jù)制造企業(yè)實際情況設定三個單一目標的權(quán)重w1w2w3，在此模型中我們分別假定各目標權(quán)重為分別為0. 4，0. 2，0.1，以此來確定總目標函數(shù)值?？紤]到整個過程加工時間也是企業(yè)不得不顧及的因素，在仿真中加入加工過程時間最小化即Eventcontroller. SimTime 最小約束，并賦予權(quán)重0.3。

因為目標函數(shù)O1 值相比于其他三項過小，所以在此模型中將此值乘以10 后加權(quán)。

交叉方法采用部分匹配交叉(PMX):隨機選取兩個交叉點，交換附帶個體交叉點之間的片段，對于交叉點外的基因，若它不與換過來的片段沖突則保留，若沖突則通過部分映射來確定，直到?jīng)]有沖突的基因為止，從而獲得后代個體。變異采用隨機變異方法。

圖3 PMX 交叉操作

2.4 遺傳算法求解和篩選

實驗采用的遺傳算法初始條件如下:種群大小為20，終止迭代次數(shù)為100，交叉概率為0.8，變異概率為0.2。仿真運行后得到遺傳算法的報告文件，其進化曲線如圖4，從圖中可以清楚地看出遺傳算法的優(yōu)化過程，在運行到第84 代得到了收斂的結(jié)果，得到以加工過程總時間產(chǎn)品變化率、超載時間和總切換時間、周期時間最小化為優(yōu)化目標的4 個滿意解，并在Schedule中的Opt1-Opt4 列生成，所對應的適應度函數(shù)值分別為598.205、606.915、610.515 和616.875，均能在以上目標中表現(xiàn)出優(yōu)秀的性狀。

在混流裝配線的排程過程中必須兼顧另一個方面是裝配線的平衡問題，它與裝配線排序問題不能孤立開來研究。按照新的順序投產(chǎn)不能以損失裝配線的平衡為代價，否則也會造成人員、固定資產(chǎn)的浪費，那優(yōu)化后的產(chǎn)品排產(chǎn)順序就會失去價值。為此，在得到的滿意解中綜合考慮裝配線平衡的目標從而得到最優(yōu)排序。

圖4 進化曲線

本文算法的4 個滿意解整體表現(xiàn)都能滿足優(yōu)化要求，但就生產(chǎn)線平衡來衡量的話，按照方案二Opt2 順序安排生產(chǎn)所得裝配線平衡率最高，且其切線時間也有較好的表現(xiàn)，由此可以得出Opt2 是最優(yōu)投產(chǎn)順序。此外，本文是為驗證此方法的實用性，所以在對一個MPS 中產(chǎn)品種類、數(shù)量、在各工位上加工時間等的數(shù)據(jù)進行反復調(diào)整仍然可以得到符合要求的排產(chǎn)。在此例中我們得到一個 MPS 內(nèi)產(chǎn)品的投產(chǎn)順序為AAABBBBCCHPHHHB。另外多目標遺傳算法求的結(jié)果是一組非劣解集合，這為管理者提供了較好的選擇空間。在仿真運行過程中，還可設定各裝配工站的故障發(fā)生率等生產(chǎn)過程中可能出現(xiàn)的隨機因素，從而更貼近生產(chǎn)實際，而這也是現(xiàn)有的數(shù)學模型很難實現(xiàn)的。

圖5 Opt1-Opt4 中各工作站負荷圖

表3 仿真結(jié)果比較

3 結(jié)束語

在本文的研究中，我們考慮了四個在生產(chǎn)中常見的目標，像超載時間最小化、總加工時間最小化、零部件消耗速率均勻化和調(diào)整時間最小化，這些目標對于混流裝配線的有效運行來說是非常重要的，特別是當生產(chǎn)線建成后短時期內(nèi)不會做大規(guī)模調(diào)整，單純建立數(shù)學模型求解可能無法照顧到生產(chǎn)實際的方方面面，所以有必要對這些生產(chǎn)線的運行做盡可能真實的模擬，通過內(nèi)置的遺傳算法優(yōu)化，基本可以按照實際生產(chǎn)的要求進行優(yōu)化，得到滿意的產(chǎn)品排序方案，最后結(jié)合裝配線平衡方面的考量，得出最優(yōu)排序方案，對混流裝配線的排程問題的解法提出了新的思路。

［1］苑明海，李東波，于敏建. 面向大規(guī)模定制的混流裝配線平衡研究［J］. 計算機集成制造系統(tǒng)，2008，14(1):79 -83，131.

［2］Wester L，Kilbridge M. The assembly line model-mix sequencing problem［C］. Proceedings of the third international conference on Operations Research， Oslo， 1963:247 -260.

［3］Mansouri S A. A multi-objective genetic algorithm for mixedmodel sequencing on JIT assembly lines［J］. European Journal of Operational Research，2005，167(3):696 -716.

［4］Hyun C J，Kim Y，Kim Y K. A genetic algorithm for multiple objective sequencing problems in mixed model assembly lines［J］. Computers ＆ Operations Research，1998，25(7-8):675 -690.

［5］曹振新，朱云龍. 多目標遺傳算法在混流裝配線排序中的應用［J］. 計算機工程，2005，31(22):1 -3，142.

［6］Kim Y K，Kim J Y，Kim Y. An endosymbiotic evolutionary algorithm for the integration of balancing and sequencing in mixed-model U-lines［J］. European Journal of Operational Research，2006，168(3):838 -852.

［7］宋華明，馬士華. 考慮流水線平衡的混合裝配線排序［J］. 中國機械工程，2006，17(11):1138 -1147.

［8］蘇平，于兆勤. 基于混合遺傳算法的混合裝配線排序問題研究［J］. 計算機集成制造系統(tǒng)，2008，14(5):1001 -1007.

［9］朱華炳，王龍，涂學明，等. 隨機型混流裝配線動態(tài)排序問題研究［J］. 組合機床與自動化加工技術(shù)，2013 (11):114 -118.

［10］門田安弘，著，王瑞珠，李瑩，譯. 新豐田生產(chǎn)方式［M］.保定:河北大學出版社，2008.

［11］Miltenburg J. Level schedules for mixed-model assembly lines in just-in-time production systems［J］. Management Science，1989，35(2):192 -207.