2022年數(shù)維杯大禮包2018優(yōu)秀國賽題

如RGV工作循環(huán)定義、系統(tǒng)效率均衡原則、CNC滿載工作上限等。同時，給出了相關(guān)分析和證明，包括在一定條件下的RGV循環(huán)的最短用時證明，系統(tǒng)最優(yōu)上限的證明等。優(yōu)化模型，并基于對時間進行離散化，為減少迭代步數(shù)，根據(jù)劃分結(jié)果構(gòu)建最優(yōu)狀型中的優(yōu)化原則結(jié)合已明確的優(yōu)化準則構(gòu)建各個階段的決策方案從而完成問題的求解，得到在8個小時內(nèi)三組參數(shù)下系統(tǒng)可產(chǎn)生最大熟料數(shù)量分別為 對于情景二，我們分析了兩類CNC在系統(tǒng)中存時產(chǎn)生的復(fù)雜約束情況，結(jié)合系統(tǒng)效率均衡對應(yīng)系統(tǒng)整體較大效率的規(guī)律，近似確定了兩種CNC的數(shù)量比例。再通過搜索找到了最優(yōu)的CNC空間排布方案，從而建立帶工約束的最優(yōu)狀態(tài)轉(zhuǎn)換圖模型。在求解時，通過改進的狀態(tài)轉(zhuǎn)移優(yōu)化準則對模型進行求解，得到在該約束條件下，8個小時 決策求解時除了追求完成物料數(shù)最大，還要保持系統(tǒng)內(nèi)兩類CNC工作能力均衡以取得更高的工作效率由于情況較多，結(jié)果可見附件Excel。狀態(tài)圖模型多階段決策模型非線性優(yōu)化模型RGV334問題分析.......................................... .............44.1問題一分析....................................... ..........44.2問題二分析............................. . ....... ......5模型的建立與分析.......................... ....... ......65.1模型建立........................ ...... ... .. ........65.2最優(yōu)狀態(tài)轉(zhuǎn)移圖模型................... .... . ...........85.3帶工序約束的最優(yōu)狀態(tài)轉(zhuǎn)移圖模型.. ........................5.4帶有故障風險的最優(yōu)狀態(tài)轉(zhuǎn)移圖模型 .........................5.5模型的求解......... ............. ......................551552553554模型求解與AC++BPythonControllerCNCehicleRGV料傳送帶及其他附屬設(shè)備組成。RGV是一種無人駕駛的、能在固定軌道上自由運行的在該類系統(tǒng)中，RGV的運行情況對整個作業(yè)系統(tǒng)的工作效率有著巨大影響，運行RGV系統(tǒng)的運行效率，是進一步促使智能加工系統(tǒng)發(fā)CNCCNC上CNC在加工過程中可能發(fā)生故障（1%）的情況，每即刻加入作業(yè)序列。要求分別考慮道工序和兩道工序的物料加工作業(yè)情況。2：1中系統(tǒng)作3組數(shù)據(jù)分別檢驗?zāi)Ｐ偷膶嵱眯院退惴ǖ挠行裕o出GV的調(diào)度策略和系統(tǒng)的作業(yè)效率，并將具體的結(jié)果分別填入附件2的Excel表中。生料時，其傳送帶保證CNC前方總有所需生料；假設(shè)除了CNC在加工過程中可能發(fā)生故障外，其他部件都不發(fā)生意外和磨損，且可符 意 CNC 系統(tǒng)處于第k k RGV在第k個狀態(tài)時所處的 41RGV動態(tài)調(diào)度模型和相應(yīng)的求解算法。針對該問策略下各部分機器效率應(yīng)當均衡的。這些規(guī)則將用于構(gòu)建RGV動態(tài)調(diào)度模型。18C8（有向有權(quán)圖CNC表V將工作、停止等待以及移動所需要的時間，由此構(gòu)建狀態(tài)向量和V簡工作可以考慮以兩無權(quán)點及該兩點所確定的一條帶權(quán)有向邊代替原來的帶權(quán)點，從而完成對模型的構(gòu)建和化簡。針對情況2，我們可以建立帶有工序約束的最優(yōu)狀態(tài)轉(zhuǎn)移模型該模型依然是基于系統(tǒng)狀態(tài)轉(zhuǎn)移的思想，可以證明工序一、二緊鄰是系統(tǒng)高效率的指導(dǎo)原則我們修改狀的基礎(chǔ)上引入突發(fā)隨量，通過引該隨量限制部分狀態(tài)的轉(zhuǎn)移效果，同時對于算法的求解可以采用引剪枝規(guī)則、回溯法、分支限界法等。值得注意的是，用分階段優(yōu)化的策略完成模型的求解，同時采用基于的時間離散化處理，最后可以以采用混合遺傳算法[1] 搜索算法[2]等。42CNC的工作時間511(RGV工作循環(huán))RGVCNC都操作且僅操作一次并最后回到出發(fā)位置的可證：對于本題中三組數(shù)據(jù)，RGV6個單位長度且中途停止為4次時的循環(huán)是所有循環(huán)中用時最短的。證明1在本題中，RGV一次循環(huán)的總耗時為t，t由上料時間1，時間t2和移動時間t3組成。即t=t1+ CNC的種類和數(shù)量確定時tt2t的相對大小僅由t3決定RGV移動i(i=123)個單位所需時間tmi=?t1+(i1)?t2，其中?t1為移1個單位的時間?t2為后續(xù)每1單位時間所需時間，且根據(jù)數(shù)據(jù)可知?t1>?t2。RGV44?t1RGV在一?t2，我們可以得出單個循環(huán)間的下限為4?t12?t2。系統(tǒng)均衡優(yōu)化原則CNC裝有一種類型刀片的情況下，RGVCNC協(xié)同工RGV和CNC的效率達到最大化，二者對物料的處理能力應(yīng)當盡量匹配。因RGVCNC的時候，RGVCNCCNC出現(xiàn)的，造兩種CNCCNC和CNCRGVCNC的處理能力大于第二類CNC，會造成產(chǎn)生過多的半成品物料而沒有足夠的第二類CNC進行處理，造成阻塞，而第二類CNC的處理能力大于第一類CNC，會造成沒有足夠的半成品物料供給第二類CNC加工，造成閑置。所以為了最大化最大化整個系統(tǒng)的效率，我們必須盡量保持第一類CNC和第二類CNC處理能力的均衡。3(CNC滿載條件下的系統(tǒng)工作上限)CNCCNC都處理進行“上下料-CNC只有一種刀片時，在一個班次內(nèi)，i位置處的CNC物料加工數(shù)量的上限Ui為Ui=

Tmtp+一個班次的總加工上限為U=∑n Ui，其中tp為CNC加工完成一個一道工序的物料所需時間，tli為RGV為CNC一次上下料所需時間當CNC有裝配有2種不同類型的刀片的時，一個班次內(nèi)CNCCNC中加工的物料上限較低的決定，這本質(zhì)由系統(tǒng)的短板原理 U= 圖 帶約束的隊列調(diào)度示意們從時間維度對系統(tǒng)基于進行狀態(tài)劃分提供了視角。以隱性的反應(yīng)RGV的狀態(tài)：移動、等。從時間維度對其進行離散化處理，由此可1s為基本步長，會導(dǎo)致迭代狀對于情況一，我們建立最優(yōu)狀態(tài)轉(zhuǎn)移圖模型來描述整 C系統(tǒng)的調(diào)度圖 最優(yōu)狀態(tài)轉(zhuǎn)移圖模型示意狀態(tài)。由于以秒為處理單位會出現(xiàn)大量的重復(fù)狀態(tài)和重復(fù)計算，我們從RGV運動的視

.1

,0≤tk≤Tm,pk∈N+pk≤?n/2?,rk,i≥M01，tkk個狀態(tài)時的時刻，pk代表RGVk個狀態(tài)時Vk1以構(gòu)建齊次轉(zhuǎn)移矩陣，rk,i變量代表當系統(tǒng)處于第V的一次上料行為完成時，模型狀態(tài)發(fā)生轉(zhuǎn)移，V移動到下一個位置進行上料（移動之前V可能會執(zhí)行在原地“停止等待”信號M。ii1次上料的間隔時間大于RGV從第一個位置運動到c1,1·· C .. ···其中ci,j為RGV從位置i移動到到位置j需要的時間，ci,j=cj,i，，當i=jci,j0CNCEk ek,i

VkCNCiVkCNCi

k1=f ···X Aki

.. 1移到第k+1個狀態(tài)所需要的時間，其定義如下?ti=tcek,pk+ts+tli+cpk,its=max{cpk,i,rk,i}pkRGVk個狀態(tài)時的位置tliCNC的上料時間tc表示當前狀態(tài)后工件的時間，代表如果CNC空置則，否則不;cpk,i表示從當前狀態(tài)(k)轉(zhuǎn)移到下一個狀態(tài)(k+1)需要的移動時間。對于，函數(shù)f(Vk)定義如下f(Vk)=max{0,rk,i},1≤i≤n,i∈Nf(VkVkCNCrk,imax{0Rk,i}，因為剩余時間非負，并且rk+1,i=tp，ek+1,i=1(8小時)的時間內(nèi)，RGV約束三：RGV一定能夠回到原點。tk+ts+t+ci,0≤tk+ts+ tp+tc+ci,0≤8CNC的M值，換言之，最大化狀態(tài)轉(zhuǎn)移圖中狀態(tài)傳遞max

k+1 tk+ts+tli+ci,0≤Tm,?i∈tk+ts+2tli+tp+tc+ci,0≤Tm,?i∈V、E和移動矩陣C的定義。.Q ,qi∈{0,..iq CNCii CNCi的時候，RGV的下一個操作目標不能是第一類CNC，證明如下：?RGVCNCCNCRGV機械臂上?CNC由??可知，RGV一個非空第一類CNC以后必須接著第二類CNC。k個狀態(tài)到第k+1個狀態(tài)進行轉(zhuǎn)移的時候通過下式實現(xiàn)約束一：(1?qpk ?=?ti=tcek,pq+t+tli+tli=(imod2)tl0+((i+1)mod總的數(shù)學(xué)模為：maxtk+ts+tli+ci,0≤Tm,?i∈ (1?qpk)ek,pk?qpk+1?=1,tli=(imod2)tl0+((i+1)mod完成后，該CNC1pki=gigiiCNC600gi1200giRi=1...mm0CNC由于在最優(yōu)狀態(tài)轉(zhuǎn)移圖模型當RGV的一次上料行為完成時，模型狀態(tài)才發(fā)生轉(zhuǎn)移。所以可對模型進行如下修改；當CNC只有一種刀具時，狀態(tài)轉(zhuǎn)移矩陣集Ak，增加以下Ak=Tki,pi=0Bk=Tki,pi ek,i=012RGV應(yīng)能力與CNC工作能力之間的平衡。當CNCCNCCNC工作效率降故障未修復(fù)時RGVCNC，RGV出現(xiàn)等待情況，系統(tǒng)效率降低，故障修復(fù)以后效率重新提高當CNC安裝有兩種刀具時，（除了滿足（1）-（3）幾項約束外根據(jù)系統(tǒng)效率均衡原則，任一CNC將導(dǎo)致各工作部件之間的均衡性被打破，55解，但是由于解空間樹過于龐大，剪枝的搜索算法復(fù)雜度高達O(8n)，效率較低、1最優(yōu)性剪枝優(yōu)化后的搜索算法實現(xiàn)參見附tpiiCNCRGV本質(zhì)上是為CNC提供服務(wù)的，即：盡可能使CNC減少等待時間，增加工作時間從而提升系統(tǒng)整體的工作效率。由此建立工作效率度量指標——CNC的工作效率為：t∑tWCNC= 分階段優(yōu)化原則的目標是：RGV在當前段在所有八臺候選CNC中，選擇可以最快上料并進入物料加工程序的CNC作為下一階段的目標CNC。隨著系統(tǒng)的變化算法循環(huán)所有的八臺候選CN 計算到每一臺CNC的路程代價該CNC加工時間的剩余，取其中的最大值為評估值。選擇八臺CNC中評估值最小的CNC作為目標CNC，意為選擇可以最快上料從目標CNC。RGVCNCCNCCNC系統(tǒng)在狀CNC系統(tǒng)的相似的分階段優(yōu)化算法進行計算，框架和算法框架1中算法設(shè)計基本相同，選擇路程代價、加工時間的剩余中的大者為評估值。選擇評估值最小的CNC作為目標，但不能以下約束：如果評估值最小的CNC約束，則選擇評估值次小，如此往復(fù)，直到找到不約束的目標CNC。0 2 3 5 圖 CNC刀片類型比例與系統(tǒng)產(chǎn)出關(guān)系根據(jù)前文提到的系統(tǒng)均衡優(yōu)化原則，我們認為系統(tǒng)中擁有兩種不同型號的CNC的CNC的比例被達到當且盡量兩類CNC處理物料的時間代價大致相同。CNCCNC加工物料的時間和RGVRGV到達CNC付出的地位。圖3的橫軸是第一類、第二類CNC的比例，縱軸是采用分階段優(yōu)化算法計算三種情況下，第一類、第二類CNC比例相同的空間排布方案的成品數(shù)的平均值。正如圖3CNC4:4為對稱軸的對稱且在兩種CNC為幾乎1:1的情況下取得峰值。而當?shù)谝活怌NC物料處理時間CNCCNC的數(shù)目小于第峰值偏向左側(cè)即第一類CNC的數(shù)目大于第二類CNC。一定程度上證明了我們的系統(tǒng)均1020分鐘之間隨機生RGV每次進行上料的時候以1%的概率發(fā)生故障，如果發(fā)生故障，在物CNC發(fā)生故障時，需要設(shè)置該CNC故障變量為1。RGV如果狀態(tài)轉(zhuǎn)移的最優(yōu)目標為某一故障的CNC時，則選擇次優(yōu)CNC，直到目標無故障為止。當故障時間結(jié)束，CNC重新恢復(fù)正常故障變量恢復(fù)成0t1，第一類NCn1第二類刀片的物料t2CNCntn1>t2nt1n1?t2n2>t2?n2?t1(n1?1CNCt1n1<t2n2t2n2?t1n1>t1n1?t2(n2?1),則關(guān)閉一個第二類CNC。約束的含義是，從優(yōu)勢方關(guān)閉CNC是優(yōu)劣勢方差距減小的情況下，關(guān)閉一個優(yōu)勢方的CNC以平衡產(chǎn)能,達到更優(yōu)匹配。在情況一條件下，一個工時（8小時）內(nèi)第一、二、三組能夠生產(chǎn)熟料的最大數(shù)量分別為、、個，CNCRGV具體的調(diào)度規(guī)則見支撐材料。實線部分描述了CNC只安裝一種刀片時移動的路徑情況，而相見的“豎線”部分則刻畫了RGV正在上下料與交替進行。紅色虛線則表示在最優(yōu)調(diào)度下此時RGV會對在工作的CNC進行操作，因此其模式是在某處先后操作者兩側(cè)的CNC；此外可以圖 優(yōu)化后RGV的運動路線和各項操作時間λ= UU條件下的系統(tǒng)具有工作上限)的近似程度表 最優(yōu)狀態(tài)轉(zhuǎn)移圖模型結(jié)果分析123 CNC編號1-8上的刀片類型分別為CNC與RGV具體的調(diào)度規(guī)則見支撐材料。在該圖中，x軸、y軸分別描述了表 帶有工序約束的最優(yōu)狀態(tài)轉(zhuǎn)移圖模型刀片類型最優(yōu)分布12345678圖 優(yōu)化后RGV的運動路線和各項操作時間CNC只安裝二種類型刀片時移動的路RGV是攜帶物料進行“搬運”操作；而綠色虛線部分則是描述其不帶任何貨物進行移動的情況顯然后者的具有更大的時間開銷。相見的“豎線”部分則刻畫了RGV正在上下料與交替進行。紅色虛線則表示在最優(yōu)調(diào)度下此時RGVRGV在某處重復(fù)執(zhí)行該操作組合，其模式也是在某處先后表 帶有工序約束的最優(yōu)狀態(tài)轉(zhuǎn)移圖模型結(jié)果分析123376,250,387243,205,224模型建立基于理性分析和合理推導(dǎo)，并對于部分重要原則給出了有保證的定義和證明，對求解的決策原則進行全面的分析和討論，使得模型具有較多的能評價準確到位。該模型的狀態(tài)空間較大，在不加必要限制的情況下，每次搜索的空間為8個，隨考慮使用分階段優(yōu)化求解，但是所求為近似解，且較為近最優(yōu)值，但仍有一定長的遺傳算法（MessyGA）[3]。此外在交叉、變異操作時應(yīng)當保證否是滿足終條件在基束規(guī)則否適應(yīng)值評價(當前方案完成熟數(shù))，存最圖 改進遺傳算法流程[1],,,.基于遺傳算法的RGV動態(tài)調(diào)度研究[J].起重機[2],.基于TS算法的直線往復(fù)2-RGV系統(tǒng)調(diào)度研究[J].工業(yè)工程與管[3]D.E.Goldberg,B.Korb,andK.Deb,“Messygeneticalgorithms:Mo-tivation,ysis,andfirstresults,”inComplexSyst.,Sept.1989,vol.3,pp.93–530無法給出答案（調(diào)整代碼中tot_t的值。1#include2#include3#include4#includetypedefpair<int,int>pii;typedefpair<pii,vector<int>>typedefpair<int,int>pii;typedefpair<pii,vector<int>>piv;constintmov_t[]={0,20,33,constintproc_t[]={560,400,constintud_t[]={28,31};constintclr_t=25;678913constinttot_t=15vector<piv>dfs_stack,16intglobal_ans=18voidprint_st(piv&st) cout<<st.first.first <<stfirst.sec for(inti:st.second) cout<<''<< cout<<2426voidprint_ta for t: 3032inteval_func(intrem_t,intcur_pos,vector<int>&cnc_sts) intres= rem_t?= if(rem_t<0)rem_t= for(inti=0;i<8;i++) if(cnc_sts[i]!=?1&&rem_t>=cnc_sts[i]) res+=rem_t*8/(proc_t[0]+ return voiddfs(intrem_t,intcur_pos,vector<int>cnc_sts,intcur_ans) if(cur_ans+eval_func(rem_t,cur_pos,cnc_sts)<=global_ans) if(rem_t<=mov_t[cur_pos]) if(cur_ans>global_ans) global_ans= ans_stack= vector<int>order={0,1,2,3,4,5,6, for(inti=0;i<8;i++) intcur_max= for(intj=i;j<8;j++) if(max(mov_t[abs(cur_pos?order[cur_max]/2)]cnc_sts[order[cur_max]])+ud_t[oer[cur_max]%2]max(mov_t[abs(cur_pos?order[j/2)],cc_sts[ode[j]])+ud_t[order[j]%2]){ cur_max= swap(order[cur_max],orde for(inti:order) intpos=i/ intt=max(mov_t[abs(r_pos?ps)],cnc_sts[i])+ud_t[i% vector<int>newcnc_sts= csts[]=roc_t[0]?(cnc_sts[i]==?1?0: forintj=;j<8;j++)if(i!=j) ew_n ==?1) cstj]?=t+ if(new s[]< c_sts[j]= dfs(rem_t?t?clr_t,pos, c_sts,cur_ans+(cnc_sts[i]==?1

?0

intmain() vector<int>init_st={?1,?1,?1,?1,?1,?1,?1, dfs(tot_t,0,init_st, cout<<global_ans<< returnreturn}1import23move_step_times=[0,20,33,4process_times=[560,400,5up_down_times=[28,6clean_time=78#move_step_times=[0,23,41,9#process_times=[580,280,10#up_down_times=[30,11#clean_time=##move_step_times=[0,18,32,#process_times=[545,455,#up_down_times=[27,32]#clean_time=25#INFcur_pos=cur_time=defmove_time(p1,preturnmov_st_tim 25cnt=26res=27cnc_states=[0oriin28fst_time=[True in item_idx=[?1 in30broken=[0foriin31items=32broken_items=34while candidates=[iforiin candidates.sort(key=lambdai:max(move_time(cur_pos,i//2),cnc_states[i])+up_down_times[i%2]) ok= cin t1= c//2), c_time=t1+ c% ct=clean_timeifnot c]else ifcur_time c_time+ct+move_time(cur_pos,0)>8* ok= #print(cur_time,cur_pos,cnc_states, if c]> ifrandom.random()< c]=random.randint(10*60,20* c+1,'up_time':cur_time+t1,'down_time': c+1,cur_time+ c_time,ur_time+ c+1,'upime':cu_time+t'down_time':None}) foriin cnc_states[i] c_time+ broken[i] c_time+ ifcnc_states[i]< cnc_states[i]= ifbroken[i]< broken[i]= items.append({'cnc':c c+1,uptime:cur_time+t1,'down_time': proces_tims[0]? iffst_tie[cur fst_time[ur_cc]= es= items[item_dx[cu cur_time+ r_nc_time+ cur_pos=cr_cc// item_idx[cur_cc]=len(items)? ifnot

me']=cur_time+7576print(res*process_times[0]/(8*8*77foritemin 7980foritemin 821move_step_times=[0,20,33,2process_times=[560,400,3up_down_times=[28,4clean_time=56#move_step_times=[0,23,41,7#process_times=[580,280,8#up_down_times=[30,9#clean_time=11#move_step_times=[0,18,32,12#process_times=[545,455,13#up_down_times=[27,14#clean_time=15INF18defmove_time(pos1, returnmove_step_times[abs(pos1?pos21count=23forbin_classinrange(1<< cnc_class=[0if(bin (1<i))==0else1foriin ifbin_class!= cnc_class=[0,10,1,01,0, res= half_prod= cnc_states=[0foin fst_time=[Truefriin item_idx=[?1foriin items= while candidates=[iforiin candidates.sort(key=lambdai:max(move_time(cur_pos,i//2),+up_down_times[i% ok= cin ifhalf_prodandc] t1=c2), c_time=t1+ c% ct=clean_timeif c]==1else ifcur_time c_time+ct+move_time(cur_pos,0)>8* if c]== ifcur_time+ c_time+process_times[1]+process_times[2]+clean_time+move_time(cur_pos,0)>8*3600: half_prod= ok= # c,cnc_states, c],half_prod, foriin cnc_states[i] c_time+ ifcnc_states[i]< cnc_states[i]=c]=ifc]=ifc]== c+1,'up_time1 cur_tme+t,'down_time1':None,'cnc2':Non,'up_time2 Non,'down_time2': if c]!= ']=cur_time+ half_prod= c]= ifnot items[half_pro['cnc2] c+ items[half_prod]up_tim2']=cur_time+ ifitem_ix[cur_cc]!= items[ c]['down_time2']=cur_time+ item_i c]= s half =No cur_tim c_time+ cu_cnc// ifnot num_1= ifcount.get((8?num_1,num_1))is count[(8?num_1,num_1)]= count[(8?num_1,85importimport23#move_step_times=[0,20,33,4#process_times=[560,400,5#up_down_times=[28,6#clean_time=78#move_step_times=[0,23,41,9#process_times=[580,280,10#up_down_times=[30,11#c