離散生產(chǎn)中作業(yè)車間調(diào)度問題的研究

離散生產(chǎn)中作業(yè)車間調(diào)度問題的研究

運(yùn)營場地的規(guī)劃問題（jbs）是一個(gè)典型的硬件問題。求解作業(yè)車間調(diào)度問題的算法主要分為兩類:精確算法和近似算法。精確算法由于其指數(shù)級(jí)增長的時(shí)間復(fù)雜度,僅適用于小規(guī)模的問題;近似算法由于其運(yùn)行速度快,常用于求解規(guī)模較大的作業(yè)車間調(diào)度問題,其中以基于群體的智能算法和鄰域搜索算法為主。應(yīng)用智能算法求解作業(yè)車間調(diào)度問題的典型成果,如:Gen等近年來,學(xué)者們提出了愈來愈多新穎的智能算法,智能算法的共同特點(diǎn)都是模擬了自然過程,但是每種智能算法的優(yōu)缺點(diǎn)不同,對(duì)于解決某些特定問題的效果也不一樣,因此嘗試并發(fā)掘各種智能算法的優(yōu)點(diǎn)并運(yùn)用到實(shí)際問題中去,是一個(gè)很重要的研究方向。萬有引力搜索算法(GS)是一種新穎的群智能算法,由Rashedi等1運(yùn)營場地的規(guī)劃和設(shè)計(jì)1.1機(jī)床加工的特點(diǎn)給定已知條件和假設(shè):(1)已知工件的加工路線和加工時(shí)間。(2)假設(shè)在任何時(shí)刻,每臺(tái)機(jī)器最多只能加工一個(gè)工件,每個(gè)工件最多只能由一臺(tái)機(jī)器加工。(3)假設(shè)工件按照給定的工藝路線進(jìn)行加工且加工過程不能間斷。(4)機(jī)器之間緩沖區(qū)容量為無窮大,且機(jī)器不發(fā)生故障。JSSP通常描述為n個(gè)工件在m臺(tái)機(jī)器上加工,每個(gè)工件均需要不重復(fù)地經(jīng)過所有機(jī)床加工,G為單件車間調(diào)度。調(diào)度的目標(biāo)是確定各機(jī)器上工件的加工順序,使得最大完工時(shí)間C1.2約束工序?qū)衔墨I(xiàn)[13]采用線性規(guī)劃定義了作業(yè)車間調(diào)度的模型,描述如下:令J={J令A(yù)表示同一工件的工序前后關(guān)系的約束工序?qū)?V其中:式(1)為作業(yè)車間調(diào)度問題的目標(biāo)函數(shù),本文中的目標(biāo)為最小化最大完工時(shí)間;不等式(2)保證每個(gè)工件的工序順序滿足要求,式中〈i,j〉指約束工序?qū)?表示同一工件的前后工序,i表示前工序,j表示后續(xù)工序;不等式(3)保證每臺(tái)機(jī)器一次只能加工一個(gè)工件,〈i,j〉表示在機(jī)器M2遺傳鄰近生產(chǎn)力算法用于解決工作場所的規(guī)劃問題2.1染色體的解碼本文采用文獻(xiàn)[14]提出的應(yīng)用于遺傳算法的基于工序的編碼方式,對(duì)本文的染色體進(jìn)行編碼。每個(gè)染色體由n×m個(gè)基因組成,其中每個(gè)基因代表對(duì)應(yīng)的工件號(hào),工件的加工順序取決于該工件號(hào)在染色體中出現(xiàn)的順序。圖1為規(guī)模3×3的染色體編碼示意圖,O按照上述的解碼方式得到的調(diào)度方案為一個(gè)半主動(dòng)調(diào)度。半主動(dòng)調(diào)度指各工序按最早可能開始時(shí)間進(jìn)行加工的調(diào)度類型,不能保證充分利用機(jī)器的空閑時(shí)間,因此采用主動(dòng)調(diào)度的方式來對(duì)染色體進(jìn)行解碼。主動(dòng)調(diào)度指任何一臺(tái)機(jī)器的每一段空閑時(shí)間都不足以加工一道可加工工序的半主動(dòng)調(diào)度,采用插入式的主動(dòng)調(diào)度解碼方式2.2父代的選擇及搜索效率交叉操作是遺傳算法中一項(xiàng)重要的進(jìn)化算子,主要標(biāo)準(zhǔn)是子代個(gè)體對(duì)父代個(gè)體優(yōu)良特性的繼承以及可行性,因此父代個(gè)體的選擇對(duì)子代的質(zhì)量及算法的搜索效率上有很大程度上的影響。本文借鑒萬有引力搜索算法中慣性質(zhì)量和歐式距離的概念,將其運(yùn)用于交叉操作中父代個(gè)體的選擇。2.2.1改進(jìn)萬有引力搜索算法萬有引力算法是一種基于萬有引力定律和牛頓第二定律的種群優(yōu)化算法。在牛頓萬有引力定律中,兩個(gè)個(gè)體間的萬有引力大小主要由兩個(gè)個(gè)體的質(zhì)量以及個(gè)體間的歐氏距離決定,萬有引力的大小影響了個(gè)體位置的移動(dòng)方向,是解決連續(xù)問題的有效算法。對(duì)于JSSP這類離散問題,采用原始的萬有引力搜索算法將變得不可行,因此本文借鑒萬有引力搜索算法中慣性質(zhì)量和歐氏距離的概念,將其運(yùn)用到交叉算子中,提出了一種新型的交叉策略。具體操作為:根據(jù)歐氏距離的概念衍生出染色體差距的概念,對(duì)染色體差距大的個(gè)體進(jìn)行交叉,提高解的多樣性;利用慣性質(zhì)量來控制個(gè)體的交叉對(duì)象數(shù)目,個(gè)體慣性質(zhì)量與適應(yīng)度值成正比,選擇慣性質(zhì)量較大的個(gè)體作為交叉?zhèn)€體的候選解,以增強(qiáng)算法的收斂性。原始萬有引力搜索算法中,個(gè)體a受到k假設(shè)種群大小P(1)針對(duì)當(dāng)前代t的每個(gè)父代染色體,選擇其他父代染色體中最優(yōu)的k其中,k(3)選取當(dāng)前代t的k2.2.2工序編碼的交叉操作在JSSP問題中,由于其編碼的特殊性,若基于傳統(tǒng)的兩點(diǎn)交叉操作,則會(huì)產(chǎn)生不可行解,因此本文采用基于工序編碼的交叉算子(POX)2.2.3增加交叉率來提高點(diǎn)代體的質(zhì)量交叉操作主要是為了繼承父代優(yōu)良的特性,從兩個(gè)父代染色體中獲取有效的基因,重組后得到子代染色體。但對(duì)于父代染色體中較優(yōu)的個(gè)體來說,需要盡可能保留個(gè)體不被破壞,因此要減小交叉率;而對(duì)于父代染色體中性能較差的個(gè)體,則需要通過與其他性能較優(yōu)的個(gè)體進(jìn)行交叉進(jìn)行改善,因此通過增加交叉率來實(shí)現(xiàn)。對(duì)于不同的染色體,設(shè)置不同的交叉率p其中:f2.3變異染色體生成變異操作的目的是為了增加染色體的多樣性,增強(qiáng)算法的探索能力,本文用3種染色體變異方式:倒轉(zhuǎn)、交換、移位。倒轉(zhuǎn)變異為選定染色體一段基因,將基因順序倒置得到新的染色體,如圖4(a)所示。交換變異為選取工件號(hào)不同的s個(gè)位置,交換這s個(gè)位置的工件,圖4(b)所示為s為3時(shí)交換變異后所有能得到的變異染色體。本文設(shè)定s為4。移位變異為選定一段基因,并將其整段進(jìn)行移動(dòng),如圖4(c)所示。對(duì)于變異方式的選擇,通過產(chǎn)生一個(gè)隨機(jī)小數(shù)p,若0≤p<0.3,進(jìn)行倒轉(zhuǎn)變異;若0.3≤p<0.7,進(jìn)行交換變異;否則進(jìn)行移位變異。2.4區(qū)域搜索鄰域結(jié)構(gòu)影響了算法求解的效率以及質(zhì)量,對(duì)于JSSP問題而言,基于關(guān)鍵路徑工序塊的鄰域結(jié)構(gòu)對(duì)于解鄰域的搜索效果顯著2.5變異率求解(1)算法初始化。初始化種群大小P(2)根據(jù)式(6)得到k(3)根據(jù)變異率對(duì)個(gè)體進(jìn)行變異操作,采用N5鄰域結(jié)構(gòu)進(jìn)行個(gè)體解的局部搜索。(4)根據(jù)適應(yīng)度函數(shù),采用主動(dòng)調(diào)度的方式進(jìn)行解碼,得到種群的適應(yīng)度值,并評(píng)價(jià)其大小。(5)判斷是否已經(jīng)滿足算法終止條件,若是,則結(jié)束運(yùn)行并輸出最優(yōu)解;否則,轉(zhuǎn)向步驟2。3ndows7的計(jì)算為了驗(yàn)證本文提出的遺傳鄰域萬有引力算法求解作業(yè)車間調(diào)度問題的有效性,采用3個(gè)FT類測試算例以及10個(gè)LA類測試算例進(jìn)行驗(yàn)證,算法基于VisualC++編程語言,在操作系統(tǒng)為Windows7,中央處理器的主頻2.67Hz,內(nèi)存為2GB的計(jì)算機(jī)上運(yùn)行。并將GA-LS-GS算法與標(biāo)準(zhǔn)的遺傳算法(GA)和加入鄰域搜索的遺傳算法(GALS)進(jìn)行對(duì)比。GA和GALS算法參數(shù)設(shè)置為:交叉率p從表1可知,本文提出的遺傳鄰域萬有引力算法針對(duì)3個(gè)FT類測試算例以及10個(gè)LA類測試算例都能找到最優(yōu)解,且其平均值以及標(biāo)準(zhǔn)差的性能也明顯優(yōu)于遺傳算法和結(jié)合鄰域搜索的遺傳算法,其中較為典型的FT10算例最優(yōu)解930和FT20算例最優(yōu)解1165對(duì)應(yīng)的甘特圖如圖6和圖7所示,驗(yàn)證了本文提出的遺傳鄰域萬有引力算法的有效性以及魯棒性。4實(shí)際應(yīng)用結(jié)果實(shí)際水表制造企業(yè)在生產(chǎn)水表零件過程中,為了提高企業(yè)的生產(chǎn)效率,增強(qiáng)企業(yè)對(duì)市場反應(yīng)的靈敏度,需引進(jìn)車間生產(chǎn)調(diào)度指導(dǎo)生產(chǎn)過程的運(yùn)行。水表的制造過程可以抽象化為作業(yè)車間調(diào)度模型,其中有6×6(6個(gè)工件、6臺(tái)機(jī)器)規(guī)模、30×15(30個(gè)工件、15臺(tái)機(jī)器)規(guī)模的水表零件制造過程。表2所示為6×6規(guī)模的水表制造企業(yè)實(shí)例數(shù)據(jù)(其中“—”表示該工件的工序不在對(duì)應(yīng)的機(jī)器上加工),由于30×15規(guī)模的實(shí)例數(shù)據(jù)量太大,此處不一一列出。針對(duì)6×6規(guī)模、30×15規(guī)模的實(shí)際水表制造的作業(yè)車間調(diào)度過程,利用本文提出的GA-LS-GS算法進(jìn)行求解,并與GA、GALS算法進(jìn)行對(duì)比。3種算法的種群大小以及最大迭代次數(shù)相同,具體參數(shù)設(shè)置如表3所示,分別獨(dú)立運(yùn)行50次后,得到仿真結(jié)果見表3。從表3中可知,對(duì)于6×6小規(guī)模的實(shí)際水表制造的作業(yè)車間調(diào)度問題,遺傳算法、加入鄰域搜索的遺傳算法以及本文提出的遺傳鄰域萬有引力算法每次都能找到相同的最大完工時(shí)間為868min,且其標(biāo)準(zhǔn)差都為0,最優(yōu)解下的甘特圖如圖8所示。對(duì)于30×15大規(guī)模實(shí)際水表制造的作業(yè)車間調(diào)度問題,GA-LS-GS算法求解得到的最大完工時(shí)間為2872min,比GA算法求解的3178min、GALS算法求解的3152min分別有306min和280min的時(shí)間縮減,可知有明顯的優(yōu)化。從平均值和方差上看,GA-LS-GS算法平均性能相比其他兩種算法更優(yōu),最優(yōu)解對(duì)應(yīng)的甘特圖如圖9所示。因此,本文提出的GA-LS-GS算法在解決實(shí)際水表制造問題中具有有效性和可行性,具有推廣價(jià)值。5算法的魯棒性問題針對(duì)作業(yè)車間調(diào)度問題,本文提出了一種遺傳鄰域萬有引力算法。該算法采用基于工序的編碼方式對(duì)問題進(jìn)行編碼、主動(dòng)調(diào)度的方式進(jìn)行解碼,個(gè)體進(jìn)化中算法借