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

(1.中國科學(xué)院網(wǎng)絡(luò)化控制系統(tǒng)重點(diǎn)實(shí)驗(yàn)室,遼寧沈陽 110016;2.中國科學(xué)院沈陽自動(dòng)化研究所,遼寧沈陽 110016;3.中國科學(xué)院機(jī)器人與智能制造創(chuàng)新研究院,遼寧沈陽 110169;4.中國科學(xué)院大學(xué),北京 100049;5.沈陽建筑大學(xué)信息與控制工程學(xué)院,遼寧沈陽 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)問題.由于可重入工序的存在,會(huì)使工件的加工路徑更加復(fù)雜,又由于有限緩沖區(qū)的存在,更增加了局部任務(wù)指派和資源調(diào)度的難度.在生產(chǎn)過程中,執(zhí)行可重入工序的工件會(huì)再次折返進(jìn)入該重入工序所對(duì)應(yīng)的緩沖區(qū),若該緩沖區(qū)為有限緩沖區(qū),則來自前道工序完工的工件與折返重入的工件將爭奪緩沖區(qū)資源,如果該緩沖區(qū)中存儲(chǔ)的工件數(shù)量達(dá)到其容量上限,前道工序的工件無法進(jìn)入該緩沖區(qū),導(dǎo)致前道工序發(fā)生阻塞,同時(shí),本應(yīng)折返重入該緩沖區(qū)的工件,也由于緩沖區(qū)無空閑緩沖車位而被滯留在其當(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)問題更為復(fù)雜.

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

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

若能利用歷史生產(chǎn)數(shù)據(jù)對(duì)未來可能出現(xiàn)的死鎖現(xiàn)象進(jìn)行預(yù)測(cè),干預(yù)生產(chǎn)任務(wù)在各工序的移動(dòng),保證緩沖區(qū)資源的合理分配,避免死鎖現(xiàn)象的發(fā)生,則無需為車間配置冗余的緩沖區(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ù),通過運(yùn)用馬爾可夫鏈預(yù)測(cè),計(jì)算并預(yù)測(cè)緩沖資源釋放的概率.根據(jù)預(yù)測(cè)結(jié)果對(duì)局部調(diào)度過程進(jìn)行干預(yù),將折返執(zhí)行可重入工序的工件預(yù)留緩沖區(qū)容量,減少工件對(duì)緩沖區(qū)資源的爭奪,降低死鎖現(xiàn)象出現(xiàn)的概率.研究內(nèi)容與以往研究工作不同之處在于: 1)深入分析RFFLBS過程中死鎖現(xiàn)象,找到死鎖現(xiàn)象產(chǎn)生的原因;2)通過調(diào)度緩沖區(qū)資源來干預(yù)局部指派過程,避免對(duì)生產(chǎn)線已配置資源進(jìn)行大規(guī)模重新調(diào)整和擴(kuò)充的前提下,就可以有效的克服死鎖現(xiàn)象,并獲得較好的排產(chǎn)結(jié)果;3)提出DBRMMC方法,通過預(yù)測(cè)生產(chǎn)過程中出現(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 問題描述

2.1 問題描述

LBRFFS問題可描述如下: 存在n個(gè)工件的待加工隊(duì)列{J1,J2,···,Jn},需經(jīng)過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)過指定的工序進(jìn)行加工,工件在重入工序中至少加工一次,每個(gè)工件有不同的重入次數(shù)rtsi(工件Ji總共被加工nrm+rm×rtsi次).工件每經(jīng)過一道工序,需選擇一個(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è)工序的開工時(shí)間、完工時(shí)間.RFFLBS模型示意圖如圖1所示.

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

2.2.1 模型參數(shù)

n: 工件總數(shù);

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

t: 生產(chǎn)加工過程中某時(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)過的工序總數(shù),fmi≥m;

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

2.2.2 假設(shè)變量

2.2.3 約束條件

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

1)約束1.

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

3)約束3.

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

4)約束4.

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

5)約束5.

工件經(jīng)過工序總數(shù)等于經(jīng)過的非可重入工序與可重入工序次數(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í)便立即開始加工;

10)約束10.

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

11)約束11.

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

12)約束12.

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

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

由于在具有有限緩沖區(qū)的柔性流水車間的生產(chǎn)線上,只能設(shè)置容量有限的緩沖區(qū),當(dāng)工件完成在前道工序的加工任務(wù)時(shí),該工件可能會(huì)因無空閑緩沖車位而滯留在前道工序的工位上,影響生產(chǎn)線的局部生產(chǎn)過程,造成阻塞現(xiàn)象.若隨著生產(chǎn)過程的繼續(xù),后道工序中有工件完工并從工位移出,緩沖區(qū)中待加工工件能夠進(jìn)入后道工序執(zhí)行加工任務(wù),此時(shí)緩沖區(qū)資源得到釋放,被阻塞的工件可從前道工序移入緩沖區(qū),即自解阻塞.如果無法自解阻塞則會(huì)導(dǎo)致死鎖現(xiàn)象.通過分析生產(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ù)其工藝流程離開可重入工序段,因此Ord中出現(xiàn)空閑Wrd,2,依據(jù)局部指派方法,Brd中的工件競(jì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過程中自解阻塞現(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中的工件無法進(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)線中無法移動(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ū)容量再被來自非可重入工序段的工件占用,Bru被完全占滿,接下來事件1–2再發(fā)生,則會(huì)產(chǎn)生死鎖現(xiàn)象.因此探索解決死鎖現(xiàn)象的方法重點(diǎn)在,如何干預(yù)可重入工序段中第1個(gè)工序?qū)?yīng)緩沖區(qū)資源的使用.

圖4 來自非可重入工序段工件爭奪緩沖車位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)問題的方法

針對(duì)可重入工序段中首道工序,即工件折返執(zhí)行的可重入工序,其工位的狀態(tài)的變化過程是一種隨機(jī)變化過程符合馬爾可夫過程的特性,與近期狀態(tài)有關(guān)而與過去狀態(tài)無關(guān),具有無后效性.故提出DBRMMC,解決在RFFLBS過程中出現(xiàn)死鎖現(xià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方法通過預(yù)測(cè)可重入工序段中首道工序中工位加工工件的變化情況,進(jìn)而預(yù)測(cè)對(duì)應(yīng)緩沖區(qū)緩沖車位的釋放概率,根據(jù)計(jì)算結(jié)果判斷是否預(yù)留緩沖區(qū)資源,通過提前預(yù)留緩沖區(qū)資源,保證折返工件能夠順利進(jìn)入緩沖區(qū).該方法減少了因來自不同工序段的工件對(duì)緩沖區(qū)資源爭奪而導(dǎo)致嚴(yán)重連續(xù)阻塞對(duì)進(jìn)程的影響,保證能夠順利進(jìn)行排產(chǎn)過程.具體步驟如下.

步驟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離開Oru的時(shí)間,由于可能存在阻塞現(xiàn)象,t1大于等于;t2為可重入工序段末道工序Ord中最先完工的工件JD離開Ord的時(shí)間.

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

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

通過概率統(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í)刻到未來t2時(shí)刻的時(shí)間段內(nèi)包含t′的數(shù)量.

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

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

當(dāng)P1較大時(shí),表示在未來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)過程的初期,根據(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í)行可沖入工序的工件占比增多,由于緩沖區(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í)行加工過程的剩余的加工時(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í)間越長優(yōu)先權(quán)越高,即先進(jìn)先出;3)工件的優(yōu)先權(quán)會(huì)隨著其在待加工隊(duì)列中等待時(shí)間的增加而增大,如果工件等待時(shí)間較長,則工件的優(yōu)先權(quán)受等待時(shí)間影響更大,優(yōu)先權(quán)隨之增大,便有利于長作業(yè).

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

3.3 DBRMMC的改進(jìn)

DBRMMC中采用馬爾科夫鏈進(jìn)行預(yù)測(cè)運(yùn)算,由于概率統(tǒng)計(jì)誤差、計(jì)算誤差等原因,通過預(yù)測(cè)模型所計(jì)算出的概率可能出現(xiàn)偏差,會(huì)導(dǎo)致Jnrm進(jìn)入緩沖區(qū)Bru,搶占唯一資源,面對(duì)復(fù)雜度較高的排產(chǎn)過程,即使采用了DBRMMC方法排產(chǎn)過程依舊可能產(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)行過程進(jìn)行分析,分別對(duì)不同規(guī)模的數(shù)據(jù)建立多組仿真方案,進(jìn)行仿真實(shí)驗(yàn).由于目前對(duì)于RFFLBS問題的研究仍處于初始階段,針對(duì)該類問題的研究很少,尚無RFFLBS問題的標(biāo)準(zhǔn)算例.本文的測(cè)試用例來自于某大型客車生產(chǎn)企業(yè),采用其涂裝車間多遍貼彩條工序段的生產(chǎn)數(shù)據(jù)來構(gòu)建,規(guī)模與取值均基于實(shí)際生產(chǎn).

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

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

涂裝車間工作人員會(huì)根據(jù)彩條的模板對(duì)不同車體噴繪的圖案分解成多種顏色,依照工藝流程,經(jīng)過多遍噴繪形成車體圖案,不同車型因噴漆面積、彩條復(fù)雜程度等原因在同一道工序加工工時(shí)不同,客車在每道工序的加工時(shí)長在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}為無限緩沖區(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è)工件的開始到最后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)行過程

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

圖8 加入方法后無死鎖現(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中,由于在此之前沒有為J14預(yù)留B2的容量,在t=122時(shí),B2已經(jīng)被占滿,所以J14滯留在W3,1中,發(fā)生生產(chǎn)阻塞,B3中的工件無法進(jìn)入O3中進(jìn)行加工.隨著時(shí)間推移,工件{J13,J4}因B2已經(jīng)被占滿無法折返滯留{W3,3,W3,1}.當(dāng)運(yùn)行到t=148時(shí),所有工件都被阻塞在當(dāng)前位置上,這種嚴(yán)重阻塞的情況無法隨著時(shí)間自解阻塞.從t=122時(shí)開始出現(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大于無工件完工并移出的概率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ū)的指派過程,可以減少死鎖現(xiàn)象的發(fā)生.DBRMMC中采用馬爾科夫鏈進(jìn)行預(yù)測(cè)運(yùn)算,由于存在概率統(tǒng)計(jì)誤差、計(jì)算誤差等原因,因此通過預(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)過程中降低死鎖出現(xià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í)沒有出現(xiàn)死鎖現(xiàn)象,投產(chǎn)工件數(shù)量增加死鎖現(xiàn)象出現(xiàn).總投產(chǎn)工件數(shù)n=15時(shí),方案1由于沒有采用DBRMMC方法,隨著具有可重入工序的工件數(shù)占總投產(chǎn)工件數(shù)比例Po增加,死鎖概率PL由10.00%增長到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)爭愈發(fā)激烈,如果不采取一定的措施,排產(chǎn)過程將無法正常進(jìn)行.

表3 不同數(shù)據(jù)規(guī)模的加工任務(wù)下RFFLBS過程中出現(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)無法進(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)過程中死鎖現(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)過程中仍有死鎖現(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)過程的死鎖現(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%,由此可見在一定的需求產(chǎn)能范圍內(nèi),該方法可以基本消除RFFLBS過程中出現(xiàn)的死鎖現(xiàn)象,引入偏差補(bǔ)償措施會(huì)進(jìn)一步提升DBRMMC方法在控制RFFLBS排產(chǎn)過程中出現(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)過程的局部指派,對(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依舊沒有出現(xiàn)死鎖現(xiàn)象,降低死鎖概率的效果最優(yōu),方案7基本可以有效的消除LRFFLBS排產(chǎn)過程中的死鎖現(xiàn)象.

對(duì)以上結(jié)果研究發(fā)現(xiàn),采用IDBRMMC方法與基于高響應(yīng)比優(yōu)先算法(HRRN)的局部指派方法相結(jié)合的方案7(IDBRMMC-HRRN),可以有效的降低在RFFLBS排產(chǎn)過程中出現(xiàn)死鎖現(xiàn)象發(fā)生的概率,避免死鎖現(xiàn)象發(fā)生.在IDBRMMC方法為折返執(zhí)行可重入工序的工件動(dòng)態(tài)預(yù)留緩沖區(qū)容量的同時(shí),使用基于HRRN調(diào)度算法的局部指派方法控制工件的局部調(diào)度,使具有較低復(fù)雜加工過程的工件優(yōu)先加工,加速完成其加工任務(wù),使之能夠先完工下線,在排產(chǎn)過程中減少工件對(duì)緩沖區(qū)對(duì)資源的爭奪,降低發(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)致來自非可重入工序段的完工工件阻塞當(dāng)前工位上,引起阻塞時(shí)間的增加,進(jìn)而可能使工件總等待加工時(shí)間變長,同時(shí)也可能會(huì)引起總完工時(shí)間增加和設(shè)備利用率降低等問題.

為綜合分析IDBRMMC-HRRN 方法對(duì)整個(gè)排產(chǎn)過程的影響,本文采用多種評(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)過程會(huì)發(fā)生停滯,因此無法獲得上述指標(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

可見DBRMMC方法對(duì)排產(chǎn)過程的影響具有一定的規(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í)間增長,進(jìn)而使得整個(gè)生產(chǎn)過程變緩.

因此從排產(chǎn)的局部指派過程看,DBRMMC方法的引入可以消除那些滿足緩沖區(qū)預(yù)留條件的生產(chǎn)死鎖現(xiàn)象,以增加局部阻塞時(shí)間的代價(jià),提前破壞形成死鎖潛在條件,換來整體生產(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)過程中不僅可以顯著降低死鎖現(xiàn)象出現(xiàn)的概率,同時(shí),也可以有效的改善以最大完工時(shí)間為代表的各項(xiàng)評(píng)價(jià)指標(biāo),特別是在RFFLBS排產(chǎn)過程中的引入基于高響應(yīng)比優(yōu)先(HRRN)算法的局部指派方法,能夠有效改善各項(xiàng)評(píng)價(jià)指標(biāo).

綜合分析上述結(jié)果,在引入DBRMMC方法后,能夠在求解RFFLBS排產(chǎn)過程中有效的降低死鎖現(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方法帶來的局部阻塞時(shí)間增加對(duì)排產(chǎn)結(jié)果的影響,在處理大規(guī)模數(shù)據(jù)時(shí)可以獲得更好的排產(chǎn)結(jié)果.

5 結(jié)論

本文以客車制造企業(yè)中存在的具有可重入工序的柔性流水車間有限緩沖區(qū)排產(chǎn)(RFFLBS)問題為研究對(duì)象,分析RFFLBS中阻塞與死鎖現(xiàn)象的產(chǎn)生原因和影響,提出一種基于馬爾可夫鏈的有限緩沖區(qū)容量動(dòng)態(tài)預(yù)留方法(DBRMMC),該方法通過為折返執(zhí)行可重入工序的工件提前預(yù)留緩沖區(qū)資源,減少對(duì)緩沖區(qū)資源的爭奪,采用基于采用自適應(yīng)閾值二值化算法的偏差補(bǔ)償措施改進(jìn)(IDBRMMC),再與基于高響應(yīng)比優(yōu)先(HRRN)算法的局部指派方法結(jié)合,進(jìn)一步完善該方法,即改進(jìn)的IDBRMMC-HRRN,保證排產(chǎn)過程順利進(jìn)行的同時(shí)獲得更好的排產(chǎn)效果.該問題的研究成果可以為相關(guān)企業(yè)的生產(chǎn)運(yùn)作過程提供切實(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é)果.