【正文】 考慮到作業(yè)的 費用 主要包括刀具的轉換的時間 費用 和刀具行進的 費用 。這說明改變雙鉆頭加工的合作間距可以使雙鉆頭加工的生產(chǎn)效能得到很好的改善。 6 4 2 0 2 4 6x 1 042 . 22 . 42 . 62 . 833 . 23 . 4x 1 05中間圓域內(nèi)行進路線圖16 圖 由圖 8 可知， 與傳統(tǒng) 單鉆頭相比 ， 無論在行進時間還是換刀費用上，雙鉆頭作業(yè)的方式都有了明顯的提高。右半?yún)^(qū)域的加工回路圖如下所示。 由于兩個鉆頭工作是相互獨立的，且合作間距已知不小于 3cm。y=270000 mil/100和以（ x,y） =（ 0,270000）為圓心，以 3/sqrt(2)cm為半徑 劃分出來的中心圓域，可以再不影響求解雙鉆頭加工的最優(yōu)方案的前提下很好地控制 題目中所給的限制條件，即 在過孔加工的任何時刻必須保持兩鉆頭間距不小于 3cm（稱為兩鉆頭合作間距） 。 11 圖 為了使所劃分的區(qū)域模型，在滿足限制條件的前提下使作業(yè)方案最優(yōu)，要盡可能得減小中間控制區(qū)域的大小。對此，首先嘗試劃分如圖 6 所示的區(qū)域模型。 首先 ， 為控制使雙鉆頭加工的路徑和時間 同時得到 最優(yōu)， 我們將由問題一所述方法得到的， 印刷板上所有的孔 即 ??~??孔的位置信息和所需刀具的各項信息 進行了分析及統(tǒng)計。若循環(huán)的總次數(shù)沒有達到最大的循環(huán)次數(shù)，則將繼續(xù)轉到第二步執(zhí)行，若滿足結束條件循環(huán)將結束，同時輸出結果數(shù)據(jù)。 單鉆頭加工完所有類型的孔，為使加工費用最優(yōu)化，我們需要得到刀具轉換的最優(yōu)順序，從而得到刀具轉換的最優(yōu)費用。 將各類型孔 的所有待加工孔 分別按照上述規(guī)則標號后全部列入下表 ， 置于矩陣 ??左側 ，表示正在加工的孔 ??；然后 對該序列 進行轉置，置于矩陣 ??上側 ，表示下一個進行加工的孔 ??。 TSP 問題 的 等效賦權圖 旅行商 問題 旅行商問題（ 即 TSP 問題 ）也稱最小哈密頓回路問題。 費用 使用 01 規(guī)劃模型判定從起始孔 ??孔到下一個孔 ??孔這條路徑是否在所求的最短路線上，若在路線上則 ??????取 1，否則取 0。 ?? = { |???? ?????| , |???? ?????| ≤ 4 8 ?|???? ?????| , |???? ? ????| 4 (2) 10 種孔型的類 型中大部分是由多個刀具進行加工的，題目中說明不要求在加工完一個孔 后才可以繼續(xù)加工下一個孔 。建立模型分別對刀具轉換費用和鉆頭行進費用 進行求解，再建立優(yōu)化模型求得 最優(yōu)作業(yè)線路下的最優(yōu)費用 。 （ 3） 假定針對不同孔型加工作業(yè)時，刀具的轉換時間相同 。轉換的 同時的增添了一個約束，即在過孔加工的任何時刻必須保持兩鉆頭間距不小于 3cm（稱為兩鉆頭合作間距）。 考慮到總的作業(yè) 費用 主要包括刀具的轉換 費用 和鉆頭的行進 費用 ，我們需要分別建立模型對刀具的轉換 費用 ??1和鉆頭的行進 費用 ??2進行計算。 （ i）針對附件 1 的數(shù)據(jù)，給出雙鉆頭作業(yè)時的最優(yōu)作業(yè)線路、行進時間和作業(yè) 費用 ，并與傳統(tǒng)單鉆頭打孔機進行比較，其生產(chǎn)效能提高多少？ （ ii）研究打孔機的兩鉆頭合作間距對作業(yè)路線和生產(chǎn)效能產(chǎn)生的影響。刀具在行進過程中可以同時進行刀具轉換，但相應費用不減。為了 研究打孔機的兩鉆頭合作間距對作業(yè)路線和生產(chǎn)效能產(chǎn)生的影響。 應 用蟻群算法對模型進行編譯 ， 得到單鉆頭作業(yè) 的最優(yōu) 加工線路 ， 行進時間為 ， 作業(yè) 費用 為 元 。摘 要 過孔是印刷線路板的重要組成部分之一， 過 孔的 加工 費用通常占制板費用的30%到 40%。 對于問題二，從單鉆頭改為了雙鉆頭作業(yè)， 屬于 多旅行商問題（ MTSP）。我們改變中心圓域的半徑為 √2cm， 得到該限制條件下的鉆頭行進時間為 ，加工總費用為 元。 不同的刀具加工不同的孔型。 二 .問題的分析 本問題旨在提高某類打孔機的生產(chǎn)效能。 其中行進 費用 ??2的計算可以用解決 TSP 問題的方法，借助蟻群算法進行近似優(yōu)化計算?？紤]到這一約束 ， 應該建立模型在能夠很好的解決合作間距問題的基礎上使雙鉆頭作業(yè)路線最優(yōu)，得到最優(yōu)的行進時間和作業(yè)費用。 （ 4） 在計算兩孔之間距離時 ， 假設打孔機的鉆頭為一質點 。 4 圖 作業(yè)費用劃分圖 刀具轉換 費用 將 刀具 ??,??,????依次標為 1,2,3?8。 只要 對于須用兩種或兩種以上刀具加工的過孔，只要保證所需刀具加工次序正確即可。 ??????’ = {0 , 表示 (??,??)不在得到的最優(yōu)路徑上1 , 表示 (??,??)不在得到的最優(yōu)路徑上 (5) 為使鉆頭的行進費用最少，需要找到每個刀具打完符合要求的所有孔的最佳行進路線，從而得到單個刀具加工的最少行進費用，加和后得到總的單鉆頭工作的最少行進費用。假設 ??(??,??,??)表示帶權連通圖 ??，其中 ??為圖 G的結點集， ??為 圖 ??的邊集， ??表示 圖 G的邊上權集合。 運用等效賦權矩陣將所有點之間的加工費用進行羅列，并進行全局搜索，尋找最優(yōu)路線。 式（ 9） 為單鉆頭加工最優(yōu)路線時的刀具轉換順序 。 由圖 2 中藍色折線所示，通過不斷的增加循環(huán)次數(shù)，可以發(fā)現(xiàn)所走的路徑的最小值有減小的趨勢。 并引用 matlab 軟 件繪制了如圖（ 3）所示的所有孔的分布圖。劃分時，控制使左右兩個大區(qū)域內(nèi)的單孔數(shù)目近似相等，中間區(qū)域的寬度控制為 3cm。 經(jīng)過實驗、分析得到當把中間區(qū)域建立為一個以 x=0。 12 圖 區(qū)域模型 將兩個鉆頭同時開始加工，從中心圓域的圓周上的點為起點。因此在解決雙鉆頭最優(yōu)作業(yè)方案時基礎上再加上另一個鉆頭作業(yè)所需的各種費用并增加約束條件，保證合作間距在要求范圍之內(nèi)。 圖 3 . 5 3 2 . 5 2 1 . 5 1 0 . 5 0x 1 0510123x 1 05 3 . 5 3 2 . 5 2 1 . 5 1 0 . 5 0x 1 05246810x 1 05左半?yún)^(qū)域行進路線14 圖 其中上方的圖為 ????????21的加工回路圖，下方的圖為 ????????22的加工回路圖，在鉆頭二 加工完 ????????21后直接移到 ????????22進行加工。 為了更加明確的將兩種加工方式進行比較我們對生產(chǎn)效能各方面的提高分別進行了計算。 五 .模型的評價及改進 模型的核心思路是在第一問建立模型的基礎上，解決第二問對于雙鉆頭的求解方法，將最終解決了調(diào)高打孔機工作效能的問題。通過對單位時間內(nèi)刀具的轉換 費用 ????和行進 費用 ????進行計算和對比： ???? = /s ???? = /s，故在求解最佳路線時優(yōu)先考慮刀具的轉換方案，在此基礎上選擇更為優(yōu)良的鉆頭行進線路。 對于模型一，考慮到構建的以 TSP 問題為基礎的等效賦權圖在編程計算時由于軟件、硬件、及實際編譯操作技能的限制， 利用蟻群算法很難得到全局性的最優(yōu)結果，所以我們提出了另一種方法。 圖 由圖 9 可知，當雙鉆頭加工時縮小合作間距可以有效的改善作業(yè)的生產(chǎn)效能，即改進后的雙鉆頭加工相較于之前的雙鉆頭加工而言，無論在加工費用還是在行進時間上都減小了。 表 區(qū)域 Area11 Area12 Area21 Area22 中心 圓域 合 計