打孔機生產效能提高的優化方案匯報人扈詩揚一、問題重述打孔是印刷線路板的重要組成部分之一，打孔的加工費用通常占制板費用的30%到40%，打孔機主要用于在制造印刷線路板流程中的打孔作業.因此我們要研究的問題旨在提高某類打孔機的生產效能.打孔機的生產效能主要取決于三個方面：即單個過孔的鉆孔作業時間和鉆頭的行走時間以及刀具的轉換時間.現有某種鉆頭，上面裝有8種刀具a，b，c，…,h，依次排列呈圓環狀，如右圖所示.某種鉆頭上8種刀具的分布情況并且8種刀具的順序固定，不能調換.鉆孔在加工作業時，一種刀具使用完畢后，可以轉換使用另一種刀具.相鄰兩刀具的轉換時間是18s，作業時，可以采用順時針旋轉的方式轉換刀具，也可以采用逆時針的方式轉換刀具.將任一刀具轉換至其它刀具處，所需時間是相應轉換時間的累加，例如，從刀具a轉換到刀具c，所需的時間是36s（采用順時針方式）.為了簡化問題，假定鉆頭的行走速度是相同的，為180mm/s，行走成本為0.06元/mm，刀具轉換的時間成本為7元/min.刀具在行走過程中可以同時進行刀具轉換，但相應費用不減.不同的刀具加工不同的孔型，有的孔型只需一種刀具來完成，如孔型A只用到刀具a.有的孔型需要多種刀具及規定的加工次序來完成，如孔型C需要刀具a和刀具c，且加工次序為a，c.下表列出了10種孔型所需加工刀具及加工次序（標*者表示該孔型對刀具加工次序沒有限制）.我們要建立的數學模型需要完成以下問題：（1）附件1提供了某塊印刷線路板過孔中心坐標的數據，單位是密爾（1/100mil）（也稱為毫英寸，1inch=1000mil），計算出單鉆頭作業的最優作業線路（包括刀具轉換方案）、行走時間和作業成本.（2）為提高打孔機效能，現在設計一種雙鉆頭的打孔機，兩鉆頭可以同時作業，且作業是獨立的，即可以兩個鉆頭同時進行打孔，也可以一個鉆頭打孔，另一個鉆頭行走或轉換刀具.為避免鉆頭間的觸碰和干擾，在過孔加工的任何時刻必須保持兩鉆頭間距不小于3cm.為使問題簡化，我們可以將鉆頭看作質點.（i）針對附件1的數據，給出雙鉆頭作業時的最優作業線路、行走時間和作業成本，并與傳統單鉆頭打孔機進行比較，其生產效能提高多少？（ii）研究打孔機的兩鉆頭合作間距對作業路線和生產效能產生的影響.10種孔型所需加工刀具及加工次序二、模型假設1.假設對于同一孔型鉆孔作業時間都是相同的；2.假設每個孔型加工完后不再加工；3.假設鉆頭在加工同種孔型時不進行刀具轉換；4.假設鉆頭在孔間以直線方式行走時不走彎路；5.假設周圍環境對鉆頭和刀具沒有干擾；6.假設加工每塊板工作過程中，無刀具磨損、損壞情況，中途無間斷.三、符號說明四、問題的分析問題一：

問題一中要研究的是最優作業線路和行走時間及作業成本這三個問題，很顯然這是一個典型的組合優化問題.由于有的孔型需要多種刀具共同加工，而且有的刀具有轉刀順序，有的轉刀沒有順序，這更加劇了問題的復雜性，為此，我們將需要多種刀具加工的一種孔型看成需要單種刀加工的多種孔型，即這些孔的位置相同但是代表不同的孔型，通過這種孔點拆分思想可以大大簡化問題.考慮到需要處理2124個數據，如果用常規方法很難求解.因此這是一個典型的組合優化問題，所以我們巧妙的利用K-means聚類分析方法將2124個孔的過孔中心坐標分為92類，經過線性回歸分析，這92類點孔很具有代表性.對于刀具轉換順序問題，通過約束條件建立整數0-1規劃模型,以成本為目標函數進行求解，從而求得刀具最優作業路線和行走作業時間及最小成本.最終得到較為合理的分配方案.問題二:（i）首先在問題一的基礎上，我們把雙鉆頭作業路線轉化為單鉆頭二次行走路線問題，為了得到最大生產效能，又設計兩套方案分別進行求解，通過比較三套方案生產效能得出最優作業線路進而得到行走時間和作業成本.（ii）問題研究的是兩鉆頭合作間距對作業線路和生產效能產生的影響.考慮到兩鉆頭間距d是一個不定變量，它隨著線路改變不斷發生變化，因此我們有選擇性的選取一組d值，在鉆頭間距d值不斷變化下，求出對應的最優作業路線和最大生產效能，然后繪制出生產效能隨兩鉆頭工作間距隨d值變化的曲線.然后利用圖像分析法得到最優值d時的最優路線和生產效能.通過曲線可以研究打孔機的兩鉆頭合作間距對作業路線和生產效能產生的影響.五、模型的建立與求解圖25.2問題一的解決

5.2.1作業成本的各項費用根據產生關系如下圖1：圖1.作業成本的各項費用關系圖2.2124個孔的中心坐標示意圖返回K-means函數的聚類效果，得出A、B、C、D、E、F、G、H、I、J10種類型孔的K均值，如下

圖3所示：圖3.8種類型孔的K均值圖圖4.8種類型孔的K均值圖K均值曲線分析：從上述曲線可以看出，K均值呈現先上升后下降的趨勢，由此我們得出8種孔型的K均值分類如表一所示：

聚類分析的合理性檢驗：通過上述方法，最終我們將所有點孔歸為92類點孔.利用Matlab軟件將這92類點孔繪制成散點圖，如圖5所示.通過該圖可以發現這92類點很具有代表性，能反映所有數據的分布規律.表一.K均值分類表圖5.92類點孔中心坐標示意圖孔點拆分法：由于有的孔型需要多種刀具加工，為了簡化加工過程，將需要多種刀具加工的一種孔型轉化為僅需要一種刀具的多種孔型.基于此方法，將92類點孔轉化為134類點孔進行加工.最小成本模型的建立：目標函數式為滿足生產總成本最小模型，涵蓋了刀具轉換費用與行走費用二個階段的評價指標，其中約束式①,②兩式表示所有孔最后均被打完，且不重復.約束式③表示在達到生產成本最小的前提下，盡量使行走路程規定在實際加工的范圍內，約束式④中為修正系數表明在用鉆頭加工需要多種刀具加工孔型的換刀順序.六、模型的求解最小成本模型的求解：該最小成本模型求解的是組合模型中的0-1規劃問題，利用Lingo軟件進行求解，以最小成本為衡量標準，單鉆頭作業的最優作業線路和刀具轉換方案如表二所示：表二.最優作業線路和刀具轉換方案表三表三.最優作業線路和刀具轉換方案由表三數據分析：通過對改進后刀具轉換方案的分析，最小加工時間475.18s，與刀具轉換方案優化前相比較，加工時間減少u=889.18-475.18=414.00s，不難發現改進后的優化方案更具有實用價值.問題二：雙鉆頭作業時最優作業線路，行走時間和作業成本的討論：我們定義了3個評價原則:１．在打完所有孔的情況下，作業時間最短；２．在打完所有孔的情況下，成本最小；３．在打完所有孔的情況下，生產效能最大.評價標準：生產效能=-總加工費用×總加工時間問題二（i）

模型的建立：

求解單鉆頭打孔機第一次行走路線：

通過對問題的分析，把雙鉆頭作業問題轉化為單鉆頭兩次行走作業路線問題，在保證打完所有孔情況下以兩次行走路線中最近距離不小于3cm為約束條件,以生產效能最大為目標函數建立模型如下:其中,其中目標函數表示單鉆頭打孔機按第一次行走路線最大生產效能；約束式②表示單鉆頭打孔機按第一次行走路線可以不必走完所有點孔；約束式④表示當兩孔型間的距離>3cm時，單鉆頭沒有從i孔到j孔.求解單鉆頭打孔機第二次行走路線：單鉆頭打孔機第二次行走路線是在第一次的行走路線的基礎上打完剩余的點孔，以最小生產效能為目標函數求解出最優作業路線.模型的求解：

通過對模型的分析要研究的問題是0-1的規劃問題，因此利用Lingo軟件得到單鉆頭打孔機兩次最優作業路線和具體轉刀方案，如表四所示：表四.鉆頭1最優作業路線和具體轉刀方案表五.鉆頭2最優作業路線和具體轉刀方案雙鉆頭最優作業路線分析：基于表四，表五中的作業路線和轉刀方案，同樣用模擬退火法準確地計算出每一類的數據，經整合后得到表六：表六.單雙鉆頭的對比雙鉆頭方案的進一步探究：方案二：成本最小目標函數：在上一問的基礎上，利用Lingo軟件得出雙鉆頭的最優路線及刀具轉換方案，如下表：表七.鉆頭1最優路線及刀具轉換方案表八.鉆頭2最優路線及刀具轉換方案方案三：加工時間最小目標函數問題二（ii）由題意可知，兩鉆頭間距對作業路線和生產效能有影響，因此假定兩鉆頭的合作間距為d，則把生產效能看做合作間距的函數.然而實際生活中很難直接發現他們的規律，所以我們對此方法做了進一步改進，運用圖像統計出不同d值下的生產效能，畫出曲線如圖6所示：圖6.生產效能曲線圖圖像分析：通過該圖像的走向趨勢，我們發現如下規律：當兩鉆頭合作間距大于3cm且小于3.90cm時，生產效能隨著兩鉆頭合作間距的增大而增大.當兩鉆頭合作間距大于3.90cm時，生產效能隨著兩鉆頭合作間距的增大而減小.當兩鉆頭合作間距等于3.90cm時，生產效能最大.七、模型評價與優化（1）優點：①在建立模型的過程中，做出了一些假設，去掉了一些不合理實際情況的干擾，降低了建模的復雜度.②在開始建模前的數據預處理中用到了矩陣的相關運算，易于用數學軟Matlab求解和驗證.③在部分模型的建立和求解中，考慮到算法實現時的時間復雜度和空間復雜度，將問題簡化處理得到近似最優解，在實際問題的解決中，該處理方法擁有較高的適用性.④通過兩個互補模型的連立復合，對刀具轉換順序進行了合理的限制.（2）缺點：①本模型對鉆孔加工的合理范圍缺乏描述，造成解出現一些誤差.②由于模擬退火算法需要一些特定的初值.所以初值的選取好壞對最終結果有一定影響.③由于對模型進行了簡化處理，所得結果與實際精確值存在一定誤差.（3）模型優化1.本文在討論刀具轉換順序的問題中，假設同一種孔型不需要轉換刀具，對于兩種刀具的孔型在現實生產中是需要考慮的，模型可以考慮朝這個方向進行優化.2．限于本文一些參數為假設數值或自定義，如針對題目中問題的求解結果可能會出現一定誤差；文中假設限于本文計算和討論，針對某一實際印刷線路板，需要更為復雜的模型建立和數值求解.另外，文中所用的部分數值已將現實問題簡化，實際鉆刀打孔的影響因素有很多，該模型在應用中需要適當修正或調整部分參數，并加以改進.八、模型的推廣通過對題目的解讀不難發現這是一個組合優化問題，組合優化問題是規劃的一個重要分支，它在解決城市建設、公共設施安置、工業生產選址等中都發揮著重要的作用.文中建立的“單鉆頭作業的最優作業線路”算法具有通用性，可以推廣至大型超市、醫院、小區內居民服務點的設點問題，該模型能夠對已知相關數據的區域或路網，進行合理規劃，合理選用給出的優化算法，可實現城市基礎設施服務民眾的高效性.參考文獻：[1]姜啟源.數學模型[M].北京:高等教育出版社,2011.[2]科曼.算法導論[M]北京:機械工業出