d14西南財(cái)經(jīng)大學(xué)

1、打孔機(jī)最優(yōu)作業(yè)方案隊(duì)員：指導(dǎo)老師：1總體簡介 本文以題中提供的某塊印刷線路板過孔中心坐標(biāo)的數(shù)據(jù)為基礎(chǔ)，收集相關(guān)資料，研究打孔機(jī)作業(yè)的相關(guān)關(guān)系，通過對孔的技術(shù)性處理，最終建立了類似于TSP的模型，我們將孔按所需的刀具類型分群，并制定了鉆頭等待-規(guī)避策略與雙鉆頭任務(wù)均衡的方法，結(jié)合蟻群算法很好的解決了單鉆頭與雙鉆頭的最優(yōu)作業(yè)問題?；炯僭O(shè)1.單個(gè)過孔的鉆孔作業(yè)時(shí)間是由生產(chǎn)工藝決定，為了簡化問題，這里假定對于同一孔型鉆孔作業(yè)時(shí)間都是相同的，過孔費(fèi)用不計(jì)。2. 鉆頭的行進(jìn)速度是相同的，為180 mm/s，行進(jìn)成本為0.06元/mm，刀具轉(zhuǎn)換的時(shí)間成本為7元/min3. 刀具在行進(jìn)過程中可以同時(shí)進(jìn)行刀具

2、轉(zhuǎn)換，但相應(yīng)費(fèi)用不減。4. 一塊線路板上的過孔全部加工完成后，再制作另一線路板。但在同一線路板上的過孔不要求加工完畢一個(gè)孔，再加工另一個(gè)孔，即對于須用兩種或兩種以上刀具加工的過孔，只要保證所需刀具加工次序正確即可?；炯僭O(shè)打孔機(jī)連續(xù)作業(yè)（打孔機(jī)的連續(xù)作業(yè)即是把所有的孔按相應(yīng)的刀具要求、順序要求打一遍，最終回到出發(fā)點(diǎn)，形成生產(chǎn)線作業(yè)）6. 把需要多種刀具加工的單個(gè)孔技術(shù)性地看作多個(gè)分別需要一種刀具加工的孔（例如：孔型C需要刀具a和刀具c，且加工次序?yàn)閍、c，于是我們將這一個(gè)孔看作兩個(gè)孔，它們分別需要刀具a和c，并且打孔順序按原來的要求）7. 題目所給數(shù)據(jù)真實(shí)可靠單鉆頭打孔機(jī)模型的建立賦權(quán)聯(lián)通圖的

3、構(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) 。最后我們對混合圖 的每一條邊進(jìn)行相應(yīng)的賦權(quán)就得到了賦權(quán)連通圖 G(E,V)。其中，邊權(quán)對應(yīng)邊的相應(yīng)的費(fèi)用（或時(shí)間）?？仔头植紙D權(quán)數(shù)的確定 （ 表示第 個(gè)孔所需的刀具類型對應(yīng)的次序，例如第一種刀具a對應(yīng)的次序便為1，即 ，由于可能是順時(shí)針或者逆時(shí)針轉(zhuǎn)動(dòng)，故用絕對值表示）兩孔之間的距離為：兩孔之間

4、由于刀具轉(zhuǎn)換而產(chǎn)生的時(shí)間為:在成本最優(yōu)下，我們的目標(biāo)是使印刷單個(gè)電路板的費(fèi)用盡可能的小。即每條邊的權(quán)數(shù)為：在時(shí)間最優(yōu)的情況下，我們的目標(biāo)是使印刷單個(gè)電路板的時(shí)間盡可能的小。即每條邊的權(quán)數(shù)為：權(quán)數(shù)的確定單鉆頭打孔機(jī)的模型 圈C 表示一條連接圖G內(nèi)所有點(diǎn)的一個(gè)圈。建立的數(shù)學(xué)模型如下:其中 ，并且對于任意的 ，在 中有且并只出現(xiàn)一次 , 為總頂點(diǎn)數(shù)。權(quán)數(shù)分別取時(shí)間或費(fèi)用分別來求時(shí)間最優(yōu)或費(fèi)用最優(yōu)情況下的最優(yōu)解。模型求解算法選擇分析 由于我們面對的問題的數(shù)據(jù)規(guī)模特別大（有多達(dá)2814個(gè)點(diǎn)）無法直接求出最優(yōu)解，只能利用啟發(fā)式算法。蟻群算法具有以下的特點(diǎn)： 1)采用正反饋機(jī)制，使得搜索過程不斷收斂，最終逼

5、近最優(yōu)解。 2)每個(gè)個(gè)體可以通過釋放信息素來改變周圍的環(huán)境，且每個(gè)個(gè)體能夠感知 周圍環(huán)境的實(shí)時(shí)變化，個(gè)體間通過環(huán)境進(jìn)行間接的通訊。 3)搜索過程采用分布式計(jì)算方式，多個(gè)個(gè)體同時(shí)進(jìn)行并行計(jì)算，大大提高了算法的運(yùn)行效率。 4)啟發(fā)式的概率搜索方式不容易陷入局部最優(yōu)，易于尋找到全局最優(yōu)解。所以我們使用了人工蟻群算法來搜索一個(gè)逼近全局最優(yōu)解的解。模型求解算法選擇分析 從實(shí)際運(yùn)行效果來看，對于以 題目中數(shù)據(jù)所給的第一個(gè)孔為初始點(diǎn)，用三種算法求解，結(jié)果如下表所示，可以清晰的看到蟻群算法的優(yōu)勢。算法時(shí)間（s)退火算法1210.7遺傳算法7189蟻群算法328模型求解蟻群算法描述 在使用蟻群算法求解現(xiàn)實(shí)問題時(shí)

6、，先生成具有一定數(shù)量螞蟻的蟻群，讓每一只螞蟻建立一個(gè)解或解的一部分，每只人工蟻從問題的初始狀態(tài)出發(fā)，根據(jù)“激素”濃度來選擇下一個(gè)要轉(zhuǎn)移到的狀態(tài)，直到建立起一個(gè)解，每只螞蟻根據(jù)所找到的解的好壞程度在所經(jīng)過的狀態(tài)上釋放與解的質(zhì)量成正比例的“激素”。之后，每只螞蟻又開始新的求解過程，直到尋找到滿意解。為避免停滯現(xiàn)象，引入了激素更新機(jī)制。算法步驟如下：步驟一:初始化 ,各邊的信息素濃度初始化。步驟二:將 m個(gè)螞蟻置于初始頂點(diǎn)上。步驟三:按順序選定一只螞蟻；若已經(jīng)選完所有的螞蟻則轉(zhuǎn)步驟七模型求解蟻群算法描述步驟四：篩選出這只螞蟻從當(dāng)前位置出發(fā)允許到達(dá)的點(diǎn)（去掉已經(jīng)走過的點(diǎn)和刀 具加工順序有沖突的點(diǎn)）步驟

7、五：螞蟻根據(jù)連接當(dāng)前點(diǎn) 與剩下點(diǎn) 之間的邊 的信息素的濃度 計(jì)算出轉(zhuǎn)移概率 。對于其他的點(diǎn)，令概率為零 。然后依據(jù)隨機(jī)生成的概率來選擇一個(gè)點(diǎn)作為下一個(gè)點(diǎn)。步驟六：重復(fù)步驟四直到螞蟻?zhàn)哌^所有的點(diǎn)，否則轉(zhuǎn)入下一只螞蟻，進(jìn)入步驟三步驟七：讓當(dāng)前所有邊上的信息素濃度進(jìn)行衰減。步驟八：每一只螞蟻行走時(shí)分泌信息素，它會(huì)增加它所經(jīng)過的每一條邊的信息素濃度步驟九: 進(jìn)入下一階段的迭代運(yùn)算，若迭代次數(shù)達(dá)到最大迭代次數(shù)則算法結(jié)束。模型求解蟻群算法流程圖兩種目標(biāo)下的求解結(jié)果分析時(shí)間最優(yōu)下刀具轉(zhuǎn)換方案的優(yōu)化 由上面分析，我們以總時(shí)間最優(yōu)為目標(biāo)，與此同時(shí)可以發(fā)現(xiàn)，鉆頭更換刀具的時(shí)間(252秒)已經(jīng)大大超過了82秒的鉆頭

8、行徑的時(shí)間，所以，為了進(jìn)一步的減少時(shí)間，我們必須減少刀具轉(zhuǎn)換的次數(shù)。 由于不同孔型對刀具加工的次序要求，通過我們技術(shù)性處理之后的模型也僅僅是類似于TSP問題，次序的要求使得個(gè)別的點(diǎn)點(diǎn)之間的連接是有向的，于是模型并非TSP問題，而是類似。所以從不同的起始位置打孔，各自最終求解出來，對模型的結(jié)果是有影響的，所以需要進(jìn)一步優(yōu)化。 再者，從蟻群算法的角度，對于非線性問題，初始值的改變對最終的結(jié)果也將帶來影響。時(shí)間最優(yōu)下刀具轉(zhuǎn)換方案的優(yōu)化刀具轉(zhuǎn)換方案的約束條件：1）首先鉆頭上的刀具只能向鄰近位轉(zhuǎn)移2）其次我們有8種刀具的加工需求，所以 每一種刀具類型都必須鉆動(dòng)過刀具轉(zhuǎn)換方案的約束條件3）另外我們還需要保

9、證加工次序。由于我們把孔按所需刀具類型分成了10種（包括a,b,d,e,f,g；c與f則分為優(yōu)先打的c0 與f0和需要最后打的c1與f1）即我們必須保證如下次序： 打c1型前必須打a ,f0 ,e 打f1 型前必須打c0 g 打g型前必須打 d孔型ABCDEFGHIJ所需刀具aba, cd, e*c, fg, h*d, g, fhe, cf, c分群示意圖分群示意圖分群示意圖分群示意圖分群示意圖算法描述我們采用了遍歷法來尋找合適的刀具轉(zhuǎn)換方案步驟一：初始化一條鏈 L 如 鏈 的長度 為8步驟二：依次選取鏈 中的點(diǎn) i作為起點(diǎn)，步驟三：復(fù)位，給鉆頭1的轉(zhuǎn)換方案末尾添加一個(gè) j（ 為鉆頭2轉(zhuǎn)換方案

10、的起點(diǎn)），并也在鉆頭1的轉(zhuǎn)換方案末尾添加一個(gè) i。步驟四：檢驗(yàn)上述方案是否符合打孔次序的要求，并回到步驟二。如果將 中的點(diǎn)選完仍然找不到可行解，則轉(zhuǎn)到步驟五。步驟五: 加邊，依次在鏈 上按序取三點(diǎn) I j k ，并在k 與j之間插入 I j 或k j 即i j I j k 或 I j k j k 作為新的鏈 ，如：此時(shí)鏈 的長度 為10，轉(zhuǎn)入步驟二。若 選遍了 中所有的點(diǎn)，算法結(jié)束算法描述求解結(jié)果我們最終得到了2個(gè)最優(yōu)解：方案一: 方案二： 進(jìn)一步我們用上面求得的刀具轉(zhuǎn)化方案得到了最優(yōu)路線最優(yōu)路線的確定 首先我們根據(jù)每個(gè)孔所需要的刀具的類型和對加工次序的要求，我們把所有的孔分成了10種群：a

11、b c0 c1 d e f0 f1 g hc0/f0為要求優(yōu)先打的c型/f型孔 c1/f1為要求稍后打的c1型/f1型孔 其次我們根據(jù)刀具的轉(zhuǎn)換方案，把加工這十種孔的任務(wù)分配到了鉆頭每一個(gè)階段。 再其次我們用了蟻群算法求出了10種孔群的最佳打孔線路。（算法思路同第一問，在此就不再贅述） 最后我們用程序根據(jù)刀具的轉(zhuǎn)換方案尋找到了一個(gè)最佳方案把這幾個(gè)階段連接起來。算法描述我們使用了等步長搜索法來解決這個(gè)問題：步驟一：由蟻群算法求出最小Hamilton圈（通過圖中的邊能經(jīng)過途中的頂點(diǎn)。 邊可以重復(fù)走，但點(diǎn)只能經(jīng)過一次。步驟二：依次從c1群選擇一個(gè)點(diǎn)作為起點(diǎn)，同時(shí)它在Hamilton圈上的鄰點(diǎn)為終點(diǎn)。

12、若選遍所有點(diǎn)，則算法結(jié)束。步驟三：依次從c0群選擇選擇一個(gè)點(diǎn)作為起點(diǎn)，同時(shí)它在Hamilton圈上的鄰點(diǎn)為終點(diǎn)。若選遍所有點(diǎn)，則轉(zhuǎn)到步驟二。步驟四：連接c1的終點(diǎn)與c0的起點(diǎn)，并以此連接這兩個(gè)Hamilton圈。去掉連接c1的起點(diǎn)與終點(diǎn)的那條邊與連接c0的起點(diǎn)與終點(diǎn)的那條邊。步驟五：且計(jì)算這條依次從c1起點(diǎn)連接到c0終點(diǎn)的邊的長度，若這個(gè)長度短于當(dāng)前最優(yōu)解，則記錄。轉(zhuǎn)到步驟三。算法描述上一步中我們就得到的整個(gè)過程的起點(diǎn)與終點(diǎn)，我們用下面的算法把中間各個(gè)階段的任務(wù)連接起來。步驟一：由蟻群算法求出中間各個(gè)階段的最小Hamilton圈，并刪掉最長邊，由此得一條弧。步驟二：分別以每一條弧的兩個(gè)端點(diǎn)中的

13、任意一個(gè)作為起點(diǎn)，另一個(gè)作為終點(diǎn)。并且按加工順序連接所有的弧。得到一個(gè)新的圈。步驟三：計(jì)算這個(gè)圈的長度，若小于最優(yōu)解就記錄下來，找遍了步驟二中的所有情況則算法結(jié)束。模型結(jié)果最優(yōu)刀具轉(zhuǎn)換方案為：方案二： 單鉆頭行進(jìn)路線雙鉆頭打孔機(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) 。最后我們對混合圖 的每一條邊進(jìn)行相應(yīng)的賦權(quán)就

14、得到了賦權(quán)連通圖 G(E,V)。其中，邊權(quán)對應(yīng)邊的相應(yīng)的費(fèi)用（或時(shí)間）。權(quán)數(shù)的確定兩孔之間的距離為：兩孔之間由于刀具轉(zhuǎn)換而產(chǎn)生的時(shí)間為: （ 表示第 個(gè)孔所需的刀具類型對應(yīng)的次序）在時(shí)間最優(yōu)的情況下，我們的目標(biāo)是使印刷單個(gè)電路板的時(shí)間盡可能的小。即每條邊的權(quán)數(shù)為：雙鉆頭打孔機(jī)模型 由于鉆頭數(shù)由一個(gè)增加到了兩個(gè)，故問題從類似于TSP問題變成了一個(gè)類似于MTSP（多旅行商）的問題。首先我們需要把點(diǎn)集 V分成兩個(gè)部分V1 與V2 分別交由兩個(gè)鉆頭去打。對應(yīng)點(diǎn)集然 與 我們分別構(gòu)造出對應(yīng)的邊集 G1與G2 。后分別求出連接這兩部分點(diǎn)集的最小哈密頓圈 與 。其中 ， 為 中的頂點(diǎn)數(shù)其中 ， 為 中的頂點(diǎn)

15、數(shù)雙鉆頭打孔機(jī)模型 由于最終完成一個(gè)印刷電路板的總時(shí)間即為兩個(gè)鉆頭中的用時(shí)較大的時(shí)間，我們的目標(biāo)就是使兩個(gè)鉆頭中的用時(shí)較大的時(shí)間盡可能地小。所以最后我們需要平衡兩個(gè)鉆頭的工作量，要使得他們的工作量盡量平均化：鉆頭一工作總時(shí)間 其中鉆頭二工作總時(shí)間 其中與此同時(shí)我們還需要滿足雙鉆頭的最小合作間距的要求。若兩個(gè)鉆頭在任意時(shí)刻的位置為 與 ，那么有：最終總時(shí)間為 我們的目標(biāo)是 即模型求解雙鉆頭情況下的最優(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ù)后

16、，才回去轉(zhuǎn)換刀具。第二，我們只有8種刀具，在孔數(shù)量龐大的情況下，大多數(shù)情況下所有的刀具都會(huì)被使用，以時(shí)間最優(yōu)為目標(biāo)的情況下，在以所需刀具為分類依據(jù)的孔群內(nèi)鉆頭的行進(jìn)時(shí)間是一定的，為了減少總時(shí)間，刀具更換應(yīng)該是依序逐個(gè)轉(zhuǎn)換的。示意如右圖：雙鉆頭情況下的最優(yōu)刀具轉(zhuǎn)換方案此外，我們要求兩個(gè)鉆頭完成作業(yè)后，可以相互回到對方的初始位置與初始狀態(tài)，以此保證連續(xù)作業(yè)與盡可少的刀具轉(zhuǎn)換。示意圖如下： 整個(gè)過程鉆頭1：由a轉(zhuǎn)到e 整個(gè)過程鉆頭2：由e轉(zhuǎn)到a雙鉆頭情況下的最優(yōu)刀具轉(zhuǎn)換方案另外我們還需要保證加工次序。由于我們把孔按所需刀具類型分成了10種（包括a,b,d,e,f,g；c與f則分為優(yōu)先打的c0 與f0

17、和需要最后打的c1與f1）即我們必須保證如下次序：1）打c1型前必須打a ,f0 ,e2）打f1 型前必須打c0 g3）打g型前必須打 d算法描述我們采用了遍歷法來尋找合適的刀具轉(zhuǎn)換方案步驟一：初始化一條鏈 L 如 鏈的長度為8步驟二：依次選取鏈中的點(diǎn) i作為起點(diǎn)，步驟三：復(fù)位，給鉆頭1的轉(zhuǎn)換方案末尾添加一個(gè) j（ 為鉆頭2轉(zhuǎn)換方案的起點(diǎn)），并也在鉆頭1的轉(zhuǎn)換方案末尾添加一個(gè) i。步驟四：檢驗(yàn)上述方案是否符合打孔次序的要求，并回到步驟二。如果將鏈中的點(diǎn)選完仍然找不到可行解，則轉(zhuǎn)到步驟五。步驟五: 加邊，依次在鏈 上按序取三點(diǎn) I j k ，并在k 與j之間插入 I j 或k j 即i j I

18、j k 或 I j k j k 作為新的鏈。轉(zhuǎn)入步驟二，若 選遍了 中所有的點(diǎn)，算法結(jié)束平衡任務(wù)量 最終完成一個(gè)印刷電路板的總時(shí)間即為兩個(gè)鉆頭中的用時(shí)較大的時(shí)間，我們的目標(biāo)就是使兩個(gè)鉆頭中的用時(shí)較大的時(shí)間盡可能地小。所以我們要平衡兩個(gè)鉆頭的任務(wù)量。步驟一：我們首先使用了蟻群算法求出了10種孔群的最佳打孔線路，（算法思路同第一問，在此就不再贅述）并將每種孔群的作業(yè)時(shí)間作為任務(wù)量。步驟二：從可行解里面依次選取一個(gè)方案，然后根據(jù)兩鉆頭的刀具轉(zhuǎn)換方案將這打10種孔群的任務(wù)分配到對應(yīng)的鉆頭上。若選完了所有的方案則轉(zhuǎn)步驟四步驟三：計(jì)算出兩個(gè)鉆頭的總作業(yè)時(shí)間，并且以作業(yè)時(shí)間長的那個(gè)鉆頭的時(shí)間作為這個(gè)方案的總

19、作業(yè)時(shí)間。轉(zhuǎn)步驟二步驟四：選取總作業(yè)時(shí)間最少的那個(gè)方案作為最終的刀具轉(zhuǎn)換方案。求解結(jié)果最優(yōu)的刀具轉(zhuǎn)換方案：雙鉆頭的合作作業(yè)的間距的調(diào)整策略 為避免鉆頭間的觸碰和干擾，在過孔加工的任何時(shí)刻必須保持兩鉆頭間距不小于3cm（稱為兩鉆頭合作間距）。上述不考慮合作間距的基礎(chǔ)模型的結(jié)果已經(jīng)將兩個(gè)鉆頭的任務(wù)分配完畢，作業(yè)路線也已經(jīng)確定，考慮間距后我們使一個(gè)鉆頭作為優(yōu)先鉆頭，另一個(gè)鉆頭采取一定的策略來保證間距。 對于間距的處理采用等待與規(guī)避兩種策略。以下以鉆頭1作為優(yōu)先鉆頭為例進(jìn)行說明。等待策略 如果鉆頭1下一個(gè)的目標(biāo)位置的以合作間距d為半徑的圓內(nèi)存在鉆頭2，那么鉆頭1將原地等待，直到目標(biāo)的判斷區(qū)域內(nèi)沒有鉆頭

20、2，再行進(jìn)到目標(biāo)位置。規(guī)避策略 如果判斷到鉆頭2與鉆頭1距離為合作間距d時(shí)，鉆頭2就沿著兩者連線相應(yīng)的后退，直到判斷距離大于d時(shí)，繼續(xù)前往目標(biāo)點(diǎn)。算法描述采用等時(shí)間步長法來計(jì)算總的作業(yè)時(shí)間，時(shí)間步長為0.001秒步驟一：根據(jù)鉆頭1（優(yōu)先鉆頭）的作業(yè)路線記錄鉆頭1的每個(gè)時(shí)間所處的位置。步驟二：初始化時(shí)間T，讓鉆頭2開始按所給的任務(wù)進(jìn)行作業(yè)，并將路線上第二個(gè)點(diǎn)作為目標(biāo)點(diǎn)，轉(zhuǎn)入步驟三步驟三：若兩鉆頭的距離d小于最小合作間距d0，則鉆頭二進(jìn)行規(guī)避，向兩鉆頭連線的反方向后退一步，并轉(zhuǎn)入步驟六；反之則轉(zhuǎn)入步驟四。步驟四：若鉆頭2的目標(biāo)點(diǎn)與當(dāng)前鉆頭1的距離小于最小合作間距d0，則鉆頭2原地等待，轉(zhuǎn)入步驟六；

21、反之則轉(zhuǎn)入步驟五。步驟五：若鉆頭2與目標(biāo)點(diǎn)的距離大于鉆頭二每步移動(dòng)的距離，則鉆頭2向目標(biāo)點(diǎn)移動(dòng)一步。反之即認(rèn)為鉆頭二到達(dá)目標(biāo)點(diǎn)，并且將路線上的下一的點(diǎn)作為目標(biāo)點(diǎn)；如取遍了所有的點(diǎn)，算法結(jié)束。步驟六：時(shí)間走過一個(gè)步長，開始下一步轉(zhuǎn)入步驟三。算法描述 前面模型的復(fù)位點(diǎn)默認(rèn)以標(biāo)號最前的點(diǎn)作為復(fù)位點(diǎn)，而事實(shí)上最優(yōu)的情況下復(fù)位點(diǎn)應(yīng)該是所有滿足約束條件的點(diǎn)中使總時(shí)間最短的點(diǎn)。我們用了等步長搜索法來求最佳的起點(diǎn)。步驟一：得到當(dāng)前階段鉆頭1，鉆頭2結(jié)束刀具轉(zhuǎn)換開始工作的時(shí)間。步驟二：依次從當(dāng)前鉆頭1所加工的孔群中選取一個(gè)點(diǎn)作為鉆頭1的起始點(diǎn)，轉(zhuǎn)入步驟三；若取完所有的點(diǎn)，則轉(zhuǎn)入步驟五。步驟三：依次從當(dāng)前鉆頭1所

22、加工的孔群中選取一個(gè)點(diǎn)作為鉆頭2的起始點(diǎn)，轉(zhuǎn)入步驟四；若取完所有的點(diǎn)，則轉(zhuǎn)入步驟二。步驟四：將兩鉆頭開始工作的時(shí)間與開始作業(yè)的起始點(diǎn)帶入程序（算法與上一問相同，故不再贅述）計(jì)算出最終的作業(yè)時(shí)間，轉(zhuǎn)入步驟三。步驟五：比較結(jié)果得到最優(yōu)解，算法結(jié)束。求解結(jié)果雙鉆頭任務(wù)均衡化的再優(yōu)化 初始模型求出了使兩個(gè)鉆頭任務(wù)盡可能接近的組合，事實(shí)上我們可以對他進(jìn)一步優(yōu)化，原來的方案為： 鉆頭一： 鉆頭二：雙鉆頭任務(wù)均衡化的再優(yōu)化鉆頭1作業(yè)刀具abahgf鉆頭1作業(yè)時(shí)間0-17.335.3-48.73566.735-66.73584.735-87.64105.64-108.78126.78-132.306鉆頭2作業(yè)

23、刀具fedcba鉆頭2作業(yè)時(shí)間0-3.91521.915-28.9846.98-53.85571.855-84.05102.05-102.05120.05-120.05 由于之前我們將打a ,b兩孔群的任務(wù)都分配給了鉆頭1，故而鉆頭2在后面其實(shí)是不用打a b兩種孔的。但實(shí)際上在我們給出的最優(yōu)打孔方案中鉆頭1打了132.3秒而鉆頭2則僅打了120秒，這也就是說鉆頭2有12秒的時(shí)間沒有任務(wù)，如果我們把鉆頭1的任務(wù)分配給鉆頭2一部分就能進(jìn)一步降低總的作業(yè)時(shí)間。雙鉆頭任務(wù)均衡化的再優(yōu)化 我們分析發(fā)現(xiàn)，由于b型孔對于打孔的優(yōu)先順序是沒有要求的，所以如果我們改變打b型孔的時(shí)間是不會(huì)影響到其他孔的加工的。故

24、我們選擇b型孔作為任務(wù)分配的對象。為此我們便用一條水平線L將b型孔分成了上下兩個(gè)部分（分法見下圖），把上面的那一部分分配給鉆頭2，下面的分配給鉆頭1。 任務(wù)分配完后我們再次計(jì)算鉆頭1，鉆頭2工作的總時(shí)間，并根據(jù)總時(shí)間的多少反饋調(diào)節(jié)水平線L的位置，直到兩個(gè)鉆頭的總的工作時(shí)間最小。雙鉆頭任務(wù)均衡化的再優(yōu)化算法描述我們利用了斐波那契那法對水平線L的位置進(jìn)行調(diào)整步驟一：選取初始數(shù)據(jù)，確定單峰區(qū)間 ,給出搜索精度 以及搜索次數(shù) 。步驟二 ， ， 帶入子程序計(jì)算最初的兩個(gè)搜索點(diǎn)。然后計(jì)算： 為斐波那契那數(shù)列 步驟三 當(dāng)?shù)螖?shù) 時(shí)將 ， 分別代入子程序算出總的工作時(shí)間 ， 。 如果 則令：雙鉆頭任務(wù)均衡化

25、的再優(yōu)化 反之則；步驟四當(dāng)?shù)螖?shù) 時(shí)算法結(jié)束。關(guān)于計(jì)算工作時(shí)間的子函數(shù) 步驟一根據(jù)直線 ： 把b型孔分成上下兩個(gè)部分，并用蟻群算法計(jì)算出加工這兩部分孔的最短環(huán)路。進(jìn)一步去掉這兩個(gè)環(huán)的最長邊，確定起點(diǎn)，終點(diǎn)。步驟二從第二階段開始計(jì)算出兩個(gè)鉆頭的作業(yè)時(shí)間，令階段數(shù)為二，轉(zhuǎn)入下一步步驟三利用前面的程序不斷調(diào)節(jié)每個(gè)階段兩個(gè)鉆頭開始作業(yè)的起始點(diǎn)來尋找最優(yōu)的作業(yè)線路步驟四重復(fù)步驟三，直到加工完畢，計(jì)算出總時(shí)間，并以兩個(gè)鉆頭工作時(shí)間較長的那個(gè)作為程序的返回值 ，算法結(jié)束模型結(jié)果當(dāng)直線 為 時(shí)，總的工作時(shí)間達(dá)到最小值具體刀具轉(zhuǎn)換方案如下：鉆頭1作業(yè)刀具abahgf鉆頭1作業(yè)時(shí)間段 單位（秒）0-17.335

26、.3-43.50561.505-61.50579.505-82.41100.41-103.55121.55-127.076鉆頭2作業(yè)刀具fedcba鉆頭2作業(yè)時(shí)間段 單位（秒）0-3.91521.915-28.9846.9-53.85571.855-86.185104.185-108.73126.73-126.73模型結(jié)果單鉆頭方案與雙鉆頭方案對比 由上可知雙鉆頭顯著的降低了總作業(yè)時(shí)間（大約只有單鉆頭的50%），但是費(fèi)用卻有略微的增加（約6.2%）。打孔機(jī)的兩鉆頭合作間距對作業(yè)路線和生產(chǎn)效能產(chǎn)生的影響合作間距總作業(yè)時(shí)間等待時(shí)間規(guī)避時(shí)間0124.32 0.00 0.00 0.2124.33 0.01 0.02 0.4124.39 0.10 0.11 0.6124.54 0.16 0.32 0.8124.66 0.38 0.39 1124.72 0.69 0.62 1.2124.75 0.73 0.96 1.4124.85 1.00 1.18 1.6125.02 1.28 1.19 1.8125.45 1.57 1.45