機(jī)床任務(wù)分配問題數(shù)學(xué)建模(編輯修改稿)
2025-05-04 02:52 本頁面
【文章內(nèi)容簡介】 模擬達(dá)爾文的遺傳選擇和自然淘汰的生物進(jìn)化過程的計(jì)算模型，一個(gè)備選解被稱為一個(gè)染色體，每個(gè)染色體由若干基因組成，每個(gè)基因表示一個(gè)數(shù)值，若干個(gè)染色體組成一個(gè)群體。運(yùn)用遺傳算法的過程就是對備選解進(jìn)行迭代的過程，沒爹帶一次成為一代，在完成一次迭代后，利用一定的評價(jià)函數(shù)對當(dāng)前的群體進(jìn)行評估，并在此基礎(chǔ)上產(chǎn)生下一代。初始群體可根據(jù)經(jīng)驗(yàn)主觀選取，群體容量為C。算法的容量如圖1所示：以上的迭代運(yùn)算過程直到找到一個(gè)滿意的解或者達(dá)到預(yù)先設(shè)定的迭代次數(shù)為止，算法中的評價(jià)函數(shù)主要作用是：對當(dāng)前群體中的每個(gè)染色體性能進(jìn)行評價(jià)，保留高性能的染色體，除去低性能的染色體，并通過遺傳算子補(bǔ)充一些新的染色體，使群體的總性能不斷得到改善，最后得到非常優(yōu)秀的群體，滿足問題的求解要求。圖1 算法流程圖遺傳算子主要包括選擇、交叉和變異。選擇操作的目的是為了從當(dāng)前群體中選出優(yōu)良的個(gè)體，使它們有機(jī)會(huì)作為父代繁殖子孫。交叉就是利用優(yōu)良個(gè)體進(jìn)行雜交產(chǎn)生新個(gè)體的隨機(jī)過程。變異模擬了生物進(jìn)化中的基因突變過程。：設(shè)5份訂單的加工工序?yàn)椋荷a(chǎn)調(diào)度的目標(biāo)就是確定每臺(tái)設(shè)備上各個(gè)工件的加工先后次序，以保證工件在系統(tǒng)中的通過時(shí)間最短。根據(jù)這一目標(biāo)，設(shè)計(jì)N組染色體，以表示每臺(tái)設(shè)備上工件的加工次序，染色體（i=1,2,…,6）表示設(shè)備上工件的加工次序。其中，若取遺傳群體為C，按照遺傳算法應(yīng)該首先隨機(jī)產(chǎn)生C組染色體，即： （3）公式（3）中的每一行表示一種在整個(gè)加工系統(tǒng)（6臺(tái)機(jī)床）上工件的次序組合，展開來看即為：，其余的c1行按上面的形式依次展開。計(jì)算每個(gè)染色體確定的加工次序的情況下系統(tǒng)的通過時(shí)間，據(jù)此選出當(dāng)前一代染色體中最為優(yōu)秀的若干組染色體作為繁殖后代的雙親，形成交配池，然后通過遺傳算子產(chǎn)生新的染色體，形成下一代染色體的群體。為了有效地尋找最優(yōu)解，在染色體（2）的生成過程中，將充分考慮工件的加工工藝特點(diǎ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è)工件的位置。這種確定染色體的方法將有利于減少群友的時(shí)間。為了比較已經(jīng)生成了的染色體的優(yōu)劣，需要計(jì)算每一組染色體確定的系統(tǒng)的通過時(shí)間，即上式中第i臺(tái)機(jī)床加工完所有工件所用時(shí)間為。由于車間生產(chǎn)系統(tǒng)中各設(shè)備可同時(shí)加工不同工件，表現(xiàn)為時(shí)間上的并行關(guān)系。因此，一般的程序設(shè)計(jì)方法很難解決生產(chǎn)過程的仿真問題，只有利用巡回掃描模式才能解決這個(gè)問題。即程序不是只執(zhí)行一次，而是不斷地循環(huán)執(zhí)行，直到所有設(shè)備上工件都加工完畢為止。：所謂解碼算法就是根據(jù)染色體的編碼和柔性調(diào)度問題的約束條件推導(dǎo)出可行的調(diào)度方案（問題的可行解），解碼方法如下：其含義為：在調(diào)度生成過程中，首先安排第2個(gè)工件的第1道工序，接著安排第1個(gè)工件的第1道工序，然后安排第1個(gè)工件的第2道工序，按這種方式，依次從左到右將染色體上的工序都安排完為止。最終生成的調(diào)度方案(問題的可行解)為：機(jī)床的加工順序是2—1—3，機(jī)床2上的加工順序是1—2—3，機(jī)床3上的加工順序是1—2—3。：眾所周知，對于調(diào)度問題，交叉操作是最棘手的難題，由于本算法用染色體確定工序的優(yōu)先權(quán)，然后用一次通過優(yōu)先分配啟發(fā)式算法產(chǎn)生調(diào)度，因此不要求雙親和后代中部分調(diào)度的工序順序一致，故采用簡單的單斷點(diǎn)交叉法。在變異時(shí)可能產(chǎn)生非可行解(產(chǎn)生某個(gè)零件的某個(gè)工序所分配的加工機(jī)床為非加工機(jī)床),因此要進(jìn)行解的可行性檢查,如果產(chǎn)生非可行解,則不進(jìn)行變異。本文使用規(guī)劃資源算子[4 ]作為交叉操作時(shí)的算子,規(guī)劃資源算子就是將零件、工序和機(jī)床作為一個(gè)操作單元進(jìn)行交叉操作,同時(shí)改變零件、工及加工該工序所使用的機(jī)床,這樣零件的加工順序在交叉過程中不發(fā)生變化,避免了在交叉過程中破壞工序約束,因此不會(huì)產(chǎn)生非可行解。應(yīng)用規(guī)劃資源算子的交叉操作如下：交叉點(diǎn)：本題我們采用的評價(jià)調(diào)度性能的指標(biāo)是最小化零件平均流通時(shí)間(makespan)。Makespan是指完成一批零件所有n個(gè)工序需要的時(shí)間,這里主要采用資源負(fù)荷均衡和最小化零件平均流通時(shí)間作為評價(jià)指標(biāo),同時(shí)要求零件不超期。即在資源負(fù)荷平衡的前提下,盡量使makespan最小,同時(shí)使零件盡量不超期,還要滿足零件工序的順序約束。對于超期零件則在性能指標(biāo)中加入懲罰項(xiàng)。調(diào)度目標(biāo)是使工件平均流通時(shí)間和工件平均延誤時(shí)間的加權(quán)之和最小,其性能指標(biāo)為：其中，權(quán)值，反映調(diào)度目標(biāo)中和的側(cè)重誠度。為第i臺(tái)機(jī)床完成該批工件所有操作的加工時(shí)間，包括工件加工時(shí)間和調(diào)度時(shí)間；，分別為第個(gè)工件完成加工的時(shí)間和交貨時(shí)間，為加權(quán)系數(shù)，為第j個(gè)零件的第l道工序的加工完成時(shí)間，為第j個(gè)零件的l+1道工序的開始加工時(shí)間，為第j個(gè)工件的操作數(shù)。：根據(jù)FMS的資源情況和調(diào)度目標(biāo)的要求,將生產(chǎn)任務(wù)分成不同的零件批次,每一零件批次都按順序進(jìn)入系統(tǒng)。系統(tǒng)的調(diào)度時(shí)間相應(yīng)分成許多調(diào)度階段,每一調(diào)度階段對應(yīng)一個(gè)零件批次。這樣就把具體調(diào)度時(shí)間縮短了。調(diào)度時(shí)間縮短能夠減輕系統(tǒng)的調(diào)度復(fù)雜程度,增加調(diào)度的準(zhǔn)確性,有利于提高系統(tǒng)生產(chǎn)效率和資源利用率,但是零件在系統(tǒng)中的流通時(shí)間仍然沒有縮短。為了進(jìn)一步縮短系統(tǒng)的流通時(shí)間,應(yīng)用重迭調(diào)度[5]的方法安排相鄰零件批次的加工過程。重迭調(diào)度是在相鄰兩批零件的調(diào)度過程中,在安排一批零件的加工作業(yè)之前,就考慮前一批零件的生產(chǎn)安排情況,不等待前一批零件都完成加工才安排該批零件的加工,只
數(shù)學(xué)相關(guān)推薦
鄂ICP備17016276號(hào)-1