柔性作業(yè)車間多目標(biāo)動(dòng)態(tài)調(diào)度模型及算法研究

柔性作業(yè)車間多目標(biāo)動(dòng)態(tài)調(diào)度模型及算法研究

0動(dòng)態(tài)調(diào)度研究存在的問(wèn)題生產(chǎn)計(jì)劃是先進(jìn)制造領(lǐng)域研究的基礎(chǔ)和重要問(wèn)題。其主要任務(wù)是確定相關(guān)設(shè)備中零件的加工順序和加工時(shí)間，并確保所選生產(chǎn)目標(biāo)的最佳數(shù)量。其中,柔性作業(yè)車間調(diào)度問(wèn)題(FlexibleJob-shopSchedulingProblem,FJSP)因?yàn)橥黄屏藱C(jī)器約束和加工工藝路線固定的限制,每道工序可在一臺(tái)或多臺(tái)調(diào)度機(jī)器上加工,加工過(guò)程有多條工藝路線可供選擇,相比傳統(tǒng)的作業(yè)車間調(diào)度更接近生產(chǎn)實(shí)際,所以生產(chǎn)中較廣泛地采用。然而,實(shí)際柔性作業(yè)車間調(diào)度常會(huì)發(fā)生機(jī)器故障、來(lái)料延遲和緊急插單等不確定因素,此時(shí)就需要考慮在上述情況發(fā)生時(shí)進(jìn)行柔性作業(yè)車間動(dòng)態(tài)調(diào)度的問(wèn)題。NELSON等在1977年最早提出了動(dòng)態(tài)調(diào)度問(wèn)題,它將動(dòng)態(tài)調(diào)度過(guò)程分成多個(gè)連續(xù)的靜態(tài)區(qū)間,然后對(duì)上述調(diào)度區(qū)間進(jìn)行優(yōu)化以達(dá)到每個(gè)區(qū)間內(nèi)最優(yōu),從而適應(yīng)動(dòng)態(tài)環(huán)境,但他們只研究了單目標(biāo)問(wèn)題,且未對(duì)調(diào)度性能及影響調(diào)度性能的因素進(jìn)行分析。張超勇研究了原材料延期到達(dá)、加工和裝配延誤、緊急工件加入等情況下的動(dòng)態(tài)調(diào)度,但主要針對(duì)傳統(tǒng)非柔性車間調(diào)度問(wèn)題進(jìn)行研究,未考慮工藝路線的柔性化和機(jī)器資源的可選性,同時(shí)也缺乏對(duì)影響調(diào)度性能的因素進(jìn)行分析。潘全科研究了待加工工件的選取原則和再調(diào)度周期的確定方法,但對(duì)動(dòng)態(tài)調(diào)度執(zhí)行流程描述的不夠清晰,也未分析所提方法的調(diào)度性能和影響調(diào)度性能的因素。BRANLE研究了工件隨機(jī)達(dá)到的動(dòng)態(tài)調(diào)度,以合并早期空閑時(shí)間的方法來(lái)提高調(diào)度性能,但未考慮機(jī)器故障和周期性再調(diào)度問(wèn)題,且以合并早期空閑時(shí)間的方法對(duì)提高調(diào)度性能較為有限。LIU使用工件選取規(guī)則縮短工序加工的空閑時(shí)間,以達(dá)到提高調(diào)度性能的目標(biāo),但未考慮工藝路線的柔性化和機(jī)器資源的可選性,且主要針對(duì)單目標(biāo)調(diào)度問(wèn)題。吳秀麗在未考慮機(jī)器故障和周期性再調(diào)度情況下,研究了面向交貨期性能最優(yōu)的柔性作業(yè)車間動(dòng)態(tài)調(diào)度問(wèn)題,且未對(duì)影響調(diào)度性能的因素進(jìn)行分析。GEORGE研究了考慮機(jī)器故障和加工路徑可選的車間動(dòng)態(tài)調(diào)度,并以作業(yè)平均延遲和平均加工成本對(duì)調(diào)度性能進(jìn)行評(píng)估,但未考慮加工任務(wù)臨時(shí)變動(dòng)和周期性再調(diào)度時(shí)的情形,同時(shí)也缺乏對(duì)影響調(diào)度性能因素的分析。ADIBI研究了工件隨機(jī)到達(dá)和機(jī)器故障等動(dòng)態(tài)事件的處理,并以最小化加工時(shí)間和工件延期對(duì)調(diào)度性能進(jìn)行評(píng)估,卻未分析影響調(diào)度性能的因素;同時(shí),也未考慮周期性再調(diào)度、工藝路線的柔性化以及機(jī)器資源的可選性等約束條件。FATTAHI研究了考慮新機(jī)器加入、新工件到達(dá)和工件處理時(shí)間變化的柔性車間動(dòng)態(tài)調(diào)度,卻未考慮機(jī)器故障和周期性再調(diào)度;同時(shí),以最小化完工時(shí)間度量調(diào)度的有效性,評(píng)價(jià)目標(biāo)較為單一;以偏差來(lái)度量調(diào)度的穩(wěn)定性后未對(duì)影響調(diào)度性能的因素進(jìn)行分析。GHOLAMI在未考慮周期性再調(diào)度、工藝路線的柔性化和機(jī)器資源的可選性的情況下,研究了機(jī)器故障的柔性車間動(dòng)態(tài)調(diào)度,并分析了不同故障參數(shù)對(duì)調(diào)度的影響,但缺乏對(duì)影響動(dòng)態(tài)調(diào)度性能因素的全面研究?；谏鲜龇治?針對(duì)工藝路線柔性化和機(jī)器資源可選情況下的柔性生產(chǎn)車間,本文以最小化工件的拖期懲罰和和最小化最大完工時(shí)間為目標(biāo),在考慮機(jī)器故障、加工任務(wù)臨時(shí)變動(dòng)及周期性再調(diào)度等動(dòng)態(tài)生產(chǎn)環(huán)境的基礎(chǔ)上,建立了柔性作業(yè)車間多目標(biāo)動(dòng)態(tài)調(diào)度模型;然后,結(jié)合滾動(dòng)窗口再調(diào)度技術(shù),提出了基于周期和事件驅(qū)動(dòng)的自適應(yīng)多目標(biāo)柔性動(dòng)態(tài)調(diào)度算法,并分析了機(jī)器故障發(fā)生方式和交貨期變更等擾動(dòng)因素及再調(diào)度周期窗口的大小對(duì)調(diào)度性能的影響,以此確定影響生產(chǎn)進(jìn)度的主要因素,從而科學(xué)地指導(dǎo)實(shí)際生產(chǎn)。1現(xiàn)狀及約束和約束條件柔性作業(yè)車間動(dòng)態(tài)調(diào)度問(wèn)題描述為:n個(gè)工件{J1,J2,…,Jn}在m臺(tái)機(jī)器{M1,M2,…,Mm}上加工,任一工件Ji由一系列加工先后順序確定的工序{Oij,j∈(1,2,…,ni)}組成,ni表示加工工件Ji的工序總數(shù),Mij表示可以加工工件i的第j道工序的機(jī)器集合Mij?{1,2,…,M},(1≤i≤n,1≤j≤ni),工序Oij可使用Mij中的任一機(jī)器加工,加工時(shí)間隨所選擇機(jī)器的不同而不同。然而,工件生產(chǎn)加工過(guò)程中常存在機(jī)器故障、加工任務(wù)臨時(shí)變動(dòng)及周期性再調(diào)度等問(wèn)題。因此,本文正是基于上述問(wèn)題,為每道工序選擇最合適的機(jī)器,確定每臺(tái)機(jī)器上各工件工序的最佳加工順序及開(kāi)工時(shí)間,使工件生產(chǎn)周期和拖期懲罰等性能指標(biāo)達(dá)到最優(yōu)。為使研究更具可操作性,本文設(shè)定以下假設(shè)條件:(1)所有機(jī)器設(shè)備零時(shí)刻都可用。(2)工序在可供選擇的機(jī)器上的加工時(shí)間已確定。(3)出現(xiàn)再調(diào)度時(shí),不受影響的正在加工的工序繼續(xù)加工,直到本工序完成。本文從實(shí)際生產(chǎn)出發(fā),分別從生產(chǎn)周期和拖期懲罰兩個(gè)方面建立優(yōu)化目標(biāo)。生產(chǎn)周期用工件的最小化最大完成時(shí)間f1度量,拖期懲罰用f2度量。f1=min{max(Ci|i=1,2,…,n)};(1)f2=min(n∑i=1Τi)=min(n∑i=1βi×max(0,Ci-Di));(2)f2=min(∑i=1nTi)=min(∑i=1nβi×max(0,Ci?Di));(2)F=f1+βf2。(3)工件Ji的完工時(shí)間為Ci,交貨期為Di,如果Ci>Di,則工件Ji受到拖期懲罰,工件Ji的單位拖期Ti的懲罰系數(shù)為βi(i=1,2,…,n)。在加工過(guò)程中,柔性作業(yè)車間多目標(biāo)動(dòng)態(tài)調(diào)度還須滿足以下約束條件:Cijk-Ci(j-1)g≥Pijk+Lijk+Uijk,j≠1,Xijk=1;(4)Cijk-Pijk≥Lijk+Uijk;(5)∑kXijk=1,k∈Μij??i,j;(6)∑kXijk=1,k∈Mij??i,j;(6)Cijk-Cabk≥Pijk+Lijk+Uijk,Yabijk=1,Xijk=1,Xabk=1;(7)式中:Cijk為工件i的第j道工序在機(jī)器k上的完成時(shí)間;Pijk為工件i的第j道工序在機(jī)器k上的加工時(shí)間;Lijk為工件i的第j道工序在機(jī)器k上的裝載時(shí)間;Uijk為工件i的第j道工序在機(jī)器k上的卸載時(shí)間;Xijk為工件i的第j道工序在機(jī)器k上的加工的判別條件,如果是,則Xijk=1,否則Xijk=0;Yabijk為機(jī)器k上加工工序b和j的順序判別條件,如果工件a的工序b先于工件i的工序j在機(jī)器k上加工,則Yabijk=1,否則Yabijk=0;STijk表示工件i第j道工序在機(jī)器k上的開(kāi)始加工時(shí)間。其中:式(4)表示工件i的第j道工序必須在第j-1道工序完成后才能開(kāi)始;式(5)表示工件i的第j道工序在機(jī)器k上加工時(shí)間不為負(fù);式(6)表示工件i的第j道工序只能選擇在可選機(jī)器集合中的一臺(tái)機(jī)器上加工;式(7)表示任一確定時(shí)刻,機(jī)器k不能同時(shí)加工任意兩個(gè)不同的工件,也不能同時(shí)加工任意兩道不同的工序;式(8)～式(9)表示工件i的第j道工序完成時(shí)間約束。上述目標(biāo)函數(shù)、假設(shè)和約束條件可保證動(dòng)態(tài)調(diào)度結(jié)果的可行性和有效性,為生產(chǎn)活動(dòng)提供技術(shù)支持。然而,動(dòng)態(tài)調(diào)度問(wèn)題除了要證明調(diào)度的可行性和有效性以外,還需要求解偏差度來(lái)驗(yàn)證調(diào)度的穩(wěn)定性。偏差度是靜態(tài)調(diào)度和再調(diào)度兩種方案中加工周期之差的絕對(duì)值與動(dòng)態(tài)調(diào)度加工周期之比。ST和ST′分別表示靜態(tài)調(diào)度與再調(diào)度方案加工周期。Deviation=|ST-ST′|/ST′。(10)2車間的調(diào)度計(jì)劃,應(yīng)根據(jù)分配高度確定車間生產(chǎn)動(dòng)態(tài)調(diào)度是將車間生產(chǎn)看成一個(gè)動(dòng)態(tài)過(guò)程,工件依次進(jìn)入待加工狀態(tài)等待加工,一旦所需資源得到滿足就進(jìn)入加工狀態(tài),接受系統(tǒng)加工,同時(shí)完成加工的工件又不斷離開(kāi)。而靜態(tài)調(diào)度則認(rèn)為所有工件的信息和車間狀態(tài)都是明確的,一旦調(diào)度計(jì)劃確定,車間就按計(jì)劃生產(chǎn)。與靜態(tài)調(diào)度比較,動(dòng)態(tài)調(diào)度不僅需要考慮初始狀態(tài),還需要考慮工件交貨期改變及機(jī)器故障等多種突發(fā)事件、急件或計(jì)劃工件不斷加入等動(dòng)態(tài)因素。由此可知,動(dòng)態(tài)調(diào)度與靜態(tài)調(diào)度最大的不同就在于動(dòng)態(tài)調(diào)度不但能適應(yīng)動(dòng)態(tài)的加工環(huán)境,而且當(dāng)發(fā)生機(jī)器故障、工件交貨期改變等突發(fā)事件時(shí),可以迅速地做出響應(yīng),對(duì)加工工件實(shí)施再調(diào)度,以適應(yīng)變化了的生產(chǎn)環(huán)境。鑒于此,本文提出了柔性作業(yè)車間多目標(biāo)動(dòng)態(tài)調(diào)度問(wèn)題,并設(shè)計(jì)了下述調(diào)度策略:動(dòng)態(tài)調(diào)度窗口規(guī)劃、動(dòng)態(tài)調(diào)度實(shí)施的類型選擇及動(dòng)態(tài)調(diào)度算法設(shè)計(jì)。2.1工件的再調(diào)度控制實(shí)現(xiàn)動(dòng)態(tài)調(diào)度首先要定義工件集,標(biāo)注工件的處理狀態(tài)。本文將所有工件分成未加工工件集SU、待加工工件集Sa、正在加工工件集SW和己完成工件集SC四個(gè)子集。調(diào)度開(kāi)始前,所有工件信息都保存在未加工工件集中,隨著生產(chǎn)準(zhǔn)備工作的完成,根據(jù)工件的優(yōu)先級(jí)別選擇一定數(shù)量的工件調(diào)入待加工工件集等待加工,如果能夠加工該工件工序的機(jī)器設(shè)備資源得到釋放,則立即將該工件從待加工工件集轉(zhuǎn)入正在加工工件集;如果某一時(shí)刻正在加工某工件的設(shè)備出現(xiàn)故障,則立即啟動(dòng)一次再調(diào)度,將該工件連同該時(shí)刻保存到待加工工件集中,等同待加工工件,享有優(yōu)先安排加工的機(jī)會(huì),當(dāng)故障機(jī)器完成維護(hù)后,將該工件從待加工工件集轉(zhuǎn)入到正在加工工件集,直到該工件所有工序加工完成以后,將該工件從正在加工工件集轉(zhuǎn)入到己完成工件集;當(dāng)一個(gè)再調(diào)度周期到來(lái)時(shí),從未加工工件集中選擇一定數(shù)量的工件調(diào)入待加工工件集中,與待加工工件集里原先剩余的工件一起進(jìn)行下一輪調(diào)度優(yōu)化。2.2事件與周期驅(qū)動(dòng)的混合再調(diào)度動(dòng)態(tài)調(diào)度有事件驅(qū)動(dòng)再調(diào)度、周期性再調(diào)度和基于周期與事件驅(qū)動(dòng)的混合再調(diào)度三種類型。事件驅(qū)動(dòng)調(diào)度是指當(dāng)出現(xiàn)一個(gè)使系統(tǒng)狀態(tài)發(fā)生變化的事件時(shí)立即進(jìn)行再調(diào)度。在車間的生產(chǎn)加工過(guò)程中存在著各種突發(fā)事件,為及時(shí)應(yīng)對(duì)這些突發(fā)事件,必須立即進(jìn)行調(diào)度。周期性再調(diào)度是每隔一段生產(chǎn)周期進(jìn)行一次再調(diào)度。在每個(gè)生產(chǎn)周期開(kāi)始前進(jìn)行再調(diào)度,當(dāng)生產(chǎn)周期開(kāi)始后按調(diào)度結(jié)果執(zhí)行。周期性再調(diào)度使生產(chǎn)保持一定的穩(wěn)定性,是實(shí)際生產(chǎn)中采用最多的調(diào)度方法。事件驅(qū)動(dòng)再調(diào)度能處理突發(fā)事件,但對(duì)未來(lái)事件缺乏預(yù)見(jiàn)能力,沒(méi)有整體的概念,周期性再調(diào)度可提高生產(chǎn)的穩(wěn)定性,但無(wú)法處理突發(fā)事件。事件與周期驅(qū)動(dòng)的混合再調(diào)度綜合了兩者的優(yōu)點(diǎn),既可以較好地響應(yīng)實(shí)際的動(dòng)態(tài)環(huán)境,又能保持一定的穩(wěn)定性,因此本文重點(diǎn)研究基于事件和周期驅(qū)動(dòng)的混合再調(diào)度,其流程如圖1所示。上述流程描述為:在調(diào)度過(guò)程中,當(dāng)有機(jī)器故障、工件交貨期改變等事件發(fā)生時(shí),實(shí)施一次再調(diào)度;當(dāng)一個(gè)再調(diào)度周期ΔT結(jié)束時(shí),啟動(dòng)一次再調(diào)度,即將加工完成的工件遷出工件調(diào)度窗口,修改可利用設(shè)備項(xiàng),將交貨期提前的工件或待加工的工件遷入工件調(diào)度窗口,使調(diào)度窗口中工件的數(shù)目保持一定的平衡,并對(duì)調(diào)度窗口中的工件實(shí)施再調(diào)度;當(dāng)又有再調(diào)度事件發(fā)生時(shí),重復(fù)上述過(guò)程,直到全部工件加工完成。在考慮基于事件和周期驅(qū)動(dòng)的混合再調(diào)度策略的情況下,為實(shí)現(xiàn)本文所提出的柔性多目標(biāo)作業(yè)車間動(dòng)態(tài)調(diào)度的整體目標(biāo)最優(yōu),同時(shí)保證每批進(jìn)入調(diào)度窗口中的工件取得最優(yōu)值,目標(biāo)函數(shù)(式(3))可描述為:minY=maxk∈SΜ(Τk-ts,x)+βi∑i∈Sxmax(0,Ci-Di);(11)minY=maxk∈SM(Tk?ts,x)+βi∑i∈Sxmax(0,Ci?Di);(11)Τk=tkr+∑j∈Κxk(Ρjk+Ljk+Ujk)+ts,x;(12)Tk=tkr+∑j∈Kxk(Pjk+Ljk+Ujk)+ts,x;(12)ts,x+1=mini∈Sx(te+ts,x+ΔΤ)ts,x+1=mini∈Sx(te+ts,x+ΔT)。(13)2.3染色體的機(jī)器編碼及其加工自適應(yīng)多目標(biāo)柔性動(dòng)態(tài)調(diào)度算法(AdaptiveMulti-ObjectiveFlexibleDynamicSchedulingAlgorithm,AMOFDSA)操作流程如圖2所示,具體步驟如下:步驟1初始化調(diào)度次數(shù)x=0,開(kāi)始調(diào)度的時(shí)間ts,x=0,給定窗口中工件的最大數(shù)目W,并初始化Sa,SW,SC,SU。步驟2對(duì)當(dāng)前工件窗口中的工件實(shí)施以下操作:(1)初始化STk=ts,x和進(jìn)化代數(shù)t=0。(2)實(shí)施染色體編碼,產(chǎn)生初始種群P(popsize)。編碼是實(shí)施優(yōu)化的首要和關(guān)鍵問(wèn)題,目前已經(jīng)提出了基于工序、優(yōu)先表、工件對(duì)關(guān)系、工件、完成時(shí)間、優(yōu)先規(guī)則、非連接圖、機(jī)器和隨機(jī)鍵9種JSSP編碼方法,但上述方法均屬單一編碼方式,在求解多目標(biāo)柔性車間動(dòng)態(tài)調(diào)度優(yōu)化問(wèn)題時(shí),存在編碼困難和解碼繁瑣的問(wèn)題。為此,本文設(shè)計(jì)了基于工序與加工機(jī)器相融合的兩層編碼方法。第一層采用基于工序的表達(dá)法進(jìn)行編碼,即給所有同一工件的工序指定相同的符號(hào),然后根據(jù)它們?cè)诮o定染色體中出現(xiàn)的順序加以解釋。如在3×3問(wèn)題中,假設(shè)給定的染色體為,其中1代表工件j1,2代表工件j2,3代表工件j3,因?yàn)槊總€(gè)工件有三道工序,所以每個(gè)工件在一個(gè)染色體中剛好出現(xiàn)三次。第二層是該工件的相應(yīng)工序所使用的機(jī)器編號(hào),如工序Oij的機(jī)器編碼為可以加工Oij的機(jī)器集合Mij中的任一機(jī)器。圖3即為一個(gè)染色體樣例,其中工件3的第1道工序在機(jī)器集合M31中的任一臺(tái)機(jī)器上加工,工件2的第1道工序在機(jī)器集合M21中的任一臺(tái)機(jī)器上加工,工件2的第2道工序在機(jī)器集合M22中的任一臺(tái)機(jī)器上加工,依次類推。這種兩層編碼方式能滿足工藝路線柔性化和機(jī)器資源可選的約束條件,任意基因串的置換排列始終代表一種可行的操作程序,總能保證產(chǎn)生可行調(diào)度。此外,它具有編碼空間小、避免死鎖、半Lamarckian特性和2類解碼復(fù)雜性等特點(diǎn)。(3)如果t?T,則從種群中取出第Z(1≤Z≤popsize)個(gè)染色體并轉(zhuǎn)入(4)。若t=T,則輸出Fi和窗口中工件的最終調(diào)度結(jié)果,轉(zhuǎn)步驟3。(4)從可用機(jī)器集Mij中為工件i的第j道工序選擇合適的機(jī)器k,選擇的原則是在不與其他工件加工過(guò)程沖突的情況下,選擇具有最短加工時(shí)間的機(jī)器,以保證工件滿足交貨期要求。(5)如果是工件i第1道工序,則按照式(8)計(jì)算工件i的第1道工序在所選機(jī)器k上的加工時(shí)間,如果非第1道工序,則令工件i的第j+1道工序開(kāi)始時(shí)間等于工件i的第j道工序的完成時(shí)間,按照式(9)計(jì)算第j+1道工序的加工時(shí)間,直到工件i的所有工序都已經(jīng)加工完成后,按照式(3)計(jì)算出工件i的適應(yīng)度值。Ρi=Fi/popsize∑i=1FiPi=Fi/∑i=1popsizeFi(14)ΡC={ΡC1-(ΡC1-ΡC2)(f-favg)fmax-favgf≥favg,ΡC1f＜favg。(15)(8)自適應(yīng)變異操作。變異率的自適應(yīng)調(diào)整公式為:步驟3在按照步驟2的調(diào)度邏輯加工的過(guò)程中,實(shí)時(shí)判斷是否發(fā)生擾動(dòng)、再調(diào)度周期時(shí)刻是否到來(lái)。如果出現(xiàn)擾動(dòng),判斷是由于機(jī)器故障引起的還是由于工件交貨期變更引起的:如果機(jī)器發(fā)生了故障,則立即啟動(dòng)一次再調(diào)度,取消機(jī)器該時(shí)刻工件工序的加工,計(jì)算該工序的剩余加工時(shí)間,將該工序連同該時(shí)刻及剩余加工時(shí)間保存到待加工工件集中,等同待加工工件,享有優(yōu)先安排加工的機(jī)會(huì),當(dāng)故障機(jī)器完成維護(hù)后,將該工件從待加工工件集轉(zhuǎn)入到正在加工工件集進(jìn)行加工,直到該工件所有的工序加工完成;如果此刻工件交貨期發(fā)生變更,則立即啟動(dòng)一次再調(diào)度,判斷該工件是否加工完成:如果已經(jīng)加工完成,則繼續(xù)執(zhí)行其他工件的加工;如果未完成,則在保證目標(biāo)函數(shù)式(3)較優(yōu)的前提下,優(yōu)先安排該工件的加工。如果此時(shí)刻一個(gè)再調(diào)度周期到來(lái),則立即啟動(dòng)一次再調(diào)度,從未加工的工件集中選擇一定數(shù)量的工件調(diào)入待加工工件集中,與待加工工件集中原先剩余的工件一起進(jìn)行下一輪調(diào)度優(yōu)化,如果此時(shí)還未到再調(diào)度周期則進(jìn)入周期再調(diào)度等待狀態(tài),直到再調(diào)度周期時(shí)刻到來(lái)時(shí)開(kāi)始實(shí)施周期再調(diào)度?？傊?出現(xiàn)機(jī)器故障、工件交貨期改變等事件就啟動(dòng)一次再調(diào)度,當(dāng)再調(diào)度周期時(shí)刻到來(lái)時(shí),同樣需要啟動(dòng)一次再調(diào)度,轉(zhuǎn)步驟4。步驟4及時(shí)更新信息,將已經(jīng)完成的工件從SW中遷出放到SC中;將工件從待加工工件集Sa中遷入工件調(diào)度窗口SW中,使調(diào)度窗口中工件的數(shù)目保持一定的平衡。如果所有工件都已加工完成,則輸出動(dòng)態(tài)調(diào)度結(jié)果,否則,轉(zhuǎn)步驟3。其中:W為工件窗口中的最大工件數(shù);t為進(jìn)化代數(shù);STk為機(jī)器k可以開(kāi)始加工的時(shí)間。在式(15)和式(16)中:fmax為群體中最大的適應(yīng)度值,favg為每代群體的平均適應(yīng)度值,f表示交叉的兩個(gè)個(gè)體中較大的適應(yīng)度值,f*表示要變異的個(gè)體的適應(yīng)度值。2.4周期調(diào)度時(shí)間間隔相關(guān)參數(shù)描述如下:minfinishT為n個(gè)工件中的最小完成時(shí)間;minindex為對(duì)應(yīng)該工件在群體中的索引指數(shù);T_item為周期調(diào)度時(shí)間間隔;T_count為周期調(diào)度次數(shù);Mark_TorE為周期或事件驅(qū)動(dòng)的標(biāo)志;α為足夠大的正整數(shù);due_date(i)=γ為工件i的交貨期改變到γ時(shí)刻;T_event1,T_event2,T_event3分別為機(jī)器故障時(shí)刻、故障修復(fù)時(shí)刻和工件交貨期更改時(shí)刻。2.5faut4.fact以機(jī)器故障為例,說(shuō)明當(dāng)有機(jī)器故障事件發(fā)生時(shí)如何實(shí)施再調(diào)度。相關(guān)參數(shù)描述如下:TT為工件job_id的第procedure_id(job_id)個(gè)工序的機(jī)器開(kāi)始加工時(shí)間;T_item為周期調(diào)度時(shí)間間隔;fault_machine(1)、fault_machine(2)、fault_machine(3)分別為故障機(jī)器標(biāo)志、故障發(fā)生時(shí)刻和故障修復(fù)時(shí)刻;num_procedure為每個(gè)工件的工序數(shù)目;individul為染色體;job_id為工件標(biāo)志;procedure_id(job_id)為工件job_id的工序標(biāo)志;machine_id為機(jī)器標(biāo)志。3動(dòng)態(tài)調(diào)度周期對(duì)再調(diào)度加工周期的影響以某公司的柔性制造單元?jiǎng)討B(tài)調(diào)度為例進(jìn)行仿真,制造單元共有3臺(tái)加工設(shè)備,加工10類典型零件,每類零件又包括3道工序,零件類型、交貨期,加工時(shí)間等信息如表1所示。卸載時(shí)間和安裝時(shí)間都為2s,根據(jù)合同拖期懲罰條款和實(shí)際生產(chǎn)狀況取拖期完成懲罰系數(shù)β=1,群體規(guī)模為100,再調(diào)度周期ΔT=50s,最大進(jìn)化代數(shù)T=100,交叉率計(jì)算參數(shù)PC1=0.9,PC2=0.6;變異率計(jì)算參數(shù)PM1=0.1,PM2=0.001;生產(chǎn)過(guò)程中考慮以下擾動(dòng):①機(jī)器1在時(shí)刻70出現(xiàn)故障,時(shí)刻90修復(fù);②在時(shí)刻120工件10的交貨期由原來(lái)的250提前到時(shí)刻180。經(jīng)計(jì)算得到函數(shù)值變化曲線圖、最佳的靜態(tài)調(diào)度甘特圖和動(dòng)態(tài)調(diào)度甘特圖如圖4～圖6所示。由圖4～圖6可知,隨著進(jìn)化代數(shù)的增加,函數(shù)最小值和平均值逐漸穩(wěn)定,在不考慮擾動(dòng)因素和再調(diào)度周期的情況下,靜態(tài)調(diào)度輸出甘特圖的加工周期是212s,在考慮再調(diào)度周期、機(jī)器故障、交貨期提前的情況下,動(dòng)態(tài)調(diào)度輸出甘特圖的加工周期是217s。如果沒(méi)有實(shí)施動(dòng)態(tài)調(diào)度,則由圖5可知,在時(shí)刻70,工件7的第2道工序的加工被暫停,同時(shí)造成工件2的第2道工序的加工延遲,必然造成加工周期遠(yuǎn)大于動(dòng)態(tài)調(diào)度加工周期217s,可見(jiàn)動(dòng)態(tài)調(diào)度在擾動(dòng)出現(xiàn)時(shí)能大幅縮短加工周期。由圖6可知,在工件加工的整個(gè)過(guò)程中共發(fā)生了3次事件再調(diào)度、5次周期再調(diào)度和2次擾動(dòng)事件完成再調(diào)度。為驗(yàn)證算法性能,本文所提算法與文獻(xiàn)所提的多目標(biāo)遺傳算法(Multi-ObjectiveGeneticAlgorithms,MOGA)進(jìn)行對(duì)比分析,文獻(xiàn)算法參數(shù)設(shè)置如下:再調(diào)度周期ΔT=50,群體規(guī)模為100,最大進(jìn)化代數(shù)為100,交叉率為0.9,變異率為0.1。兩種算法分別運(yùn)行20次,輸出結(jié)果如表2所示。由輸出結(jié)果可以看出,AMOFDSA在解優(yōu)化的程度上都有很大的優(yōu)越性。為全面認(rèn)識(shí)擾動(dòng)因素和再調(diào)度周期對(duì)動(dòng)態(tài)調(diào)度性能的影響,通過(guò)變更再調(diào)度周期窗口的大小、機(jī)器故障發(fā)生方式和工件交貨期來(lái)研究動(dòng)態(tài)調(diào)度性能的變化。在每種擾動(dòng)狀態(tài)下,分別運(yùn)行程序20次,得到的研究結(jié)果如表3所示。表中故障機(jī)器(1:70-90)表示機(jī)器1在時(shí)刻70發(fā)生故障、在時(shí)刻90修復(fù);交貨期變更(10:250-180)表示工件10的交貨期由時(shí)刻250提前到時(shí)刻180,依次類推;ˉf1和ˉf2表示程序運(yùn)行20次得到的平均加工周期和平均拖期懲罰;ˉt表示程序運(yùn)行20次的平均時(shí)間消耗。由表3可知,在相同的ΔT和機(jī)器故障方式下,工件交貨期變更從(10:250-180),(9:195-160)到(6:160-150)的過(guò)程中,平均加工周期不斷變長(zhǎng),偏差度、平均拖期懲罰和平均時(shí)間消耗不斷提高,這種變化說(shuō)明交貨期較短的工件的交貨期變更擾動(dòng)對(duì)動(dòng)態(tài)調(diào)度性能有重要影響;在相同的ΔT和工件交貨期變更方式下,故障機(jī)器從(1:70-90),(2:70-90)到(3:70-90)變化的過(guò)程中,平均加工周期整體趨勢(shì)不斷變長(zhǎng),偏差度、平均拖期懲罰和平均時(shí)間消耗不斷提高,這種變化說(shuō)明加工任務(wù)比較均勻的機(jī)器(圖4中機(jī)器3上的工件加工時(shí)間比較均勻)的故障擾動(dòng)對(duì)動(dòng)態(tài)調(diào)度性能有重要影響;在相同的故障機(jī)器和工件交貨期變更方式下,ΔT從50～100變化的過(guò)程中,平均時(shí)間消耗呈現(xiàn)降低趨勢(shì),平均加工周期、偏差度及平均拖期懲罰出現(xiàn)不穩(wěn)定現(xiàn)象,這種變化說(shuō)明對(duì)該問(wèn)題應(yīng)該存在一個(gè)合適的再調(diào)度周期,可以有效提高機(jī)器利用率,從而對(duì)動(dòng)態(tài)調(diào)度性能產(chǎn)生重要影響。4未來(lái)研究方向本文采用多目標(biāo)柔性動(dòng)態(tài)調(diào)度算法,基于周期和事件驅(qū)動(dòng)的混合再調(diào)度策略,對(duì)柔性作業(yè)車間多目標(biāo)動(dòng)態(tài)調(diào)度進(jìn)行了研究,得到以下結(jié)論:(1)基于工序與加工機(jī)器的兩層染色體編碼方法,可實(shí)現(xiàn)加工工序與該工序可選機(jī)器集合對(duì)應(yīng)關(guān)系的編碼,能夠同時(shí)優(yōu)化FJSP中的工藝路線和加工順序。(2)與靜態(tài)調(diào)度相比,動(dòng)態(tài)調(diào)度能夠跟蹤車間加工環(huán)境的變化,從而對(duì)加工過(guò)程中發(fā)生的突發(fā)事件迅速做出反應(yīng)。(3)基于周期與事件驅(qū)動(dòng)的混合再調(diào)度同時(shí)具有事件驅(qū)動(dòng)再調(diào)度和周