機(jī)床任務(wù)分配問(wèn)題數(shù)學(xué)建模-在線(xiàn)瀏覽
2025-05-25 02:52本頁(yè)面
【正文】 們可以考慮運(yùn)用仿生智能算法中的蟻群算法建立模型，采用一種新的啟發(fā)信息：最早允許加工時(shí)間(EAPT)，并在模型中加入適量的隨機(jī)信息，使模型避免陷入局部最小的陷阱。 數(shù)據(jù)處理由各項(xiàng)任務(wù)的每件產(chǎn)品的每道工序可供選擇的加工機(jī)床編號(hào)及其所需要的完成時(shí)間表：（見(jiàn)附錄）由題目表中所給數(shù)據(jù)可知，各任務(wù)每道工序可供選擇的加工機(jī)床個(gè)數(shù)不同，為便于求解，將不能加工該任務(wù)該工序的對(duì)應(yīng)加工時(shí)間記為無(wú)窮大，例如，對(duì)于任務(wù)1的工序A，可供選擇的加工機(jī)床號(hào)為(1,3,5),對(duì)應(yīng)的加工時(shí)間(5,7,12)，處理后的數(shù)據(jù)為：可供選擇的加工機(jī)床號(hào)為(1,2,3,4,5,6),對(duì)應(yīng)的加工時(shí)間為（5,7,12,)。最長(zhǎng)的完成時(shí)間為：指標(biāo)三：最短完成總時(shí)間我們用Z來(lái)表示總的預(yù)期時(shí)間效益，要求最短完成所有工序的總時(shí)間，則，由此： 模型一的建立：01整數(shù)規(guī)劃模型（針對(duì)無(wú)序加工方式）在工序無(wú)先后加工順序的情況下，任務(wù)分配問(wèn)題是一類(lèi)典型的組合優(yōu)化問(wèn)題，不同的分配花費(fèi)不同的代價(jià)，任務(wù)分配問(wèn)題就是要找到一種所花費(fèi)代價(jià)最小的分配方案。我們用Z來(lái)表示總的預(yù)期時(shí)間效益，則。若第i臺(tái)機(jī)床完成第j項(xiàng)任務(wù)的時(shí)間，則可構(gòu)成時(shí)間代價(jià)矩陣。這里的約束條件是一個(gè)非線(xiàn)性規(guī)劃，其目標(biāo)函數(shù)也即min Z=max{, 為一個(gè)基本可行解中非零分量的系數(shù)}。5）若此二臺(tái)機(jī)床完成時(shí)間的較大者變小，記錄新方案，清除標(biāo)記，轉(zhuǎn)2)；否則，維持原方案，并將該工作記上標(biāo)記，轉(zhuǎn)4）。其中，機(jī)床2和機(jī)床3的總時(shí)間最大，均為233小時(shí)，因此問(wèn)題一的最短時(shí)間即為233小時(shí)。：遺傳算法模型在工序規(guī)定了先后加工順序的情況下，機(jī)床任務(wù)的調(diào)度即屬于非常普遍的柔性生產(chǎn)調(diào)度問(wèn)題。我們經(jīng)過(guò)反復(fù)研究，將遺傳算法與生產(chǎn)工藝結(jié)合，提出了一種新的遺傳調(diào)度方法，通過(guò)設(shè)計(jì)適合表達(dá)不同加工機(jī)床上不同零件的加工順序的染色體，變隨機(jī)生成染色體為有目的生成染色體，加速了搜索最優(yōu)解的速度，使得作業(yè)車(chē)間的柔性化制造系統(tǒng)（FMS）中最難解決的問(wèn)題之一——車(chē)間調(diào)度得到比較可行的實(shí)施。運(yùn)用遺傳算法的過(guò)程就是對(duì)備選解進(jìn)行迭代的過(guò)程，沒(méi)爹帶一次成為一代，在完成一次迭代后，利用一定的評(píng)價(jià)函數(shù)對(duì)當(dāng)前的群體進(jìn)行評(píng)估，并在此基礎(chǔ)上產(chǎn)生下一代。算法的容量如圖1所示：以上的迭代運(yùn)算過(guò)程直到找到一個(gè)滿(mǎn)意的解或者達(dá)到預(yù)先設(shè)定的迭代次數(shù)為止，算法中的評(píng)價(jià)函數(shù)主要作用是：對(duì)當(dāng)前群體中的每個(gè)染色體性能進(jìn)行評(píng)價(jià)，保留高性能的染色體，除去低性能的染色體，并通過(guò)遺傳算子補(bǔ)充一些新的染色體，使群體的總性能不斷得到改善，最后得到非常優(yōu)秀的群體，滿(mǎn)足問(wèn)題的求解要求。選擇操作的目的是為了從當(dāng)前群體中選出優(yōu)良的個(gè)體，使它們有機(jī)會(huì)作為父代繁殖子孫。變異模擬了生物進(jìn)化中的基因突變過(guò)程。根據(jù)這一目標(biāo)，設(shè)計(jì)N組染色體，以表示每臺(tái)設(shè)備上工件的加工次序，染色體（i=1,2,…,6）表示設(shè)備上工件的加工次序。計(jì)算每個(gè)染色體確定的加工次序的情況下系統(tǒng)的通過(guò)時(shí)間，據(jù)此選出當(dāng)前一代染色體中最為優(yōu)秀的若干組染色體作為繁殖后代的雙親，形成交配池，然后通過(guò)遺傳算子產(chǎn)生新的染色體，形成下一代染色體的群體。由于每道工序必須在它的前面所有工序全部加工完畢的情況下才能加工，因此，為了減少設(shè)備的等待時(shí)間，應(yīng)該盡量將工序靠前的工件安排在染色體靠前的位置加工，假設(shè)在設(shè)備上有件工件需要加工，每種工件其前面的生產(chǎn)周期之和為，值越大，工件在染色體中的位置越應(yīng)后，令 （4）T為所有K個(gè)工件前面所有工序生產(chǎn)周期之和，為工件應(yīng)該排在染色體前面的加權(quán)系數(shù)，其和： 據(jù)此可以計(jì)算每個(gè)工件排在染色體第一位的概率是：在染色體生成時(shí)將以此還綠首先確定第一個(gè)工件，然后再計(jì)算各工件處于第2位的概率，即： （6）式中，設(shè)為排在染色體第一位的工件，以（6）式確定排在第2位的工件，同理，可以確定以后個(gè)工件的位置。為了比較已經(jīng)生成了的染色體的優(yōu)劣，需要計(jì)算每一組染色體確定的系統(tǒng)的通過(guò)時(shí)間，即上式中第i臺(tái)機(jī)床加工完所有工件所用時(shí)間為。因此，一般的程序設(shè)計(jì)方法很難解決生產(chǎn)過(guò)程的仿真問(wèn)題，只有利用巡回掃描模式才能解決這個(gè)問(wèn)題。：所謂解碼算法就是根據(jù)染色體的編碼和柔性調(diào)度問(wèn)題的約束條件推導(dǎo)出可行的調(diào)度方案（問(wèn)題的可行解），解碼方法如下：其含義為：在調(diào)度生成過(guò)程中，首先安排第2個(gè)工件的第1道工序，接著安排第1個(gè)工件的第1道工序，然后安排第1個(gè)工件的第2道工序，按這種方式，依次從左到右將染色體上的工序都安排完為止。：眾所周知，對(duì)于調(diào)度問(wèn)題，交叉操作是最棘手的難題，由于本算法用染色體確定工序的優(yōu)先權(quán)，然后用一次通過(guò)優(yōu)先分配啟發(fā)式算法產(chǎn)生調(diào)度，因此不要求雙親和后代中部分調(diào)度的工序順序一致，故采用簡(jiǎn)單的單斷點(diǎn)交叉法。本文使用規(guī)劃資源算子[4 ]作為交叉操作時(shí)的算子,規(guī)劃資源算子就是將零件、工序和機(jī)床作為一個(gè)操作單元進(jìn)行交叉操作,同時(shí)改變零件、工及加工該工序所使用的機(jī)床,這樣零件的加工順序在交叉過(guò)程中不發(fā)生變化,避免了在交叉過(guò)程中破壞工序約束,因此不會(huì)產(chǎn)生非可行解。Makespan是指完成一批零件所有n個(gè)工序需要的時(shí)間,這里主要采用資源負(fù)荷均衡和最小化零件平均流通時(shí)間作為評(píng)價(jià)指標(biāo),同時(shí)要求零件不超期。對(duì)于超期零件則在性能指標(biāo)中加入懲罰項(xiàng)。為第i臺(tái)機(jī)床完成該批工件所有操作的加工時(shí)間，包括工件加工時(shí)間和調(diào)度時(shí)間；，分別為第個(gè)工件完成加工的時(shí)間和交貨時(shí)間，為加權(quán)系數(shù)，為第j個(gè)零件的第l道工序的加工完成時(shí)間，為第j個(gè)零件的l+1道工序的開(kāi)始加工時(shí)間，為第j個(gè)工件的操作數(shù)。系統(tǒng)的調(diào)度時(shí)間相應(yīng)分成許多調(diào)度階段,每一調(diào)度階段對(duì)應(yīng)一個(gè)零件批次。調(diào)度時(shí)間縮短能夠減輕系統(tǒng)的調(diào)度復(fù)雜程度,增加調(diào)度的準(zhǔn)確性,有利于提高系統(tǒng)生產(chǎn)效率和資源利用率,但是零件在系統(tǒng)中的流通時(shí)間仍然沒(méi)有縮短。重迭調(diào)度是在相鄰兩批零件的調(diào)度過(guò)程中,在安排一批零件的加工作業(yè)之前,就考慮前一批零件的生產(chǎn)安排情況,不等待前一批零件都完成加工才安排該批零件的加工,只要某臺(tái)設(shè)備所承擔(dān)的前一批次任務(wù)完成而且設(shè)備有空閑,下一批零件中分配到該設(shè)備的零件就可以進(jìn)入系統(tǒng)進(jìn)行加工。重迭調(diào)度機(jī)床1機(jī)
數(shù)學(xué)相關(guān)推薦
鄂ICP備17016276號(hào)-1