隨著計(jì)算機(jī)領(lǐng)域的飛速發(fā)展,物流等行業(yè)也開始向自動(dòng)化、智能化、無(wú)人化的方向發(fā)展。智能RGV動(dòng)態(tài)調(diào)度是智能加工系統(tǒng)的重要環(huán)節(jié),合理的調(diào)度方案能夠大大提高系統(tǒng)的作業(yè)效率。針對(duì)RGV調(diào)度問題,建立了基于自動(dòng)化加工系統(tǒng)的動(dòng)態(tài)調(diào)度模型。提出了一種基于貪心策略優(yōu)化后的搜索算法,通過貪心選擇最可能發(fā)生的情況,可減少搜索的復(fù)雜度,從而達(dá)到在極短時(shí)間內(nèi)接近最優(yōu)調(diào)度的目的。通過仿真實(shí)驗(yàn),對(duì)先后進(jìn)行2道工序的CNC進(jìn)行優(yōu)化配對(duì),以產(chǎn)量最大作為目標(biāo),搜索得到CNC的最佳分配方案,達(dá)到了接近最優(yōu)解的調(diào)度策略。在規(guī)定的工作時(shí)間內(nèi),使用貪婪優(yōu)化算法提高了搜索的有效性,使RGV系統(tǒng)能夠高效調(diào)度,驗(yàn)證了貪心優(yōu)化算法的可行性和有效性。 

【文章來(lái)源】：沈陽(yáng)師范大學(xué)學(xué)報(bào)(自然科學(xué)版). 2019,37(04)

【文章頁(yè)數(shù)】：6 頁(yè)

【部分圖文】：

圖２貪心優(yōu)化的搜索調(diào)度流程圖Ｆｉｇ．２Ｇｒｅｅｄｙｏｐｔｉｍｉｚａｔｉｏｎｏｆｔｈｅｓｅａｒｃｈｓｃｈｅｄｕｌｉｎｇｆｌｏｗｃｈａｒｔ

擇［９］。在貪婪算法中，無(wú)需從整體最優(yōu)的目標(biāo)上加以考慮，需要求出的是某一時(shí)刻某種意義的局部最優(yōu)解。由于考慮的片面性，貪心算法無(wú)法對(duì)所有問題求得整體最優(yōu)解［１０］。算法核心是貪心策略的選擇，局部選擇的貪心策略需要獨(dú)立于其他狀態(tài)，即當(dāng)前選擇與之前狀態(tài)無(wú)關(guān)且不影響之后的狀態(tài)，只與當(dāng)前狀態(tài)有關(guān)。２．２貪心優(yōu)化分析在計(jì)算機(jī)算法分析中，廣度優(yōu)先搜索的時(shí)間復(fù)雜度為Ｏ（Ｖ＋Ｅ），其中Ｖ是節(jié)點(diǎn)的數(shù)目，Ｅ是變的數(shù)目，如圖３所示。圖３ＢＦＳ在ＲＧＶ調(diào)度中可能的情況Ｆｉｇ．３ＰｏｓｓｉｂｌｅｃａｓｅｓｏｆＢＦＳｉｎＲＧＶｓｃｈｅｄｕｌｉｎｇ第４期羅敏娜，等：貪心優(yōu)化的搜索算法在ＲＧＶ動(dòng)態(tài)調(diào)度中的應(yīng)用７１３

在本文提出的算法中，Ｖ每次執(zhí)行完指令后，后續(xù)有４種可能存在的操作，此時(shí)節(jié)點(diǎn)數(shù)將會(huì)以指數(shù)增長(zhǎng)，復(fù)雜度將會(huì)高于Ｖ，當(dāng)系統(tǒng)需要長(zhǎng)時(shí)間運(yùn)行，ｎ（ＲＧＶ操作的次數(shù)）過大時(shí)，計(jì)算機(jī)將無(wú)法完成如此巨大的計(jì)算。ＢＦＳ產(chǎn)生如此巨大計(jì)算量的原因是，ＲＧＶ每次調(diào)度都有４種可選的新路徑，造成了時(shí)間指數(shù)增長(zhǎng)的情況，因此可以貪心選擇其中在全局動(dòng)態(tài)性上最可能成為最優(yōu)路徑的０～２條路徑（如圖４所示），作為下一步可能出現(xiàn)的情況。在圖４中，虛線部分為排除掉不進(jìn)行后續(xù)計(jì)算的路徑，這樣將大大減少計(jì)算耗時(shí)，并且也能達(dá)到非常良好的效果［１１］。圖４貪心選擇后可能出現(xiàn)的情況Ｆｉｇ．４Ｔｈｅｃａｓｅｔｈａｔｍａｙｈａｐｐｅｎａｆｔｅｒｇｒｅｅｄｙｃｈｏｉｃｅ２．３貪心優(yōu)化根據(jù)對(duì)每臺(tái)ＣＮＣ當(dāng)前狀態(tài)與未來(lái)狀態(tài)之間關(guān)系的考慮，給每一個(gè)位置設(shè)計(jì)了一種對(duì)其最近２臺(tái)ＣＮＣ未來(lái)狀態(tài)及周圍ＣＮＣ的狀態(tài)進(jìn)行綜合考慮的性能評(píng)價(jià)標(biāo)準(zhǔn)［１６］。在ＲＧＶ每次操作后，更新４個(gè)位置的性能權(quán)值，權(quán)值基于２個(gè)超參數(shù)由其未來(lái)運(yùn)行后的狀態(tài)來(lái)定，即目標(biāo)最近２臺(tái)ＣＮＣ的剩余時(shí)間減去運(yùn)動(dòng)花費(fèi)時(shí)間，再將其與做乘積運(yùn)算，最后加上與目標(biāo)附近４臺(tái)機(jī)器（對(duì)于１和４位置只有２臺(tái)）運(yùn)動(dòng)后的狀態(tài)平均值的乘積［１７］。超參數(shù)可以不斷擬合，使這種評(píng)價(jià)標(biāo)準(zhǔn)發(fā)揮良好的效果［１２］。將上述的評(píng)價(jià)標(biāo)準(zhǔn)轉(zhuǎn)化為數(shù)學(xué)模型，即Ｗｉ的函數(shù)為Ｗｉ＝α｛ａｂｓ（ＵＴｉ－ｄｉｓＬｉ）＋

【參考文獻(xiàn)】：
期刊論文
[1]基于改進(jìn)A*算法優(yōu)化的移動(dòng)機(jī)器人路徑規(guī)劃研究[J]. 陳豪,李勇,羅靖迪.  自動(dòng)化與儀器儀表. 2018(12)
[2]可變線路公交車輛調(diào)度算法優(yōu)化研究[J]. 邵孜科,張泉,王樹盛,張小輝,李文權(quán).  交通信息與安全. 2018(05)
[3]公交立體車庫(kù)調(diào)度算法的研究與實(shí)現(xiàn)[J]. 宋揚(yáng),田野,蘇睿聰,陳星,宮瑞澤.  自動(dòng)化博覽. 2018(10)
[4]RGV系統(tǒng)設(shè)計(jì)與應(yīng)用[J]. 劉俏.  物流科技. 2016(05)
[5]基于遺傳算法和貪婪算法的作業(yè)車間調(diào)度[J]. 王新,賈志強(qiáng),尚宏美.  機(jī)械工程師. 2015(01)
[6]基于FCFS策略的帶時(shí)間窗車隊(duì)調(diào)度問題研究[J]. 軒華.  交通運(yùn)輸系統(tǒng)工程與信息. 2013(06)
[7]結(jié)合廣度搜索的遺傳算法在水庫(kù)調(diào)度中的應(yīng)用[J]. 張忠波,張雙虎,蔣云鐘.  南水北調(diào)與水利科技. 2011(05)
[8]幾種經(jīng)典搜索算法研究與應(yīng)用[J]. 歐陽(yáng)圣,胡望宇.  計(jì)算機(jī)系統(tǒng)應(yīng)用. 2011(05)
[9]貪心算法的探討與研究[J]. 常友渠,肖貴元,曾敏.  重慶電力高等�？茖W(xué)校學(xué)報(bào). 2008(03)
[10]貪心算法在多機(jī)調(diào)度問題中的應(yīng)用[J]. 董春平.  電腦開發(fā)與應(yīng)用. 2007(10)

博士論文
[1]基于離散事件的列車調(diào)度問題模型與算法研究[D]. 徐小明.北京交通大學(xué) 2016



本文編號(hào)：2971191