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

【文章來源】：沈陽師范大學(xué)學(xué)報(自然科學(xué)版). 2019,37(04)

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

【部分圖文】：

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

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

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

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

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



本文編號：2971191