分布估計(jì)算法在車間調(diào)度問(wèn)題中的應(yīng)用研究.pdf

1、自從上世紀(jì)50年代至今,車間調(diào)度問(wèn)題一直是應(yīng)用數(shù)學(xué)、運(yùn)籌學(xué)、管理學(xué)、計(jì)算機(jī)科學(xué)等諸多學(xué)科研究的熱門課題,理論成果層出不窮。智能算法的興起,為求解復(fù)雜調(diào)度問(wèn)題提供了新的有效工具,也為車間調(diào)度問(wèn)題的研究開(kāi)辟了嶄新的空間。實(shí)驗(yàn)證明:絕大多數(shù)的車間調(diào)度問(wèn)題屬于NP-Hard問(wèn)題,不存在精確求解的多項(xiàng)式時(shí)間算法。智能算法雖然在一定程度上改善了解的質(zhì)量,但同別的優(yōu)化算法類似,對(duì)于某些問(wèn)題,該算法也存在著一定程度的枚舉以及收斂到最優(yōu)解的速度較慢的情況

2、,這就要求我們進(jìn)一步拓寬研究思路,繼續(xù)尋找更高效的智能調(diào)度新方法。分布估計(jì)算法(Estimation of Distribution Algorithins,EDAs)是一種新興的進(jìn)化算法,它將構(gòu)建概率模型和采樣引入到進(jìn)化過(guò)程中,取代了傳統(tǒng)進(jìn)化算法中的交叉和變異等模擬自然進(jìn)化的操作。該算法使用概率模型來(lái)引導(dǎo)搜索過(guò)程,避免了染色體重組帶來(lái)的盲目性和隨機(jī)性,因而,有效地提高了搜索效率,能夠快速、可靠地解決許多傳統(tǒng)進(jìn)化算法難以求解的復(fù)雜優(yōu)化問(wèn)

3、題。
　　 本文將分布估計(jì)算法應(yīng)用到流水車間調(diào)度問(wèn)題中,為了克服分布估計(jì)算法中概率模型單一固定的缺陷,提高算法的收斂速度,避免出現(xiàn)早熟收斂現(xiàn)象。本文將模擬退火算法的思想引入分布估計(jì)算法,即將模擬退火的接受概率應(yīng)用于變異后的優(yōu)勢(shì)種群的選取,提出基于模擬退火的改進(jìn)分布估計(jì)算法,同時(shí),為了減小算法的優(yōu)化性能和效率對(duì)初始種群的依賴,本文采用NEH啟發(fā)式方法和隨機(jī)方法共同產(chǎn)生初始種群。在利用改進(jìn)分布估計(jì)算法的基礎(chǔ)上,針對(duì)流水車間調(diào)度和混合