調(diào)度問題是生產(chǎn)制造的中心,在工業(yè)生產(chǎn)、自動化、車船調(diào)度領(lǐng)域廣泛應(yīng)用。車間調(diào)度問題是決策者根據(jù)資源的約束(時間人工成本,原材料等)對加工作業(yè)定量分配到相關(guān)程序上,并配置作業(yè)的加工順序,在約束條件下達(dá)到最優(yōu)安排。優(yōu)秀的調(diào)度策略可以獲得更佳的資源配置,提高生產(chǎn)系統(tǒng)的效率,獲得經(jīng)濟(jì)效益。因此,調(diào)度問題逐漸成為研究熱點(diǎn)。本文提出一種多目標(biāo)混合差分優(yōu)化算法�；旌纤惴ㄎ樟瞬罘诌M(jìn)化矢量運(yùn)算的優(yōu)點(diǎn),依據(jù)歷史記錄動態(tài)的調(diào)整搜索方向。為了克服在進(jìn)化后期,差分進(jìn)化算法由于種群多樣性變小容易陷入局部最優(yōu)的缺點(diǎn),通過一種混合采樣策略獲得解集的分布信息設(shè)計(jì)差分進(jìn)化的變異算子,使得混合算法能夠朝著有利的方向提高收斂性或者分布性,彌補(bǔ)了陷入局部最優(yōu)的缺陷,算法可以快速的向著帕累托前沿面前進(jìn)。本文首先將多目標(biāo)混合差分優(yōu)化算法在經(jīng)典的Benchmark Problems集上進(jìn)行驗(yàn)證,并與傳統(tǒng)優(yōu)秀算法進(jìn)行對比分析;針對差分進(jìn)化過程提出不同的備選個體選擇方式,并進(jìn)行對比數(shù)據(jù)分析。最后針對于最大完工時間和總流程時間的雙目標(biāo)流水車間調(diào)度問題進(jìn)行數(shù)學(xué)建模,采用改進(jìn)的變異算子增加算法的全局搜索能力。Benchmark Problem... 

【文章來源】：河南工業(yè)大學(xué)河南省

【文章頁數(shù)】：64 頁

【學(xué)位級別】：碩士

【部分圖文】：

可行域與搜索空間在圖1中，F(xiàn)是一個非凸斷開的集合，可行的最優(yōu)解是在可行域的邊緣，與最優(yōu)解

需要處理時，認(rèn)為每一代的種群被隨機(jī)分成 M 個子群。 基于不同目標(biāo)函數(shù)的每個子種群被賦予適應(yīng)度。 因此，M 個目標(biāo)函數(shù)中的每一個都被用來評估個體的質(zhì)量。在圖3說明了五個目標(biāo)函數(shù)的適應(yīng)性評估程序。每一代的種群平均分為五個部分。第一個種群中的每個個體只在第一個目標(biāo)函數(shù)的基礎(chǔ)上被賦予適應(yīng)度，而在第二個種群中的每個個體僅在第二個目標(biāo)函數(shù)的基礎(chǔ)上被賦予適應(yīng)度等等。 為了減少種群中的位置偏差，最好把個人在種群中的位置混合起來，然后再分成五個相同大小的子群體。 在每個人被賦予適應(yīng)性之后，每個亞群體中受限制的選擇操作者被雇傭，直到子群體填補(bǔ)完成。在處理目標(biāo)函數(shù)值域差別很大的問題時尤其有用。 由于子群體中的所有成員都是根據(jù)自己的目標(biāo)函數(shù)賦予適應(yīng)度的，所以只能在子群體中約束選擇算子強(qiáng)調(diào)對應(yīng)于其自身目標(biāo)函數(shù)的好群體。 另外，由于沒有兩個人根據(jù)不同的目標(biāo)函數(shù)進(jìn)行比較，與一系列不同的目標(biāo)函數(shù)不一致就不會造成任何困難。雖然獲得單個目標(biāo)信息的適應(yīng)度值簡單易行，但在工作原理上有一些限制。 缺點(diǎn)也很明顯。計(jì)算過程中每個個體都只在一個目標(biāo)函數(shù)中進(jìn)行評估。 因此，每個個體不

一代 HMOEA / DE 的演變過程如圖 5 所示。外部種群 A(t)表示在 t 代的精英種群，P(t)代表 t 代的種群，最大代數(shù)作為算法的終止標(biāo)準(zhǔn)。與傳統(tǒng)的 DE 不同，HMOEA / DE不僅使用基于 DE 的進(jìn)化搜索機(jī)制來有效地對整個區(qū)域內(nèi)有前途的解決方案進(jìn)行探索，而且還采用了有效的混合采樣策略來對局部進(jìn)行開發(fā)，進(jìn)一步提高解決方案的性能。由于差分進(jìn)化采用的是實(shí)際編碼方式，與 HMOEA 所采用的編碼方式不同，所以為解決 FSP 而提出的 HMOEA / DE 的實(shí)現(xiàn)涉及兩個關(guān)鍵問題。一個是如何對染色體的進(jìn)行評估，另一個是如何將 DE 操作應(yīng)用于染色體。為了評估染色體（由實(shí)參數(shù)向量表示），個體按照規(guī)則分組，稱為混合采樣。一種新的選擇方式取代了傳統(tǒng)的適應(yīng)度數(shù)值排序。染色體的適應(yīng)度值將根據(jù)該調(diào)度的完工時間和遲滯時間的值來設(shè)定。解決 FSP 的最優(yōu)調(diào)度排序總是一個以最小化完工時間和最大化遲滯為準(zhǔn)則的有效調(diào)度集內(nèi)，有目的性選擇個體和進(jìn)化方向可以大大減少二維空間中的搜索空間和時間消耗。在下面的小節(jié)中，將描述使用的遺傳操作。

【參考文獻(xiàn)】：
期刊論文
[1]一種求解混合零空閑置換流水車間調(diào)度禁忌分布估計(jì)算法[J]. 張曉霞,呂云虹.  計(jì)算機(jī)應(yīng)用與軟件. 2017(01)
[2]流水車間調(diào)度問題的快速多目標(biāo)混合進(jìn)化算法[J]. 張聞強(qiáng),盧佳明,張紅梅.  計(jì)算機(jī)應(yīng)用. 2016(04)
[3]面向多目標(biāo)優(yōu)化問題的自適應(yīng)差分進(jìn)化算法[J]. 劉紅平,黎福海.  計(jì)算機(jī)應(yīng)用與軟件. 2015(12)
[4]一種多目標(biāo)置換流水車間調(diào)度問題的優(yōu)化算法[J]. 何啟巍,張國軍,朱海平,劉敏.  計(jì)算機(jī)系統(tǒng)應(yīng)用. 2013(09)
[5]基于差分進(jìn)化與塊結(jié)構(gòu)鄰域的作業(yè)車間調(diào)度優(yōu)化[J]. 潘全科,王凌,高亮,桑紅燕.  機(jī)械工程學(xué)報(bào). 2010(22)
[6]一種求解隨機(jī)有限緩沖區(qū)流水線調(diào)度的混合差分進(jìn)化算法[J]. 胡蓉,錢斌.  自動化學(xué)報(bào). 2009(12)
[7]無成組技術(shù)條件下流水車間調(diào)度的多目標(biāo)優(yōu)化[J]. 楊開兵,劉曉冰.  計(jì)算機(jī)集成制造系統(tǒng). 2009(02)
[8]進(jìn)化多目標(biāo)優(yōu)化算法研究[J]. 公茂果,焦李成,楊咚咚,馬文萍.  軟件學(xué)報(bào). 2009(02)
[9]約束問題求解[J]. 季曉慧,張健.  自動化學(xué)報(bào). 2007(02)
[10]遺傳編程實(shí)現(xiàn)的研究[J]. 查志琴,高波,鄭成增.  計(jì)算機(jī)應(yīng)用. 2003(07)

碩士論文
[1]兩階段混合流水車間調(diào)度問題精確算法的研究[D]. 陳鑫.大連理工大學(xué) 2016



本文編號：2943235