【摘要】：制造過程的調(diào)度技術(shù),將在很大程度上影響產(chǎn)品生產(chǎn)的周期、成本和效率。優(yōu)化制造過程調(diào)度,可以有效地提高企業(yè)的生產(chǎn)管理水平和制造自動(dòng)化水平,從而提高企業(yè)的競爭力。作業(yè)車間調(diào)度問題是生產(chǎn)調(diào)度中許多實(shí)際問題的簡化模型,是制造類企業(yè)無法回避的一個(gè)關(guān)鍵且核心的問題。現(xiàn)行的各種調(diào)度方法在求解作業(yè)車間調(diào)度問題時(shí),都存在各種各樣的缺陷。因此,改進(jìn)現(xiàn)有的調(diào)度方法或者尋找新的調(diào)度方法,始終具有重要的理論價(jià)值和實(shí)際意義。 蟻群算法的搜索機(jī)制模擬螞蟻覓食過程中的群體行為,適合于求解旅行商問題等組合優(yōu)化問題,但應(yīng)用于作業(yè)車間調(diào)度問題的研究不多,且優(yōu)化效果不明顯,也沒有一般性規(guī)律可循。競選算法搜索機(jī)制模擬競選活動(dòng)中對更高支持率的追求動(dòng)機(jī),目前主要應(yīng)用于連續(xù)域內(nèi)的各種函數(shù)優(yōu)化問題。 本文針對作業(yè)車間調(diào)度問題,對蟻群算法進(jìn)行改進(jìn),設(shè)計(jì)了一種新的信息素更新方式；對競選算法進(jìn)行離散化設(shè)計(jì),探索新的求解作業(yè)車間調(diào)度問題的調(diào)度方法,并對這兩種算法進(jìn)行比較。本文的主要研究結(jié)果如下： (1)本文綜合分析了蟻群算法的特點(diǎn)及作業(yè)車間調(diào)度問題的特點(diǎn),討論了兩種經(jīng)典的改進(jìn)蟻群算法—蟻群系統(tǒng)與最大最小螞蟻系統(tǒng)—的算法思想及求解機(jī)制。在此基礎(chǔ)上,提出了一種新的改進(jìn)蟻群算法。為了驗(yàn)證該改進(jìn)蟻群算法的有效性,將其應(yīng)用于作業(yè)車間調(diào)度問題與柔性作業(yè)車間調(diào)度問題的求解。采用文獻(xiàn)中的測試函數(shù)進(jìn)行計(jì)算,并將計(jì)算結(jié)果與文獻(xiàn)中的結(jié)果進(jìn)行比較分析。結(jié)果表明,該改進(jìn)蟻群算法大大提高了問題的求解效率及求解結(jié)果。 (2)介紹了競選算法的基本思想、基本原理以及在連續(xù)優(yōu)化領(lǐng)域內(nèi)的應(yīng)用研究。將競選算法應(yīng)用于求解作業(yè)車間生產(chǎn)調(diào)度問題,采用基于工序的表達(dá)法表示問題的解,采用基于關(guān)鍵路徑的鄰域搜索方法生成局部選民,這兩者是競選算法的離散化設(shè)計(jì)的核心技術(shù)。將離散化的競選算法求解FT06算例以及LA系列標(biāo)準(zhǔn)調(diào)度函數(shù),無論是計(jì)算時(shí)間,還是計(jì)算結(jié)果,離散的競選算法都取得了較好的效果,表明了該改進(jìn)算法的有效性及可行性。 (3)利用Matlab 7編程實(shí)現(xiàn)了上述兩種算法的操作,構(gòu)建了一個(gè)求解作業(yè)車間調(diào)度問題的工具包。 (4)分析了改進(jìn)蟻群算法與改進(jìn)競選算法兩種啟發(fā)式優(yōu)化算法在算法特性方面的異同點(diǎn),并對這兩種算法進(jìn)行求解質(zhì)量、算法時(shí)間復(fù)雜度和空間復(fù)雜度等方面的比較分析。
[Abstract]:The scheduling technology of manufacturing process will affect the production cycle, cost and efficiency to a great extent. Optimization of manufacturing process scheduling can effectively improve the level of production management and manufacturing automation, thereby improving the competitiveness of enterprises. Job shop scheduling problem is a simplified model of many practical problems in production scheduling. It is a key and core problem that manufacturing enterprises can not avoid. All kinds of current scheduling methods have various defects in solving job shop scheduling problems. Therefore, it is always of great theoretical and practical significance to improve the existing scheduling methods or to find new scheduling methods. The search mechanism of ant colony algorithm simulates colony behavior in ant foraging process, which is suitable for solving combinatorial optimization problems such as traveling salesman problem. However, there are few researches on job shop scheduling problem and the effect of optimization is not obvious. There are no general rules to follow. The search mechanism of election algorithm simulates the motivation for higher support in the campaign, which is mainly applied to various functional optimization problems in continuous domain. In this paper, a new pheromone updating method is designed for job shop scheduling problem by improving ant colony algorithm. The election algorithm is discretized and a new scheduling method for job shop scheduling problem is explored and compared. The main results of this paper are as follows: (1) the characteristics of ant colony algorithm and job shop scheduling problem are analyzed. Two classical improved ant colony algorithms, ant colony system and maximum and minimum ant system, are discussed in this paper. On this basis, a new improved ant colony algorithm is proposed. In order to verify the effectiveness of the improved ant colony algorithm, it is applied to the solution of job shop scheduling problem and flexible job shop scheduling problem. The test function in the literature is used to calculate, and the calculated results are compared with the results in the literature. The results show that the improved ant colony algorithm greatly improves the efficiency and the result of solving the problem. (2) the basic idea, basic principle and application research in the field of continuous optimization are introduced. The election algorithm is applied to solve the job shop production scheduling problem. The solution of the problem is represented by the expression method based on the process, and the local voters are generated by the neighborhood search method based on the critical path. These two are the core techniques of discrete design of campaign algorithms. The discrete election algorithm is used to solve the FT06 example and the LA series standard scheduling function. Both the computing time and the result of the discrete election algorithm are obtained. The results show that the improved algorithm is effective and feasible. (3) Matlab 7 is used to realize the operation of the above two algorithms, and a toolkit to solve the job shop scheduling problem is constructed. (4) the similarities and differences between the improved ant colony algorithm and the improved election algorithm are analyzed, and the quality, time complexity and space complexity of the two algorithms are compared and analyzed.
【學(xué)位授予單位】：廣東工業(yè)大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2011
【分類號】：TH186

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 門君;王連玉;李忠光;巴威;;基于改進(jìn)蟻群算法的汽車搶修車巡回修理問題研究[J];軍事交通學(xué)院學(xué)報(bào);2011年05期

2 計(jì)三有;王星;;基于蟻群算法的圖書物流中心配送路徑規(guī)劃[J];湖北工業(yè)大學(xué)學(xué)報(bào);2011年04期

3 劉立;王建興;秦書碩;莫城愷;;一種改進(jìn)蟻群算法在配電網(wǎng)優(yōu)化規(guī)劃中的應(yīng)用[J];科學(xué)技術(shù)與工程;2011年24期

4 張寶健;;變異蟻群算法在電力系統(tǒng)無功優(yōu)化中的應(yīng)用[J];福建電腦;2011年05期

5 李慧;王來運(yùn);;基于混沌蟻群算法的電力短期負(fù)荷預(yù)測[J];北京信息科技大學(xué)學(xué)報(bào)(自然科學(xué)版);2011年04期

6 張敖木翰;鐘仰晉;何世偉;;基于蟻群算法的公交線網(wǎng)規(guī)劃研究[J];交通標(biāo)準(zhǔn)化;2008年13期

7 時(shí)貴英;吳雅娟;倪紅梅;;一種新改進(jìn)的粒子群優(yōu)化算法[J];長春理工大學(xué)學(xué)報(bào)(自然科學(xué)版);2011年02期

8 嚴(yán)珍珍;邢立寧;陳英武;;蟻群算法求解消防站的選址問題[J];科學(xué)技術(shù)與工程;2011年21期

9 李永勝;曲良東;李熹;;自適應(yīng)信息素更新蟻群算法求解QoS組播路由[J];山東大學(xué)學(xué)報(bào)(工學(xué)版);2011年04期

10 何開成;;一種改進(jìn)的蟻群算法求解TSP問題及實(shí)驗(yàn)結(jié)果分析[J];硅谷;2011年16期

相關(guān)會(huì)議論文 前10條

1 關(guān)洪浩;唐巍;;蟻群算法的生成樹在配電網(wǎng)網(wǎng)架規(guī)劃中的應(yīng)用[A];紀(jì)念中國農(nóng)業(yè)工程學(xué)會(huì)成立30周年暨中國農(nóng)業(yè)工程學(xué)會(huì)2009年學(xué)術(shù)年會(huì)（CSAE 2009）論文集[C];2009年

2 吳正偉;吉文來;陳偉佳;盧扣;;基于蟻群算法的城市緊急救援最佳路徑選擇[A];地理信息與物聯(lián)網(wǎng)論壇暨江蘇省測繪學(xué)會(huì)2010年學(xué)術(shù)年會(huì)論文集[C];2010年

3 王鶴;邵良杉;邱云飛;;蟻群算法在露天礦運(yùn)輸系統(tǒng)路徑優(yōu)化中的應(yīng)用[A];第五屆全國煤炭工業(yè)生產(chǎn)一線青年技術(shù)創(chuàng)新文集[C];2010年

4 劉杰;閆清東;;基于蟻群算法的移動(dòng)機(jī)器人路徑規(guī)劃技術(shù)的研究[A];邏輯學(xué)及其應(yīng)用研究——第四屆全國邏輯系統(tǒng)、智能科學(xué)與信息科學(xué)學(xué)術(shù)會(huì)議論文集[C];2008年

5 嚴(yán)彬;熊偉清;程美英;葉青;;基于擁塞控制的多種群二元蟻群算法[A];第二十七屆中國控制會(huì)議論文集[C];2008年

6 肖嶺;熊輝;;一種針對頻率指配問題的改進(jìn)蟻群算法[A];電波科學(xué)學(xué)報(bào)[C];2011年

7 宋春峰;侯媛彬;趙圣剛;;蟻群算法在陀螺溫控系統(tǒng)中的應(yīng)用研究[A];第十四屆全國煤礦自動(dòng)化學(xué)術(shù)年會(huì)暨中國煤炭學(xué)會(huì)自動(dòng)化專業(yè)委員會(huì)學(xué)術(shù)會(huì)議論文集[C];2004年

8 張如偉;黃捍東;趙迪;;一種新的地震非線性反演方法[A];中國地球物理學(xué)會(huì)第二十四屆年會(huì)論文集[C];2008年

9 師凱;蔡延光;鄒谷山;王濤;;運(yùn)輸調(diào)度問題的蟻群算法研究[A];04'中國企業(yè)自動(dòng)化和信息化建設(shè)論壇暨中南六省區(qū)自動(dòng)化學(xué)會(huì)學(xué)術(shù)年會(huì)專輯[C];2004年

10 陳峻;沈潔;秦玲;;蟻群算法進(jìn)行連續(xù)參數(shù)優(yōu)化的新途徑[A];加入WTO和中國科技與可持續(xù)發(fā)展——挑戰(zhàn)與機(jī)遇、責(zé)任和對策（下冊）[C];2002年

相關(guān)重要報(bào)紙文章 前2條

1 惠永輝　徐源;張昌龍—— 勇于挑戰(zhàn)難題[N];解放軍報(bào);2009年

2 本報(bào)記者 張巍巍;瞧瞧“機(jī)器游俠”特種兵[N];科技日報(bào);2011年

相關(guān)博士學(xué)位論文 前10條

1 許志紅;交流接觸器智能化控制與設(shè)計(jì)技術(shù)的研究及實(shí)現(xiàn)[D];福州大學(xué);2006年

2 薛云;基于蟻群算法和支持向量機(jī)的礦化蝕變信息提取研究[D];中南大學(xué);2008年

3 顧中舜;中繼衛(wèi)星動(dòng)態(tài)調(diào)度問題建模及優(yōu)化技術(shù)研究[D];國防科學(xué)技術(shù)大學(xué);2008年

4 劉傳文;仿生優(yōu)化算法在數(shù)字圖像處理中的應(yīng)用研究[D];武漢理工大學(xué);2008年

5 陳寶文;蟻群優(yōu)化算法在車輛路徑問題中的應(yīng)用研究[D];哈爾濱工業(yè)大學(xué);2009年

6 唐連生;突發(fā)事件下的車輛路徑問題研究[D];西南交通大學(xué);2008年

7 何滎;用信息法研究天空亮度分布[D];重慶大學(xué);2008年

8 閆博;基于蟻群算法的集裝箱港口選擇與網(wǎng)絡(luò)均衡分析[D];大連海事大學(xué);2008年

9 呂雄偉;郵政物流車輛路徑問題研究[D];西南交通大學(xué);2009年

10 劉波;蟻群算法改進(jìn)及應(yīng)用研究[D];燕山大學(xué);2010年

相關(guān)碩士學(xué)位論文 前10條

1 劉志勇;基于蟻群算法與競選算法的作業(yè)車間調(diào)度求解及比較研究[D];廣東工業(yè)大學(xué);2011年

2 傅宏;基于遺傳多蟻群算法的QoS組播路由算法研究[D];重慶大學(xué);2010年

3 潘鵬竹;協(xié)同制造調(diào)度問題的蟻群算法研究[D];沈陽工業(yè)大學(xué);2010年

4 饒躍東;基于改進(jìn)蟻群算法的無人飛行器航跡規(guī)劃應(yīng)用研究[D];武漢理工大學(xué);2010年

5 于沛欣;一種混合蟻群算法在JSP問題中的應(yīng)用研究[D];中國海洋大學(xué);2008年

6 邵曉路;蟻群群體智能網(wǎng)絡(luò)可視化試驗(yàn)平臺研制[D];浙江理工大學(xué);2010年

7 呂海鵬;改進(jìn)蟻群算法在YKK系列中型高壓電機(jī)優(yōu)化設(shè)計(jì)中的應(yīng)用[D];哈爾濱理工大學(xué);2010年

8 呂曉慧;一種混合蟻群算法在JSP中的應(yīng)用研究[D];青島大學(xué);2009年

9 張守年;改進(jìn)的蟻群算法及其在QoS中的應(yīng)用[D];華南理工大學(xué);2010年

10 林時(shí)來;基于蟻群算法的呼吸信號情感識別研究[D];西南大學(xué);2011年

，

本文編號：2379924