1、封一答卷編號（參賽學校填寫）：答卷編號（競賽組委會填寫）：論文題目： （標明A、B、C、D之一） D 組 別：(填寫研究生、本科生、專科生或中學生) 本科生 參賽隊員信息(必填)： 姓 名學 號聯系電話參賽隊員1參賽隊員2參賽隊員3 參賽學校： 黑龍江工程學院 封二答卷編號（參賽學校填寫）：答卷編號（競賽組委會填寫）：評閱情況（學校評閱專家填寫）：學校評閱1.學校評閱2.學校評閱3. 評閱情況（聯賽評閱專家填寫）：聯賽評閱1.聯賽評閱2.聯賽評閱3.打孔機生產效能的提高摘要在現代電子設備中印刷電路板占有重要地位，是集成各種電子元器件的信息載體，在各個領域得到了廣泛的應用。近年來，隨著電子、信息

2、、通訊等產業的蓬勃發展，使得對印刷電路板的需求快速增加，更帶動了印刷電路板產業的加速成長。然而，印刷電路板制造過程相當繁瑣、耗時，并且制造過程中常會出現不確定性的變異，進而影響制造時間，制作成本及產品質量，甚至延誤交貨期。而現有的打孔機的操作系統雖然具有自動生成鉆孔NC程序的功能，但是其生成的走刀路徑并沒有足夠優化，這樣會影響打孔機的生產效率，對于大批量生產的廠商來說，其影響相當明顯從而造成制造商的損失。鑒于鉆孔作業在印制電路板的制造過程中耗費時間最長、制造過程變異最多。因此，鉆孔作業常常成為整個印制電路板的生產瓶頸。本次研究以印刷電路板制作過程中的生產效能即打孔機鉆孔的作業線路作為研究對象，

3、經過對本問題的深入研究，利用遺傳算法可以快速得出最優方案。但鑒于求解過程中涉及大量計算，而遺傳算法在大規模計算中很容易陷入“早熟”，即遺傳算法在計算過程中會過早的收斂于局部最優解，從而使得結果的誤差偏大。鑒于遺傳算法可擴展性強，容易與其他算法結合利用的優點，并采用1stOpt軟件及其所開發的最大繼承法最終得出多目標并行的打孔機鉆頭的最優作業線路（包括刀具轉換方案），進而提高打孔機的生產效能，達到生產線平衡、提升整體產量和質量。(針對問題一,針對問題二,寫具體的解決方案,不要泛泛的說!把你以上說的東西拿到模型的優缺點中去!)關鍵字: 遺傳算法、 1stOpt、 最大繼承法 (再加兩個) 一、問題

4、重述1、問題背景在現代電子設備中印刷電路板占有重要的地位，是集成各種電子元器件的信息載體，在各個領域得到了廣泛的應用。隨著技術的不斷發展和工業的持續進步，使得對印刷電路板的需求快速增加。打孔機主要用于在制造印刷線路板流程中的打孔作業。所以提高某類打孔機的生產效能成為生產廠商增加利潤的主要途徑。根據打孔機打孔作業原理，通過改善鉆頭的作業線路（包括刀具轉換方案）可以提高印刷線路板的生產效能。附件1和表1提供了該塊線路板的各孔的分布和十種孔型所需的加工刀具和加工次序。 2、問題提出（1）在單鉆頭作業條件下，根據該塊線路板的各孔的分布和十種孔型所需的加工刀具和加工次序，給出最優作業線路（包括道具轉換方

5、案），并且求出單鉆頭在最優作業線路下的行進時間和作業成本。（2）在兩個鉆頭同時作業時（各自的作業孤立），兩鉆頭間距不小于3cm的條件下給出雙鉆頭作業時的最優作業線路、行進時間和作業成本，并與傳統單鉆頭打孔機進行比較，其生產效能提高多少，并研究打孔機的兩鉆頭合作間距對作業路線和生產效能產生的影響。二、問題的分析問題一針對打孔機單鉆頭作業，其最優作業線路是由印刷線路板上各孔型的分布及其所需加工刀具和加工次序所決定。1stOpt軟件在基于遺傳算法上開發的最大繼承法可以更好的應用于組合優化問題，綜合鉆頭的作業線路，為了簡化模型，將該塊印刷電路板上的所有孔劃分為若干個區域，這樣就可以針對每一個區域，都是

6、相同孔的點，這樣就可以在鉆頭作業時只需考慮路徑最短，進而可歸結為旅行商問題（TSP問題），最終可得出各區域的最優作業線路，然后對各個區域間的路徑進行分析并結合刀具轉換方案，最終可以得到單孔作業的最優作業線路。而在印刷線路板上的孔共有n個，每個孔都可以用l，2，3n中唯一的編號表示。假設鉆頭按照2，5，7。4，3，6，8，9，1順序進行加工，則這條走刀路徑就可以被表示為(2，5，7。4，3，6，8，9，1)。最終的鉆頭作業線路就可以用孔的編號進行表示。問題二鑒于兩個鉆頭單獨工作并且鉆頭間距離不得小于3cm的條件，應利用用直線劃分的方案，將整塊的印刷電路板分為三個區域，中間區域寬度略大于合作間距。

7、兩個鉆頭分別負責左右兩個區域，中間區域最后加工。進而求解最優作業線路、行進時間和作業成本。3 符號說明與模型假設1.符號說明(這一塊整體東西少,再加東西)n：各區域內孔的個數Xi：第i個孔的橫坐標Yi：第i個孔的縱坐標Xj：第j個孔的橫坐標Yj：第j個孔的橫坐標 根據附件1中給定的孔的坐標順序，把所有的孔從先至后按從1到2124的順序依次進行編號2.模型假設1.為了問題簡化，假設打孔機鉆頭從一個孔移動到下一個孔，其路徑就是兩點之間的連線。2.假設打孔機鉆頭加工單個孔的成功率為百分之百。3.假設打孔機在作業過程中，不會出現機器停止運轉的情況。 四問題求解問題（1）將附件1給出的某塊印刷電路板上所

8、有孔的坐標及孔型將孔進行劃分，劃分原則為相同孔型劃分為一個區域，考慮到1stOpt軟件的字符上限，每個區域最多的孔數目為220。則可劃分為以下區域劃分區域孔的編號孔型一1200A二221440三441660四661860B五8611060六10611260七12611448八14491648C九16491718十17191930D十一19312025E十二20262059F十三20602079G十四20802085H十五20862095I十六20962124J 第一個區域是編號1220的孔，第二個區域是編號221440的孔，第三個區域是編號441660的孔。在第一個區域內，因為A型孔只需用刀具

9、a加工，那么，鉆頭的最優作業線路只需滿足路徑最短即可，不必考慮刀具轉換問題。那么這就可以歸結為旅行商問題（TSP問題）。即有個孔，從某一孔出發，每個孔訪問一次，最后回到起始孔，試求最短距離的訪問路線。(這些原理所用的數學表達式寫上,整篇論文沒有什么數學表達式,給人直觀印象不好)那么就可以利用旅行商問題的算法的解決鉆頭作業線路最短問題，結合1stOpt軟件及其所開發的最大繼承法，通過編輯程序代碼和參數設置，就可以得出最優作業線路，具體如下：程序代碼：NewDivision;/33894.Constant n = 220; /number of holesConstantxData(0:n-1)=

10、100,-10000,-100200,-100200,-100200,-101324,-101324,-101324,-101324,-101324,-101324,-101324,-101324,-101324,-101324,-101400,-101400,10200,102000,102000,102000,102000,102000,102000,102000,102000,102000,102000,102000,102000,102000,102000,102000,102000,-103200,103400,103400,103600,103600,103600,103600,1

11、03600,103600,103600,103600,103600,103600,103600,103600,103600,103600,103600,-10400,-104474,-104474,-104474,-104474,-104474,-104474,-104474,-104474,-104474,-104474,-10474,-104800,-105000,-107000,-107000,-107600,-107623,-107623,-107623,-107623,-107623,-107623,-107623,-107623,-107623,-107623,-107623,-1

12、07700,-107700,-108800,-109000,11000,-11000,-110688,-110700,-110773,-110773,-110733,-110773,-110773,-110773,-110773,-110800,-110800,-111000,-112000,-113000,-113922,-113922,-113922,-113922,-113922,-113922,-113922,-113922,-113922,-113922,114000,114000,114000,114000,114000,114000,114000,114000,114000,11

13、4000,114000,114000,114000,114000,-115000,-11600,116000,116000,116000,116000,116000,116000,116000,116000,116000,116000,116000,116000,116000,116000,-116800,-117000,-117072,-117072,-117072,-117072,-117072,-117072,-117072,-117072,-117072,-117072,-117072,-118800,1200,-120200,-120200,-120222,-120222,-1202

14、22,-120222,-120222,-120222,-120222,-120222,-120222,-120222,-120222,-120222,-120222,-120530,-120800,-121400,-121400,-122000,-122600,-122800,-123371,-123371,-123371,-12400,-12400,-12400,12400,12400,-124467,-124800,-126400,-126521,-126521,-126521,-126521,-126521,-126521,-126521,-126521,-126521,-126521,

15、-126521,-126800,12800,12800,-128800,-129600,-129670,-129670,-129670,-129670,-129670,-129670,-129670,-129670,-129670,-129670,-129670,-129670,-129670,-129670,-130600,13200;Constant yData(0:n-1) = 243600,301000,246000,322400,122800,265174,268324,271474,274623,277773,284072,287222,293521,296670,299820,3

16、06200,315600,242600,246000,269600,297200,301200,305000,309000,312800,316800,320800,324800,328600,332600,336400,340400,344400,348400,121200,247800,271600,295200,299200,303000,307000,311000,314800,318800,322800,326600,330600,334400,338400,342400,346200,350200,318600,265174,271474,274623,280922,287222,

17、293521,296670,299820,306119,309269,312418,233400,122800,121200,383400,312400,265174,268324,271500,274623,277773,281000,287222,296670,299820,306119,309269,284000,293500,248000,122800,123000,267000,246000,271500,265174,268324,274623,293521,296670,299820,309269,290200,306000,121200,518600,122800,268324

18、,284072,287222,293521,296670,299820,302970,306119,309269,312418,137600,141600,145600,149400,153400,157200,161400,169200,173200,177000,181000,185000,188800,192800,121200,320600,135800,139600,143600,147600,151400,155400,159400,167200,171200,175000,179000,183000,187000,190800,122800,268400,271474,27777

19、3,284072,287222,293521,296670,299820,302970,306119,309269,312418,121200,111600,274500,281000,262025,268324,271474,277773,284072,287222,293521,296670,299820,302970,306119,309269,312418,246000,122800,109000,99200,515200,248000,121200,268324,309269,312418,211200,223200,251600,400800,403000,246000,12280

20、0,248000,274623,280922,284072,287222,293521,296670,299820,302970,306119,309269,312418,121200,221600,250800,122800,265200,268324,271474,274623,277773,280922,284072,287222,293521,296670,299820,302970,306119,309269,312418,121200,123000;Parameter Holes(0:n-1)0,n-1;Minimum = True;Exclusive = True;StartPr

21、ogram;Var TemSum : Double; i : integer;Begin TemSum := 0; for i := 0 to n-2 do TemSum := temSum + sqrt(sqr(xDataHolesi+1-xDataHoles i)+ sqr(yDataHolesi+1-yDataHolesi); FunctionResult := temSum + sqrt(sqr(xDataHolesn-1-xDataHoles0)+ sqr(yDataHolesn-1-yDataHoles0);end;EndProgram參數設置：打孔順序12345678910孔編號

22、136120137121138122139123140124打孔順序11121314151617181920孔編號19362037383940422543打孔順序21222324252627282930孔編號26442745484932313029打孔順序31323334353637383940孔編號2846475033513452184185打孔順序41424344454647484950孔編號99175684176469806316打孔順序51525354555657585960孔編號15141312115859607782打孔順序61626364656667686970孔編號768175

23、747288143156160159打孔順序71727374757677787980孔編號1421019015818818617617131打孔順序81828384858687888990孔編號1820218386253126244123打孔順序919293949596979899100孔編號2221201181182671190191194打孔順序101102103104105106107108109110孔編號195196197216215214213212193147打孔順序111112113114115116117118119120孔編號148149106107951091101531

24、70169打孔順序121122123124125126127128129130孔編號168167166165164163162157161144打孔順序131132133134135136137138139140孔編號91735655789105761打孔順序141142143144145146147148149150孔編號627997108151152179180199218打孔順序151152153154155156157158159160孔編號2171981509478931051049296打孔順序161162163164165166167168169170孔編號10310214514

25、6192211210209208189打孔順序171172173174175176177178179180孔編號2072062052041788970548387打孔順序181182183184185186187188189190孔編號658498100125141154172177187打孔順序191192193194195196197198199200孔編號2002032191731746766355155打孔順序201202203204205206207208209210孔編號85220111127128112129113130114打孔順序21121221321421521621721

26、8219220孔編號131115132116133117134118135119 則在A型孔的第一段區域內，打孔機鉆頭最優作業線路為：因為A孔型只需一種刀具加工，所以不涉及刀具轉換。鉆頭在該區域內的作業成本只包括行進成本。孔編號（1220）作業成本P1（元 ）作業時間為T1（秒）3583.48331.80 經過深入分析只需一種刀具加工的孔型所在區域均可以利用第一個區域求解最優作業線路的算法，求出鉆頭的最優作業線路。每個區域內不涉及刀具轉換問題，這些區域包括區域二，區域三，區域四，區域五，區域六，區域七，區域十四，通過1stOpt軟件及其所開發的最大繼承法即可算出每個區域內鉆頭的最佳作業線路，行

27、進成本及作業時間。具體結果見附件一。對于需要兩個或兩個以上刀具加工的孔型，最優作業線路取決于鉆頭路徑與刀具轉換。鑒于上述，采鉆頭優先加工完畢作業孔，再繼續加工下一個孔，以此類推，按照此方案實現加工區域內所有的孔。對于區域十三，就可利用上述方案求解鉆頭作業的最優作業線路（刀具轉換方案），行進時間和作業成本。當加工完一個孔時在加工下一個空。對于相同孔型的孔，加工每個孔時道具的的轉換次數為4，并且每次加工完畢一個孔時，向下一個孔移動，中間轉換的刀具次數為2。并且每個孔都是遵循上述的刀具轉換數量。 根據下列公式： a1a2a3n (|a1-a2|+ |a2-a3|)×n+ |a3-a1| &

28、#215;(n-1) |a1-a2|4, |a2-a3|4, |a3-a1|4 (8-|a1-a2|+ |a2-a3|)×n+ |a3-a1| ×(n-1) |a1-a2|>4, |a2-a3|4, |a3-a1|4 (8+|a1-a2|- |a2-a3|)×n+ |a3-a1| ×(n-1) |a1-a2|4, |a2-a3|>4, |a3-a1|4 (|a1-a2|+ |a2-a3|)×n+ (8-|a3-a1|)× (n-1) |a1-a2|4, |a2-a3|4, |a3-a1|>4 (16-|a1-a2|-

29、 |a2-a3|)×n+ |a3-a1| ×(n-1) |a1-a2|>4, |a2-a3|>4, |a3-a1|4 (8-|a1-a2|+ |a2-a3|)×n+ (8-|a3-a1|)×(n-1) |a1-a2|>4, |a2-a3|4, |a3-a1|>4 (8+|a1-a2|- |a2-a3|)×n+ (8-|a3-a1|)×(n-1) |a1-a2|4, |a2-a3|>4, |a3-a1|>4 (16-|a1-a2|- |a2-a3|)×n+(8-|a3-a1|)×(

30、n-1) |a1-a2|>4, |a2-a3|>4, |a3-a1|>4 計算出鉆頭在G孔作業過程中刀具轉換的次數,經運算得到轉換刀具的次數為118次。由于孔型相同，那么在作業過程中刀具轉換是固定的，所以鉆頭在這個區域內的最優作業線路取決于鉆頭的的行進路徑，因此采取旅行商問題的算法并利用1stOpt軟件及其所開發的最大繼承法，就可以解決路徑最短問題，從而可得出最佳作業線路具體程序代碼及參數設置如下：NewDivision;/33894.Constant n = 20; /number of HolesConstant xData(0:n-1) = -301300,-30130

31、0,-301300,-301300,-301300,-301300,-301300, -301300,-321300,-321300,-321300,-321300,-321300,-321300, -321300,-321300,153000,173000,193000,213000;ConstantyData(0:n-1)=-301300,-301300,-301300,-301300,-301300,-301300,-301300, -301300,-321300,-32,-321300,-321300,-321300, -321300,-321300,153000,173000,193

32、000,213000;Parameter Holes(0:n-1)0,n-1;Minimum = True;Exclusive = True; StartProgram;Var TemSum : Double; i : integer;Begin TemSum := 0; for i := 0 to n-2 do TemSum := temSum + sqrt(sqr(xDataHolesi+1-xDataHolesi)+ sqr(yDataHolesi+1-yDataHolesi); FunctionResult := temSum + sqrt(sqr(xDataHolesn-1-xDat

33、aHoles0)+ sqr(yDataHolesn-1-yDataHoles0);end;EndProgram參數設置： 則可以得出最優作業線路為：打孔順序12345678910孔編號2079206720652074206920712070207220752073打孔順序11121314151617181920孔編號2068206620612060206220632064207620772078則作業成本極其作業時間為：孔編號（20602079）作業成本P13（元 ）作業時間為T13（秒） 2511.0122337.25 經過深入分析需要兩種或兩種以上刀具加工的孔型所在區域均可以利用第十三個區

34、域求解最優作業線路的算法，每個區域內涉及刀具轉換問題，但是對于同一個區域內的空來說轉換刀具的次數是相同的，所以只需求解區域內的鉆頭最短運行路徑即可。故以利用旅行商問題的并算法通過1stOpt軟件及其所開發的最大繼承法即可算出每個區域內鉆頭的最佳作業線路（包括刀具轉換方案），行進成本及作業時間。具體結果見附件。 以上求出了十六個區域各自的鉆頭最優作業線路（包括刀具轉換方案），且對于每一個區域，鉆頭的起始位置和最終位置都已經確定。鉆頭在加工整塊印刷電路板時，加工完一個區域內的孔向另一個區域移動時，這十六個區域只是通過各自內部的起始點與終點進行連接，與其他的點無關，所以為了簡化模型，這十六個區域可以

35、看作是三十二個點，那么，只需求解鉆頭在這三十二個點之間的最優作業線路，根據遺傳算法可以解決多目標規劃的線路調度問題可得出最優的作業線路(包括刀具轉換方案)，行進成本及作業時間。 所有的孔作業成本P （元 ）作業時間為T（秒） 97594.87 60513.67 再結合附表中的各區域最優作業線路，行進成本及作業時間可得出在該塊印刷線路板上打孔機鉆頭的最優作業線路為：2079206720652074206920712070207220752073 2068206620612060206220632064207620772078 19491940195020112013201520172018202

36、02022 2024202520232021201920162014201220102008 2009200720062005200219471938193919482001 2004200319341945195819781979198019861985 1984198319821977197619621961195919551953 1944193519991997196919571960199219982000 1956196319741965197019711972197319681967 1966197519961943198119461988199319941991 1941198

37、919951990198719311964193319361937 19421952195419511932 20332037204520422034 2030203820392031203520432047204620492048 2044203620322028202620292027205720502052 2055205620542053205120592058204020411668 1670166917051706170417031651165016831684 1685168616581657167216731674167516761678 1677167116641663165

38、916601661166216821649 1710171117131715171617181692169016871699 1652165616551654165316971695169817021696 1701170016941689168816931691171717141712 1680167916811709170817071665166616671840 1839183818371827182619031907190219011906 1905190419001899183219241831183418331830 18731872185618571858187418891888

39、18841883 1891189218931894189518961897189818901887 1886188518691870187118551854185318521868 1867185117381737173317341732173117291730 1724172317191720172617251735173617221721 1727172818491850175417531752183618351909 1915191319121908191019141916191119261921 1744174017411756175717421745174618421843 1792

40、180917931776175917751758175517491748 1747191919201923192219271928192919301925 1844184518461847184817431739175017511763 1780177917621761176017771794181018111795 1778179618121813179718141815179817811764 1765178217991816181718001783176617671784 1801181818021819182018031785176817691770 17861804182118221

41、80517871771178817721789 1773179017741791180818071806182318241825 1841191819171866188218811865186418801879 1878186318621861187718761860185918751829 1828208320842085208120802082163016351642 1645163914741467145614511449153415361462 1545160516141604161916231458145314551459 162216271621161815491554155716

42、3816411647 1648164616001599159315941592159115891583 1584158015761572157015741578158215881587 1581157715731569156515661586159815961560 1564155915951597158516011561156216021568 1464146114681472147814821483149214911516 1515151816441632159015791575157115671563 1612161716111606160316131465146614751476 14

43、81148414941509151715211540154415411530 1535152515221520151915061499149815031500 1486148714881489149314901496149715241523 1526153915381542153115271528153315321529 1546154315371512150214851480162816241471 1477147915511548155015531609161016161505 1511151015081504151415131507162916261620 162516151607160

44、8155215471631163715011495 1643163614501556155515581454145214571460 1463146914701473163316401634209220882090 2091208920932095209420872086211821032102 2099209821192108210421202116211421002101 2115211220962097211721132122210721232124 2111212121062105211021091423142414351414 1415141614171418133213331319

45、133013311408 1407140914101406143814191412134712671265 1404139813971396140114001429142814361393 1384136913551364137114391437137413811380 1379137813771376137513951394138613821372 1370136613651363136013531320134013571373 1427142614411411140213901356136814401430 1446143114421432142014431444142113591358

46、1329138513131361133913361324132313221413 1272126112761277127413071312130513041300 1283127912691262127012801284129113011308 1316131813111310130212941293130312901285 1287128812891295126412711278128212921298 1315131413211317130612991286128112751268 1263127312661362134113251328132713511447 1448142514051

47、387135213381337134513461334 1335134913891388139914031392138313501344 1342132613671297129613541309139113481343 1422144514331434136 120137 121 138122139123 140 1241936 203738394042254326442745484932 313029284647503351345218418599175684176469 80631615141312115859607782768175747288 143 15616015914210190

48、1581881861761713118202183 86 253 126 2441232221201181182671190191194195196197216215 214 21321219314714814910610795109110153170169168167166165164 16316215716114491735655789105761627997108 1511521791801992182171981509478931051049296103102145 14619221121020920818920720620520417889705483876584 98 100125141154172177187200203219173174676635515585220111 127128112129113130114131115132116133117134118135119 528520 4995105195275335425505565675695