基于排隊(duì)理論的制造單元構(gòu)建與加工路徑選擇*

李 翔，周建偉，張雪麗，李忠學(xué)

(蘭州交通大學(xué)機(jī)電工程學(xué)院，甘肅蘭州 730070)

0 引言

單元制造是成組技術(shù)(GT)在制造領(lǐng)域中的一個(gè)重要應(yīng)用。單元制造系統(tǒng)在減少加工成本與物料搬運(yùn)成本、縮短任務(wù)期、實(shí)現(xiàn)集中管理等方面體現(xiàn)出很大的優(yōu)勢(shì)。目前單元制造系統(tǒng)的研究主要包括:單元構(gòu)建、單元布局設(shè)計(jì)與單元管理三方面［1］。

設(shè)備組與零件族是單元構(gòu)建的兩個(gè)重要因素，針對(duì)單元構(gòu)建問題，國內(nèi)外學(xué)者提出了很多數(shù)學(xué)模型。用于構(gòu)建單元的目標(biāo)規(guī)劃模型主要是基于成本最優(yōu)原則［2-4］，劃分的單元塊與選定的工件加工路徑能夠保證較低的加工成本與物料搬運(yùn)成本，但由于在建立模型時(shí)并沒有考慮加工系統(tǒng)中存在的排隊(duì)現(xiàn)象，會(huì)導(dǎo)致某種設(shè)備前有排隊(duì)而某種設(shè)備卻一直閑置的問題，這不僅會(huì)增加后續(xù)的設(shè)備維修費(fèi)用，而且設(shè)備負(fù)荷強(qiáng)度不均衡則不能保證相近的零件加工進(jìn)度，不但對(duì)企業(yè)是一種資源的浪費(fèi)，也會(huì)增加生產(chǎn)管理難度。Buzacott等［5］提出用排隊(duì)理論將具有相似加工時(shí)間的零件分配到同一單元，使單元便于生產(chǎn)管理。Arghis等［6］運(yùn)用排隊(duì)理論建立了減少閑置成本與等待成本的單目標(biāo)規(guī)劃數(shù)學(xué)模型。

筆者借鑒Buzacott和Arghis運(yùn)用排隊(duì)理論的建模方法，將每臺(tái)設(shè)備看作是一個(gè)M/M/1排隊(duì)系統(tǒng)，整個(gè)系統(tǒng)等效為一個(gè)開環(huán)排隊(duì)網(wǎng)絡(luò)模型。模型中的工件具有多種加工路徑，優(yōu)化加工成本與等待成本的同時(shí)，削弱排隊(duì)影響、均衡設(shè)備服務(wù)強(qiáng)度與單元服務(wù)強(qiáng)度，最終實(shí)現(xiàn)單元構(gòu)建與工件加工路徑選擇。

1 理論基礎(chǔ)

1．1 排隊(duì)基本原理

排隊(duì)在生產(chǎn)實(shí)際中是一種常見的現(xiàn)象，例如車間中在機(jī)床邊等待加工的零件。在排隊(duì)理論中，把要求服務(wù)的對(duì)象統(tǒng)稱為“顧客”，把提供服務(wù)的人或機(jī)構(gòu)稱為“服務(wù)臺(tái)”。一個(gè)排隊(duì)系統(tǒng)有3個(gè)基本組成部分:輸入過程、排隊(duì)規(guī)則和服務(wù)機(jī)構(gòu)，本文中的排隊(duì)系統(tǒng)采用M/M/1形式，即到達(dá)過程是泊松過程，服務(wù)時(shí)間服從負(fù)指數(shù)分布的單服務(wù)臺(tái)排隊(duì)系統(tǒng)［7］。在構(gòu)建單元前，首先將多種設(shè)備組成的整個(gè)加工系統(tǒng)看作一個(gè)服務(wù)臺(tái)，如圖1所示，則整個(gè)系統(tǒng)構(gòu)成一個(gè)M/M/1排隊(duì)模型。假設(shè)存在i種零件，每種零件的到達(dá)率是λi，則對(duì)整個(gè)加工系統(tǒng)而言，零件的到達(dá)率是:

圖1 系統(tǒng)排隊(duì)模型

1．2 排隊(duì)網(wǎng)絡(luò)

一個(gè)排隊(duì)網(wǎng)絡(luò)是一些節(jié)點(diǎn)的集合，作業(yè)在這些節(jié)點(diǎn)間移動(dòng)并接受服務(wù)。每一個(gè)節(jié)點(diǎn)從其本身而言都是一個(gè)排隊(duì)系統(tǒng)。開環(huán)排隊(duì)網(wǎng)絡(luò)是指既有到達(dá)網(wǎng)絡(luò)的顧客流又有向網(wǎng)絡(luò)外部輸出的顧客流。當(dāng)把每一臺(tái)設(shè)備看作是一個(gè)節(jié)點(diǎn)時(shí)，工件在一個(gè)節(jié)點(diǎn)接受服務(wù)后，可以離開網(wǎng)絡(luò)或者去下一個(gè)節(jié)點(diǎn)繼續(xù)接受服務(wù)，整個(gè)系統(tǒng)就構(gòu)成一個(gè)Jackson開環(huán)網(wǎng)絡(luò)模型［8］。

每個(gè)節(jié)點(diǎn)n的總體到達(dá)率λn是外部到達(dá)率λn'和網(wǎng)絡(luò)內(nèi)部到達(dá)率之和。對(duì)任意節(jié)點(diǎn)m=1，2，．．．，M，作業(yè)在節(jié)點(diǎn)m接受服務(wù)后到節(jié)點(diǎn)n繼續(xù)接受服務(wù)的概率是pmn。根據(jù)定理:M/M/1隊(duì)列的離去過程也是泊松過程，這個(gè)過程與到達(dá)過程相同［］。即離開節(jié)點(diǎn)m的離開率與到達(dá)率λm相等。因此有:

1．3 排隊(duì)系統(tǒng)的經(jīng)濟(jì)分析

排隊(duì)現(xiàn)象在加工制造系統(tǒng)中的存在是必然的，但以完全消除排隊(duì)現(xiàn)象為研究目標(biāo)是不合理的，這會(huì)造成設(shè)施的嚴(yán)重浪費(fèi)。從經(jīng)濟(jì)成本角度考慮，排隊(duì)系統(tǒng)中的費(fèi)用包括服務(wù)費(fèi)用與等待費(fèi)用。前者是服務(wù)水平的遞增函數(shù)，后者是服務(wù)水平的遞減函數(shù)，如圖2所示。文中優(yōu)化的目標(biāo)之一是使兩者的費(fèi)用之和最小，即:

式中:Cm是服務(wù)費(fèi)用;Cw是等待費(fèi)用。

圖2 排隊(duì)系統(tǒng)經(jīng)濟(jì)模型

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

基于排隊(duì)理論的單元構(gòu)建模型滿足下述假設(shè)條件:①工件與設(shè)備滿足M/M/1排隊(duì)模型的要求;②每種工件至少存在一種加工路徑即r≥1，加工之前須指定特定的加工路徑;③加工工序先后順序不會(huì)對(duì)構(gòu)建單元產(chǎn)生影響;④零件種類與設(shè)備種類已知;⑤在同一設(shè)備上完成不同工件的加工所需時(shí)間相同，且每種設(shè)備的服務(wù)率與單位時(shí)間運(yùn)行費(fèi)用已知;⑥設(shè)備前的單位時(shí)間等待費(fèi)用有兩種，分別是本單元內(nèi)的工件排隊(duì)時(shí)的單位時(shí)間等待費(fèi)用與其它單元內(nèi)的工件排隊(duì)時(shí)的單位時(shí)間等待費(fèi)用，兩種費(fèi)用均不受單元內(nèi)與單元間布局形式的影響。

模型具體形式如下:

令:i為工件編號(hào)，i=1，2，．．．，P;j為設(shè)備編號(hào)，j=1，2，．．．，M;k 為單元編號(hào)，k=1，2，．．．，C;r為加工路徑編號(hào)，r=1，2，．．．R;vj為設(shè)備 j的單位時(shí)間運(yùn)轉(zhuǎn)費(fèi)用;μj為設(shè)備j單位時(shí)間內(nèi)可完成的同類操作數(shù)目，即設(shè)備j的服務(wù)率;λj為工件到達(dá)設(shè)備j的到達(dá)率;λi為工件 i的到達(dá)率;ρj為設(shè)備 j的服務(wù)強(qiáng)度;ρk為單元k的服務(wù)強(qiáng)度;Wj為設(shè)備j前的平均等待時(shí)間;Wj'為工件在設(shè)備j的排隊(duì)系統(tǒng)中的逗留時(shí)間;ν，ν'為設(shè)備前的兩種單位時(shí)間等待費(fèi)用，且 ν＜ν';αirj為工件i在路徑r下是否需要設(shè)備j上加工，如果需要?jiǎng)tαirj=1，反之為零;Mmax為一個(gè)單元內(nèi)的最大設(shè)備數(shù)目;Mmin為一個(gè)單元內(nèi)的最小設(shè)備數(shù)目;Pmax為一個(gè)單元內(nèi)可加工的最多工件數(shù);Pmin為一個(gè)單元內(nèi)可加工的最少工件數(shù);ρjmax為設(shè)備j的最大服務(wù)強(qiáng)度;ρjmin為設(shè)備j的最小服務(wù)強(qiáng)度;ρkmax為單元k的最大服務(wù)強(qiáng)度;ρkmin為單元k的最小服務(wù)強(qiáng)度。

決策變量:

xik:如果工件分配到單元k內(nèi)，則xik=1，其它等于0。

yik:如果設(shè)備分配到單元k內(nèi)，則yik=1，其它等于0。

zir:如果工件i選擇路徑r加工，則zir=1，其它等于0。

目標(biāo)函數(shù)有:

式(4)中，第一部分是工件的加工成本，第二部分與第三部分是排隊(duì)費(fèi)用，其中zirαirjxikyjk表示工件i與在加工路徑r下需要的設(shè)備j在同一單元內(nèi)，zirαirjxikyjk'表示工件i與在加工路徑r下需要的設(shè)備j不在同一單元內(nèi)。式(5)表示最小化設(shè)備服務(wù)強(qiáng)度范圍，式(6)表示最小化單元服務(wù)強(qiáng)度范圍。

約束:

在上列約束中，式(7)和式(8)限制每種工件和設(shè)備只能屬于唯一的單元;式(9)保證每種工件只能選擇一種加工路徑;式(10)表示單元大小限制;式(11)表示單元加工能力限制;式(12)計(jì)算任意設(shè)備前的排隊(duì)時(shí)間，其中根據(jù)式(1)、(2)和假設(shè)(2)可得:

式(13)表示設(shè)備負(fù)荷強(qiáng)度約束;式(14)計(jì)算單元負(fù)荷強(qiáng)度;式(15)表示不能有設(shè)備始終閑置;式(16)決策變量域約束。

將三個(gè)目標(biāo)函數(shù)利用線性加權(quán)和法構(gòu)造成一個(gè)評(píng)價(jià)函數(shù)，多目標(biāo)函數(shù)轉(zhuǎn)化為單目標(biāo)優(yōu)化問題。加權(quán)因子分別為 ω1、ω2、ω3，構(gòu)造的評(píng)價(jià)函數(shù)如下:

3 算例

為了檢驗(yàn)上述模型的有效性，隨機(jī)選擇如下數(shù)據(jù):有10種分別有兩種加工路徑的工件與10種設(shè)備，工件-設(shè)備原始矩陣如表1所列，表中前一列數(shù)據(jù)表示加工路徑1，后一列數(shù)據(jù)表示加工路徑2;工件的到達(dá)率如表2所列;設(shè)備服務(wù)率及單位時(shí)間運(yùn)行費(fèi)用如表3所列;設(shè)備前的兩種單位時(shí)間等待費(fèi)用分別取 ν=0．3，ν'=0．7。

表1 設(shè)備-工件原始矩陣

表2 工件到達(dá)率

表3 設(shè)備服務(wù)率以及單位時(shí)間運(yùn)轉(zhuǎn)費(fèi)用

參數(shù)設(shè)置:構(gòu)建3個(gè)單元;單元大小限制為:Mmin=2，Mmax=4;單元加工能力限制為:Pmin=2，Pmax=4;加權(quán)因子分別取 ω1=0．5，ω2=0．4，ω3=0．1。筆者采用分枝定界法，在Lingo軟件環(huán)境里對(duì)其編程仿真，可以得到一個(gè)Pareto解。

實(shí)驗(yàn)結(jié)果:評(píng)價(jià)函數(shù)值是3．451815;每臺(tái)設(shè)備的 Wj、Wj'λj以及 ρj值如表 4;單元構(gòu)建結(jié)果與路徑選擇結(jié)果如表5 所列，工件1、2、3、5、6、8、9 選擇加工路徑1，工件4、7、10選擇加工路徑2;單元服務(wù)強(qiáng)度如表6所列。

表 4 設(shè)備的 ρj、W j'、W j和 λj值

從圖表4～6可看出，通過該模型能夠較好的構(gòu)建單元并選出加工路徑。通過優(yōu)化設(shè)備服務(wù)強(qiáng)度范圍，工件通過系統(tǒng)的時(shí)間也得到了優(yōu)化。單元服務(wù)強(qiáng)度與單元內(nèi)的設(shè)備種類、設(shè)備服務(wù)率、工件種類、工件到達(dá)率等息息相關(guān)，通過模型優(yōu)化，三個(gè)單元的服務(wù)強(qiáng)度也處于相近的范圍內(nèi)。針對(duì)這個(gè)算例，筆者通過改變單元數(shù)等相關(guān)等參數(shù)進(jìn)行了多次求解，結(jié)果表明劃分三個(gè)單元時(shí)評(píng)價(jià)函數(shù)值最小。

表5 單元構(gòu)建結(jié)果矩陣

表6 單元服務(wù)強(qiáng)度

4 結(jié)語

研究了如何利用排隊(duì)理論解決單元制造系統(tǒng)的單元構(gòu)建與工件加工路徑選擇問題。構(gòu)造了以最小化加工成本與等待成本、最小化設(shè)備與單元服務(wù)強(qiáng)度范圍(設(shè)備、單元負(fù)荷均衡)為目標(biāo)的多目標(biāo)非線性0-1整數(shù)規(guī)劃模型，采用線性加權(quán)和法將多目標(biāo)問題轉(zhuǎn)換為一個(gè)評(píng)價(jià)函數(shù)，模型求解用分枝定界法。最后在Lingo12平臺(tái)上驗(yàn)證了一個(gè)隨機(jī)算例，實(shí)驗(yàn)結(jié)果證明該模型能夠?qū)崿F(xiàn)單元構(gòu)建、工件加工路徑選擇、優(yōu)化設(shè)備服務(wù)強(qiáng)度與單元服務(wù)強(qiáng)度的目標(biāo)，達(dá)到了預(yù)期效果。

筆者采用的排隊(duì)基本模型是M/M/1形式，實(shí)際上當(dāng)工件到達(dá)分布與設(shè)備服務(wù)時(shí)間分布是一般情形時(shí)，文中所建模型也同樣適用。但是所建模型是基于不受單元內(nèi)與單元間布局方式的影響假設(shè)，針對(duì)這個(gè)問題，如何完善模型并應(yīng)用啟發(fā)式算法求解大規(guī)模問題還有待深入。

［1］ 吳曉丹，王云峰，朱昭杰，等．單元制造系統(tǒng)集成建模研究［J］．計(jì)算機(jī)集成制造系統(tǒng)，2000，6(2):36-40．

［2］ Jabal AmeliM S，Moshref JavadiM．Concurrent Cell Formation and layout Design using Scatter ssearch［J］．International Journal of Advanced Technology，2014，71(1/4):1-22．

［3］ Raminfar R，Zulkifli N，Vasili M，etal．An Integrated Model of Production Planning and Cell Formation in Cellular Manufacturing Systems［J］．Journal of Applied Mathematics，2013:1-10．

［4］ Asgharpour M J，Javadian N．Solving a Stochastic Cellular Manufacturing Model by Using Genetic Algorithms［J］．International Journal of Engineering，Transactions A:Basics，2004，17(2):145-155．

［5］ Buzacott JA，Shanthikumar JG．Design of Manufacturing Systems using Queuing Models［J］．Queuing Systems:Theory and Applications，1992，12(1/2):135-213．

［6］ Arghish O，AzadiS，Anvari A，etal．Cellular Manufacturing System design with Queuing Approach［J］．Journal of Basic and Applied Scientific Research，2012，2(11):11884-11890．

［7］ 熊 偉．運(yùn)籌學(xué)［M］．北京:機(jī)械工業(yè)出版社，2005．

［8］ Salvendy G(著)．鄭 立，李從東(譯)．工業(yè)工程手冊(cè)［M］．北京:清華大學(xué)出版社，2005．

［9］ 曾 勇，董麗華，馬建峰．排隊(duì)現(xiàn)象的建模、解析與模擬［M］．西安:西安電子科技大學(xué)出版社，2011．