基于遺傳算法的車間調(diào)度優(yōu)化及其仿真

《基于遺傳算法的車間調(diào)度優(yōu)化及其仿真》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、武漢理工大學(xué)碩士學(xué)位論文單機(jī)調(diào)度問題是所有的操作任務(wù)都在單臺(tái)機(jī)器上完成，為此存在任務(wù)的優(yōu)化排隊(duì)問題；多臺(tái)并行機(jī)的調(diào)度問題更復(fù)雜，因而優(yōu)化問題更突出；FlowShop型問題假設(shè)所有作業(yè)都在同樣的設(shè)備上加工，并有一致的加工操作和加工順序；JobShop是最一般的調(diào)度類型，不同的作業(yè)具有不同的加工操作和加工順序，并不限制作業(yè)的加工設(shè)備。現(xiàn)代車間調(diào)度類型往往是JobShop類型的。2．根據(jù)性能指標(biāo)，分為基于調(diào)度費(fèi)用和調(diào)度性能的指標(biāo)兩大類。3．根據(jù)生產(chǎn)環(huán)境的特點(diǎn)，可將調(diào)度問題分為確定性調(diào)度和隨機(jī)性調(diào)度問題。4．根據(jù)作業(yè)的加

2、工特點(diǎn)，可將調(diào)度問題分為靜態(tài)調(diào)度和動(dòng)態(tài)調(diào)度。靜態(tài)調(diào)度是指所有待安排加工的工作均處于待加工狀態(tài)，因而進(jìn)行一次調(diào)度后，各作業(yè)的加工時(shí)間被確定，在以后的加工過程中就不再改變；動(dòng)態(tài)調(diào)度是指作業(yè)依次進(jìn)入待加工狀態(tài)、各種作業(yè)不斷進(jìn)入系統(tǒng)接受加工、同時(shí)完成加工的作業(yè)又不斷離開，還要考慮作業(yè)環(huán)境中不斷出現(xiàn)的動(dòng)態(tài)擾動(dòng)、如作業(yè)的加工超時(shí)、設(shè)備的損壞等。因此動(dòng)態(tài)調(diào)度要根據(jù)系統(tǒng)中作業(yè)、設(shè)備等的狀況，不斷地進(jìn)行調(diào)度。實(shí)際調(diào)度的類型往往是JobShop型，且是動(dòng)態(tài)的。實(shí)際的調(diào)度問題有以下特點(diǎn)：1．復(fù)雜性由于裝卸作業(yè)、裝卸設(shè)備、庫場、搬運(yùn)系統(tǒng)

3、之間相互影響、相互作用，每個(gè)作業(yè)又要考慮它的到達(dá)時(shí)間、裝卸時(shí)間、準(zhǔn)備時(shí)間、操作順序、交貨期等，因而相當(dāng)復(fù)雜。而且調(diào)度問題是在等式或不等式約束下求性能指標(biāo)的優(yōu)化，在計(jì)算量上往往是NP完全問題，即隨著問題規(guī)模的增大，對(duì)于求解最優(yōu)化的計(jì)算量呈指數(shù)增長，使得一些常規(guī)的最優(yōu)化方法往往無能為力。2．動(dòng)態(tài)隨機(jī)性在實(shí)際的生產(chǎn)調(diào)度系統(tǒng)中存在很多隨機(jī)的和不確定的因素，比如作業(yè)到達(dá)時(shí)間的不確定性、作業(yè)的加工時(shí)間也有一定的隨機(jī)性，而且生產(chǎn)系統(tǒng)中常出現(xiàn)一些突發(fā)偶然事件，如設(shè)備的損壞／修復(fù)、作業(yè)交貨期的改變等。3．多目標(biāo)性實(shí)際的計(jì)劃調(diào)度往往

4、是多目標(biāo)的，并且這些目標(biāo)間可能發(fā)生沖突。Kiran等人將調(diào)度目標(biāo)分三類：基于作業(yè)交貨期的目標(biāo)、基于作業(yè)完成時(shí)間的目標(biāo)、基于生產(chǎn)成本的目標(biāo)。這種多目標(biāo)性導(dǎo)致調(diào)度的復(fù)雜性和計(jì)算量急劇增加。武漢理工大學(xué)碩士學(xué)位論文1．3國內(nèi)外車間調(diào)度問題研究現(xiàn)狀和存在的問題1．國內(nèi)外車間調(diào)度問題研究現(xiàn)狀調(diào)度問題的研究始于20世紀(jì)50年代，Johnson提出了解決車間調(diào)度部分特殊問題的優(yōu)化算法，代表調(diào)度理論研究的開始。60．70年代建立了調(diào)度理論的主體(經(jīng)典調(diào)度理論)并重視調(diào)度復(fù)雜性的研究。大量的研究促使車間調(diào)度領(lǐng)域取得了豐碩的成果，產(chǎn)

5、生了很多重要的調(diào)度方法。隨著70年代后期調(diào)度理論研究的深入及各種交叉學(xué)科的發(fā)展，又涌現(xiàn)出了許多新的車間調(diào)度理論與方法。Davis是最早把GA(GeneticAlgorithm，遺傳算法)應(yīng)用于車間調(diào)度問題的學(xué)者之一，他在使用GA求解車間調(diào)度的研究中取得了近似最優(yōu)解。1985年，Davis發(fā)表了關(guān)于把GA成功應(yīng)用于車間調(diào)度問題的論文，充分展示了GA在解決車問調(diào)度問題中的前景。此后，很多學(xué)者就遺傳算法在車間調(diào)度問題方面的應(yīng)用做了大量研究，發(fā)表了大量卓有成效的論文，使車間調(diào)度這類NP--hard問題的解決嶄露曙光。例如

6、，以DavidEGoldberg，Yamada，Nakano，w11iuey，F(xiàn)ang，Kobayashi等為代表的一些學(xué)者在他們的論文中提出了一些具有突破性的新思想，改進(jìn)并完善了傳統(tǒng)GA車間調(diào)度中的應(yīng)用方法，同時(shí)在解決一些著名的標(biāo)準(zhǔn)檢測問題(Benchmark)中取得了最優(yōu)(或接近最優(yōu))解，進(jìn)一步證明了遺傳算法在解決NP問題方面的有效性。㈦國內(nèi)對(duì)車間調(diào)度的研究起步較晚，由于技術(shù)上的制約，基本上是靠調(diào)度人員的經(jīng)驗(yàn)進(jìn)行車間作業(yè)分配和調(diào)度。隨著遺傳算法在作業(yè)調(diào)度方面的應(yīng)用，國內(nèi)也掀起了一股應(yīng)用遺傳算法研究車間調(diào)度的熱

7、潮：研究工作主要集中在清華大學(xué)等等CIMS國家重點(diǎn)實(shí)驗(yàn)室，而目前這些實(shí)驗(yàn)室的系統(tǒng)開發(fā)基本上還處在剛投入試運(yùn)行階段，離開發(fā)出成熟的軟件系統(tǒng)還有很長一段距離，因此各實(shí)驗(yàn)室還在投入大量的人力和物力進(jìn)行該方面的研究，特別是在開展對(duì)車間作業(yè)調(diào)度算法的研究方面，目前尚處在實(shí)驗(yàn)研究階段。2．存在的問題由于大多調(diào)度問題屬于一類NP困難組合問題，因此尋找具有多項(xiàng)式復(fù)雜性的最優(yōu)算法幾乎是不可能的。各種近似／啟發(fā)式方法、諸如基于規(guī)則的算法等，由于能在合理的時(shí)間內(nèi)產(chǎn)生比較滿意的調(diào)度，因此廣泛應(yīng)用于實(shí)際調(diào)度中，但其往往對(duì)所得的調(diào)度解的次優(yōu)

8、性不能進(jìn)行評(píng)估。在這方面有必要探索更好的近似最優(yōu)調(diào)度算法，可以考慮增加合理的計(jì)算時(shí)間為代價(jià)，提高解的次優(yōu)性。各4武漢理工大學(xué)碩士學(xué)位論文種基于統(tǒng)計(jì)優(yōu)化的方法、諸如模擬退火法、遺傳算法等，提供了一種解決調(diào)度優(yōu)化問題的新途徑，但同別的優(yōu)化算法類似，其也存在著一定程度的枚舉、一般來說收斂到最優(yōu)解較慢，并且對(duì)于判斷解的最優(yōu)性也很困難。在這方面也需要做進(jìn)一步的研究。在調(diào)度問題的理論