多目標模糊柔性作業調度模型研究

0多目標模糊柔性車間調度車間配置管理一直是生產管理領域的研究熱點之一。由于工藝路徑和加工設備的多樣性，靈活車間配置管理在多個方面的實際生產計劃中變得越來越復雜。因此,為了尋求較為科學合理的生產調度排產計劃最優值或近似最優值,以縮短產品生產時間、提高交貨率,許多學者引入和提出了多種智能算法,以期解決柔性車間調度的最優生產排產問題,其中以1994年DAVIS引入的遺傳算法最具成效。該方法具有魯棒性好、通用性強、計算性能穩定等特點,在制造系統的車間調度領域獲得了廣泛的應用和發展。然而,進一步的研究發現,普通遺傳算法在求解復雜約束條件下的車間調度時,存在局部搜索能力較差、易早熟收斂且消耗時間長等不足。為了克服遺傳算法的上述缺陷,國內外學者分別從算法編碼、種群初始化、遺傳操作和算法邏輯設計等方面對該算法進行改進。其中,多種群遺傳算法因在改善算法性能與拓展應用范圍上的突出表現,得到眾多研究者的青睞。蔡良偉提出了由多個普通種群和一個優良種群構成的多種群遺傳算法,各個普通種群將進化得到的優良個體貢獻出來,組成一個靜態的、不參與進化的優良種子庫,普通種群在自己的后續進化進程中,直接從優良種群引進若干優良種子個體,代替本種群中的較劣個體,以改善本種群的品質,提高算法性能,但上述算法主要用于求解傳統的單目標作業車間調度問題,未考慮工件交貨期服從模糊時間窗分布且工藝路線柔性化條件下的多目標模糊柔性車間調度;COCHRAN提出了多種群兩階段遺傳算法,第一階段以單一種群進行進化,然后多個種群獨自進化,其本質上是一種串并混聯的算法,在不考慮工件模糊交貨期和工藝路線柔性化時的多目標平行機調度問題中,該算法表現出了較好的收斂性和穩定性;LI提出了雙鏈代理結構的多種群協同遺傳算法,并設計了各子種群之間的分享代理機制,以實現算法的協同進化,進而達到并行數據全局優化的目的,將其應用于經典JobShop問題時表現出了較高的求解精度和較快的收斂速度;SAKAWA在不考慮工藝路線可變及機器可選的條件下,以最大化顧客滿意度及最小化最大完成時間為目標,設計了一種基于種群個體間相似度的多種群遺傳算法,以解決具有模糊加工時間和模糊交貨期的多目標調度問題;GU提出了基于多種群改進協同進化思想和量子理論概念的兩種群量子遺傳算法,該算法依據競爭獵手、合作生存和大魚吃小魚的策略實現種群進化的目標,在應用于單目標隨機作業車間調度問題時,較標準遺傳算法表現出更為良好的性能;TOLEDO提出了含有遷移策略的多種群遺傳算法,當算法連續執行多次、目標函數值始終未發生變化時,就啟動并執行優良種群的遷移策略,直至滿足算法的停止準則,然而該算法主要致力于解決多作業車間同步集成的批量調度問題,不考慮工件交貨期服從模糊時間窗分布和工藝路線柔性化條件下的多目標作業車間調度;于曉義提出了基于工序染色體編碼的并行協同進化多種群遺傳算法,在不考慮工件模糊交貨期和工藝路線柔性化等約束條件下,將其應用于多車間協同生產作業調度,并驗證了該算法較標準遺傳算法在解決此類作業車間調度上的優越性;路飛提出了多種群并行遺傳算法,在進化過程中找出當前多個種群中各自的最優個體和最差個體,并選出總體最優個體取代各子種群中的最差個體,實現了各種群之間的橫向協作,該算法主要適用于考慮提前/拖期懲罰條件下的多機多階段流水車間調度問題。綜上所述,目前具有代表性的多種群遺傳算法研究成果均強調通過競爭與協作的思想,實現種群間或者個體間的信息遷移與共享,并通過算例驗證算法的先進性。但上述諸算法在進化過程中明顯缺乏種群間縱向信息的交流與反饋,以及種群協同進化的參考標準,易造成種群協同進化方向短時間內偏離理論目標值,且在有限的搜索時間內可能錯失最優解;同時,其應用多面向傳統作業車間調度,或不考慮工件模糊交貨期和工藝路線柔性化等約束條件下的多目標調度。基于以上分析并結合前述研究成果,本文提出了基于雙層編碼和縱橫雙層協同進化的多種群遺傳算法,并通過與其他算法進行對比分析考察該改進算法的有效性,然后把該算法用于多目標模糊柔性車間調度,驗證其在解決該類調度問題時所表現出的優良性能。1i道工序的計算多目標柔性作業車間調度研究的是N個工件在M臺機器上的加工過程,每個工件i(i=1,2,…,N)有ni道工序,Mij表示可以加工工件i的第j個工序的機器集合,Mij?{1,2,…,M},1≤i≤N,1≤j≤ni,每道工序可以在不同的機器上加工,每臺機器也可以加工不同工件的多道工序。調度的目標是在滿足工藝約束和機器可用的前提下,使工件的加工時間最短,同時使顧客滿意度最大,調度方案的數學描述如下:1.1目標函數1.2其他方面Xijk={1,?件i的?序j在機器k上加?;0,其他。(8)Rijabk={1?件i第j道?序和?件a第b道?序在同一機器k上執行?若?序j先于?序b;0其他。(9)1.3模型求解和建模在現實生產中,滿足模糊隸屬函數的梯形交貨期窗口可以反映加工中的不確定因素的影響,更能代表實際的生產作業過程,如圖1所示。圖中交貨期時間窗口被表示成Di(dci,dai,dbi,ddi),如果工件在時間窗[dai,dbi]配送,則客戶的滿意度為1,否則服從線性函數變化:μi(x)={0,x≤dci,x≥ddi;x-dcidai-dci,dci?x?dai;ddi-xddi-dbi,dbi?x?ddi;1,dai?x?dbi。(10)為了方便建模和求解,需要對現實問題進行一些抽象和簡化:(1)所有機器在零時刻都可以使用。(2)每個工件在每臺機器上的加工時間確定且已知。(3)一臺機器同一時刻只能加工一個工件,一個工件同一時刻只能在一臺機器上加工。(4)加工過程不允許中斷。2新種群的形成和發展根據變量協同配合、信息交換的思想,本文提出了一種縱橫雙層協同進化的多種群遺傳算法。其思路為:初始化n個并行普通種群,分別從這n個普通種群中根據適應度值排序選擇出優秀個體組成一個優良種群,即第n+1個種群,這n+1個種群協同進化,然后按照適應度值進行排序,從而選擇出最優解。在種群協同進化過程中,基于縱橫雙層協同的進化機制可以實現各種群之間的信息共享和優勢互補。橫向協同表現為:普通種群各子群在自己的進化進程中,直接引進n個普通種群中的最優個體代替本種群中的較劣個體?？v向協同表現為:n個普通種群協同進化完成以后,從n個普通種群中根據適應度值排序選擇出popsize個優秀個體形成新種群1,同時對第n+1個種群個體適應度值進行排序,選擇其中的優秀個體替換新種群1中的較劣個體,形成新種群2。算法結構如圖2所示。步驟1初始化參數。子種群個數為n,每個子種群隨機產生popsize個個體,最大進化代數為T,各子種群的交叉概率為PC,變異概率為PM。步驟2隨機產生滿足約束的n個初始群體pop(popsize),設定初始進化參數t=0。步驟3定義適應度函數f(x),計算子種群中每個個體的適應函數值f(xij)(i=1,…,n,j=1,…,popsize)并進行排序,選擇前popsize個優秀個體組成第n+1個種群,同時保存n個種群中最優適應度值f*,最小染色體i*。步驟4令t=1,對每一個子種群i(1≤i≤n)實施如下操作,產生一個新種群:(1)計算子種群中每個個體的適應函數值f(xij)(i=1,…,n,j=1,…,popsize)。(2)用i*取代各子群中的最差染色體。步驟5對第n+1個種群實施步驟4中的(1),(3)和(4)操作。步驟6令t=t+1,若t<T,則轉步驟4和步驟5,否則轉步驟7。步驟7根據適應度值排序,從當前n個子群中選擇popsize個優秀染色體,組成種群pop1(popsize)。步驟8根據適應度值排序,從第n+1個種群中選擇的優秀個體替換種群pop1(popsize)中的較劣個體,形成種群pop2(popsize)。步驟9計算pop2(popsize)中個體的適應度值,找出最小的染色體χ及適應度值λ,如果λ?f*且滿足循環代數,則令i*=χ,f*=λ,輸出f*和i*。步驟10若當前總最優個體滿足收斂條件,則算法結束,返回最優解;否則返回步驟4。3算法的設計3.1染色體的編碼本文設計了一種基于工序和加工機器的雙層基因編碼方式,第一層編碼表示待加工的工序,第二層編碼表示工序所選加工機器。具體的編碼方式如下:(1)確定染色體的長度L=n∑i=1Ri,n為工件數,Ri為工件i的工序數。(2)第一層編碼是基于工序的編碼,給所有同一工件的工序指定相同的符號,然后根據它們在給定染色體中出現的順序進行解釋,很容易看出染色體的任意排列總能夠產生可行調度。(3)第二層編碼表示各工件工序所選的加工機器,在該工序的可選加工機器集中隨機選取。圖3所示為一個染色體樣例,其中工件3的第1道工序在機器集合M31中任一臺機器上加工,工件2的第1道工序在機器集合M21中任一臺機器上加工,依次類推。這種兩層編碼方式既可滿足工藝路線和加工機器固定的約束條件,又可滿足工藝路線柔性化和機器資源可選的約束條件,任意基因串的置換排列始終代表一種可行的操作程序,總能夠保證產生可行調度。3.2計算顧客滿意度的計算為實現最小化最大完工時間和最大化顧客滿意度的調度目標,采用如下算法步驟:(1)從popsize個種群中選取一個個體S。(2)根據S計算調度工序P。(3)把P解碼成工件編號a、工序編號b和所使用機器編號m。(4)讀出機器m加工工件a的工序b所需的時間t,計算該工件的完成時間Ci(i=1,2,…,N)。(5)依據Ci的大小計算顧客對工件i的滿意度μi(C)。(6)分別計算N個工件的完成時間和顧客滿意度。(7)根據式(3)計算目標函數F。3.3在混合期間，描述了錯誤代碼3.4交叉和變異算子3.4.1分析兩個父代中的代次交叉操作是遺傳算法中增加種群多樣性、防止算法早熟和停滯的操作。由于本文是兩層編碼,需對兩部分分別進行交叉操作。步驟1第一層編碼從兩個父代隨機產生一點交叉位,根據交叉位將每個父代染色體分為兩個子集set1和set2。步驟2交換父代中的set1。步驟3把子代個體和父代個體進行對比分析,查找多余基因和缺失基因并進行修補。步驟4保留交叉前的機器基因。步驟5把子代個體和父代個體進行對比分析,根據交叉前的工序與機器的對應關系,把機器基因填寫到子代個體中。步驟6重復步驟1～步驟5,得到所需的新種群。3.4.2群體變換、互補變異及空間變異變異是按一定的概率改變個體基因鏈,變異操作的目的是維持群體多樣性,改善局部搜索能力,同時防止出現早熟現象。對于本文多種群遺傳算法,互換變異操作如下(如圖4):(1)變異過程同樣引入競爭機制,依變異概率PM得到需進行變異的個體。(2)對于第一層編碼,隨機選擇染色體中的兩基因位,交換其值;對于第二層編碼,根據第一層編碼的變換基因位及順序進行相應的變換。4數據與分析4.1影響pbest的因素由于控制參數對算法的搜索性能有重要影響,選取合理的參數并使算法沿著最佳的搜索軌跡快速找到全局最優解十分必要。鑒于此,本文通過算法敏感性分析了解控制參數對算法性能的影響程度,達到指導控制參數選取的目的。本文提出的多種群遺傳算法所涉及的主要控制參數包括種群個數N、種群規模popsize、進化代數MAXGEN、交叉概率PC和變異概率PM。在遺傳算法優化理論證明的參數范圍內選取以下基準參數值:種群個數N=4,種群規模popsize=50,進化代數MAXGEN=300,交叉率計算參數PC=0.8,變異率計算參數PM=0.2。以FT10為例,以最小化加工時間為目標,分別改變每個參數并運行20次,進行算法敏感性分析,如表1所示。由表1參數敏感性分析可知:(1)當基準參數值popsize=50,MAXGEN=300,PC=0.8,PM=0.2,種群個數處于區間時,對Pbest的影響程度較大,屬于敏感區;而當種群個數大于3時,這種影響就較小,屬于不敏感區。(2)當基準參數值N=4,MAXGEN=300,PC=0.8,PM=0.2,種群規模從10到200的增長過程中,Pbest明顯增加,在種群規模為200時,Pbest達到80%,但此時的平均收斂時間較長;進化代數與Pbest表現為同向增長趨勢,且這種趨勢隨著進化代數的增加而減弱。(3)當基準參數值N=4,popsize=50,MAXGEN=300,PM=0.2,交叉率從1到0的方向變化時,Pbest表現為同向減小的趨勢;在[0.8,1]的區間內Pbest保持在60%以上,在(0,0.2)區間,算法值收斂于1180,明顯劣于理論最優解,此時算法停滯不前,達到局部最優。(4)當基準參數值N=4,popsize=50,MAXGEN=300,PC=0.8,變異率在(0,0.6)區間時,Pbest表現為增加的趨勢,隨著變異率的不斷增加,算法表現為隨機搜索,Cbest也隨之出現下降趨勢。通過上述算法的敏感性分析,綜合考慮其收斂精度與速度,本文算法參數的選擇是合理有效的。4.2算法性能分析基于以上多種群遺傳算法的研究,以FisherandThompson的三個經典JobShop問題為例,以最小化加工時間為目標進行算法有效性驗證。算法相關參數設置如上,分別運行20次,得到的對比結果如表2所示。式中:Hi是第i次迭代的加工時間值(i=1,…,MAXGEN),E(Cmax)是加工時間期望值。由表2可知,本文提出的多種群遺傳算法比SGA算法有明顯的優勢,在處理FT6和FT10問題時比MPGA收斂時間短,找到最優解的概率大,在處理三類問題上都比C-Com算法有較大的優勢。通過以上分析驗證了本文多種群遺傳算法優良的收斂和尋優性能,為探索在處理多目標模糊柔性車間調度問題上是否也有突出的表現,采用文獻給出的10臺機器、6個工件、6道工序實驗數據進行仿真,參數如表3所示。以表3所示的數據為輸入,以式(3)為目標函數進行仿真,根據目標偏好和理論值的大小,選擇α=6,β=1,其余參數的選擇與上述標準FT調度相同,分別采用基本遺傳算法和多種群遺傳算法進行求解,經多次運行,得到的最優調度結果如圖5和圖6所示。圖5中,目標函數為256,時間消耗為9s,最大加工時間為55s;圖6中,目標函數為235,時間消耗為7s,最大加工時間為50s。通過圖5、圖6可知,對于多目標模糊柔性車間調度問題,在運行時間相差很小的情況下,多種群遺傳算法比基本遺傳算法搜索到更優解,同時工件的加工時間也得到優化,從而驗證了縱橫雙層協同進化的多種群遺傳算法適合于求解復雜的車間調度問題。5仿真結果與分析本文提出了縱橫雙層協同進化的多種群遺傳算法,該