可重入柔性流水車間有限緩沖區(qū)容量動(dòng)態(tài)預(yù)留方法

韓忠華 ,劉約翰?,史海波

(1.中國(guó)科學(xué)院網(wǎng)絡(luò)化控制系統(tǒng)重點(diǎn)實(shí)驗(yàn)室,遼寧沈陽(yáng) 110016;2.中國(guó)科學(xué)院沈陽(yáng)自動(dòng)化研究所,遼寧沈陽(yáng) 110016;3.中國(guó)科學(xué)院機(jī)器人與智能制造創(chuàng)新研究院,遼寧沈陽(yáng) 110169;4.中國(guó)科學(xué)院大學(xué),北京 100049;5.沈陽(yáng)建筑大學(xué)信息與控制工程學(xué)院,遼寧沈陽(yáng) 110168)

1 引言

在客車制造和半導(dǎo)體生產(chǎn)等關(guān)鍵制造行業(yè)中,其多芯片半導(dǎo)體封裝線的鍵合工序段和客車生產(chǎn)線的多遍彩條工序段,存在一種具有可重入工序的有限緩沖區(qū)柔性流水車間排產(chǎn)(reentrant flexible flow-shop with limited buffer scheduling,RFFLBS)問(wèn)題.由于可重入工序的存在,會(huì)使工件的加工路徑更加復(fù)雜,又由于有限緩沖區(qū)的存在,更增加了局部任務(wù)指派和資源調(diào)度的難度.在生產(chǎn)過(guò)程中,執(zhí)行可重入工序的工件會(huì)再次折返進(jìn)入該重入工序所對(duì)應(yīng)的緩沖區(qū),若該緩沖區(qū)為有限緩沖區(qū),則來(lái)自前道工序完工的工件與折返重入的工件將爭(zhēng)奪緩沖區(qū)資源,如果該緩沖區(qū)中存儲(chǔ)的工件數(shù)量達(dá)到其容量上限,前道工序的工件無(wú)法進(jìn)入該緩沖區(qū),導(dǎo)致前道工序發(fā)生阻塞,同時(shí),本應(yīng)折返重入該緩沖區(qū)的工件,也由于緩沖區(qū)無(wú)空閑緩沖車位而被滯留在其當(dāng)前的完工工位上,導(dǎo)致后道工序也發(fā)生了生產(chǎn)阻塞,前、后道工序同時(shí)發(fā)生阻塞時(shí)會(huì)產(chǎn)生一種很難自解的生產(chǎn)阻塞現(xiàn)象即死鎖現(xiàn)象,嚴(yán)重的情況下會(huì)使得整個(gè)生產(chǎn)進(jìn)程停滯.由于會(huì)出現(xiàn)死鎖現(xiàn)象,這進(jìn)一步增大了排產(chǎn)的不確定性,提高了生產(chǎn)排產(chǎn)難度,較一般柔性流水車間排產(chǎn)問(wèn)題更為復(fù)雜.

為研究RFFLBS,可分別從可重入工序和有限緩沖區(qū)兩類問(wèn)題展開(kāi),提取兩類問(wèn)題的特點(diǎn)和特征,分析求解方法和研究進(jìn)展,為更好解決RFFLBS問(wèn)題做好準(zhǔn)備.客車等大體積在制品的生產(chǎn)車間由于受到物理空間的限制,無(wú)法設(shè)置大容量的緩沖區(qū),即緩沖區(qū)容量受限,同時(shí)企業(yè)對(duì)于挖掘現(xiàn)有生產(chǎn)資源潛力、提升生產(chǎn)資源利用率越來(lái)越重視,因此,近年來(lái)具有有限緩沖區(qū)的排產(chǎn)問(wèn)題引起了越來(lái)越多的關(guān)注.Zhang等[1]設(shè)計(jì)了一種結(jié)合差分進(jìn)化的混合方法與一種靈活的緩沖區(qū)服務(wù)策略的方法求解具有有限緩沖區(qū)的柔性流水車間調(diào)度問(wèn)題;Zhao等[2]采用一種改進(jìn)的粒子群算法,該算法通過(guò)在標(biāo)準(zhǔn)粒子群公式添加線性遞減擾動(dòng)項(xiàng),集中資源求解可行解;Tao等[3]提出一種啟發(fā)式算法,并在適當(dāng)時(shí)間使用,以減少具有有限緩沖區(qū)的柔性流水車間的阻塞現(xiàn)象,來(lái)獲得高質(zhì)量的排產(chǎn)結(jié)果;Xie等[4]提出了一種基于變鄰域搜索策略的Memetic算法,并驗(yàn)證了所提算法的有效性;Pan等[5]采用了一種改進(jìn)的混沌和聲算法,該算法在局部搜索中引入概率跳躍,對(duì)解決具有有限緩沖區(qū)的柔性流水車間排產(chǎn)問(wèn)題具有很好的效果.同時(shí),在客車制造、半導(dǎo)體封裝等行業(yè)中還廣泛存在一類具有可重入工序的柔性流水車間,依據(jù)加工流程被加工工件需多次進(jìn)入可重入工序段加工.隨著產(chǎn)品種類的增多和產(chǎn)品批量的增大,工件的遷移和加工過(guò)程中相互之間的影響和制約進(jìn)一步加劇,使得排產(chǎn)過(guò)程中的不確定性增加.因此,具有可重入工序的柔性流水車間排產(chǎn)問(wèn)題也成為近些年學(xué)者研究的熱點(diǎn)問(wèn)題.Hekmatfar等[6]提出了以最小最大完工時(shí)間為目標(biāo)的一種偏隨機(jī)密鑰混合遺傳算法,用于求解兩階段的具有可重入工序排產(chǎn)問(wèn)題;Xie等[7]針對(duì)車間具有可重入工序段車間排產(chǎn)問(wèn)題,提出了兩種可能解決問(wèn)題的情況并等效成兩階段混合流水車間問(wèn)題進(jìn)行求解;Zhou和Zhong[8]采用一種基于松弛機(jī)器能力約束的拉格朗日松弛算法,求解可重入混合流水車間排產(chǎn)問(wèn)題;Topaloglu和Kilincli[9]提出了一種改進(jìn)的瓶頸轉(zhuǎn)換啟發(fā)式算法,將問(wèn)題分解成多個(gè)單機(jī)問(wèn)題進(jìn)行求解;Chen等[10]針對(duì)具有可重入工序排產(chǎn)問(wèn)題,提出一種快速粒子群優(yōu)化算法來(lái)提高求解大規(guī)模數(shù)據(jù)效率.當(dāng)前,大部分學(xué)者對(duì)具有有限緩沖區(qū)和具有可重入工序的排產(chǎn)問(wèn)題分別進(jìn)行單獨(dú)研究,并都從全局優(yōu)化算法角度求解這些問(wèn)題,少有學(xué)者對(duì)兩類問(wèn)題并存的生產(chǎn)車間排產(chǎn)問(wèn)題進(jìn)行研究.

死鎖現(xiàn)象是一種由于嚴(yán)重生產(chǎn)阻塞而導(dǎo)致的生產(chǎn)停滯現(xiàn)象,如果不對(duì)死鎖現(xiàn)象進(jìn)行控制,會(huì)給生產(chǎn)企業(yè)的日常生產(chǎn)帶來(lái)巨大影響,嚴(yán)重制約生產(chǎn)進(jìn)程,增加了生產(chǎn)管控的難度.邢科義等[11]通過(guò)將死鎖避免策略嵌入到粒子群算法中,提出一種無(wú)死鎖改進(jìn)粒子群調(diào)度算法,去除解中可能導(dǎo)致死鎖現(xiàn)象出現(xiàn)的加工序列,避免死鎖現(xiàn)象出現(xiàn);Xing等[12]建立了一種無(wú)死鎖遺傳調(diào)度算法,設(shè)計(jì)一種具有多項(xiàng)式復(fù)雜性的死鎖避免策略(deadlock avoidance policy,DAP),采用DAP對(duì)遺傳算法中的染色體的可行性進(jìn)行檢測(cè)與修復(fù),來(lái)獲得可行解;Fan等[13]提出了一種改進(jìn)遺傳算法,通過(guò)判斷轉(zhuǎn)換觸發(fā)條件來(lái)檢驗(yàn)和修正算法中染色體即生產(chǎn)序列的可行性,使每個(gè)染色體都能被解碼成一個(gè)可行的調(diào)度序列,避免死鎖現(xiàn)象的出現(xiàn).當(dāng)前學(xué)者對(duì)于死鎖問(wèn)題,更多是從全局優(yōu)化的角度開(kāi)展研究,多數(shù)采用改進(jìn)的群體進(jìn)化算法,通過(guò)增加算法的相應(yīng)規(guī)則,去除可能產(chǎn)生死鎖的解,來(lái)解決死鎖問(wèn)題,但是這類方法會(huì)隨著需求產(chǎn)能增加,可行解將迅速減少,當(dāng)需求產(chǎn)能與提供產(chǎn)能達(dá)到一定比例時(shí)將無(wú)法得到可行解,通過(guò)在所有解中篩選可行解的方法也極大增加了運(yùn)算的時(shí)間成本,因此當(dāng)前死鎖問(wèn)題的這類解決方法不適合在實(shí)際工程項(xiàng)目中應(yīng)用.

通過(guò)對(duì)近年來(lái)相關(guān)研究文獻(xiàn)的分析,目前少有學(xué)者開(kāi)展對(duì)RFFLBS問(wèn)題進(jìn)行系統(tǒng)的研究,也少有學(xué)者對(duì)RFFLBS中出現(xiàn)的死鎖現(xiàn)象進(jìn)行更深入的探索,也沒(méi)有從控制工件在緩沖區(qū)分配過(guò)程中降低死鎖現(xiàn)象出現(xiàn)的概率的角度,來(lái)探索解決RFFLBS中出現(xiàn)死鎖現(xiàn)象的方法.

若能利用歷史生產(chǎn)數(shù)據(jù)對(duì)未來(lái)可能出現(xiàn)的死鎖現(xiàn)象進(jìn)行預(yù)測(cè),干預(yù)生產(chǎn)任務(wù)在各工序的移動(dòng),保證緩沖區(qū)資源的合理分配,避免死鎖現(xiàn)象的發(fā)生,則無(wú)需為車間配置冗余的緩沖區(qū)資源和對(duì)已配置在車間中的緩沖區(qū)資源進(jìn)行大規(guī)模的調(diào)整,對(duì)于節(jié)約生產(chǎn)資源、降低企業(yè)的整體生產(chǎn)成本具有重要意義.

為解決死鎖現(xiàn)象,本文提出一種基于馬爾可夫鏈的有限緩沖區(qū)動(dòng)態(tài)容量預(yù)留方法(dynamic buffer reservation method based on Markov chain,DBRMMC).該方法根據(jù)歷史生產(chǎn)數(shù)據(jù),通過(guò)運(yùn)用馬爾可夫鏈預(yù)測(cè),計(jì)算并預(yù)測(cè)緩沖資源釋放的概率.根據(jù)預(yù)測(cè)結(jié)果對(duì)局部調(diào)度過(guò)程進(jìn)行干預(yù),將折返執(zhí)行可重入工序的工件預(yù)留緩沖區(qū)容量,減少工件對(duì)緩沖區(qū)資源的爭(zhēng)奪,降低死鎖現(xiàn)象出現(xiàn)的概率.研究?jī)?nèi)容與以往研究工作不同之處在于: 1)深入分析RFFLBS過(guò)程中死鎖現(xiàn)象,找到死鎖現(xiàn)象產(chǎn)生的原因;2)通過(guò)調(diào)度緩沖區(qū)資源來(lái)干預(yù)局部指派過(guò)程,避免對(duì)生產(chǎn)線已配置資源進(jìn)行大規(guī)模重新調(diào)整和擴(kuò)充的前提下,就可以有效的克服死鎖現(xiàn)象,并獲得較好的排產(chǎn)結(jié)果;3)提出DBRMMC方法,通過(guò)預(yù)測(cè)生產(chǎn)過(guò)程中出現(xiàn)死鎖現(xiàn)象時(shí)生產(chǎn)線的生產(chǎn)運(yùn)作狀態(tài),提前為執(zhí)行重入工序的工件預(yù)留緩沖區(qū)容量,并對(duì)該方法進(jìn)行改進(jìn),引入基于自適應(yīng)閾值二值化算法的偏差補(bǔ)償措施,結(jié)合基于高響應(yīng)比優(yōu)先算法(highest response ratio next,HRRN)的局部指派方法,提出一種改進(jìn)的基于馬爾可夫鏈的有限緩沖區(qū)容量動(dòng)態(tài)預(yù)留方法(improved DBRMMC with local dispatching rule based on HRRN,IDBRMMC-HRRN).

2 問(wèn)題描述

2.1 問(wèn)題描述

LBRFFS問(wèn)題可描述如下: 存在n個(gè)工件的待加工隊(duì)列{J1,J2,···,Jn},需經(jīng)過(guò)m道工序的加工,其中,nrm道為非可重入工序,在非可重入工序段內(nèi);rm道為可重入工序,在可重入工序段內(nèi),每道工序都由一組數(shù)量不完全相同但相同型號(hào)的并行機(jī)(工位)組成.每個(gè)并行機(jī)代表一個(gè)工位,每個(gè)工位同一時(shí)刻只能加工一個(gè)工件.受生產(chǎn)資源約束的影響,緩沖區(qū)只能容納有限數(shù)量的工件.工件依據(jù)對(duì)應(yīng)工藝流程順序經(jīng)過(guò)指定的工序進(jìn)行加工,工件在重入工序中至少加工一次,每個(gè)工件有不同的重入次數(shù)rtsi(工件Ji總共被加工nrm+rm×rtsi次).工件每經(jīng)過(guò)一道工序,需選擇一個(gè)工位進(jìn)行加工,完工后移出至對(duì)應(yīng)的緩沖區(qū)存放.當(dāng)后道序工位空閑時(shí)依據(jù)局部指派方法選擇工件進(jìn)行加工.所有工件至少執(zhí)行一次可重入工序段中全部可重入工序.需執(zhí)行可重入工序的工件,在遍歷可重入工藝段后,需重新進(jìn)入指定工序?qū)?yīng)的緩沖區(qū)中等待加工.排產(chǎn)結(jié)果要確定工件的工位分配、加工順序以及工件依據(jù)工藝流程在每個(gè)工序的開(kāi)工時(shí)間、完工時(shí)間.RFFLBS模型示意圖如圖1所示.

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

2.2.1 模型參數(shù)

n: 工件總數(shù);

Ji: 第i個(gè)工件,i ∈{1,···,n};

t: 生產(chǎn)加工過(guò)程中某時(shí)刻;

rm: 可重入工序數(shù);

nrm: 非可重入工序數(shù);

m: 總工序數(shù),m=nrm+rm;

Oj: 第j道工序j ∈{1,···,m};

Mj:Oj中包含的工位數(shù),j ∈{1,···,m};

Wj,k:Oj中第k個(gè)工位,j ∈{1,···,m},k ∈{1,···,Mj};

Bj:Oj對(duì)應(yīng)的緩沖區(qū),j ∈{2,···,m};

Bcj:Bj的最大緩沖容量,j ∈{2,···,m};

bj,p:Bj的第p個(gè)緩沖車位,j ∈{2,···,m},p ∈{1,2,···,Bcj};

FLi:Ji的工藝流程,即Ji需經(jīng)遍歷工序的集合,i ∈{1,···,n};

rtsi:Ji遍歷可重入工序段次數(shù),i ∈{1,···,n};

fmi:FLi中Ji經(jīng)過(guò)的工序總數(shù),fmi≥m;

li:Ji執(zhí)行的工序在FLi中順序號(hào),li ∈{1,···,fmi};

2.2.2 假設(shè)變量

2.2.3 約束條件

在前文設(shè)置的模型參數(shù)和假設(shè)變量下建立數(shù)學(xué)公式,通過(guò)數(shù)學(xué)公式描述在生產(chǎn)過(guò)程中各變量間的約束關(guān)系,從而反映RFFLBS問(wèn)題的過(guò)程及特點(diǎn).其中,約束1–5為柔性流水車間約束,影響工件在生產(chǎn)線中如何遷移;約束6–9為有限緩沖區(qū)約束,影響工件進(jìn)出緩沖區(qū)和工位;約束10–12為其他約束,保證生產(chǎn)過(guò)程具有合理性.

1)約束1.

工件在后道工序開(kāi)始加工時(shí)間大于等于前道工序結(jié)束加工時(shí)間;

3)約束3.

每經(jīng)歷道工序工件只能選擇一個(gè)工位進(jìn)行加工;

4)約束4.

工件需依據(jù)工藝流程遍歷全部包含的工序;

5)約束5.

工件經(jīng)過(guò)工序總數(shù)等于經(jīng)過(guò)的非可重入工序與可重入工序次數(shù)之和;

6)約束6.

工序Oj的等待加工隊(duì)列包含t時(shí)刻在對(duì)應(yīng)緩沖區(qū)Bj中所有的工件;

7)約束7.

在任意時(shí)刻t,待加工隊(duì)列WAj(t)中的工件數(shù)小于等于緩沖區(qū)Bj的最大緩沖區(qū)容量Bcj;

8)約束8.

在忽略轉(zhuǎn)運(yùn)時(shí)間的前提下,Ji從前道工序移出的時(shí)刻等于其進(jìn)入緩沖區(qū)的時(shí)刻,且該時(shí)刻大于等于在前道工序的完工時(shí)間;

9)約束9.

式(9)中,當(dāng)工件Ji從緩沖區(qū)的加工列隊(duì)中進(jìn)入加工工序Oj時(shí)便立即開(kāi)始加工;

10)約束10.

不可中斷約束: 如果工件在工位上已開(kāi)始加工,則不能中斷,直到完成在該工位的生產(chǎn)過(guò)程;

11)約束11.

工位唯一性約束: 一個(gè)工位在同一時(shí)刻只能加工一道工序;

12)約束12.

工位可用性約束: 所有工位在調(diào)度時(shí)刻都是空閑可用的.

2.3 阻塞與自解阻塞現(xiàn)象分析

由于在具有有限緩沖區(qū)的柔性流水車間的生產(chǎn)線上,只能設(shè)置容量有限的緩沖區(qū),當(dāng)工件完成在前道工序的加工任務(wù)時(shí),該工件可能會(huì)因無(wú)空閑緩沖車位而滯留在前道工序的工位上,影響生產(chǎn)線的局部生產(chǎn)過(guò)程,造成阻塞現(xiàn)象.若隨著生產(chǎn)過(guò)程的繼續(xù),后道工序中有工件完工并從工位移出,緩沖區(qū)中待加工工件能夠進(jìn)入后道工序執(zhí)行加工任務(wù),此時(shí)緩沖區(qū)資源得到釋放,被阻塞的工件可從前道工序移入緩沖區(qū),即自解阻塞.如果無(wú)法自解阻塞則會(huì)導(dǎo)致死鎖現(xiàn)象.通過(guò)分析生產(chǎn)阻塞現(xiàn)象的形成,進(jìn)一步討論自解阻塞的條件,進(jìn)而分析和得出死鎖現(xiàn)象的產(chǎn)生的原因和條件.

例如可重入工序段中包含2個(gè)工序且均為3個(gè)工位,緩沖區(qū)容量為2舉例,如圖2所示,在可重入工序段存在阻塞,當(dāng)系統(tǒng)運(yùn)行至?xí)r刻t,Ord中存在完成可重入工序段加工的工件,依據(jù)其工藝流程離開(kāi)可重入工序段,因此Ord中出現(xiàn)空閑Wrd,2,依據(jù)局部指派方法,Brd中的工件競(jìng)爭(zhēng)Wrd,2,Brd出現(xiàn)空余,Oru中完工工件可以進(jìn)入Brd,即自解阻塞現(xiàn)象.

圖2 自解阻塞現(xiàn)象示意圖Fig.2 Diagram of self-unblocking phenomenon

RFFLBS中生產(chǎn)阻塞現(xiàn)象的數(shù)學(xué)模型為

其中:WSS(t)j,k表示t時(shí)刻可重入工序中工位的加工狀態(tài),當(dāng)工位處于被占用狀態(tài)時(shí),值取為1;并行工位數(shù)Mj在可重入生產(chǎn)工序取值為Mj ∈{Mrd,Mru};b表示t時(shí)刻,可重入生產(chǎn)工序的緩沖區(qū)中的工件數(shù);Bcj表示可重入生產(chǎn)工序緩沖區(qū)的最大容量.

式(10)在t時(shí)刻,可重入工序中的工位都處于被占用狀態(tài);式(11)在t時(shí)刻,緩沖區(qū)中存放的工件數(shù)達(dá)到最大容量;式(12)在t時(shí)刻,存在已完工的工件Ji,其將進(jìn)入可重入工序Oru進(jìn)行生產(chǎn).

RFFLBS過(guò)程中自解阻塞現(xiàn)象的數(shù)學(xué)模型為

式(13)表示在Ord中存在不需要進(jìn)入可重入工序段的工件;式(14)表示在t時(shí)刻Ord中存在空閑工位.

2.4 死鎖現(xiàn)象分析

假設(shè)場(chǎng)景,在t時(shí)刻,假設(shè)工序Oru,Ord中所有工位都處在加工狀態(tài),且緩沖區(qū)Bru,Brd均被占滿,若順序發(fā)生事件1–6則會(huì)出現(xiàn)死鎖現(xiàn)象,如圖3所示.

圖3 死鎖現(xiàn)象示意圖Fig.3 Diagram of deadlock

事件1依據(jù)其工藝流程J8完成了在Ord中的加工,將進(jìn)入Bru中的緩沖車位等待加工;

事件2在事件1發(fā)生的時(shí)候,工件J8不能進(jìn)入緩沖區(qū)Bru,導(dǎo)致J8停留在當(dāng)前工位Wrd,1上發(fā)生阻塞,Brd中的工件無(wú)法進(jìn)入Wrd,1中加工;

事件3在事件1和2發(fā)生后,J9完成當(dāng)前工序的加工,根據(jù)J9的工藝流程,將再次進(jìn)入可重入工序段的工序Oru;

事件4J9所在的工位Wrd,2發(fā)生阻塞;

事件5在事件3和事件4發(fā)生后J10完成當(dāng)前工序的加工,根據(jù)J10的工藝流程,也將再次進(jìn)入可重入工序段的工序Oru進(jìn)行加工;

事件6J10所在的工位Wrd,3發(fā)生阻塞.

由于發(fā)生連續(xù)的阻塞,且在可重入工序段中的工位和對(duì)應(yīng)的緩沖區(qū)均不會(huì)因生產(chǎn)進(jìn)程的繼續(xù)而釋放資源,導(dǎo)致工件在生產(chǎn)線中無(wú)法移動(dòng),致使生產(chǎn)停滯,最終導(dǎo)致死鎖現(xiàn)象發(fā)生.

數(shù)學(xué)模型描述和分析t時(shí)刻死鎖現(xiàn)象如下:

其中: 式(15)表示在t時(shí)刻可重入工序段中所有工序Oj,j=ru,rd的全部工位均被占用;式(16)表示在t時(shí)刻可重入工序段中所有緩沖區(qū)Bj,j=ru,rd的緩沖車位均被占用;式(17)表示存在等待折返可重入工序段前道工序的待加工工件;式(18)表示在非可重入工序段中存在等待進(jìn)入可重入工序段的待加工工件.

一種特殊情況: 依據(jù)工藝流程,可重入工序段中,當(dāng)最后一道工序工位上的全部工件都需要折返前道工序進(jìn)行加工時(shí),即Ord中的全部工件均滿足條件式(18),則會(huì)導(dǎo)致全部工件滯留在當(dāng)前位置,造成阻塞,如果不采取措施且持續(xù)出現(xiàn)阻塞現(xiàn)象,就會(huì)導(dǎo)致死鎖現(xiàn)象發(fā)生,陷入停滯狀態(tài).

在上述場(chǎng)景發(fā)生之前,如圖4,工序Oru的緩沖區(qū)Bru還剩下一些緩沖區(qū)容量,如果這些緩沖區(qū)容量再被來(lái)自非可重入工序段的工件占用,Bru被完全占滿,接下來(lái)事件1–2再發(fā)生,則會(huì)產(chǎn)生死鎖現(xiàn)象.因此探索解決死鎖現(xiàn)象的方法重點(diǎn)在,如何干預(yù)可重入工序段中第1個(gè)工序?qū)?yīng)緩沖區(qū)資源的使用.

圖4 來(lái)自非可重入工序段工件爭(zhēng)奪緩沖車位Fig.4 The job from non-reentrant process compete for buffer parking spaces

因此,如果能找到預(yù)測(cè)死鎖現(xiàn)象的方法,并采取有效的處理措施,避免死鎖現(xiàn)象發(fā)生,從而避免了生產(chǎn)資源的浪費(fèi),節(jié)約了企業(yè)的整體生產(chǎn)成本.

3 求解RFFLBS排產(chǎn)問(wèn)題的方法

針對(duì)可重入工序段中首道工序,即工件折返執(zhí)行的可重入工序,其工位的狀態(tài)的變化過(guò)程是一種隨機(jī)變化過(guò)程符合馬爾可夫過(guò)程的特性,與近期狀態(tài)有關(guān)而與過(guò)去狀態(tài)無(wú)關(guān),具有無(wú)后效性.故提出DBRMMC,解決在RFFLBS過(guò)程中出現(xiàn)死鎖現(xiàn)象問(wèn)題,并對(duì)DBRMMC方法進(jìn)行進(jìn)一步的改進(jìn),引入基于自適應(yīng)閾值二值化算法的偏差補(bǔ)償措施,結(jié)合HRRN的局部指派方法,提出IDBRMMC-HRRN.

3.1 DBRMMC方法描述

為了能夠?yàn)檎鄯祱?zhí)行可重入工序的工件動(dòng)態(tài)預(yù)留緩沖區(qū)容量,DBRMMC方法通過(guò)預(yù)測(cè)可重入工序段中首道工序中工位加工工件的變化情況,進(jìn)而預(yù)測(cè)對(duì)應(yīng)緩沖區(qū)緩沖車位的釋放概率,根據(jù)計(jì)算結(jié)果判斷是否預(yù)留緩沖區(qū)資源,通過(guò)提前預(yù)留緩沖區(qū)資源,保證折返工件能夠順利進(jìn)入緩沖區(qū).該方法減少了因來(lái)自不同工序段的工件對(duì)緩沖區(qū)資源爭(zhēng)奪而導(dǎo)致嚴(yán)重連續(xù)阻塞對(duì)進(jìn)程的影響,保證能夠順利進(jìn)行排產(chǎn)過(guò)程.具體步驟如下.

步驟1依據(jù)歷史生產(chǎn)數(shù)據(jù)建立馬爾可夫狀態(tài)矩陣.

取單位時(shí)間段t′為全部工件在該工序的工位上加工時(shí)間中位值,建立在t′內(nèi)可重入工序段的首道工序Oj(j=ru)中各工位轉(zhuǎn)移概率矩陣Py(y=1,···,Mru),該矩陣用于預(yù)測(cè)對(duì)應(yīng)緩沖區(qū)Bru資源釋放概率,其中

可重入工序Oru中的工位在單位時(shí)間t′內(nèi)有工件完工并移出,使得存放在緩沖區(qū)Bru中待加工的工件能夠進(jìn)入該工位進(jìn)行加工,Bru中的緩沖車位得到釋放,故以上4種概率可以被視為,在4種情況下時(shí)間段t′內(nèi)緩沖區(qū)車位能否被釋放的概率.

步驟2判斷t時(shí)刻啟動(dòng)馬爾可夫預(yù)測(cè)運(yùn)算.

當(dāng)運(yùn)行狀態(tài)如圖5所示時(shí),如果滿足條件1–5,則執(zhí)行步驟3,否則終止后續(xù)操作.

圖5 t時(shí)刻運(yùn)行狀態(tài)示意圖Fig.5 Diagram of workshopstate at time t

條件1: 非可重入工序段中存在將要進(jìn)入Bru的完工工件Jnrm.

條件2:Bru中僅剩一個(gè)緩沖車位空閑,即=Bcru-1.

條件3: 可重入工序段首道工序Oru中的全部工均為被占用狀態(tài).

條件4: 依據(jù)工藝流程,在可重入工序段末道工序Ord中存在需折返并再次遍歷可重入段的工件.

條件5: 條件1–4均滿足的基礎(chǔ)上可重入工序段首道工序Oru中最先完工JU的完工時(shí)間小于等于末道工序Ord中最先完工JD的完工時(shí)間t2,則繼續(xù)執(zhí)行步驟3,否則執(zhí)行步驟4直接預(yù)留緩沖區(qū).

在圖5中,t1(t1≥t)為可重入工序段首道工序Oru中最先完工的工件JU離開(kāi)Oru的時(shí)間,由于可能存在阻塞現(xiàn)象,t1大于等于;t2為可重入工序段末道工序Ord中最先完工的工件JD離開(kāi)Ord的時(shí)間.

步驟3啟動(dòng)馬爾可夫預(yù)測(cè)運(yùn)算,預(yù)測(cè)緩沖區(qū)資源釋放概率.

在t時(shí)刻采用馬爾科夫鏈計(jì)算未來(lái)t2時(shí)刻工位上加工工件發(fā)生變化的概率向量[P1P2].通過(guò)計(jì)算得出t2時(shí)刻P2,即等價(jià)于Bru的緩沖車位釋放的概率,進(jìn)而動(dòng)態(tài)判斷Bru剩余緩沖車位是否為JD預(yù)留,降低因工件Jnrm爭(zhēng)奪緩沖區(qū)車位而產(chǎn)生死鎖現(xiàn)象的概率.

通過(guò)概率統(tǒng)計(jì)的方法計(jì)算從第1個(gè)工件投產(chǎn)運(yùn)行到t時(shí)刻時(shí),單位時(shí)間t′內(nèi)工位上加工的工件變化的概率向量S0,即

式中:a1與a2均為統(tǒng)計(jì)得出,a1表示從0到t的時(shí)間段內(nèi),中未改變加工其他工件的單位時(shí)間段t′的數(shù)量與包含t′總數(shù)量的比值;a2表示從0到t的時(shí)間段內(nèi),中改變加工其他工件的單位時(shí)間段t′的數(shù)量與包含t′總數(shù)量的比值,即被不同工件占用的概率.

將S0代入式(21)計(jì)算在t2時(shí)刻工位上加工的工件變化的概率向量Sv,即

式中v表示從計(jì)算t時(shí)刻到未來(lái)t2時(shí)刻的時(shí)間段內(nèi)包含t′的數(shù)量.

步驟4根據(jù)計(jì)算結(jié)果判別是否預(yù)留.

如果P1≥P2,則為將要折返工件預(yù)留緩沖車位,禁止來(lái)自非可重入工序的工件Jnrm進(jìn)入可重入工序段;如果P1

當(dāng)P1較大時(shí),表示在未來(lái)t2時(shí)刻工位一直處于被同一工件占用,加工不同工件的概率較低,即在t2之前Bru中存放工件進(jìn)入前道工序Oru的工位概率較低,Bru的緩沖車位難以被釋放.若在期間允許非可重工序段中先完工的工件Jnrm進(jìn)入Bru中,搶占了緩沖車位,會(huì)引起阻塞現(xiàn)象,Ord中先完工工件JD滯留在工位上.如果Ord中的所有工件都需要再次遍歷可重入工序段會(huì)引起連續(xù)的生產(chǎn)阻塞現(xiàn)象,最終可能導(dǎo)致死鎖現(xiàn)象發(fā)生.

步驟5依據(jù)判斷結(jié)果,執(zhí)行為即將重入工件預(yù)留緩沖區(qū)剩余車位操作,如圖6所示.

圖6 折返執(zhí)行可重入工序的工件進(jìn)入預(yù)留緩沖區(qū)示意圖Fig.6 Diagram of the reentrant Job entering the reserved buffer parking space

3.2 基于高響應(yīng)比優(yōu)先算法的局部指派方法

不同的局部指派方法也會(huì)影響死鎖現(xiàn)象出現(xiàn)的概率的值,以基于短作業(yè)優(yōu)先算法(shortest job first,SJF)的局部指派方法為例: 在生產(chǎn)過(guò)程的初期,根據(jù)短作業(yè)優(yōu)先規(guī)則,緩沖區(qū)待加工隊(duì)列中,依據(jù)工藝流程擁有更短剩余加工時(shí)間的工件具有更高優(yōu)先權(quán),不易出現(xiàn)阻塞現(xiàn)象(一般情況工件的工藝流程中工序較少剩余加工時(shí)間也越少),但隨著生產(chǎn)進(jìn)程的推進(jìn),該類工件依次完工下線,在生產(chǎn)線中剩余加工時(shí)間長(zhǎng)、需多次執(zhí)行可沖入工序的工件占比增多,由于緩沖區(qū)資源受限,在生產(chǎn)線中易發(fā)生生產(chǎn)阻塞,故死鎖現(xiàn)象出現(xiàn)的概率也可能隨之增大.

高響應(yīng)比優(yōu)先算法(highest response ratio next,HNNR)作為局部規(guī)則既考慮作業(yè)的執(zhí)行時(shí)間也兼顧了作業(yè)的等待時(shí)間,綜合了短作業(yè)優(yōu)先算法和先到先服務(wù)算法(first come first service,FCFS) 的特點(diǎn).基于高響應(yīng)比優(yōu)先算法的局部指派方法屬于一種非搶占式優(yōu)先權(quán)調(diào)度方法,高響應(yīng)比是指作業(yè)等待時(shí)間與未運(yùn)行時(shí)間的比值,一旦把工位分配給緩沖區(qū)待加工隊(duì)列中具有最高優(yōu)先權(quán)(比值)的待加工任務(wù),則該加工任務(wù)便一直執(zhí)行下去直至完成,定義如下.

系統(tǒng)運(yùn)行到t時(shí)刻時(shí)有

其中: 式(22)中TW表示Ji在當(dāng)前所在的緩沖區(qū)中等待加工的時(shí)間;式(23)中TR表示Ji依據(jù)其工藝流程FLi執(zhí)行加工過(guò)程的剩余的加工時(shí)間;式(24)KR表示此刻Ji對(duì)應(yīng)的響應(yīng)比值,且比值大于等于1.

基于高響應(yīng)比優(yōu)先算法的局部指派方法具有以下特點(diǎn): 1)當(dāng)工件在待加工隊(duì)列中等待相同時(shí)間時(shí),具有越短剩余加工時(shí)間的工件優(yōu)先權(quán)越高,即有利于短作業(yè);2)當(dāng)在等待加工隊(duì)列中的工件具有相同的剩余加工時(shí)間時(shí),工件的等待時(shí)間越長(zhǎng)優(yōu)先權(quán)越高,即先進(jìn)先出;3)工件的優(yōu)先權(quán)會(huì)隨著其在待加工隊(duì)列中等待時(shí)間的增加而增大,如果工件等待時(shí)間較長(zhǎng),則工件的優(yōu)先權(quán)受等待時(shí)間影響更大,優(yōu)先權(quán)隨之增大,便有利于長(zhǎng)作業(yè).

因此,該方法通過(guò)計(jì)算和比較工件的響應(yīng)比來(lái)確定待加工隊(duì)列中工件的指派優(yōu)先權(quán),即考慮短作業(yè)又考慮工件的抵達(dá)順序,同時(shí)又不會(huì)使得部分工件因長(zhǎng)時(shí)間等待而無(wú)法進(jìn)入工位加工,是一種折衷的局部指派方法.

3.3 DBRMMC的改進(jìn)

DBRMMC中采用馬爾科夫鏈進(jìn)行預(yù)測(cè)運(yùn)算,由于概率統(tǒng)計(jì)誤差、計(jì)算誤差等原因,通過(guò)預(yù)測(cè)模型所計(jì)算出的概率可能出現(xiàn)偏差,會(huì)導(dǎo)致Jnrm進(jìn)入緩沖區(qū)Bru,搶占唯一資源,面對(duì)復(fù)雜度較高的排產(chǎn)過(guò)程,即使采用了DBRMMC方法排產(chǎn)過(guò)程依舊可能產(chǎn)生死鎖現(xiàn)象.為避免此類預(yù)測(cè)偏差的出現(xiàn),引入自適應(yīng)閾值二值化改進(jìn)DBRMMC方法,提出一種DBRMMC方法的改進(jìn)方法IDBRMMC,為計(jì)算出的預(yù)測(cè)結(jié)果進(jìn)行偏差補(bǔ)償.

在步驟4中,若判斷結(jié)果為P1

如果P1>P2且r1>α,不必對(duì)步驟4的結(jié)果進(jìn)行偏差補(bǔ)償,則緩沖區(qū)Bru剩余車位不為JD預(yù)留;

如果P1>P2且r1≤α,需對(duì)步驟4的結(jié)果進(jìn)行偏差補(bǔ)償(即Jnrm不進(jìn)入Bru,剩余緩沖車位為JD預(yù)留).

當(dāng)α=1時(shí),表示Ord中的工件依據(jù)工藝流程全部需再次遍歷可重入工序段,而r1因其取值范圍一定小于α,所以即使當(dāng)前時(shí)刻的預(yù)測(cè)結(jié)果出現(xiàn)偏差,也可以為即將折返的JD預(yù)留緩沖區(qū)剩余車位,因此,該方法能夠避免預(yù)測(cè)偏差.

4 仿真實(shí)驗(yàn)

采用某客車生產(chǎn)企業(yè)的車間實(shí)例數(shù)據(jù),對(duì)DBRMMC方法的運(yùn)行過(guò)程進(jìn)行分析,分別對(duì)不同規(guī)模的數(shù)據(jù)建立多組仿真方案,進(jìn)行仿真實(shí)驗(yàn).由于目前對(duì)于RFFLBS問(wèn)題的研究仍處于初始階段,針對(duì)該類問(wèn)題的研究很少,尚無(wú)RFFLBS問(wèn)題的標(biāo)準(zhǔn)算例.本文的測(cè)試用例來(lái)自于某大型客車生產(chǎn)企業(yè),采用其涂裝車間多遍貼彩條工序段的生產(chǎn)數(shù)據(jù)來(lái)構(gòu)建,規(guī)模與取值均基于實(shí)際生產(chǎn).

4.1 構(gòu)造仿真數(shù)據(jù)

客車制造企業(yè)的客車涂裝車間工序段包括“粘貼彩條模具”、“車體噴繪上漆”、“車身烘漆”工序,由于每遍彩條只能噴涂一種顏色,若客車涂裝圖案具有多種顏色則需多次噴漆和烘烤,即有有限緩沖區(qū)的特征也有存在可重入工序的工藝流程.

涂裝車間工作人員會(huì)根據(jù)彩條的模板對(duì)不同車體噴繪的圖案分解成多種顏色,依照工藝流程,經(jīng)過(guò)多遍噴繪形成車體圖案,不同車型因噴漆面積、彩條復(fù)雜程度等原因在同一道工序加工工時(shí)不同,客車在每道工序的加工時(shí)長(zhǎng)在5～45 min之間.同時(shí),為了提高生產(chǎn)效率,減少客車在不同工位間的轉(zhuǎn)運(yùn)時(shí)間,“粘貼彩條模具”和“車體噴繪上漆”在統(tǒng)一個(gè)工序的同一個(gè)工位進(jìn)行加工.

因此構(gòu)造仿真數(shù)據(jù)共包含3個(gè)工序,即{O1,O2,O3},其中{O2,O3}模擬涂裝車間的可重入工序,3個(gè)工序的并行工位數(shù)Mj均為3,3個(gè)工序分別擁有對(duì)應(yīng)的緩沖區(qū),即{B1,B2,B3},其中{B1}為無(wú)限緩沖區(qū),{B2,B3}為有限緩沖區(qū),緩沖車位數(shù)量分為Bc2=2,Bc3=3.

4.2 排產(chǎn)評(píng)價(jià)指標(biāo)

1)最大完工時(shí)間.

式(26)表示完成全部加工任務(wù)時(shí)間,即所有工件依據(jù)工藝流程,完成最后一道工序的加工任務(wù)的完工時(shí)間中最大值.

2)總工位加工空閑時(shí)間.

式中TWT表示生產(chǎn)線中包含的全部工位的加工空閑時(shí)間之和,即工位加工第1個(gè)工件的開(kāi)始到最后1個(gè)工件的完工期間的空閑時(shí)間.

3)總工件阻塞時(shí)間.

式中TPB表示所有工件在加工完成后,滯留在工位的時(shí)間之和.

4)總設(shè)備利用率.

式中FUR表示生產(chǎn)線中包含的全部工位的總設(shè)備利用率,即全部工位的有效加工時(shí)間與全部工位被占用時(shí)間之比.

5)出現(xiàn)死鎖現(xiàn)象概率.

式中DLP表示E次仿真實(shí)驗(yàn)中死鎖現(xiàn)象的概率.

4.3 排產(chǎn)結(jié)果仿真與對(duì)比分析

4.3.1 實(shí)例分析DBRMMC方法運(yùn)行過(guò)程

首先采取一組數(shù)據(jù)進(jìn)行測(cè)試并舉例分析,其中工件總數(shù)n=15,即投產(chǎn)客車數(shù),對(duì)應(yīng)工件的重入次數(shù){rts1,rts2,···,rts15}={5,5,4,4,4,4,3,3,3,3,3,3,2,2,1},采用基于先到先服務(wù)(FCFS)算法的局部指派方法.具體工藝流程如圖7–8所示,加工時(shí)間如表1所示.

表1 工件遍歷各工序時(shí)的加工時(shí)間(單位: min)Table 1 The processing time of the job in the process(min)

圖7 當(dāng)出現(xiàn)死鎖現(xiàn)象時(shí)排產(chǎn)結(jié)果甘特圖Fig.7 Gantt chart when deadlock occurs

圖7是未采用DBRMMC 方法的RFFLBS 排產(chǎn)結(jié)果,圖8是采用DBRMMC方法控制工件局部指派過(guò)程的RFFLBS排產(chǎn)結(jié)果,圖7–8中Gantt圖的橫坐標(biāo)是時(shí)間軸,縱坐標(biāo)表示的是每個(gè)工序的工位以及每個(gè)緩沖區(qū)的車位.圖中綠色表示客車在緩沖區(qū)停留時(shí)間,紅色代表加工客車滯留在加工工位上的阻塞時(shí)間.

圖8 加入方法后無(wú)死鎖現(xiàn)象排產(chǎn)結(jié)果甘特圖Fig.8 Gantt chart without deadlock after using DBRMMC

如圖7所示,t=122時(shí),工件J6,J8和J15已經(jīng)完成在O1中的加工任務(wù),準(zhǔn)備進(jìn)入可重入工序O2的緩沖區(qū)B2,B2中存放著工件{J1,J5},B2的容量Bc2=3,B2中有且僅有一個(gè)空閑緩沖車位,O2中的工位均處于被占用狀態(tài),在O3的工位上存在將要折返執(zhí)行O2的{J4,J13,J14},O2中最先完工的J3的預(yù)計(jì)完工時(shí)間C3,2,2=128小于O3中最先完工的J14的預(yù)計(jì)完工時(shí)間C14,3,1=132,滿足DBRMMC方法步驟2中啟動(dòng)馬爾可夫鏈預(yù)測(cè)運(yùn)算及執(zhí)行后續(xù)預(yù)留判斷步驟的條件.

假設(shè)在t=122 時(shí)不啟用DBRMMC方法,當(dāng)t=132時(shí),在工位W3,1中完成了加工的J14,根據(jù)其工藝流程需要折返進(jìn)入B2中,由于在此之前沒(méi)有為J14預(yù)留B2的容量,在t=122時(shí),B2已經(jīng)被占滿,所以J14滯留在W3,1中,發(fā)生生產(chǎn)阻塞,B3中的工件無(wú)法進(jìn)入O3中進(jìn)行加工.隨著時(shí)間推移,工件{J13,J4}因B2已經(jīng)被占滿無(wú)法折返滯留{W3,3,W3,1}.當(dāng)運(yùn)行到t=148時(shí),所有工件都被阻塞在當(dāng)前位置上,這種嚴(yán)重阻塞的情況無(wú)法隨著時(shí)間自解阻塞.從t=122時(shí)開(kāi)始出現(xiàn)前文第1.4節(jié)中的死鎖現(xiàn)象事件所描繪的場(chǎng)景,整個(gè)生產(chǎn)進(jìn)程完全停滯,即出現(xiàn)死鎖現(xiàn)象.

如果在t=122 時(shí)啟用DBRMMC 方法,圖8所示,馬爾可夫鏈預(yù)測(cè)運(yùn)算得出概率向量

W2,2上有工件完工并移出的概率P2=0.785621143大于無(wú)工件完工并移出的概率P1=0.214378857,依據(jù)步驟3中的判別條件為J14預(yù)留B2容量,令工件J15在工位W1,2中等待,當(dāng)t=132 時(shí),工件J3進(jìn)入預(yù)留緩沖車位b2,3中,避免了死鎖現(xiàn)象的出現(xiàn),保證排產(chǎn)順利進(jìn)行,故采用DBRMMC方法干預(yù)工件在緩沖區(qū)的指派過(guò)程,可以減少死鎖現(xiàn)象的發(fā)生.DBRMMC中采用馬爾科夫鏈進(jìn)行預(yù)測(cè)運(yùn)算,由于存在概率統(tǒng)計(jì)誤差、計(jì)算誤差等原因,因此通過(guò)預(yù)測(cè)模型所計(jì)算出的概率可能出現(xiàn)偏差.

4.3.2 IDBRMMC方法降低死鎖現(xiàn)象出現(xiàn)的概率仿真結(jié)果與分析

共設(shè)計(jì)7組仿真方案:方案1采用傳統(tǒng)的排產(chǎn)方法,默認(rèn)采用FCFS先到先服務(wù)調(diào)度算法進(jìn)行局部指派;方案2在方案1的基礎(chǔ)上加入DBRMMC方法;方案3在方案2的基礎(chǔ)上引入補(bǔ)償措施,這3組方案?jìng)?cè)重于討論DBRMMC方法以及加入偏差補(bǔ)償對(duì)死鎖現(xiàn)象的影響;其余4組方案分別引入基于SJF短作業(yè)優(yōu)先算法的局部指派規(guī)則以及基于RHHN高響應(yīng)比優(yōu)先調(diào)度算法局的部指派規(guī)則,并測(cè)試DBRMMC方法在不同的局部指派規(guī)則下對(duì)于RFFSP排產(chǎn)過(guò)程中降低死鎖出現(xiàn)概率的效果.仿真方案信息見(jiàn)表2.

表2 仿真方案信息表Table 2 Simulation scheme information table

針對(duì)7組方案采用不同數(shù)據(jù)規(guī)模(投產(chǎn)工件數(shù))進(jìn)行仿真實(shí)驗(yàn),在相同投產(chǎn)工件數(shù)情況下,依據(jù)不同重入次數(shù)的工件數(shù)量的差異構(gòu)建多個(gè)仿真實(shí)例.設(shè)計(jì)統(tǒng)計(jì)變量Po,表示每個(gè)仿真實(shí)例中可重入工件占投產(chǎn)工件數(shù)的比例,如式(31)所示,該比例增加則表示可重入工件數(shù)量的增多.每個(gè)實(shí)例分別進(jìn)行30次仿真實(shí)驗(yàn),每次隨機(jī)生成工件的上線序,工件在工位上加工時(shí)間采用10到30之間隨機(jī)數(shù),統(tǒng)計(jì)7組方案出現(xiàn)死鎖現(xiàn)象的次數(shù)LN和死鎖現(xiàn)象出現(xiàn)的概率PL,結(jié)果表2所示.

如表3所示,總投產(chǎn)工件數(shù)n=10時(shí)沒(méi)有出現(xiàn)死鎖現(xiàn)象,投產(chǎn)工件數(shù)量增加死鎖現(xiàn)象出現(xiàn).總投產(chǎn)工件數(shù)n=15時(shí),方案1由于沒(méi)有采用DBRMMC方法,隨著具有可重入工序的工件數(shù)占總投產(chǎn)工件數(shù)比例Po增加,死鎖概率PL由10.00%增長(zhǎng)到26.67%.若總投產(chǎn)工件數(shù)量n增加,死鎖概率PL也會(huì)增大,n=50時(shí)實(shí)例L和實(shí)例M的死鎖概率PL=100%.故隨著投產(chǎn)工件總數(shù)、可重入工件數(shù)在總工件數(shù)占總投產(chǎn)工件數(shù)比例的增加,死鎖現(xiàn)象出現(xiàn)的概率不斷增大,即隨著加工任務(wù)的需求產(chǎn)能增加,對(duì)緩沖區(qū)資源的競(jìng)爭(zhēng)愈發(fā)激烈,如果不采取一定的措施,排產(chǎn)過(guò)程將無(wú)法正常進(jìn)行.

表3 不同數(shù)據(jù)規(guī)模的加工任務(wù)下RFFLBS過(guò)程中出現(xiàn)死鎖現(xiàn)象及概率統(tǒng)計(jì)表Table 3 The number of occurrences of deadlock and the probability of occurrence of deadlock in RF-FLBS process under different data scale processing tasks

引入DBRMMC方法的方案2對(duì)比方案1,當(dāng)投產(chǎn)工件數(shù)n=20時(shí),實(shí)例G中具有可重入工序的工件數(shù)占總投產(chǎn)工件數(shù)比例P=30.00%的情況下,方案2的死鎖概率PL2,20,G=3.33%比方案1降低30.00%;當(dāng)實(shí)例I的P增加到80.00%時(shí),方案2的死鎖概率PL2,20,I=13.33%比方案1降低53.34%;投產(chǎn)工件數(shù)量n增加到50時(shí),實(shí)例M的死鎖概率達(dá)到了100.00%,排產(chǎn)無(wú)法進(jìn)行,方案2死鎖概率PL2,50,M=36.67%,死鎖概率相較下降63.33%;投產(chǎn)工件數(shù)量n增加到100時(shí),實(shí)例O采用方案2的死鎖概率PL2,100,O=46.67%.可以看出DBRMMC方法的引入可顯著降低RFFLBS排產(chǎn)過(guò)程中死鎖現(xiàn)象出現(xiàn)的概率,在一定的需求產(chǎn)能范圍內(nèi),具有可重入工序工件數(shù)量占總投產(chǎn)工件數(shù)的比例越大,投產(chǎn)工件數(shù)量的越多,效果更明顯.

由表3數(shù)據(jù)可發(fā)現(xiàn),即使引入了DBRMMC方法,實(shí)例I的結(jié)果仍有13.33%的概率出現(xiàn)死鎖現(xiàn)象,而P相同的條件下,投產(chǎn)工件數(shù)n增加到100時(shí),實(shí)例O概率會(huì)增加到46.67%,這是由于馬爾可夫鏈預(yù)測(cè)緩沖區(qū)資源釋放概率可能出現(xiàn)預(yù)測(cè)偏差,導(dǎo)致在RFFLBS排產(chǎn)過(guò)程中仍有死鎖現(xiàn)象出現(xiàn),且死鎖現(xiàn)象出現(xiàn)的概率會(huì)隨著需求產(chǎn)能的增大而進(jìn)一步增大.對(duì)比方案3與方案2的平均死鎖概率可知,加入偏差補(bǔ)償改進(jìn)的IDBRMMC方法能進(jìn)一步降低RFFLBS排產(chǎn)過(guò)程的死鎖現(xiàn)象出現(xiàn)的概率:當(dāng)投產(chǎn)工件數(shù)n=20時(shí),實(shí)例I采用方案3死鎖概率為0.00%,投產(chǎn)工件數(shù)n增加到50時(shí),實(shí)例M采用方案3比采用方案2死鎖概率減少30.00%,而工件數(shù)n=100時(shí),實(shí)例O采用方案3比采用方案2死鎖概率減少40.00%,由此可見(jiàn)在一定的需求產(chǎn)能范圍內(nèi),該方法可以基本消除RFFLBS過(guò)程中出現(xiàn)的死鎖現(xiàn)象,引入偏差補(bǔ)償措施會(huì)進(jìn)一步提升DBRMMC方法在控制RFFLBS排產(chǎn)過(guò)程中出現(xiàn)死鎖現(xiàn)象的概率的效果.

方案5采用基于SJF調(diào)度算法局部指派規(guī)則,在實(shí)例M中死鎖概率為3.33%,低于方案3采用基于FCFS調(diào)度算法局部指派規(guī)則的6.67%,對(duì)比采用不同局部指派方法的方案發(fā)現(xiàn),使用不同的調(diào)度算法控制排產(chǎn)過(guò)程的局部指派,對(duì)降低死鎖現(xiàn)象出現(xiàn)概率也有一定程度的影響.方案7 采用IDBRMMC 方法,結(jié)合基于HNNR高響應(yīng)比優(yōu)先算法的局部指派方法,在不同投產(chǎn)工件數(shù)所有實(shí)例測(cè)試中死鎖概率始終保持0.00%,即使投產(chǎn)工件數(shù)達(dá)到100依舊沒(méi)有出現(xiàn)死鎖現(xiàn)象,降低死鎖概率的效果最優(yōu),方案7基本可以有效的消除LRFFLBS排產(chǎn)過(guò)程中的死鎖現(xiàn)象.

對(duì)以上結(jié)果研究發(fā)現(xiàn),采用IDBRMMC方法與基于高響應(yīng)比優(yōu)先算法(HRRN)的局部指派方法相結(jié)合的方案7(IDBRMMC-HRRN),可以有效的降低在RFFLBS排產(chǎn)過(guò)程中出現(xiàn)死鎖現(xiàn)象發(fā)生的概率,避免死鎖現(xiàn)象發(fā)生.在IDBRMMC方法為折返執(zhí)行可重入工序的工件動(dòng)態(tài)預(yù)留緩沖區(qū)容量的同時(shí),使用基于HRRN調(diào)度算法的局部指派方法控制工件的局部調(diào)度,使具有較低復(fù)雜加工過(guò)程的工件優(yōu)先加工,加速完成其加工任務(wù),使之能夠先完工下線,在排產(chǎn)過(guò)程中減少工件對(duì)緩沖區(qū)對(duì)資源的爭(zhēng)奪,降低發(fā)生死鎖現(xiàn)象的概率.

4.3.3 評(píng)價(jià)指標(biāo)的結(jié)果對(duì)比分析

依據(jù)第4.3.2節(jié)分析,IDBRMMC-HRRN方法能有效的降低死鎖現(xiàn)象出現(xiàn)的概率,但由于為折返工件提前預(yù)留緩沖區(qū)容量會(huì)導(dǎo)致來(lái)自非可重入工序段的完工工件阻塞當(dāng)前工位上,引起阻塞時(shí)間的增加,進(jìn)而可能使工件總等待加工時(shí)間變長(zhǎng),同時(shí)也可能會(huì)引起總完工時(shí)間增加和設(shè)備利用率降低等問(wèn)題.

為綜合分析IDBRMMC-HRRN 方法對(duì)整個(gè)排產(chǎn)過(guò)程的影響,本文采用多種評(píng)價(jià)指標(biāo)對(duì)第4.3.2節(jié)中所設(shè)計(jì)的7 組方案的排產(chǎn)結(jié)果進(jìn)行進(jìn)一步分析,評(píng)價(jià)指標(biāo)包括: 平均最大完工時(shí)間max、平均工位空閑時(shí)間、工件的平均滯留時(shí)間、平均設(shè)備利用率由于當(dāng)出現(xiàn)死鎖現(xiàn)象時(shí),排產(chǎn)過(guò)程會(huì)發(fā)生停滯,因此無(wú)法獲得上述指標(biāo),所以,仿真實(shí)驗(yàn)中若出現(xiàn)死鎖現(xiàn)象的實(shí)驗(yàn)結(jié)果不記入統(tǒng)計(jì)結(jié)果中,具體數(shù)據(jù)如表4所示.

表4 不同求解方案下的評(píng)價(jià)指標(biāo)Table 4 _Evaluation indicators under different schemes

可見(jiàn)DBRMMC方法對(duì)排產(chǎn)過(guò)程的影響具有一定的規(guī)律,為進(jìn)一步研究在不同的投產(chǎn)任務(wù)情況下DBRMMC方法對(duì)排產(chǎn)結(jié)果的影響,繪制方案1、方案2的平均最大完工時(shí)間max與投產(chǎn)工件數(shù)關(guān)系曲線圖如圖9,其中各組數(shù)據(jù)可重入工件占投產(chǎn)工件總數(shù)采取相同比例,每組數(shù)據(jù)進(jìn)行30次仿真實(shí)驗(yàn)并取平均值,相同投產(chǎn)工件數(shù)的數(shù)據(jù),方案1與方案2采用相同上線序.

圖9 不同投產(chǎn)工件數(shù)7組方案的平均最大完工時(shí)間Fig.9 The average maximum completion time of different number of jobs put into production in 7 groups of schemes

方案1與方案2的最大完工時(shí)間隨投產(chǎn)工件數(shù)n增加而增大,n=15時(shí)方案1的平均最大完工時(shí)間max為274.2,采用DBRMMC方法的方案2的max=321.3比方案1增加47;當(dāng)n=21時(shí),方案1和方案2的max相等為384.1;若n繼續(xù)增加方案2的max小于方案1,在n=30的情況下,采用方案2的max較方案1降低132.由此可知,DBRM-MC方法的引入會(huì)導(dǎo)致增大最大完工時(shí)間.但隨著投產(chǎn)數(shù)的增加,即需求產(chǎn)能的增加,由于受到有限緩沖區(qū)的影響,生產(chǎn)阻塞情況隨之增加,同時(shí),隨著執(zhí)行可重入工序的工件數(shù)的增加,進(jìn)一步加劇了生產(chǎn)阻塞,雖未出現(xiàn)死鎖現(xiàn)象,但生產(chǎn)阻塞現(xiàn)象出現(xiàn)的機(jī)率增大導(dǎo)致自解鎖時(shí)間增長(zhǎng),進(jìn)而使得整個(gè)生產(chǎn)過(guò)程變緩.

因此從排產(chǎn)的局部指派過(guò)程看,DBRMMC方法的引入可以消除那些滿足緩沖區(qū)預(yù)留條件的生產(chǎn)死鎖現(xiàn)象,以增加局部阻塞時(shí)間的代價(jià),提前破壞形成死鎖潛在條件,換來(lái)整體生產(chǎn)進(jìn)程的加快.

針對(duì)采用基于SJF局部調(diào)度方法的方案4和方案5,當(dāng)n=22時(shí),方案4 的max小于方案1,當(dāng)n=24時(shí),方案5的max小于方案1;針對(duì)采用基于HRRN局部調(diào)度方法的方案6和方案7,當(dāng)n=20時(shí),max小于方案1.偏差補(bǔ)償措施的引入會(huì)小幅增加最大完工時(shí)間,但在不同的局部指派方法下引入偏差補(bǔ)償措施對(duì)于評(píng)價(jià)指標(biāo)的影響不同.

采用基于HNNR 算法的局部指派方法的方案7,當(dāng)n=50 時(shí),其=1012 比方案3 減少207,=962 比方案5減少2,方案7的各項(xiàng)評(píng)價(jià)指標(biāo)為所有方案中最優(yōu),其設(shè)備利用率達(dá)到0.830,當(dāng)n=100時(shí),設(shè)備利用率較方案3和方案5分別提高了3.5%和4%.由此可知IDBRMMC 方法和基于高響應(yīng)比優(yōu)先(HRRN)算法的局部指派方法運(yùn)用在LRFFLBS排產(chǎn)過(guò)程中不僅可以顯著降低死鎖現(xiàn)象出現(xiàn)的概率,同時(shí),也可以有效的改善以最大完工時(shí)間為代表的各項(xiàng)評(píng)價(jià)指標(biāo),特別是在RFFLBS排產(chǎn)過(guò)程中的引入基于高響應(yīng)比優(yōu)先(HRRN)算法的局部指派方法,能夠有效改善各項(xiàng)評(píng)價(jià)指標(biāo).

綜合分析上述結(jié)果,在引入DBRMMC方法后,能夠在求解RFFLBS排產(chǎn)過(guò)程中有效的降低死鎖現(xiàn)象出現(xiàn)的概率,但同時(shí)也因局部的阻塞時(shí)間的增加,在處理小規(guī)模數(shù)據(jù)時(shí)對(duì)排產(chǎn)結(jié)果產(chǎn)生了不利的影響.加入偏差補(bǔ)償措施的IDBRMMC方法可以進(jìn)一步的降低死鎖現(xiàn)象出現(xiàn)的概率,再結(jié)合基于高相應(yīng)比優(yōu)先算法(HRRN)的局部指派方法,可以更有效的降低死鎖現(xiàn)象出現(xiàn)的概率,在處理小規(guī)模數(shù)據(jù)時(shí),降低因引入IDBRMMC方法帶來(lái)的局部阻塞時(shí)間增加對(duì)排產(chǎn)結(jié)果的影響,在處理大規(guī)模數(shù)據(jù)時(shí)可以獲得更好的排產(chǎn)結(jié)果.

5 結(jié)論

本文以客車制造企業(yè)中存在的具有可重入工序的柔性流水車間有限緩沖區(qū)排產(chǎn)(RFFLBS)問(wèn)題為研究對(duì)象,分析RFFLBS中阻塞與死鎖現(xiàn)象的產(chǎn)生原因和影響,提出一種基于馬爾可夫鏈的有限緩沖區(qū)容量動(dòng)態(tài)預(yù)留方法(DBRMMC),該方法通過(guò)為折返執(zhí)行可重入工序的工件提前預(yù)留緩沖區(qū)資源,減少對(duì)緩沖區(qū)資源的爭(zhēng)奪,采用基于采用自適應(yīng)閾值二值化算法的偏差補(bǔ)償措施改進(jìn)(IDBRMMC),再與基于高響應(yīng)比優(yōu)先(HRRN)算法的局部指派方法結(jié)合,進(jìn)一步完善該方法,即改進(jìn)的IDBRMMC-HRRN,保證排產(chǎn)過(guò)程順利進(jìn)行的同時(shí)獲得更好的排產(chǎn)效果.該問(wèn)題的研究成果可以為相關(guān)企業(yè)的生產(chǎn)運(yùn)作過(guò)程提供切實(shí)的指導(dǎo)和幫助,提高企業(yè)現(xiàn)有資源的利用率.下一階段的工作是引入強(qiáng)化學(xué)習(xí)對(duì)該求解方法進(jìn)一步完善,優(yōu)化針對(duì)更大規(guī)模生產(chǎn)線的執(zhí)行效率,并引入全局優(yōu)化算法進(jìn)一步改善工位空閑時(shí)間、設(shè)備利用率等評(píng)價(jià)指標(biāo),在保證排產(chǎn)能夠順利執(zhí)行的前提下獲得更優(yōu)的排產(chǎn)結(jié)果.