基于遺傳算法的流水車間調(diào)度的方法及實際應用

《基于遺傳算法的流水車間調(diào)度的方法及實際應用》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在學術論文-天天文庫。

1、浙江1=業(yè)大學碩士學位論文國涌現(xiàn)出聯(lián)想集團有限公司、海爾集團公司、黑龍江斯達造紙有限公司等一批先行企業(yè)，通過管理信息化，提高了管理水平，改善了經(jīng)濟效益，增強了市場競爭力。所以吉利集團豪情汽車制造有限公司的發(fā)動機金加工車間的生產(chǎn)調(diào)度問題就在這種背景下進行研究的。1．2國內(nèi)外車間調(diào)度問題研究現(xiàn)狀和存在的問題1．2．1國內(nèi)外車間調(diào)度問題研究現(xiàn)狀調(diào)度問題的研究始于20世紀50年代，Johnson提出了解決車間調(diào)度部分特殊問題的優(yōu)化算法，代表調(diào)度理論研究的開始。60．70年代建立了調(diào)度理論的主體(經(jīng)典調(diào)度理論)

2、并重視調(diào)度復雜性的研究。大量的研究促使車間調(diào)度領域取德了豐碩的成果，產(chǎn)生了很多重要的調(diào)度方法。隨著70年代后期調(diào)度理論研究的深入及各種交叉學科的發(fā)展，又涌現(xiàn)出了許多新的車問調(diào)度理論與方法。Davis是最早把遺傳算法GA(GeneticAlgorithm)應用于車l’BJ調(diào)度問題的學者之一，他在使用GA求解車間調(diào)度的研究中取得了近似雖優(yōu)解?！?85年，Davis發(fā)表了關于把GA成功應用于車間調(diào)度問題的論文，充分展示了GA在解決車間調(diào)度問題中的前景。此后，很多學者就遺傳算法在車間調(diào)度問題方面的應用做了大量

3、研究發(fā)表了大量卓有成效的論文，使車間調(diào)度這NP．hard完全問題的解決嶄露曙光。t，,bn，以DavidEGoldberg，Yamada，Nakano，wlliuey，F(xiàn)ang，Kobayashi等為代表的一些學者在他們的論文中提出了一些具有突破性的新思想，改進并完善了傳統(tǒng)GA車間調(diào)度中的應用方法，同時在解決一些著名的標準檢測問題(Benchmark)中取得了最優(yōu)(或接近最優(yōu))解，進一步證明了遺傳算法在解決NP問題方面的有效性。國內(nèi)對車間調(diào)度的研究起步較晚，由于技術上的制約，基本上是靠調(diào)度人員的經(jīng)驗進

4、行車間作業(yè)分配和調(diào)度。隨著遺傳算法在車間調(diào)度方面的應用，國內(nèi)也掀起了一股應用遺傳算法研究車間調(diào)度的熱潮，研究工作主要集中在清華大學等CIMS國家重點實驗室，而目前這些實驗室的系統(tǒng)開發(fā)基本上還處在剮投入試運行階段，離開發(fā)出成熟的軟件系統(tǒng)還有很長一段距離，因此各實驗室還在投入大量的人力和物力進行該方面的研究，特別是在開展對車間作業(yè)調(diào)度算法的研究方面，目前尚處在實驗研究階段。塹翌三些奎堂堡主堂篁堡奎1．2．2研究中存在的問題由于大多調(diào)度問題屬于～類NP困難組合問題，因此尋找具有多項式復雜性的最優(yōu)算法幾乎是不

5、可能的。各種近似／啟發(fā)式方法、諸如基于規(guī)則的算法等，由于能在合理的時間內(nèi)產(chǎn)生比較滿意的調(diào)度，因此廣泛應用于實際調(diào)度中，但其往往對所得的調(diào)度解的次優(yōu)性不能進行評估。在這方面有必要探索更好的近似最優(yōu)調(diào)度算法，可以考慮增加合理的計算時間為代價，提高解的次優(yōu)性。各種基于統(tǒng)計優(yōu)化的方法、諸如模擬退火法、遺傳算法等，提供了一種解決調(diào)度優(yōu)化問題的新途徑，但同別的優(yōu)化算法類似，其也存在著一定程度的枚舉、一般來說收斂到最優(yōu)解較慢，并且對于判斷解的最優(yōu)性也很困難。在這方面也需要做進一步的研究。在調(diào)度問題的理論研究中，大多

6、數(shù)還是集中在針對經(jīng)典的調(diào)度問題設計優(yōu)化算法，而經(jīng)典調(diào)度問題與實際相差較大，尤其在目前柔性制造環(huán)境下，柔性車間作業(yè)調(diào)度問題將是～個研究的重點和進一步研究的方向，而目前對于這方面研究的文獻相對來說較少。在實際車間調(diào)度中，車間計劃與車間調(diào)度往往是分層進行的，但這可能造成計劃在實際調(diào)度中的不可行問題，如何將計劃與調(diào)度結(jié)合考慮，以求總體的優(yōu)化也是需要進一步研究的。1．3進化計算與遺傳算法近年來，一類基于生物界的選擇和遺傳機制的計算方法，包含如遺傳算法(Gas，GeneticAlgorithms)、進化策略(ES

7、，EvolutionStrategies)和進化規(guī)劃(EP,EvolutionProgramming)等方法，在科研和實際工程中的應用越來越廣泛，并取得了一定的效果。這些方法模擬生物演化思想來實現(xiàn)數(shù)學建模、仿真，并由此設計、控制和優(yōu)化人工系統(tǒng)。一般稱為進化計算(EC，EvolutionaryComputation)。EC是計算智能的一方面，主要有Holland等創(chuàng)立的遺傳算法。Schwefel等創(chuàng)立的進化策略以及Fogel等創(chuàng)立的進化規(guī)劃。生物進化理論表明，復雜結(jié)構(gòu)的生命是在相當短的時間進化而來的，這

8、種機制目前尚未完全弄清楚，但某些特征已被人們所掌握。大多數(shù)生物的進化是通過有性繁殖和自然選擇這兩種基本過程進行的。有性繁殖完成了對后代基因的重組，重組的結(jié)果產(chǎn)生了群體中對自然環(huán)境具有不同適應能力的個體，自然選擇的機制決定了那些適應性較強的個體可以存活下去，而較弱的將要被淘汰。自然選擇的塑堅三些丕蘭堡主蘭堡絲苧原則是適者生存。進化算法就是基于上述思想發(fā)展起來的一類隨機搜索技術，他們模擬了群體的進化過程。其中每個個體表示給定問題搜索空問的一點，進化計算從任一