不同生產(chǎn)方式下的隨機(jī)調(diào)度方案研究

不同生產(chǎn)方式下的隨機(jī)調(diào)度方案研究

0主要的計(jì)算方法公司在生產(chǎn)過(guò)程中的優(yōu)化計(jì)劃已成為提高公司生產(chǎn)效率的中心問(wèn)題。在實(shí)際生產(chǎn)中,當(dāng)加工時(shí)間不確定、機(jī)器故障等隨機(jī)事件發(fā)生時(shí),如何優(yōu)化隨機(jī)流水車間調(diào)度問(wèn)題(StochasticFlowShopSchedulingProblem,SFSSP)已成為企業(yè)關(guān)注的焦點(diǎn)。確定性情況下的流水車間調(diào)度問(wèn)題通常假設(shè):①任務(wù)的每道工序的加工時(shí)間確定且已知;②交貨期為確定值;③機(jī)器連續(xù)可用;④無(wú)突發(fā)訂單。松弛其中的一項(xiàng)假設(shè)就會(huì)產(chǎn)生新的調(diào)度問(wèn)題。文獻(xiàn)以最小化完工時(shí)間(Makespan)為目標(biāo),研究了加工時(shí)間服從指數(shù)分布的2臺(tái)機(jī)器流水車間調(diào)度問(wèn)題;文獻(xiàn)把文獻(xiàn)的算法擴(kuò)展到解決多機(jī)SFSSP問(wèn)題。同時(shí),機(jī)器突發(fā)故障會(huì)嚴(yán)重影響調(diào)度方案的有效實(shí)施,也是生產(chǎn)調(diào)度領(lǐng)域的一個(gè)研究熱點(diǎn)。文獻(xiàn)研究帶有隨機(jī)機(jī)器故障的流水車間調(diào)度問(wèn)題,但規(guī)模限制在2臺(tái)機(jī)器;文獻(xiàn)同時(shí)考慮隨機(jī)加工時(shí)間和隨機(jī)機(jī)器故障2種隨機(jī)因素,把帶有隨機(jī)故障的多機(jī)SFSSP分為一系列無(wú)故障調(diào)度問(wèn)題,然后采用已有的無(wú)故障算法求解;文獻(xiàn)對(duì)近幾年隨機(jī)調(diào)度問(wèn)題的相關(guān)研究進(jìn)行了綜述。但是,以上對(duì)帶有機(jī)器故障的SFSSP問(wèn)題的研究都局限于一類生產(chǎn)車間,即機(jī)器一旦開(kāi)始加工便持續(xù)運(yùn)轉(zhuǎn)到故障發(fā)生或所有生產(chǎn)任務(wù)結(jié)束。實(shí)際生產(chǎn)過(guò)程中,不同的生產(chǎn)車間,甚至同一個(gè)生產(chǎn)車間往往存在不同的機(jī)器工作方式:①機(jī)器一旦開(kāi)始加工便持續(xù)運(yùn)轉(zhuǎn)到故障發(fā)生或所有生產(chǎn)任務(wù)結(jié)束;②機(jī)器只在加工任務(wù)時(shí)才運(yùn)轉(zhuǎn)。因此,對(duì)于不同機(jī)器工作方式下的故障應(yīng)采用不同的規(guī)則。本文對(duì)此展開(kāi)研究,探討了不同機(jī)器工作方式下性能指標(biāo)Cmax期望值的計(jì)算方法、故障計(jì)算規(guī)則及其對(duì)性能指標(biāo)的影響,并進(jìn)行分析比較;針對(duì)加工時(shí)間隨機(jī)且機(jī)器隨機(jī)故障、目標(biāo)函數(shù)為最小化最大完工時(shí)間(Makespan)的SFSSP問(wèn)題進(jìn)行了研究,提出了不同流水車間隨機(jī)調(diào)度的3種方法,采用啟發(fā)式規(guī)則和遺傳算法相結(jié)合的方法確定加工任務(wù)的最優(yōu)排序。1機(jī)器的排列時(shí)間,有以下幾種基本概念假定m臺(tái)機(jī)器加工n個(gè)不同類型的任務(wù),每個(gè)任務(wù)有m道工序,以相同的順序在m臺(tái)機(jī)器上加工,并且每個(gè)任務(wù)在每臺(tái)機(jī)器上只加工一次;在同一時(shí)間,每臺(tái)機(jī)器只能加工處理一個(gè)工序,某工序只能在一個(gè)機(jī)器上加工處理;任務(wù)的每道工序在每臺(tái)機(jī)器上的加工時(shí)間為隨機(jī)變量,機(jī)器故障發(fā)生時(shí)刻和修復(fù)時(shí)間也是隨機(jī)變量,且它們都服從指數(shù)分布expλ,其期望1/λ為服從均勻分布的隨機(jī)變量。相關(guān)參數(shù)的定義如下:m—機(jī)器總數(shù);n—待加工任務(wù)總數(shù);si—排在第i個(gè)位置的任務(wù),i=1,2,…,n;S—任務(wù)排列集合,S={s1,s2,…,sn};p(i,j)—任務(wù)i在第j機(jī)器上的加工時(shí)間,相互獨(dú)立的隨機(jī)變量,i=1,2,…,n,j=1,2,…,m;Bj—機(jī)器j的連續(xù)可用時(shí)間,即機(jī)器j從開(kāi)始(或修復(fù)后重新)運(yùn)轉(zhuǎn)到下次發(fā)生故障期間的運(yùn)轉(zhuǎn)時(shí)間,隨機(jī)變量j=1,2,…,m;Rj—機(jī)器j的故障修復(fù)時(shí)間,隨機(jī)變量j=1,2,…,m;t(i,j)—任務(wù)i在機(jī)器j上的開(kāi)始加工時(shí)刻;c(i,j)—任務(wù)i在機(jī)器j上的完工時(shí)刻;c(i)—任務(wù)i在最后一臺(tái)機(jī)器上的加工完成時(shí)刻;Cmax—所有任務(wù)的最大完成時(shí)刻;EX—隨機(jī)變量X的期望值,例如,Ep(i,j)表示加工時(shí)間的期望值。當(dāng)僅考慮加工時(shí)間隨機(jī)時(shí),對(duì)應(yīng)于排列S的各個(gè)任務(wù)在每臺(tái)機(jī)器上的完成時(shí)間描述如下:t(s1,1)=0;Ec(s1,1)=t(s1,1)+Ep(s1,1);Ec(s1,j)=Ec(s1,j-1)+Ep(s1,j-1),j=2,3,…,m;Ec(si,1)=Ec(si-1,1)+Ep(si-1,1),i=2,3,…,n;Ec(si,j)=max{Ec(si,j-1),Ec(si-1,j)}+Ep(si-1,j),i=2,3,…,n,j=2,3,…,m;Ec(si)=Ec(si,m),i=1,2,…,n。至于當(dāng)每道工序的加工時(shí)間隨機(jī)且機(jī)器故障隨機(jī)時(shí),對(duì)應(yīng)于排列S的各個(gè)任務(wù)在每臺(tái)機(jī)器上的完成時(shí)間將在第2章中詳述。目標(biāo)是最小化最大完工時(shí)間,即minECmax=max{Ec(si)|i=1,2,…,n}=Ec(sn)。以最小化最大完工時(shí)間(ECmax)為目標(biāo)的SFSSP調(diào)度問(wèn)題就是確定n個(gè)任務(wù)的加工順序S*={s1,s2,…,sn},使得ECmax最小,其最優(yōu)結(jié)果記作EC*max,即S*=arg{EC*max}。2機(jī)器的工序故障期望計(jì)算為合理地計(jì)算故障發(fā)生的期望時(shí)刻和相應(yīng)的目標(biāo)值ECmax,設(shè)計(jì)了3類計(jì)算規(guī)則,用以計(jì)算不同機(jī)器工作方式下的故障發(fā)生時(shí)刻,并計(jì)算任務(wù)i(i=1,2,…,n)在機(jī)器j(j=1,2,…,m)上的完工時(shí)間期望值。假設(shè)一個(gè)任務(wù)正在機(jī)器上加工時(shí)機(jī)器出現(xiàn)故障,修好后,被故障中斷的任務(wù)的工序在原來(lái)已加工的基礎(chǔ)上繼續(xù)加工,其計(jì)算規(guī)則如下:假定在初始時(shí)刻,所有機(jī)器可用,且任務(wù)可以加工,有:t(s1,1)=0,Ec(s1,1)=t(s1,1)+Ep(s1,1);Et(si,j)=max{Ec(si-1,j),Ec(si,j-1)},i=2,3,…,n,j=2,3,…,m。情況1機(jī)器從加工第一個(gè)任務(wù)開(kāi)始運(yùn)轉(zhuǎn),一直運(yùn)轉(zhuǎn)到故障發(fā)生或所有任務(wù)結(jié)束,任意時(shí)刻都可能發(fā)生故障。機(jī)器j的故障時(shí)刻期望值為機(jī)器j的開(kāi)機(jī)時(shí)刻期望值Et(s1,j)(或上次故障修復(fù)的時(shí)刻)與機(jī)器連續(xù)可用時(shí)間期望值EBj之和,j=1,2,…,m。任務(wù)i(i=1,2,…,n)在機(jī)器j(j=1,2,…,m)上的完工時(shí)間期望值計(jì)算如下:如圖1所示,若故障發(fā)生在EA時(shí)刻,if(Ec(si-1,j)<=EAandEc(si,j-1)>EA)Ec(si,j)=Et(si,j)+Ep(si,j)+max{Et(si,j),EA+ERj}-Et(si,j)=max{Et(si,j),EA+ERj}+Ep(si,j);endif其中,如果max{Et(si,j),EA+ERj}=Et(si,j),說(shuō)明故障可以在機(jī)器正常閑置時(shí)間內(nèi)修好,因此這種故障不會(huì)影響生產(chǎn)。若故障發(fā)生在EB時(shí)刻,if(t(si,j)<=EBandEt(si,j)+Ep(si,j)>EB)Ec(si,j)=Et(si,j)+Ep(si,j)+ERj;endif這種故障導(dǎo)致任務(wù)i的第j道工序的完成時(shí)間后延Rj。情況2機(jī)器從加工第一個(gè)任務(wù)開(kāi)始運(yùn)轉(zhuǎn),一直運(yùn)轉(zhuǎn)到故障發(fā)生或所有任務(wù)結(jié)束,且機(jī)器只有在加工過(guò)程中才可能發(fā)生故障。當(dāng)機(jī)器j的故障時(shí)間期望值存在于非加工時(shí)間區(qū)間[Ec(si-1,j),Ec(si,j-1)]上時(shí),令故障時(shí)刻期望值等于Et(si,j),由此保證機(jī)器在非加工時(shí)間內(nèi)不會(huì)出現(xiàn)故障,即不存在圖1中的EA類故障時(shí)刻;當(dāng)不屬于區(qū)間[Ec(si-1,j),Ec(si,j-1)]時(shí),機(jī)器的故障時(shí)刻期望值計(jì)算規(guī)則同情況1。任務(wù)i(i=1,2,…,n)在機(jī)器j(j=1,2,…,m)上的完工時(shí)間期望值計(jì)算方法如下:Lettemp=min{Ec(si-1,j),Et(si,j)};if(temp<=EBandEt(si,j)+Ep(si,j)>EB)Ec(si,j)=Et(si,j)+Ep(si,j)+ERj;endif情況3機(jī)器只在加工任務(wù)時(shí)才運(yùn)轉(zhuǎn),且機(jī)器故障時(shí)刻僅與總的加工磨損時(shí)間有關(guān),機(jī)器故障只可能發(fā)生在圖1中的EB類時(shí)刻點(diǎn)。容易理解,機(jī)器j(j=1,2,…,m)的累計(jì)工作時(shí)間達(dá)到機(jī)器連續(xù)可用時(shí)間EBj時(shí),所對(duì)應(yīng)的時(shí)刻就是一個(gè)期望發(fā)生的故障時(shí)刻。任務(wù)i(i=1,2,…,n)在機(jī)器j(j=1,2,…,m)上的完工時(shí)間期望值計(jì)算方法如下:不失一般性,假設(shè)時(shí)刻EB是機(jī)器j的第x次故障點(diǎn),把上一次(第x-1次)機(jī)器j發(fā)生故障時(shí)正在其上加工的任務(wù)的號(hào)碼記作Q,令aj=∑k=Q+1,Q+2,…,Q+i-1Ep(sk,j),bj=∑k=Q+1,Q+2,…,Q+iEp(sk,j),j=1,2,…,m;if(aj<=EBandbj>EB)Ec(si,j)=Et(si,j)+Ep(si,j)+ERj;endif根據(jù)上述3種情況計(jì)算得到的Ec(si,j),可求得任務(wù)i(i=1,2,…,n)的完工時(shí)間為Ec(si)=Ec(si,m),且Ecmax=Ec(sn)。由此可見(jiàn),對(duì)于具有相同期望連續(xù)可用時(shí)間EBj(j=1,2,…,m)的機(jī)器,不難發(fā)現(xiàn):(1)情況3的機(jī)器j(j=1,2,…,m)故障間隔時(shí)間最大因?yàn)榍闆r3中的機(jī)器只在有任務(wù)時(shí)才運(yùn)轉(zhuǎn),沒(méi)有任務(wù)時(shí)停止。(2)情況3的EC*max最小因?yàn)楣收祥g隔時(shí)間越大,任務(wù)被中斷的概率越小,故障對(duì)性能指標(biāo)ECmax的影響越小。因此,對(duì)于其他兩種情況,情況3的EC*max最小。(3)情況1中機(jī)器故障影響EC*max增大的程度比情況2中小情況1能夠在機(jī)器的正?？臻e時(shí)間內(nèi)修好或修理EA類故障,若故障可以在機(jī)器正?？臻e時(shí)間內(nèi)修理好,則該故障對(duì)生產(chǎn)不造成影響,可以忽略不計(jì)。而情況2則把EA類故障后移變?yōu)镋B類故障,修理時(shí)間完全占用機(jī)器的正常工作時(shí)間。顯然,情況1機(jī)器故障影響EC*max增大的可能性比情況2小。由此得出如下性質(zhì):EC*max(情況3)≤EC*max(情況1)≤EC*max(情況2)。3啟發(fā)式規(guī)則與智能優(yōu)化相結(jié)合一般情況下,以最大完工時(shí)間Cmax為性能指標(biāo),機(jī)器數(shù)≥3的流水車間調(diào)度已經(jīng)是NP難題,機(jī)器數(shù)的增加會(huì)加劇算法的復(fù)雜性。精確求解的方法只能局限于小規(guī)模問(wèn)題,實(shí)際應(yīng)用價(jià)值不大。啟發(fā)式規(guī)則與智能優(yōu)化相結(jié)合的方法能在較短的時(shí)間內(nèi)求解大規(guī)模問(wèn)題的近優(yōu)解。針對(duì)具有隨機(jī)機(jī)器故障且加工時(shí)間隨機(jī)的SFSSP,本文采用啟發(fā)式規(guī)則和遺傳算法相結(jié)合的方法,確定所有任務(wù)的最優(yōu)加工排序。(1)任務(wù)號(hào)的生成采用自然數(shù)編碼。用一段順序碼表示任務(wù)處理的優(yōu)先級(jí)順序,如3-1-2,數(shù)字表示任務(wù)號(hào),排在最前的任務(wù)優(yōu)先級(jí)最高。初始種群由兩部分生成,一部分隨機(jī)產(chǎn)生,另一部分按照經(jīng)典NEH排序規(guī)則生成(NEH被認(rèn)為是至今最好的多項(xiàng)式構(gòu)造型算法)。產(chǎn)生的初始種群隨機(jī)生成排序,使種群具有多樣性,且搜索結(jié)果必然優(yōu)于已知的NEH排序。(2)調(diào)度排序是當(dāng)機(jī)器正常工作時(shí)間的一個(gè)重要誤直接把目標(biāo)值ECmax作為適應(yīng)值。目標(biāo)值不僅與任務(wù)的排序有關(guān),而且受隨機(jī)的加工時(shí)間和機(jī)器故障影響,好的調(diào)度排序能夠把這些隨機(jī)因素對(duì)目標(biāo)值的影響降到最小,例如故障發(fā)生在機(jī)器正?？臻e時(shí)間內(nèi)且可以在正?？臻e時(shí)間內(nèi)修復(fù)時(shí),這種故障不影響生產(chǎn)。(3)遺產(chǎn)活動(dòng)選擇操作采用錦標(biāo)賽選擇策略,交叉操作采用雙位置次序交叉,變異操作采用互換變異(SWAP)。(4)精英保留和新種群保留種群數(shù)量為一個(gè)定值N,采用精英保留與隨機(jī)選擇相結(jié)合的策略。把父代和子代放到一起,統(tǒng)一評(píng)估。選擇其中目標(biāo)值較小的M(1≤M<N)個(gè)個(gè)體無(wú)條件地保留到新種群里,即精英保留;然后從所有個(gè)體中隨機(jī)選取N-M個(gè)體進(jìn)入新種群,從而在保留較好個(gè)體加快收斂速度的同時(shí)又不失種群的多樣性。(5)終止條件設(shè)定最大迭代代數(shù)為n×m。4最優(yōu)調(diào)度方案選取用VisualC++6.0編程實(shí)現(xiàn)上述算法,對(duì)隨機(jī)變量服從指數(shù)分布的情況進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)中,機(jī)器數(shù)分別取3,7,10,任務(wù)數(shù)分別取7,20,50,100。每道工序的加工時(shí)間和每臺(tái)機(jī)器的故障等隨機(jī)變量服從指數(shù)分布expλ時(shí),其期望1/λ服從均勻分布。任意時(shí)刻,一臺(tái)或多臺(tái)機(jī)器都有可能發(fā)生故障。隨機(jī)加工時(shí)間、故障周期和修復(fù)時(shí)間期望的取值范圍如表1所示。遺傳算法中,取種群規(guī)模為20,交叉概率為0.6,變異概率為0.1。根據(jù)表1中每種機(jī)器數(shù)與任務(wù)數(shù)的組合情況,對(duì)情況1～情況3和不考慮故障情況的流水車間調(diào)度分別運(yùn)行20次,隨機(jī)產(chǎn)生20組初始數(shù)據(jù),計(jì)算結(jié)果取平均值(EC?maxˉˉˉˉˉˉˉˉˉˉ)(ECmax*ˉ),并給出各自的標(biāo)準(zhǔn)方差(如表2)。在表2中,j為機(jī)器號(hào),p(*,j)為每個(gè)任務(wù)在機(jī)器j上的隨機(jī)加工時(shí)間。20次隨機(jī)計(jì)算中最小的EC*max(限于篇幅,僅列出3臺(tái)機(jī)器、7個(gè)任務(wù)的排序結(jié)果)對(duì)應(yīng)的最優(yōu)排序結(jié)果如表3所示。實(shí)驗(yàn)結(jié)果給出了3種不同情況下最優(yōu)調(diào)度排序的EC?maxˉˉˉˉˉˉˉˉˉˉECmax*ˉ值(如表2)及其部分排序結(jié)果(如表3),表明了帶有機(jī)器故障的流水車間最優(yōu)調(diào)度方案與不考慮故障情況下的結(jié)果不同,且不同生產(chǎn)方式下流水車間的最優(yōu)調(diào)度方案也各不相同。這是因?yàn)?某工序正在相應(yīng)的機(jī)器上加工時(shí),若機(jī)器發(fā)生故障并在一定時(shí)間范圍內(nèi)修復(fù),這個(gè)過(guò)程可以看作是延長(zhǎng)了被中斷任務(wù)的該道工序的加工時(shí)間,而任務(wù)的各個(gè)工序加工時(shí)間的長(zhǎng)短直接影響其在最優(yōu)排序中的位置,因此,考慮機(jī)器故障的最優(yōu)調(diào)度方案與無(wú)故障情況下的結(jié)果是不同的。機(jī)器隨機(jī)故障且加工時(shí)間不確定是生產(chǎn)中經(jīng)常發(fā)生的事情,顯然,不考慮故障的調(diào)度方案已經(jīng)不能有效地指揮生產(chǎn)。同時(shí),表2中的計(jì)算結(jié)果表明,EC?maxˉˉˉˉˉˉˉˉˉˉECmax*ˉ(情況3)≤EC?maxˉˉˉˉˉˉˉˉˉˉ3)≤ECmax*ˉ(