本文在國內(nèi)外相關(guān)研究的基礎(chǔ)上,針對車間混合作業(yè)調(diào)度(MSP)問題進(jìn)行了相關(guān)研究,涉及到模型建立、計(jì)算復(fù)雜性分析、算法實(shí)現(xiàn)、算法性能分析及驗(yàn)證等多方面的問題。 首先,由于MSP問題規(guī)模龐大、系統(tǒng)復(fù)雜,為了表達(dá)MSP問題內(nèi)部的多層階結(jié)構(gòu)網(wǎng)絡(luò)關(guān)系,本文利用網(wǎng)絡(luò)理論對MSP問題建立了多級(jí)賦權(quán)圖模型,對其進(jìn)行了清晰的描述。 進(jìn)而,對制造系統(tǒng)MSP問題的計(jì)算復(fù)雜性進(jìn)行了分析,本文對其中包含的各種作業(yè)方式的計(jì)算復(fù)雜性分別進(jìn)行了研究,并利用復(fù)雜性理論中歸約和轉(zhuǎn)換的思想,引入背包問題著重研究了其中兩種作業(yè)方式的計(jì)算復(fù)雜性,最后表明MSP問題屬于NP-hard問題,計(jì)算復(fù)雜度為指數(shù)級(jí)或階乘級(jí),不可能找到可以精確求得最優(yōu)解的多項(xiàng)式時(shí)間算法。 然后,研究了遺傳算法在解決MSP問題中的應(yīng)用過程,并對遺傳算法的收斂性能進(jìn)行了討論分析。本文提出了一種十進(jìn)制整數(shù)和實(shí)數(shù)相結(jié)合的編碼方案,并針對這種編碼方式實(shí)施了具體的遺傳操作,使得交叉操作不失繼承性,變異操作能夠?qū)崿F(xiàn)種群的多樣性;利用馬爾科夫鏈(Markov)理論相關(guān)知識(shí)證明了所設(shè)計(jì)遺傳算法以概率1收斂到全局最優(yōu),并對算法的收斂速度進(jìn)行了分析,指出各參數(shù)取值不同時(shí)對算法...

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

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

【部分圖文】：

圖2.1車間HFSP調(diào)度簡圖

-13-圖2.1車間HFSP調(diào)度簡圖JSP和FSP都是研究在m臺(tái)機(jī)器上n個(gè)工件的加工過程，如果各個(gè)工件技術(shù)約束條件相同，一個(gè)JSP問題就會(huì)轉(zhuǎn)化為一個(gè)較為簡單的FSP問題，進(jìn)而，如果各機(jī)器上各工件的加工次序也相同，那么問題就可以進(jìn)一步轉(zhuǎn)化為置換FSP問題。通常情況下，JSP....

圖2.2MSP多級(jí)賦權(quán)圖模型

2.4車間混合作業(yè)調(diào)度系統(tǒng)建模2.4.1模型建立研究制造系統(tǒng)MSP建模方法，對推動(dòng)MSP調(diào)度方法在制造企業(yè)中的應(yīng)用，開發(fā)新一代的企業(yè)生產(chǎn)管理控制系統(tǒng)，提高我國制造企業(yè)對市場需求的響應(yīng)速度以及制造系統(tǒng)的運(yùn)行效率，把我國建設(shè)成為管理水平先進(jìn)的制造業(yè)基地具有重要的意義。對于制造系統(tǒng)M....

圖3.2n個(gè)工件3階段4臺(tái)機(jī)器作業(yè)實(shí)例排序描述

∈jTiS∈證明過程如下：123maxH/m=1,m=1,m=2/C問題的判定形式有解的必要充分條件是背包問題。首先來證明問題的充分性：如果背包問題有解，則可以構(gòu)造一個(gè)排序問題123max/m=1,m=1,m=2/C的實(shí)例，即工件總數(shù)為n=t+2；工件n1J的....

圖3.3、n個(gè)工件4個(gè)階段5臺(tái)機(jī)器實(shí)例排序描述

工件nJ排在最后加工（如上圖3.3），否則就會(huì)產(chǎn)生空閑時(shí)間，其他零件的安排亦如上圖3.3所示。對于問題的必要性，可以用反證法來證明。若背包問題無解，則∑=≠0∈abciSi，那么對于每一個(gè)ST，都有加工順序n1J，{}JiSi/∈，{}JiTSi/∈

本文編號(hào)：3927983