d-14-西南財(cái)經(jīng)大學(xué)(編輯修改稿)
2025-06-15 22:43 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 點(diǎn)與終點(diǎn)的那條邊與連接 c0的起點(diǎn)與終點(diǎn)的那條邊。 步驟五：且計(jì)算這條依次從 c1起點(diǎn)連接到 c0終點(diǎn)的邊的長(zhǎng)度，若這個(gè)長(zhǎng)度短于當(dāng)前最優(yōu)解，則記錄。轉(zhuǎn)到步驟三。 169。Copyright 2021 SWUFE. All rights reserved. Page29 算法描述 上一步中我們就得到的整個(gè)過(guò)程的起點(diǎn)與終點(diǎn)，我們用下面的算法把中間各個(gè)階段的任務(wù)連接起來(lái)。 步驟一：由蟻群算法求出中間各個(gè)階段的最小 Hamilton圈，并刪掉最長(zhǎng)邊，由此得一條弧。 步驟二：分別以每一條弧的兩個(gè)端點(diǎn)中的任意一個(gè)作為起點(diǎn)，另一個(gè)作為終點(diǎn)。并且按加工順序連接所有的弧。得到一個(gè)新的圈。 步驟三：計(jì)算這個(gè)圈的長(zhǎng)度，若小于最優(yōu)解就記錄下來(lái)，找遍了步驟二中的所有情況則算法結(jié)束。 169。Copyright 2021 SWUFE. All rights reserved. Page30 模型結(jié)果 作業(yè)成本 加工總時(shí)間 刀具轉(zhuǎn)換次數(shù) 刀具轉(zhuǎn)換總時(shí)間 行進(jìn)總時(shí)間 行進(jìn)路程（厘米） 優(yōu)化前 14 252秒 方案一 10 180秒 方案二 10 180秒 最優(yōu)刀具轉(zhuǎn)換方案為： 方案二： c d c b a h g f e d c? ? ? ? ? ? ? ? ? ?169。Copyright 2021 SWUFE. All rights reserved. Page31 單鉆頭行進(jìn)路線 169。Copyright 2021 SWUFE. All rights reserved. Page32 雙鉆頭打孔機(jī)模型的建立 賦權(quán)聯(lián)通圖的構(gòu)造 首先我們把需要多種刀具加工的孔分解成若干個(gè)只需要一種刀具加工的孔。這樣我們便得到了 2814個(gè)孔，它們作為圖中的點(diǎn)，組成的集合記為點(diǎn)集 V(G) 。點(diǎn)集 V(G)中任意兩點(diǎn)之間的連線記為邊 。點(diǎn)集中所有點(diǎn)兩兩之間的連線構(gòu)成邊集 V(E)。然后用點(diǎn)集 V(G)與邊集 V(E) 一起構(gòu)成混合圖 G(E,V) 。最后我們對(duì)混合圖 的每一條邊進(jìn)行相應(yīng)的賦權(quán)就得到了賦權(quán)連通圖 G(E,V)。其中，邊權(quán)對(duì)應(yīng)邊的相應(yīng)的費(fèi)用（或時(shí)間）。 169。Copyright 2021 SWUFE. All rights reserved. Page33 權(quán)數(shù)的確定 兩孔之間的距離為： 22( ) ( )ij i j i jd x x y y? ? ? ?? ?1 8 m in , 8i j j i j it ty p e ty p e ty p e ty p e? ? ? ? ?兩孔之間由于刀具轉(zhuǎn)換而產(chǎn)生的時(shí)間為 : （ 表示第 個(gè)孔所需的刀具類(lèi)型對(duì)應(yīng)的次序） 在時(shí)間最優(yōu)的情況下，我們的目標(biāo)是使印刷單個(gè)電路板的時(shí)間盡可能的小。即每條邊的權(quán)數(shù)為： itype i? ? 00m a x ,18 ijij ijdw e t t t??? ? ????? 169。Copyright 2021 SWUFE. All rights reserved. Page34 雙鉆頭打孔機(jī)模型 由于鉆頭數(shù)由一個(gè)增加到了兩個(gè)，故問(wèn)題從類(lèi)似于 TSP問(wèn)題變成了一個(gè)類(lèi)似于 MTSP（多旅行商）的問(wèn)題。首先我們需要把點(diǎn)集 V分成兩個(gè)部分 V1 與 V2 分別交由兩個(gè)鉆頭去打。對(duì)應(yīng)點(diǎn)集然 與 我們分別構(gòu)造出對(duì)應(yīng)的邊集 G1與 G2 。后分別求出連接這兩部分點(diǎn)集的最小哈密頓圈 與 。 1C 2C 1 1 1 2 2 3 3 1jjC v e v e v e v e v? 1ivV? j 1V2 1 1 2 2 3 3 1kkC v e v e v e v e v? 2ivV? k2V其中 ， 為 中的頂點(diǎn)數(shù) 其中 ， 為 中的頂點(diǎn)數(shù) 169。Copyright 2021 SWUFE. All rights reserved. Page35 雙鉆頭打孔機(jī)模型 由于最終完成一個(gè)印刷電路板的總時(shí)間即為兩個(gè)鉆頭中的用時(shí)較大的時(shí)間，我們的目標(biāo)就是使兩個(gè)鉆頭中的用時(shí)較大的時(shí)間盡可能地小。所以最后我們需要平衡兩個(gè)鉆頭的工作量，要使得他們的工作量盡量平均化： 鉆頭一工作總時(shí)間 其中 鉆頭二工作總時(shí)間 其中 1 1 ()jiiT w e???2 1 ()kiiT w e???1ieC?2ieC?與此同時(shí)我們還需要滿(mǎn)足雙鉆頭的最小合作間距的要求。若兩個(gè)鉆頭在任意時(shí)刻的位置為 與 ，那么有： 11( , )xy 22( , )xy221 2 1 2( ) ( ) 3D x x y y? ? ? ? ?12m a x { , }T T T? min{ }T 12m in{ m a x{ , }}TT最終總時(shí)間為 我們的目標(biāo)是 即 169。Copyright 2021 SWUFE. All rights reserved. Page36 模型求解 ? 雙鉆頭情況下的最優(yōu)刀具轉(zhuǎn)換方案 第一，以時(shí)間最優(yōu)為目標(biāo)進(jìn)行處理時(shí)，我們可以發(fā)現(xiàn)，轉(zhuǎn)換一次刀具耗時(shí) 18s，而 18s鉆頭可以行進(jìn)324cm ，已經(jīng)遠(yuǎn)遠(yuǎn)超出印刷電路板上最遠(yuǎn)的兩點(diǎn)之間的距離，所以只有當(dāng)鉆頭完成一種孔型的任務(wù)后，才回去轉(zhuǎn)換刀具。 第二，我們只有 8種刀具，在孔數(shù)量龐大的情況下，大多數(shù)情況下所有的刀具都會(huì)被使用，以時(shí)間最優(yōu)為目標(biāo)的情況下，在以所需刀具為分類(lèi)依據(jù)的孔群內(nèi)鉆頭的行進(jìn)時(shí)間是一定的，為了減少總時(shí)間，刀具更換應(yīng)該是依序逐個(gè)轉(zhuǎn)換的。示意如右圖： b c d e f g h a 169。Copyright 2021 SWUFE. All rights reserved. Page37 雙鉆頭情況下的最優(yōu)刀具轉(zhuǎn)換方案 此外，我們要求兩個(gè)鉆頭完成作業(yè)后，可以相互回到對(duì)方的初始位置與初始狀態(tài)，以此保證連續(xù)作業(yè)與盡可少的刀具轉(zhuǎn)換。示意圖如下： 整個(gè)過(guò)程鉆頭 1：由 a轉(zhuǎn)到 e 整個(gè)過(guò)程鉆頭 2：由 e轉(zhuǎn)到 a b c d e a e f g h a 169。Copyright 2021 SWUFE. All rights reserved. Page38 雙鉆頭情況下的最優(yōu)刀具轉(zhuǎn)換方案 另外我們還需要保證加工次序。由于我們把孔按所需刀具類(lèi)型分成了 10種（包括 a,b,d,e,f,g； c與 f則分為優(yōu)先打的 c0 與 f0和需要最后打的 c1與 f1）即我們必須保證如下次序： 1）打 c1型前必須打 a ,f0 ,e 2）打 f1 型前必須打 c0 g 3）打 g型前必須打 d 169。Copyright 2021 SWUFE. All rights reserved. Page39 算法描述 我們采用了遍歷法來(lái)尋找合適的刀具轉(zhuǎn)換方案 步驟一：初始化
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號(hào)-1