蟻群魚(yú)群混合算法在差異工件批調(diào)度中的應(yīng)用
本文選題:批調(diào)度 + 蟻群算法; 參考:《中國(guó)科學(xué)技術(shù)大學(xué)》2017年碩士論文
【摘要】:在現(xiàn)實(shí)的生產(chǎn)生活中,無(wú)論是機(jī)器加工、零件制造,還是貨物裝運(yùn)、航天運(yùn)輸,都需要解決調(diào)度問(wèn)題。調(diào)度問(wèn)題不僅是一種組合優(yōu)化問(wèn)題,更有著廣泛的應(yīng)用背景,它在提高全社會(huì)資源利用效率、勞動(dòng)生產(chǎn)率和降低生產(chǎn)成本方面起到了極其積極巨大的作用,并且有著非常豐富的研究成果。批調(diào)度問(wèn)題是對(duì)經(jīng)典調(diào)度問(wèn)題的擴(kuò)展,主要是起源于半導(dǎo)體生產(chǎn)過(guò)程中的一類新型現(xiàn)代調(diào)度問(wèn)題。批調(diào)度問(wèn)題具有非常重要的理論和經(jīng)濟(jì)研究?jī)r(jià)值。本論文研究的批調(diào)度問(wèn)題是NP-難問(wèn)題,而簡(jiǎn)單高效的求解算法設(shè)計(jì)是批調(diào)度研究的重點(diǎn)方向。文中主要用到的算法為蟻群算法和魚(yú)群算法。在簡(jiǎn)單介紹蟻群算法和魚(yú)群算法的思想和應(yīng)用后,還根據(jù)算法特性以及視野限制的問(wèn)題,提出了一種改進(jìn)的魚(yú)群算法,通過(guò)視野的動(dòng)態(tài)變化,改進(jìn)算法前期搜索寬度和后期收斂速度,實(shí)現(xiàn)算法效率的提高,并且通過(guò)案例結(jié)果分析,改進(jìn)的魚(yú)群算法比傳統(tǒng)魚(yú)群算法更加高效。本文還根據(jù)批調(diào)度問(wèn)題特性,結(jié)合蟻群算法和魚(yú)群算法之間的優(yōu)缺點(diǎn),提出了兩種混合算法,混合算法通過(guò)魚(yú)群算法擁擠度因子的結(jié)合,避免蟻群算法在早期陷入局部極值,從而導(dǎo)致算法早熟的缺點(diǎn),使算法具有全局尋優(yōu)能力,能更好的找到全局極值。文中主要解決的問(wèn)題是差異工件單機(jī)批調(diào)度問(wèn)題,該問(wèn)題中工件尺寸不盡相同,并且只有一臺(tái)加工機(jī)器。針對(duì)具體問(wèn)題算法參數(shù)需要重新設(shè)置,文中對(duì)蟻群算法中信息素定義、啟發(fā)式信息和信息素初始化作出相應(yīng)改進(jìn),并且對(duì)魚(yú)群算法也有相應(yīng)的調(diào)整。為保證實(shí)驗(yàn)的說(shuō)服力和有效性,本文根據(jù)實(shí)驗(yàn)的數(shù)量的多少、工件加工的尺寸大小和工件加工時(shí)間的長(zhǎng)短,進(jìn)行了分類的實(shí)驗(yàn)。為了直觀全面地對(duì)比實(shí)驗(yàn)結(jié)果的好壞,我們應(yīng)用了批的利用率和負(fù)載率的概念。批的利用率側(cè)面反應(yīng)了在批加工時(shí)間內(nèi),工件加工對(duì)機(jī)器容量的利用程度;批的負(fù)載率體現(xiàn)總體加工時(shí)間中浪費(fèi)程度。從實(shí)驗(yàn)結(jié)果看,在算法尋優(yōu)的過(guò)程中,蟻群算法的性能要優(yōu)于魚(yú)群算法,但是蟻群算法本身的早熟性,導(dǎo)致尋優(yōu)結(jié)果局部最優(yōu)。但如果將蟻群算法和魚(yú)群算法相結(jié)合,利用魚(yú)群算法中的擁擠度因子,并與蟻群算法相結(jié)合,可以有效地避免早熟,并且對(duì)于尋找最優(yōu)解、減少尋優(yōu)時(shí)間有著一定的幫助。通過(guò)第一種混合算法和第二種混合算法的比較,第二種混合算法對(duì)于工件數(shù)量較小、迭代次數(shù)較少的問(wèn)題有較高效率。而第一種混合算法對(duì)于工件數(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é)位授予單位】:中國(guó)科學(xué)技術(shù)大學(xué)
【學(xué)位級(jí)別】:碩士
【學(xué)位授予年份】:2017
【分類號(hào)】:TP18
【參考文獻(xiàn)】
相關(guān)期刊論文 前10條
1 姚剛;;計(jì)算機(jī)人工智能算法研究新進(jìn)展[J];科技創(chuàng)新導(dǎo)報(bào);2012年24期
2 郝尚剛;陳華平;李小林;;兩階段流水車間批處理機(jī)調(diào)度的聚類算法[J];計(jì)算機(jī)工程;2012年14期
3 郭旭寧;胡鐵松;呂一兵;張濤;;跨流域供水水庫(kù)群聯(lián)合調(diào)度規(guī)則研究[J];水利學(xué)報(bào);2012年07期
4 杜冰;陳華平;邵浩;許瑞;李小林;;具有不同到達(dá)時(shí)間的差異工件批調(diào)度問(wèn)題的蟻群聚類算法[J];系統(tǒng)工程理論與實(shí)踐;2010年09期
5 廖四輝;程緒水;施勇;馬真臻;趙建世;王忠靜;;淮河生態(tài)用水多層次分析平臺(tái)與多目標(biāo)優(yōu)化調(diào)度模型研究[J];水力發(fā)電學(xué)報(bào);2010年04期
6 許瑞;陳華平;邵浩;王栓獅;;極小化總完工時(shí)間批調(diào)度問(wèn)題的兩種蟻群算法[J];計(jì)算機(jī)集成制造系統(tǒng);2010年06期
7 王栓獅;陳華平;程八一;李燕;;一種差異工件單機(jī)批調(diào)度問(wèn)題的蟻群優(yōu)化算法[J];管理科學(xué)學(xué)報(bào);2009年06期
8 程八一;陳華平;王栓獅;;優(yōu)化差異工件單機(jī)批調(diào)度問(wèn)題的改進(jìn)蟻群算法[J];系統(tǒng)仿真學(xué)報(bào);2009年09期
9 邵浩;陳華平;許瑞;程八一;賈兆紅;;優(yōu)化差異工件單機(jī)批調(diào)度問(wèn)題的混合微粒群算法[J];系統(tǒng)工程;2008年12期
10 王聯(lián)國(guó);洪毅;趙付青;余冬梅;;一種改進(jìn)的人工魚(yú)群算法[J];計(jì)算機(jī)工程;2008年19期
相關(guān)博士學(xué)位論文 前4條
1 許瑞;基于蟻群優(yōu)化算法的批調(diào)度問(wèn)題研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2011年
2 杜冰;批處理機(jī)調(diào)度問(wèn)題的模型與優(yōu)化方法研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2011年
3 王聯(lián)國(guó);人工魚(yú)群算法及其應(yīng)用研究[D];蘭州理工大學(xué);2009年
4 李曉磊;一種新型的智能優(yōu)化方法-人工魚(yú)群算法[D];浙江大學(xué);2003年
相關(guān)碩士學(xué)位論文 前3條
1 鄭春薈;基于學(xué)習(xí)效應(yīng)的單機(jī)調(diào)度總完工時(shí)間最小化問(wèn)題研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2015年
2 王凱;差異工件單機(jī)批調(diào)度的自適應(yīng)蟻群退火算法研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2011年
3 劉娟;基于云模型的改進(jìn)PSO算法在差異工件單機(jī)批調(diào)度中的應(yīng)用研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2010年
,本文編號(hào):1884899
本文鏈接:http://www.sikaile.net/kejilunwen/zidonghuakongzhilunwen/1884899.html