本文選題：批調(diào)度 + 蟻群算法�。� 參考：《中國科學(xué)技術(shù)大學(xué)》2017年碩士論文

【摘要】：在現(xiàn)實的生產(chǎn)生活中,無論是機器加工、零件制造,還是貨物裝運、航天運輸,都需要解決調(diào)度問題。調(diào)度問題不僅是一種組合優(yōu)化問題,更有著廣泛的應(yīng)用背景,它在提高全社會資源利用效率、勞動生產(chǎn)率和降低生產(chǎn)成本方面起到了極其積極巨大的作用,并且有著非常豐富的研究成果。批調(diào)度問題是對經(jīng)典調(diào)度問題的擴展,主要是起源于半導(dǎo)體生產(chǎn)過程中的一類新型現(xiàn)代調(diào)度問題。批調(diào)度問題具有非常重要的理論和經(jīng)濟研究價值。本論文研究的批調(diào)度問題是NP-難問題,而簡單高效的求解算法設(shè)計是批調(diào)度研究的重點方向。文中主要用到的算法為蟻群算法和魚群算法。在簡單介紹蟻群算法和魚群算法的思想和應(yīng)用后,還根據(jù)算法特性以及視野限制的問題,提出了一種改進的魚群算法,通過視野的動態(tài)變化,改進算法前期搜索寬度和后期收斂速度,實現(xiàn)算法效率的提高,并且通過案例結(jié)果分析,改進的魚群算法比傳統(tǒng)魚群算法更加高效。本文還根據(jù)批調(diào)度問題特性,結(jié)合蟻群算法和魚群算法之間的優(yōu)缺點,提出了兩種混合算法,混合算法通過魚群算法擁擠度因子的結(jié)合,避免蟻群算法在早期陷入局部極值,從而導(dǎo)致算法早熟的缺點,使算法具有全局尋優(yōu)能力,能更好的找到全局極值。文中主要解決的問題是差異工件單機批調(diào)度問題,該問題中工件尺寸不盡相同,并且只有一臺加工機器。針對具體問題算法參數(shù)需要重新設(shè)置,文中對蟻群算法中信息素定義、啟發(fā)式信息和信息素初始化作出相應(yīng)改進,并且對魚群算法也有相應(yīng)的調(diào)整。為保證實驗的說服力和有效性,本文根據(jù)實驗的數(shù)量的多少、工件加工的尺寸大小和工件加工時間的長短,進行了分類的實驗。為了直觀全面地對比實驗結(jié)果的好壞,我們應(yīng)用了批的利用率和負載率的概念。批的利用率側(cè)面反應(yīng)了在批加工時間內(nèi),工件加工對機器容量的利用程度;批的負載率體現(xiàn)總體加工時間中浪費程度。從實驗結(jié)果看,在算法尋優(yōu)的過程中,蟻群算法的性能要優(yōu)于魚群算法,但是蟻群算法本身的早熟性,導(dǎo)致尋優(yōu)結(jié)果局部最優(yōu)。但如果將蟻群算法和魚群算法相結(jié)合,利用魚群算法中的擁擠度因子,并與蟻群算法相結(jié)合,可以有效地避免早熟,并且對于尋找最優(yōu)解、減少尋優(yōu)時間有著一定的幫助。通過第一種混合算法和第二種混合算法的比較,第二種混合算法對于工件數(shù)量較小、迭代次數(shù)較少的問題有較高效率。而第一種混合算法對于工件數(shù)量較多,迭代次數(shù)較多的算法有較高的性能。
[Abstract]:In the actual production and life, the scheduling problem needs to be solved whether machine processing, parts manufacturing, cargo shipment and space transportation. The scheduling problem is not only a combination optimization problem, but also a wide application background. It plays an extremely important role in improving the utilization efficiency of the whole society, labor productivity and reducing the cost of production. The batch scheduling problem is a new type of modern scheduling problem originating in the process of semiconductor production. The batch scheduling problem has very important theoretical and economic research value. The batch scheduling problem in this paper is a NP- difficult problem. And simple and efficient algorithm design is the key direction of batch scheduling research. The main algorithms used in this paper are ant colony algorithm and fish swarm algorithm. After simply introducing the idea and application of ant colony algorithm and fish swarm algorithm, an improved fish swarm algorithm is proposed based on the characteristics of the algorithm and the limit of field of vision. State changes, improved algorithm early search width and later convergence speed, improve the efficiency of the algorithm, and through the analysis of the case results, the improved fish swarm algorithm is more efficient than the traditional fish swarm algorithm. Based on the characteristics of the batch scheduling problem, combined with the advantages and disadvantages of ant colony algorithm and fish swarm algorithm, two hybrid algorithms are proposed. By combining the crowding factor of the fish swarm algorithm, the algorithm avoids the early fall of the ant colony algorithm into the local extremum, which leads to the premature weakness of the algorithm, and makes the algorithm have the global optimization ability, and can better find the global extremum. The main problem in this paper is the problem of the single machine batch scheduling problem of the difference workpieces, and the size of the workpiece is not the same in the problem. There is only one machine. In order to ensure the persuasiveness and effectiveness of the fish swarm algorithm, the pheromone definition, the heuristic information and the pheromone initialization of the ant colony algorithm are improved in this paper. The size of the processing and the length of the working time of the workpiece are classified. In order to compare the results of the experiment directly and comprehensively, we apply the concept of the utilization ratio and the load rate of the batch. The utilization ratio of the batch reacts to the utilization degree of the machine capacity during the batch processing time; the load rate of the batch shows the total. From the experimental results, in the process of optimizing the algorithm, the performance of the ant colony algorithm is better than the fish algorithm, but the early maturity of the ant colony algorithm itself leads to the local optimization of the optimization results. But if the ant colony algorithm is combined with the fish algorithm, the crowding factor in the fish swarm algorithm is used and the ant colony algorithm is used. Combined, it can effectively avoid precocity and help to find the optimal solution and reduce the optimization time. Through the comparison between the first hybrid algorithm and the second hybrid algorithms, the second hybrid algorithm is more efficient for smaller number of jobs and less iterative times. The first hybrid algorithm is more effective for the number of jobs. Many algorithms with more iterations have higher performance.

【學(xué)位授予單位】：中國科學(xué)技術(shù)大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：TP18

【參考文獻】

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

1 姚剛;;計算機人工智能算法研究新進展[J];科技創(chuàng)新導(dǎo)報;2012年24期

2 郝尚剛;陳華平;李小林;;兩階段流水車間批處理機調(diào)度的聚類算法[J];計算機工程;2012年14期

3 郭旭寧;胡鐵松;呂一兵;張濤;;跨流域供水水庫群聯(lián)合調(diào)度規(guī)則研究[J];水利學(xué)報;2012年07期

4 杜冰;陳華平;邵浩;許瑞;李小林;;具有不同到達時間的差異工件批調(diào)度問題的蟻群聚類算法[J];系統(tǒng)工程理論與實踐;2010年09期

5 廖四輝;程緒水;施勇;馬真臻;趙建世;王忠靜;;淮河生態(tài)用水多層次分析平臺與多目標優(yōu)化調(diào)度模型研究[J];水力發(fā)電學(xué)報;2010年04期

6 許瑞;陳華平;邵浩;王栓獅;;極小化總完工時間批調(diào)度問題的兩種蟻群算法[J];計算機集成制造系統(tǒng);2010年06期

7 王栓獅;陳華平;程八一;李燕;;一種差異工件單機批調(diào)度問題的蟻群優(yōu)化算法[J];管理科學(xué)學(xué)報;2009年06期

8 程八一;陳華平;王栓獅;;優(yōu)化差異工件單機批調(diào)度問題的改進蟻群算法[J];系統(tǒng)仿真學(xué)報;2009年09期

9 邵浩;陳華平;許瑞;程八一;賈兆紅;;優(yōu)化差異工件單機批調(diào)度問題的混合微粒群算法[J];系統(tǒng)工程;2008年12期

10 王聯(lián)國;洪毅;趙付青;余冬梅;;一種改進的人工魚群算法[J];計算機工程;2008年19期

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

1 許瑞;基于蟻群優(yōu)化算法的批調(diào)度問題研究[D];中國科學(xué)技術(shù)大學(xué);2011年

2 杜冰;批處理機調(diào)度問題的模型與優(yōu)化方法研究[D];中國科學(xué)技術(shù)大學(xué);2011年

3 王聯(lián)國;人工魚群算法及其應(yīng)用研究[D];蘭州理工大學(xué);2009年

4 李曉磊;一種新型的智能優(yōu)化方法-人工魚群算法[D];浙江大學(xué);2003年

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

1 鄭春薈;基于學(xué)習(xí)效應(yīng)的單機調(diào)度總完工時間最小化問題研究[D];中國科學(xué)技術(shù)大學(xué);2015年

2 王凱;差異工件單機批調(diào)度的自適應(yīng)蟻群退火算法研究[D];中國科學(xué)技術(shù)大學(xué);2011年

3 劉娟;基于云模型的改進PSO算法在差異工件單機批調(diào)度中的應(yīng)用研究[D];中國科學(xué)技術(shù)大學(xué);2010年

，

本文編號：1884899