摘要本文就打孔機生產效能的提高，運用模擬退火演算法求出最優路徑，用列舉法找出最優換刀方案，為將問題簡化採取分區域的方法。
首先通過列舉法列出道具換刀方案，找出最優換刀方案，即d-c-b-a-h-g-f-e-c，共轉換9刀。用模擬退火法求出每個道具行進的最短路徑為mil，鑽頭的行進成本為所有刀具的行進成本與刀具轉換成本之和為元，行進時間為所有道具的行進時間與刀具轉換時間之和為s。
其次將整個作業區間分成四個區域，先讓兩個刀具分別在區域
一、四的對角線作業，完畢後轉向區域
三、二。轉換刀具的方案不變，利用模擬退火法分別算出每個區域鑽頭的作業線路和最短路徑，求出每個區域的行進成本和行進時間，利用matlab求和算出總行進成本和總行進時間，並與問題一作比較。
關鍵字： 列舉法模擬退火法 matlab 分區域法
一問題重述
過孔是印刷線路板的重要組成部分之一，過孔的加工費用通常佔製板費用的30%到40%，打孔機主要用於在製造印刷線路板流程中的打孔作業。本問題旨在提高某類打孔機的生產效能。
打孔機的生產效能主要取決於以下幾方面：（1）單個過孔的鑽孔作業時間，這是由生產工藝決定，為了簡化問題，這裡假定對於同一孔型鑽孔作業時間都是相同的；（2）打孔機在加工作業時，鑽頭的行進時間；（3）針對不同孔型加工作業時，刀具的轉換時間。目前，實際採用的打孔機普遍是單鑽頭作業，即乙個鑽頭進行打孔。
現有某種鑽頭，上面裝有8種刀具a，b，c，… , h，依次排列呈圓環狀，如圖1所示。
圖1 某種鑽頭上8種刀具的分布情況
而且8種刀具的順序固定，不能調換。在加工作業時，一種刀具使用完畢後，可以轉換使用另一種刀具。相鄰兩刀具的轉換時間是18 s，例如，由刀具a轉換到刀具b所用的時間是18s，其他情況以此類推。
作業時，可以採用順時針旋轉的方式轉換刀具，例如，從刀具a轉換到刀具b；也可以採用逆時針的方式轉換刀具，例如，從刀具a轉換到刀具h。將任一刀具轉換至其它刀具處，所需時間是相應轉換時間的累加，例如，從刀具a轉換到刀具c，所需的時間是36s（採用順時針方式）。為了簡化問題，假定鑽頭的行進速度是相同的，為180 mm/s，行進成本為0.
06元/mm，刀具轉換的時間成本為7元/min。刀具在行進過程中可以同時進行刀具轉換，但相應費用不減。
不同的刀具加工不同的孔型，有的孔型只需一種刀具來完成，如孔型a只用到刀具a。有的孔型需要多種刀具及規定的加工次序來完成，如孔型c需要刀具a和刀具c，且加工次序為a，c。表1列出了10種孔型所需加工刀具及加工次序（標*者表示該孔型對刀具加工次序沒有限制）。
表1 10種孔型所需加工刀具及加工次序
一塊線路板上的過孔全部加工完成後，再製作另一線路板。但在同一線路板上的過孔不要求加工完畢乙個孔，再加工另乙個孔，即對於須用兩種或兩種以上刀具加工的過孔，只要保證所需刀具加工次序正確即可。
請建立相應的數學模型，並完成以下問題：
1）附件1提供了某塊印刷線路板過孔中心座標的資料，單位是密爾（mil）（也稱為毫英吋，1 inch=1000 mil），請給出單鑽頭作業的最優作業線路（包括刀具轉換方案）、行進時間和作業成本。
2）為提高打孔機效能，現在設計一種雙鑽頭的打孔機（每個鑽頭的形狀與單鑽頭相同），兩鑽頭可以同時作業，且作業是獨立的，即可以兩個鑽頭同時進行打孔，也可以乙個鑽頭打孔，另乙個鑽頭行進或轉換刀具。為避免鑽頭間的觸碰和干擾，在過孔加工的任何時刻必須保持兩鑽頭間距不小於3cm（稱為兩鑽頭合作間距）。為使問題簡化，可以將鑽頭看作質點。
二問題的分析
問題一，用matlab畫出個孔點分布圖，初步分析孔型。通過列舉法列出道具的轉換方案，找出最優轉換方案為d-c-b-a-h-g-f-i-e-c，總共轉換9次。由於每一中孔只需要它所需要的刀打一次，則每乙個刀具所產生最小行進距離就可以等效為旅行商的問題，由於單個過孔的鑽孔作業時間，這是由生產工藝決定，為了簡化問題，計算時忽略單個過孔的作業時間。
用模擬退火法求解最短距離，通過最短距離算出該部分行進成本和行進時間，即鑽頭總行進成本為最短距離行進成本加上鑽頭轉換成本；同理，鑽頭總行進時間為最短距離行進時間加上鑽頭轉換所花時間。
問題二，考慮到雙鑽頭打孔，避免鑽頭間的觸碰和干擾，在過孔加工的任何時刻必須保持兩鑽頭間距不小於3cm。根據線路板上所有點的散點圖，將整個線路板分成四個區域，兩個鑽頭先分別在
一、四區域內同時作業，結束後再分別在
三、二區域內工作。利用問題一中的換刀方案在各個區域打孔。利用模擬退火法在每個局域找出鑽頭的最短行進路線，反覆計算得出各個區域中打孔的成本和時間，將四個區域的成本和時間分別彙總，計算出兩個鑽頭合作間距作業所需的總成本與總時間，與單個鑽頭打孔所花成本與時間比較，分析兩鑽頭合作間距對作業路線和生產效能產生的影響。
三問題的假設
1) 假定對於同一孔型鑽孔作業時間都是相同的。
2) 假定鑽頭行進時間都是相同的 。
3) 假定刀具轉換朝轉換所需最低步驟的方式轉換，比如a轉換到g，應該沿a-h-g,總共二步，而不是a-b-c-d-e-f-g，總共六步。
4) 兩鑽頭同時作業時，將鑽頭看著質點。
5) 忽略鑽頭打孔的算花時間。
四符號說明
五模型的建立與求解
5.1 選擇刀具最佳轉換方案
在刀具轉換的序列的選擇上最複雜的就是必須要滿足c，e，g，i，j孔的換刀時順序的要求。分析這幾個點的最短工序如下：
c(a,c): a-b-c； a-h-g-f-e-d-c；
e(c,f):c-d-e-f； c-b-a-h-g-f；
g(d,g,f):d-e-f-g-f； d-c-b-a-h-g-f-e-d-c；
i(e,c):e-d-c； e-f-g-h-a-b-c；
j(f,c):f-g-h-a-b-c； f-e-d-c。
由於選擇刀具最短的轉換方案必須同時滿足上述c，e，g，i，j孔的兩種最短工序的其中的一種。所以設計刀具最短的轉換方案需遵循下面幾項原則：
1) 從g孔的兩種工序先出發，尋找滿足其他點的序列。因為g點所要滿足的條件是最複雜的，需滿足三種刀具的轉換順序，所以滿足了g孔的順序要求同時可能會有一些子串行會滿足其他孔的要求從而減少了工序。若從簡單的序列出發，要想滿足g孔的刀具轉換方式會有點複雜，且會增加不必要的工序，增加轉換成本。
2） 選擇孔的換刀順序時，選擇與已組合的工序重複度高的工序進行組合。
從d-e-f-g-f出發，組合的最佳換刀的方案為：c-d-e-f-g-f-g-h-a-b-c；
從d-c-a-h-g-e-d-c出發，組合的最佳換刀的方案為：d-c-b-a-h-g-f-e-d-c；
比較上述兩種換刀的方案，第一種方案需要換十次刀，第二種換刀方案只要換9次刀，故第二種為最優換刀方案。
根據以上對問題的分析，打孔機的生產效能主要取決於鑽頭的行進時間和刀具轉換時間，加工總費用=刀具行進費用+刀具轉換費用。
建立優化模型為
min5.2 模擬退火的原理
模擬退火演算法源於對固體退火原理。在熱力學和統計物理學的研究中，固體退火首先將固體加溫至溫度充分高，再讓其徐徐冷卻。加溫時，固體內部粒子隨著溫度的公升高而變為無序狀態，內能增大，而徐徐冷卻時粒子漸趨有序，如果降溫速度足夠慢，那麼每個溫度下，粒子都可以達到乙個平衡態，最後在常溫時達到基態，內能減為最小。
另一方面，粒子在某個溫度t時，固體所處的狀態具有一定的隨機性，而這些狀態之間的轉換能否實現由準則metropolis準則決定。
metropolis準則
考慮從狀態i轉換為狀態j， metropolis準則
表示如下：
若e(j)≤e(i),則接受狀態轉移
若e(j)＞e(i)，則按概率p(t)接受狀態轉移。p(t)如下所示：
其中e(j)和e(i)分別表示固體在狀態i和j下的內能，t是溫度，k是波爾茲曼常數。
從metropolis準則可以看到，在某個溫度t下，系統處於某種狀態，由於粒子的運動，系統的狀態就會發生變化，並且導致系統能量的變化。如果變化是朝著減少系統能量的方向進行的，那麼就接受該變化，否則以一定的概率接受這種變化。另一方面，從p(t)的公式可以看到，在同一溫度下，導致能量增加的增加量越大，接受的概率越小；而且隨著溫度t的降低，接受系統能量增大的變化的概率將會越小。
當溫度趨於0時，只剩下那些具有最小能量的狀態，系統處於其他狀態的概率趨於0，所以最終系統將以概率處於具有最小能量的乙個狀態。
用固體退火模擬組合優化問題，將內能e模擬為目標函式值f，溫度t演化成控制引數t，如圖2**所給出的模擬，即得到解組合優化問題的模擬退火演算法，演算法流程圖如圖3所示。
圖2 從物理退火過程到模擬
5.4模型的建立
本題可以轉換為用模擬退火的方法解旅行商的問題。每一種刀具尋找其最佳路徑就可以等效為乙個單獨的旅行商的問題，其能量表示式為，根據刀具轉換順序d-c-b-a-h-g-f-e-c來將所需要這個刀具的孔打掉，比如說用a刀時，同時打a與c型別的孔，就是要求出過a,c所有的點最短距離。由於需要打的孔的數量相對較多，不能想像點的整個分布情況，所以先運用matlab軟體做出散點圖分析點的分布，如圖1
將各種刀具所需座標點集合後匯入到模擬退火演算法**中，計算出近似最短路徑。執行後的結果為（由於資料較多，故以a刀具為例）。
圖1 a刀的近視最短路徑
5．5 模型的求解
運用matlab依次計算出個中刀具所行進的距離，如表1。
表1 各個刀具行進近似最短距離
根據以上執行結果，又知，用matlab計算得：
總路徑：s =mil；
執行路徑的成本為=元；
刀具轉換的成本=18.9元；
總成本元c=+=元；
刀具行進時間=s；
換刀時間為=；
總時間=s。
5.6模型的優化
由於刀具較多，以a刀具為例說明。為了優化模型，將a刀具分兩個區域求解最短距離。結果如圖。
打孔機產品設計分析報告格式
產品設計分析報告 姓名班級學號 報告日期 2011年11月19日 藝術與設計學院 一 產品名稱 辦公用打孔機 二 外形圖 三 結構分析 1 圖 2 產品工作原理 工作原理就是利用壓強的原理，在單位面積上施加巨大的力量從而產生極大的壓強貫穿物體。打孔機就是利用跟這種原理使成疊的紙張穿出整齊地孔眼方便裝...
大型球磨機生產效能低原因分析
1 大型球磨機生產效能的發揮受到隔倉板通料能力束縛 根據托瓦洛夫公式，磨機產量為 q q n0 0.184divin 6.16 5.75 q 當物料特性 磨機填充率及磨機長徑比確定後，以上公式可簡化為 q k 1di3.5 k1 常數 即磨機產量q與磨機直徑di的3.5次方成正比。磨機隔倉板的通料能...
關於種雞生產效能下降問題分析
關於401品種種雞生產效能下降問題的 處理意見 集團公司所屬各養雞公司 自2007年以來，集團公司飼養的401品種種雞生產效能出現明顯下滑，主要表現為產蛋高峰後出現規律性的產蛋率 入孵率 受精率持續下降。為盡快解決該問題，集團生產技術部組織了專題調查並召開了研討會，就造成這種問題的主要原因 應對措施...