黃 健，劉亮，齊二石

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

0 引言

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

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

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

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

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

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

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

s表示工作站編號(hào)，共有S個(gè)工作站;

n表示產(chǎn)品編號(hào)，共有N個(gè)產(chǎn)品;

k表示產(chǎn)品類(lèi)別編號(hào)，共有K類(lèi)產(chǎn)品;

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

vc表示傳送帶的恒定的運(yùn)行速度;

Ls表示第s個(gè)工作站的長(zhǎng)度;

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

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

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

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

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

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

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

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

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

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

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

圖1 閑置和超載示意圖

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

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

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

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

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

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

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

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

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

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

圖2 仿真運(yùn)行界面

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

表1 工作站裝配時(shí)間和工作站長(zhǎng)度

表2 各工作站準(zhǔn)備時(shí)間

2.3 遺傳算法的設(shè)計(jì)

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

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

因?yàn)槟繕?biāo)函數(shù)O1 值相比于其他三項(xiàng)過(guò)小，所以在此模型中將此值乘以10 后加權(quán)。

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

圖3 PMX 交叉操作

2.4 遺傳算法求解和篩選

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

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

圖4 進(jìn)化曲線

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

圖5 Opt1-Opt4 中各工作站負(fù)荷圖

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

3 結(jié)束語(yǔ)

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

［1］苑明海，李東波，于敏建. 面向大規(guī)模定制的混流裝配線平衡研究［J］. 計(jì)算機(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］曹振新，朱云龍. 多目標(biāo)遺傳算法在混流裝配線排序中的應(yīng)用［J］. 計(jì)算機(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］. 中國(guó)機(jī)械工程，2006，17(11):1138 -1147.

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

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

［10］門(mén)田安弘，著，王瑞珠，李瑩，譯. 新豐田生產(chǎn)方式［M］.保定:河北大學(xué)出版社，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.