基于多智能體和混合遺傳算法的車間調(diào)度模型的應(yīng)用分析

《基于多智能體和混合遺傳算法的車間調(diào)度模型的應(yīng)用分析》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、浙江理_l二大學(xué)碩士學(xué)位論文合優(yōu)化問題，從計(jì)算時(shí)間復(fù)雜度看是一個(gè)NP．Hard問題，隨調(diào)度規(guī)模的增大，問題可行解的數(shù)量呈指數(shù)級(jí)增加，因而求解非常困難。在現(xiàn)有計(jì)算條件下，一般優(yōu)化方法對(duì)于車間調(diào)度問題是低效甚至是無能為力的。(3)離散性：車間生產(chǎn)系統(tǒng)是個(gè)典型的離散系統(tǒng)，其中工件的加工發(fā)生在不同的時(shí)間和資源上，并且任務(wù)的到達(dá)、訂單的更改、設(shè)備的增添和故障等都是離散事件。這樣，就有可能用數(shù)學(xué)規(guī)劃、離散系統(tǒng)建模與仿真的方式，通過排序理論研究車間調(diào)度問題。(4)動(dòng)態(tài)性：在真實(shí)的車間中，有很多動(dòng)態(tài)事件發(fā)生。這些事件主要有新任務(wù)到達(dá)、緊急任務(wù)插入、交貨期改變、訂單被取消、設(shè)備故障或修復(fù)等。

2、這些事件的發(fā)生通常是隨機(jī)的。動(dòng)態(tài)事件的發(fā)生，可能導(dǎo)致整個(gè)系統(tǒng)的性能大大降低，或是在原有的調(diào)度方案下生產(chǎn)任務(wù)將無法完成。在這種情況下，必須對(duì)動(dòng)態(tài)事件做出響應(yīng)，調(diào)整現(xiàn)有的調(diào)度方案，以保證任務(wù)的順利完成，并使車間性能處于較好的狀態(tài)。(5)多目標(biāo)性：車間生產(chǎn)中，針對(duì)不同的加工任務(wù)，相應(yīng)地有其特定的調(diào)度目標(biāo)，待優(yōu)化的性能指標(biāo)有很多。例如生產(chǎn)周期、平均流通時(shí)間、平均延誤率、設(shè)備利用率等。如何使車間調(diào)度系統(tǒng)適應(yīng)不同的任務(wù)類型和規(guī)模，一直是車間調(diào)度中面臨的難題，迄今為止還沒有一個(gè)通用并且實(shí)用的車間調(diào)度系統(tǒng)。1．2．3車間調(diào)度的優(yōu)化目標(biāo)車間調(diào)度的目的就是使資源得到最優(yōu)的利用，關(guān)鍵問題也是瓶頸

3、問題就是調(diào)度模型和算法的建立，不同規(guī)模的企業(yè)，考慮的優(yōu)化目標(biāo)是不同的，在不同的優(yōu)化目標(biāo)下建立模型與算法就不盡相同，考慮目標(biāo)越多的調(diào)度算法和模型就越復(fù)雜，一般的優(yōu)化目標(biāo)有以下幾種：(1)在一定時(shí)間周期內(nèi)系統(tǒng)的產(chǎn)出最高。(2)系統(tǒng)生產(chǎn)所花的成本最少。(3)系統(tǒng)內(nèi)設(shè)備的利用率最高。(4)系統(tǒng)內(nèi)的在制品最少。(5)加工單個(gè)零件時(shí)通過系統(tǒng)的時(shí)間最短。制造系統(tǒng)車間調(diào)度建模的復(fù)雜性還體現(xiàn)在隨著系統(tǒng)規(guī)模的擴(kuò)大，所要考慮的信息呈爆炸性增長(zhǎng)的趨勢(shì)，與此同時(shí)，又要兼顧到調(diào)度方案的實(shí)時(shí)性和良好的調(diào)度效果，非常難于解決，目前尚未見到好的解決方案和實(shí)例。1．3傳統(tǒng)的調(diào)度技術(shù)與模型存在的問題調(diào)度問題的研

4、究從二十世紀(jì)五十年代起就受到應(yīng)用數(shù)學(xué)、運(yùn)籌學(xué)、自動(dòng)化和人工智能3基于多智能體和混合遺傳算法的車間調(diào)度模型的應(yīng)用研究等領(lǐng)域的科學(xué)家的重視，因其重要的理論和應(yīng)用價(jià)值始終都是研究的熱點(diǎn)。據(jù)不完全統(tǒng)計(jì)，從調(diào)度問題研究的文章首次發(fā)表以來，至今已有二萬多篇關(guān)于生產(chǎn)調(diào)度問題的文章公開發(fā)表，提出了各種各樣的研究方法同。在這些研究工作中最有影響的是二十世紀(jì)六十年代由Conway、Maxwell和Miller所提出的調(diào)度理論。按照他們的定義，所謂調(diào)度是指“如何分配一系列資源去完成一系列任務(wù)"。在生產(chǎn)系統(tǒng)中，調(diào)度被定義為“如何分配一系列機(jī)器，使它們?cè)谝欢ǖ臅r(shí)間內(nèi)完成一系列的任務(wù)訂單’’。于是，生

5、產(chǎn)調(diào)度表現(xiàn)為一個(gè)排序問題。為區(qū)別起見，他們把工件在一臺(tái)機(jī)器上的排產(chǎn)定義為“排序”，而將對(duì)于多個(gè)不同機(jī)器上工件的排序問題命名為“調(diào)度”。調(diào)度的結(jié)果是調(diào)度時(shí)序表。它是一個(gè)“任務(wù)一時(shí)間”表，是一個(gè)“關(guān)于每一個(gè)項(xiàng)目以及為完成這些項(xiàng)目所采取的必須操作的執(zhí)行序列隨時(shí)間分配的計(jì)劃"。這樣，生產(chǎn)調(diào)度問題被描述為一個(gè)“在一定的初始條件和約束條件下尋求使某一性能指標(biāo)最優(yōu)”的數(shù)學(xué)問題，即一個(gè)最優(yōu)化計(jì)算或最優(yōu)控制問題。研究證明，這是一類難以解決的NP完全問題。然而，傳統(tǒng)的調(diào)度技術(shù)和模型無論所使用具體的計(jì)算技術(shù)是屬于數(shù)學(xué)優(yōu)化方法的。還是運(yùn)籌學(xué)的、抑或是人工智能方法，調(diào)度的研究工作始終是從應(yīng)用數(shù)學(xué)的分

6、析與研究角度展開的。由于這種調(diào)度模型和概念是對(duì)實(shí)際生產(chǎn)調(diào)度問題的抽象，在實(shí)際制造系統(tǒng)開放的、動(dòng)態(tài)的環(huán)境下，生產(chǎn)調(diào)度問題呈現(xiàn)極強(qiáng)的動(dòng)態(tài)性，例如機(jī)器的損壞、加工計(jì)劃的改變以及緊急訂單的處理等，這就使得傳統(tǒng)的調(diào)度技術(shù)和模型很難直接運(yùn)用于解決實(shí)際的生產(chǎn)調(diào)度問題。1．4車問調(diào)度研究的歷史與現(xiàn)狀1．4．1車間調(diào)度研究的歷史與現(xiàn)狀在過去的40年中，大量關(guān)于車間調(diào)度的書籍文獻(xiàn)出版與發(fā)表，當(dāng)然也不乏很多關(guān)于工作車間調(diào)度的優(yōu)秀文章。其中，1967年肯韋首先系統(tǒng)地撰寫了關(guān)于調(diào)度理論的書籍，起到了里程碑的作用。隨后，大量學(xué)者也竟相研究起來。在研究的過程中，由瑪斯、湯普森(1963)和卡夫I'-J(

7、1976)編審的書籍以及派度(1995)等人的文章都為生產(chǎn)調(diào)度問題提供了更加廣闊的理論解決空間。在多年的研究中，車間調(diào)度領(lǐng)域取得了豐碩的成果，這一時(shí)期產(chǎn)生了很多重要的調(diào)度方法。這些方法主要有：運(yùn)籌學(xué)方法，基于規(guī)則的方法，系統(tǒng)仿真的方法，解析模型方法，鄰域搜索方法，人工智能方法【8】【91。(1)基于啟發(fā)式規(guī)則的方法對(duì)生產(chǎn)加工任務(wù)進(jìn)行調(diào)度的最傳統(tǒng)的方法是使用調(diào)度規(guī)則，因?yàn)閱l(fā)式調(diào)度規(guī)則簡(jiǎn)4浙江理工人學(xué)碩士學(xué)位論文單，易于實(shí)現(xiàn)，計(jì)算復(fù)雜度低等原因，故在生產(chǎn)中得到了廣泛的應(yīng)用。但啟發(fā)式規(guī)則一般不具備全局優(yōu)化的特點(diǎn)。許多年