打孔機生產(chǎn)效能的提高1

1、打孔機生產(chǎn)效能的提高國防科學技術大學王久力、李寧、萬山川指導教師：毛紫陽問題重述鉆孔加工是印制板制作過程中的一個重要環(huán)節(jié)過孔的加工費用通常占制板費用的 30%到 40%。刀具和工件的運動在加工過程中平均占用總加工時 間的 70%一個最優(yōu)的作業(yè)線路既可以減少工作時間，又可以降低加工成本，對于工業(yè)生產(chǎn)有著很大的意義問題重述問題一問題一已知印刷線路板過孔中心坐標的數(shù)據(jù)，設計適當算法，計算出單鉆頭作業(yè)的最優(yōu)作業(yè)線路（包括刀具轉(zhuǎn)換方案）、行進時間和作業(yè)成本。問題二問題二 設計一種雙孔打鉆機，兩鉆頭可以同時作業(yè)，且作業(yè)是獨立的，即可以兩個鉆頭同時進行打孔，也可以一個鉆頭打孔，另一個鉆頭行進或轉(zhuǎn)換刀具。為避

2、免鉆頭間的觸碰和干擾，在過孔加工的任何時刻必須保持兩鉆頭間距不小于 3cm（稱為兩鉆頭合作間距） ，設計算法給出出雙鉆頭作業(yè)時的最優(yōu)作業(yè)線路、行進時間和作業(yè)成本，并與傳統(tǒng)單鉆頭打孔機的生產(chǎn)效能進行比較。 問題問題研究打孔機的兩鉆頭合作間距對作業(yè)路線和生產(chǎn)效能產(chǎn)生的影響。模型假設1. 單個過孔的鉆孔作業(yè)時間忽略不計； 2. 鉆頭在行進過程中轉(zhuǎn)向沒有附加時間； 3. 兩孔間距以歐式距離計算； 4. 鉆頭以直線行進； 5. 刀具移動到目標位置沒有誤差； 模型建立帶權有向圖模型1. 只需要一種刀具加工的孔；2. 需要多種刀具加工且順序任意的孔；3. 需要多種刀具加工且有加工順序要求的孔。模型建立與旅行

3、商TSP問題的對比存在有加工順序的特殊要求現(xiàn)有成熟算法無法直接適用問題（一）求解單鉆作業(yè)條件下的求解方法遍歷所有的孔，并按照加工順序的要求完成加工，求解最優(yōu)工作線路工序要求，訪問部分頂點之前必須預先訪問其前趨節(jié)點計算過工作時間同時計算作業(yè)成本貪心算法貪心算法貪心策略結果統(tǒng)計貪心策略結果統(tǒng)計項目項目時間（秒）成本（元）工作時間行進時間時間最優(yōu)解法時間最優(yōu)解法成本最優(yōu)解法成本最優(yōu)解法綜合考慮時綜合考慮時間和成本的間和成本的折中解法折中解法最優(yōu)解統(tǒng)計最優(yōu)解統(tǒng)計貪心算法啟發(fā)式搜索貪心與深度優(yōu)先搜索算法的結合在深搜的基礎上，貪心地選取離當前頂點最近的點作為目標節(jié)點訪問而當一條回路走完之后回溯到上一層，再

4、選取離自己第二近的節(jié)點繼續(xù)訪問狀態(tài)總數(shù)不會無限增大，且為改進結果創(chuàng)造了可能啟發(fā)式搜索最優(yōu)換刀模型刀具轉(zhuǎn)換時間占據(jù)了總工作時間的大部分什么是換刀序列？什么是合理的換刀序列？如何尋找合理的最優(yōu)換刀序列？確定了換刀序列后如何工作？最優(yōu)換刀模型如何尋找最優(yōu)換刀序列？給定的換刀序列可驗證其是否合理每次換刀就會有兩種狀態(tài)與之對應，因而每個固定的換刀序列就有一個唯一的二進制編碼長度為n的序列總數(shù)是2n-1 換刀序列換刀序列換刀次數(shù)換刀序列工作時間（秒）910松弛調(diào)整算法松弛調(diào)整算法松弛調(diào)整算法算法名稱算法名稱調(diào)整前時間（秒）調(diào)整前時間（秒）調(diào)整后時間（秒）調(diào)整后時間（秒）貪心算法貪心算法313.860304

5、.761啟發(fā)式搜索啟發(fā)式搜索308.121292.940最優(yōu)換刀最優(yōu)換刀249.276237.914最優(yōu)時間解貪心算法 313.9s啟發(fā)式搜索 308.1s最優(yōu)換刀 249.3s松弛調(diào)整 237.9s單鉆打孔最優(yōu)問題解決流程問題（二）I的求解尋找兩個鉆頭的合作換刀序列和打孔方式根據(jù)事件點對時間軸離散解決同步問題建立時間 距離函數(shù)判斷是否碰撞編程求解雙鉆合作打孔方式和換刀序列目標：找到一種雙鉆頭的合作換刀序列，使得換刀總次數(shù)盡可能少，兩個鉆頭的任務量盡量均勻。需要解決的問題： 1、如何使得兩個鉆頭合作換刀次數(shù)盡可能少 2、如何分配使得兩個鉆頭的任務量盡可能相等 3、如何解決加工順序沖突問題雙鉆合

6、作打孔方式和換刀序列解決方法：1.構造一個對應的孔類型與刀具二元關系表格2.分析各個刀具的時間順序，避免出現(xiàn)加工順序不合理問題3.綜合考慮兩個鉆頭的工作量分配關系以及合作關系，均勻分配任務4、根據(jù)刀具轉(zhuǎn)換最少原則，找到雙鉆最優(yōu)合作序列5、根據(jù)所給序列，確定打孔方式第一種序列第一種序列第二種序列第二種序列鉆頭一habcdcbc鉆頭二defgfahgfe孔型與刀具二元關系表格根據(jù)事件點對時間軸離散解決同步問題 路徑離散化示意圖（上半部分為甲，下部分為乙）建立時間 距離函數(shù)判斷是否碰撞設A、B、C、D點坐標分別為（a1,b1）、（a2,b2）、（a3,b3）、（a4,b4）。設兩個鉆頭同時從A與C開

7、始向前進，由于離散化的路徑長度相同，即AB=CD，所以它們同時到達B、D點鉆頭1的運動方程為：鉆頭2的運動方程為：其中分別為線段AB與CD與X軸正方向的夾角，v為鉆頭的行進速度(對應的)。建立時間 距離函數(shù)判斷是否碰撞根據(jù)方程可求解在該段時間內(nèi)兩鉆頭的最小距離Dmin建立時間 距離函數(shù)判斷是否碰撞通過上述求解Dmin,可以判斷在兩個鉆頭選取下個目標打孔點時，是否會發(fā)生兩鉆頭間距小于3cm如果會小于3cm，則放棄該段局部最優(yōu)路徑，而選取局部次優(yōu)路徑作為下段行進路徑問題（2）I的結果依據(jù)上面的求解過程，我們編程實現(xiàn)后，在保證兩個鉆頭間距大于3cm的前提下，得到的結果為：工作時間為128.03601

8、2秒，與傳統(tǒng)單鉆頭打孔機比較生產(chǎn)效能提高了46.06%；其中行進時間為57.666秒；作業(yè)成本為1125.27元問題（2）I求解流程問題（2）II的求解按照前面介紹的方法通過選取不同的合作間距計算工作時間，得到如右數(shù)據(jù)合作間距合作間距dis（cm）工作時間工作時間T0.1111.8831860.2111.8831860.3111.5511170.4121.6070250.5122.2197820.6122.5120700.7122.5345730.8122.5202870.9122.0022761.0144.1495781.1142.3180801.2141.9875101.3142.2419

9、611.4130.7912301.5123.9249391.6135.2995791.7134.5578601.8129.3971071.9129.5599342.0159.2715162.1137.5642122.2137.4348682.3129.7815902.4138.4338242.5128.5047862.6126.6762872.7145.2261602.8135.7586892.9128.5498643.0128.0360123.1136.0297093.2134.8892353.3151.3780093.4138.7720833.5136.2833703.6137.03227

10、53.7140.1241983.8137.8377433.9142.6855184.0139.2270074.1152.1780074.2140.6560224.3177.9682354.4161.5139144.5183.9190994.6153.6196934.7146.6076214.8139.2939744.9134.0394595.0169.5592355.1160.7892695.2134.7204575.3149.1313115.4166.6543965.5151.0272935.6166.5558685.7151.8583915.8146.0858595.9133.503794

11、6.0183.4806287.0194.630717問題（2）II的求解作出合作間距與工作時間的關系圖：y = 7.018x + 119.2R = 0.520020406080100120140160180200012345678問題（2）II的求解得到一元線性回歸方程為：T = 7.018dis + 119.2對所得回歸方程做顯著性檢驗 相關系數(shù)R=0.7211 在顯著性水平為=0.001時，查表可得 1-0.01(59)=0.408; 由于R=0.72110.408,所以回歸方程式高度顯著的，可知二者滿足線性關系問題（2）II的求解結論：當兩鉆頭合作間距越小，越有益于生成更加優(yōu)化的作業(yè)線路，提高生產(chǎn)效能。模型檢驗隨機選取幾個數(shù)量較小的點集，先用窮舉法求得實際最優(yōu)解，與計算所得解作比較模型優(yōu)缺點及評價算法及模型算法及模型優(yōu)點優(yōu)點缺點缺點貪心算法計算快捷、簡單可行，易于實現(xiàn)局部最優(yōu)無法保證整體最優(yōu)；對于大規(guī)模問題與最優(yōu)解相差大,結果不