725 空氣濾清器連接板沖孔、沖槽、落料復合模設計（有cad圖+文獻翻譯）,725,空氣濾清器連接板沖孔、沖槽、落料復合模設計（有cad圖+文獻翻譯）,空氣濾清器,連接,沖孔,復合,設計,cad,文獻,翻譯 2011屆畢業(yè)設計 材 料 系 、 部： 機械工程系 學生姓名： 劉林飛 指導教師： 和道 職 稱： 講師 專 業(yè)： 材料成型及控制工程 班 級： 材料成型0704 學 號： 212070406 2011 年 6 月 湖南工學院畢業(yè)設計(論文)工作中期檢查表 題目 空氣濾清器連接板沖孔、沖槽、落料復合模設計 學生姓名 劉林飛 班級學號 070426 專業(yè) 材料成型及控制工程 指 導 教 師 填 寫 學生開題情況 學生調研及查閱文獻情況 畢業(yè)設計（論文）原計劃有無調整 學生是否按計劃執(zhí)行工作進度 學生是否能獨立完成工作任務 學生的英文翻譯情況 學生每周接受指導的次數(shù)及時間 畢業(yè)設計（論文）過程檢查記錄情況 學生的工作態(tài)度在相應選項劃“√” □認真 □一般 □較差 尚存在的問題及采取的措施： 指導教師簽字： 年 月 日 系部意見： 負責人簽字： 年 月 日 湖南工學院2011屆畢業(yè)設計（論文）指導教師審閱表 系：機械工程系 專業(yè)：材料成型及控制工程 學生姓名 劉林飛 學 號 212070426 班 級 成型0704 專 業(yè) 材料成型及控制工程 指導教師姓名 和道 課題名稱 空氣濾清器連接板沖孔、沖槽、落料復合模設計 評語：（包括以下方面，①學習態(tài)度、工作量完成情況、材料的完整性和規(guī)范性；②檢索和利用文獻能力、計算機應用能力；③學術水平或設計水平、綜合運用知識能力和創(chuàng)新能力；） 是否同意參加答辯： 是□ 否□ 指導教師評定成績 分值： 指導教師簽字： 年 月 日 湖南工學院畢業(yè)設計（論文）評閱教師評閱表 題　　目 空氣濾清器連接板沖孔、沖槽、落料復合模設計 學生姓名 劉林飛 班級學號 070426 專業(yè) 材料成型及控制工程 評閱 教師姓名 職稱 工作單位 評分內容 具 體 要 求 總分 評分 開題情況 調研論證 能獨立查閱文獻資料及從事其他形式的調研，能較好地理解課題任務并提出實施方案，有分析整理各類信息并從中獲取新知識的能力。 10 外文翻譯 摘要及外文資料翻譯準確，文字流暢，符合規(guī)定內容及字數(shù)要求。 10 設計質量 論證、分析、設計、計算、結構、建模、實驗正確合理。 35 創(chuàng)新 工作中有創(chuàng)新意識，有重大改進或獨特見解，有一定實用價值。 10 撰寫質量 結構嚴謹，文字通順，用語符合技術規(guī)范，圖表清楚，書寫格式規(guī)范，符合規(guī)定字數(shù)要求。 15 綜合能力 能綜合運用所學知識和技能發(fā)現(xiàn)與解決實際問題。 20 總評分 評閱教師 評閱意見 評閱成績 總評分ⅹ20% 評閱教師簽名 日期 湖南工學院畢業(yè)設計（論文）答辯資格審查表 題 目 空氣濾清器連接板沖孔、沖槽、落料復合模設計 學生姓名 劉林飛 學??? 號 212070426 專 業(yè) 材料成型及控制工程 指導教師 和道 內容綜述（對畢業(yè)設計或論文的研究步驟和方法、主要內容及創(chuàng)新之處進行綜述，提出答辯申請）： ???? ?? ?申請人簽名： 日期：  資? 格? 審? 查? 項? 目 是 否 01 工作量是否達到所規(guī)定要求 ? ? 02 文檔資料是否齊全（任務書、開題報告、外文資料翻譯、定稿論文及其相關附件資料等） ? ? 03 是否完成任務書規(guī)定的任務 ? ? 04 完成的成果是否達到驗收要求 ? ? 05 是否剽竊他人成果或者直接照抄他人設計（論文） 指導教師簽名： 畢業(yè)設計（論文）答辯資格審查小組意見： 符合答辯資格，同意答辯 □????? 不符合答辯資格，不同意答辯□ 審查小組成員簽名： ? ??? 年??? 月??? 日 注：此表中內容綜述由學生填寫，資格審查項目由指導教師填寫。 湖南工學院2011屆畢業(yè)設計（論文）答辯及最終成績評定表 系：機械工程系 專業(yè)：材料成型及控制工程 學生姓名 劉林飛 學號 212070426 班級 成型0704 答辯 日期 課題名稱 空氣濾清器連接板沖孔、沖槽、落料復合模設計 指導 教師 成 績 評 定 分值 評 定 小計 課題介紹 思路清晰，語言表達準確，概念清楚，論點正確，實驗方法科學，分析歸納合理，結論嚴謹，設計（論文）有應用價值。 30 答辯 表現(xiàn) 思維敏捷,回答問題有理論根據(jù)，基本概念清楚，主要問題回答準確大、深入,知識面寬。 必 答 題 40 自 由 提 問 30 合 計 100 答 辯 評 分 分值： 答辯小組長簽名： 答辯成績a： ×40％＝ 指導教師評分 分值： 指導教師評定成績b： ×40％＝ 評閱教師評分 分值： 評閱教師評定成績c： ×20％＝ 最終評定成績： 分數(shù)： 等級： 答辯委員會主任簽名： 年 月 日 說明：最終評定成績＝a+b+c，三個成績的百分比由各系自己確定，但應控制在給定標準的10％左右。 零件號 材料 T10A 毛坯重量 編制 機械加工工藝過程綜合卡片 零件名稱 沖孔凸模 生產(chǎn)類型 毛坯種類 指導 工 序 工序名稱 工序說明 機 床 夾 具 刀 具 量 具 切 削 深 度 mm 進 給 量 mm/r 主 軸 轉 速 r/min 切 削 速 度 m/min 時 間 定 額 min 5 下料 根據(jù)零件圖尺寸，下料F20360mm 10 車外圓面 車右端面，粗車外圓柱面尺寸：F10.6324，F(xiàn)14.4318，F(xiàn)1735，調頭車外圓F638 CA6140 三爪卡盤 外圓車刀 游標卡尺 4.7 0.81 500 31.4 15 檢驗 20 熱處理 按技術要求熱處理至HRC58～62 25 精車 精車F10.15mm至尺寸，并車出斜度309 CA6140 三爪卡盤 外圓車刀 游標卡尺 0.17 0.81 500 16.6 30 磨外圓面 磨F14至尺寸 外圓磨床 三爪卡盤 砂輪 游標卡尺 0.2 0.005 600 27.1 35 鉗工 去除工藝柄 40 檢驗 湖南工學院畢業(yè)設計(論文)開題報告 題　目 空氣濾清器連接板沖孔、沖槽、落料復合模設計 學生姓名 劉林飛 班級學號 212070426 專業(yè) 材料成型及控制工程 一、課題的目的和意義： 沖壓加工作為一個行業(yè)，在國民經(jīng)濟的加工行業(yè)中占有重要地位。根據(jù)統(tǒng)計，沖壓件在各個行業(yè)中均占有相當大的比重，尤其在汽車、電機、儀表、軍工、家電等方面所占比重更大。采用沖壓模具生產(chǎn)零部件，具有生產(chǎn)效益高，質量好，成本低，節(jié)約能源和原料等一系列優(yōu)點，它以成為當代工業(yè)生產(chǎn)中的重要手段和工藝發(fā)展方向。 模具工業(yè)已被我國正式確定為基礎產(chǎn)業(yè)，并在“十五”中列為重點扶持產(chǎn)業(yè)。從1997年開始，我國模具工業(yè)產(chǎn)值超過了機床工業(yè)產(chǎn)值。因此模具對國民經(jīng)濟和社會發(fā)展起著舉足輕重的作用。 對于沖壓生產(chǎn)而言，單工位模具結構單一，生產(chǎn)效率低，而且鈑金零件不能過于復雜，否則就需要多副單工位模具才能實現(xiàn)。如果采用級進模進行生產(chǎn)，就可以改變這些缺點。標志沖模技術先進水平的精密多工位級進模，具有生產(chǎn)周期短、用操作人員少、精度高、壽命長和生產(chǎn)效率高等特點，是我國重點發(fā)展的精密沖模。 本次畢業(yè)設計，指導老師給我安排的是空氣濾清器連接板沖孔、沖槽、落料復合模設計。通過對零件進行工藝分析，我們可以了解到零件材料為加工性能較好的45號鋼，零件的主要加工工序主要有：落料、沖孔、沖槽等。通過結合大學所學的專業(yè)知識，參考文獻資料，以及指導老師指導，我初步理清了本次設計的基本思路，掌握了有關畢業(yè)設計的基本方法。 二、文獻綜述 1、中國沖壓模具的發(fā)展現(xiàn)狀 中國沖壓模具的發(fā)展現(xiàn)狀改革開放帶了我國的經(jīng)濟進入高速發(fā)展的時期，模具的市場的需求量也進一步的增加。模具行業(yè)也一直以15%左右的增速再發(fā)展。因此帶來的模具工業(yè)企業(yè)的所有制成分的巨大變化，一些國有專業(yè)模具廠也如雨后春筍般的建立起來，同時也帶來了以集體、獨資、私營和合資等形式的快速發(fā)展。 賦有“模具之鄉(xiāng)”的浙江寧波和黃巖地區(qū)是現(xiàn)今我國規(guī)模最大的兩個地方；廣東地區(qū)也漸漸掀起了開建模具廠的浪潮；其中科龍、康佳等集團紛紛建立了自己的模具制造中心；中外合資或是外商獨資形式的模具企業(yè)現(xiàn)也有幾千家。 近年許多模具企業(yè)加大了用于技術進步的投資力度，將技術進步視為企業(yè)發(fā)展的重要動力。一些國內模具企業(yè)已普及了二維CAD，并陸續(xù)開始使用UG、Pro/Engineer、I-DEAS、Euclid-IS等國際通用軟件，個別廠家還引進了Moldflow、C-Flow、DYNAFORM、Optris和MAGMASOFT等CAE軟件，并成功應用于沖壓模的設計中。以汽車覆蓋件模具為代表的大型沖壓模具的制造技術已取得很大進步，東風汽車公司模具廠、一汽模具中心等模具廠家已能生產(chǎn)部分轎車覆蓋件模具。此外，許多研究機構和大專院校開展模具技術的研究和開發(fā)。經(jīng)過多年的努力，在模具CAD/CAE/CAM技術方面取得了顯著進步；在提高模具質量和縮短模具設計制造周期等方面做出了貢獻。 例如，吉林大學汽車覆蓋件成型技術所獨立研制的汽車覆蓋件沖壓成型分析KMAS軟件，華中理工大學模具技術國家重點實驗室開發(fā)的注塑模、汽車覆蓋件模具和級進模CAD/CAE/CAM軟件，上海交通大學模具CAD國家工程研究中心開發(fā)的冷沖模和精沖研究中心開發(fā)的冷沖模和精沖模CAD軟件等在國內模具行業(yè)擁有不少的用戶。 雖然中國模具工業(yè)在過去十多年中取得了令人矚目的發(fā)展，但許多方面與工業(yè)發(fā)達國家相比仍有較大的差距。例如，精密加工設備在模具加工設備中的比重比較低；CAD/CAE/CAM技術的普及率不高；許多先進的模具技術應用不夠廣泛等等，致使相當一部分大型、精密、復雜和長壽命模具依賴進口。 2、中國沖壓模具的發(fā)展方向 模具技術的發(fā)展應該為適應模具產(chǎn)品“交貨期短”、“精度高”、“質量好”、“價格低”的要求服務。達到這一要求急需發(fā)展如下幾項： (1)全面推廣CAD/CAM/CAE技術模具CAD/CAM/CAE技術是模具設計制造的發(fā)展方向。隨著微機軟件的發(fā)展和進步，普及CAD/CAM/CAE技術的條件已基本成熟，各企業(yè)將加大CAD/CAM技術培訓和技術服務的力度；進一步擴大CAE技術的應用范圍。計算機和網(wǎng)絡的發(fā)展正使CAD/CAM/CAE技術跨地區(qū)、跨企業(yè)、跨院所地在整個行業(yè)中推廣成為可能，實現(xiàn)技術資源的重新整合，使虛擬制造成為可能。 (2)高速銑削加工國外近年來發(fā)展的高速銑削加工，大幅度提高了加工效率，并可獲得極高的表面光潔度。另外，還可加工高硬度模塊，還具有溫升低、熱變形小等優(yōu)點。高速銑削加工技術的發(fā)展，對汽車、家電行業(yè)中大型型腔模具制造注入了新的活力。目前它已向更高的敏捷化、智能化、集成化方向發(fā)展。 (3)模具掃描及數(shù)字化系統(tǒng)高速掃描機和模具掃描系統(tǒng)提供了從模型或實物掃描到加工出期望的模型所需的諸多功能，大大縮短了模具的在研制制造周期。有些快速掃描系統(tǒng)，可快速安裝在已有的數(shù)控銑床及加工中心上，實現(xiàn)快速數(shù)據(jù)采集、自動生成各種不同數(shù)控系統(tǒng)的加工程序、不同格式的CAD數(shù)據(jù)，用于模具制造業(yè)的“逆向工程”。模具掃描系統(tǒng)已在汽車、摩托車、家電等行業(yè)得到成功應用，相信在“十五”期間將發(fā)揮更大的作用。 (4)電火花銑削加工電火花銑削加工技術也稱為電火花創(chuàng)成加工技術，這是一種替代傳統(tǒng)的用成型電極加工型腔的新技術，它是有高速旋轉的簡單的管狀電極作三維或二維輪廓加工(像數(shù)控銑一樣)，因此不再需要制造復雜的成型電極，這顯然是電火花成形加工領域的重大發(fā)展。國外已有使用這種技術的機床在模具加工中應用。預計這一技術將得到發(fā)展。 (5)提高模具標準化程度我國模具標準化程度正在不斷提高，估計目前我國模具標準件使用覆蓋率已達到30%左右。國外發(fā)達國家一般為80%左右。 (6)優(yōu)質材料及先進表面處理技術選用優(yōu)質鋼材和應用相應的表面處理技術來提高模具的壽命就顯得十分必要。模具熱處理和表面處理是否能充分發(fā)揮模具鋼材料性能的關鍵環(huán)節(jié)。模具熱處理的發(fā)展方向是采用真空熱處理。模具表面處理除完善應發(fā)展工藝先進的氣相沉積(TiN、TiC等)、等離子噴涂等技術。 (7)模具研磨拋光將自動化、智能化模具表面的質量對模具使用壽命、制件外觀質量等方面均有較大的影響，研究自動化、智能化的研磨與拋光方法替代現(xiàn)有手工操作，以提高模具表面質量是重要的發(fā)展趨勢。 (8)模具自動加工系統(tǒng)的發(fā)展這是我國長遠發(fā)展的目標。模具自動加工系統(tǒng)應有多臺機床合理組合；配有隨行定位夾具或定位盤；有完整的機具、刀具數(shù)控庫；有完整的數(shù)控柔性同步系統(tǒng)；有質量監(jiān)測控制系統(tǒng)。 我國沖壓模具與發(fā)達國家企業(yè)之間的差距不小，因此要發(fā)揮整體優(yōu)勢和綜合競爭力，要加強統(tǒng)籌協(xié)調、完善合作機制，創(chuàng)造性地工作。也需要加大對模具相關專業(yè)人才的綜合素質培訓投入。 2、設計內容與步驟 （1）沖壓零件的工藝性分析：材料的沖壓性能分析、結構形狀工藝性分析、尺寸的工藝性分析、精度的工藝性分析等。 （2）沖壓工藝的總體方案的分析和確定：單工序模方案、復合模方案、級進模方案的對比，最終確定的方案； （3）基于所確定的總體方案，進行排樣設計：擬定工位數(shù)、各工位的沖壓性質和沖壓順序，繪制板料的排樣圖； （4）基于總體方案和排樣方案，進行工藝計算，如：凸凹模尺寸及偏差、間隙、變形力、壓力中心、卸料力等計算； （5）模具關鍵結構的方案設計：凸凹模結構形式、導向、導料、定位、卸料等； （6）模具總體結構設計與確定：基于上述內容，設計并確定模具總體結構，描述模具的工作原理和工藝動作，并繪制二維裝配圖和相應的三維圖； （7）選擇合理的沖壓設備（考慮設備噸位與變形力的吻合、沖裁封閉高度與設備裝模高度的吻合、模具的平面尺寸與設備工作臺面尺寸的吻合等）； （8）進行模具零件的詳細設計：確定模具中的標準件（聯(lián)結零件：螺釘、銷釘、彈性元件等）的型號和數(shù)量，對模具中的非標準件進行詳細的結構尺寸設計，繪制相應的二維零件圖； （9）編制模具中主要零件的制造工藝方案和加工方法； （10）撰寫設計說明書； （11）所有設計文檔、資料的整理、收尾、答辯。 3、繪圖任務 （1） 模具總裝配圖 （2） 模具零件圖 （3） 模具總成三維圖（可選） （4） 模具主要零件三維圖（可選） 四、設計過程進度計劃 （1）第五周：完成以上設計內容中的“1-2” （2）第六周：完成以上設計內容的“3-5” （3）第七八周：完成以上設計內容的“6-7” （4）第九十周：完成以上設計內容的“8” （5）第十一、十二周：完成以上設計內容中的“9” （6）第十三、十四周：完成以上設計內容中的“10” （6）第十五周：完成以上設計內容中的“11” 指導教師批閱意見 指導教師(簽名)： 年 月 日 注：可另附A4紙 湖南工學院畢業(yè)設計(論文)工作中期檢查表 題目 空氣濾清器連接板沖孔、沖槽、落料復合模設計 學生姓名 劉林飛 班級學號 070426 專業(yè) 材料成型及控制工程 指 導 教 師 填 寫 學生開題情況 學生調研及查閱文獻情況 畢業(yè)設計（論文）原計劃有無調整 學生是否按計劃執(zhí)行工作進度 學生是否能獨立完成工作任務 學生的英文翻譯情況 學生每周接受指導的次數(shù)及時間 畢業(yè)設計（論文）過程檢查記錄情況 學生的工作態(tài)度在相應選項劃“√” □認真 □一般 □較差 尚存在的問題及采取的措施： 指導教師簽字： 年 月 日 系部意見： 負責人簽字： 年 月 日 湖南工學院2011 屆畢業(yè)設計（論文）課題任務書 系： 機械工程系 專業(yè)： 材料成型及控制工程 指導教師 和道 學生姓名 劉林飛 課題名稱 空氣濾清器連接板沖孔、沖槽、落料復合模設計 內容及任務 設計圖紙 模具總裝圖一張 全部模具零件圖紙（其中至少有一張電腦繪圖） 所有圖紙折合成0號圖不得少于3張。 設計說明書 1、資料數(shù)據(jù)充分，并標明數(shù)據(jù)出處。 2、計算過程詳細、完全。 3、公式的字母含義應標明，有時還應標注公式的出處。 4、內容條理清楚，按步驟書寫。 5、說明書要求用計算機打印。 6、設計說明書按要求格式獨立撰寫，不少于12000字。 自選一個重要模具零件編制加工工藝路線，進行相關的計算，并編制加工工藝卡和工序卡。 翻譯一篇本專業(yè)外文文獻（10000個以上印刷符號），并附譯文。 擬達到的要求或技術指標 1、保證規(guī)定的生產(chǎn)率和高質量的沖壓件的同時，力求成本低、模具壽命長。 2、設計的冷沖模必須保證操作安全、方便。 3、沖模零件必須具有良好的工藝性，即制造裝配容易、便于管理。 4、便于搬運、安裝、緊固到?jīng)_床上并且方便、可靠。 5、保證模具強度前提下，注意外形美觀，各部分比例協(xié)調。 進度安排 起止日期 工作內容 備注 2周 （2.28~3.11） 畢業(yè)調研 2周 （3.14~3.25） 集中實習 10周 （3.28~6.3） 畢業(yè)設計 1周 （6.6~6.10） 畢業(yè)答辯 主要參考資料 １、《冷沖壓工藝及模具設計》 劉心治主編重慶大學出版社 ２、《沖壓工藝及模具設計》萬戰(zhàn)勝主編 鐵道出版社 ３、《沖模設計》 吉林人民出版社 ４、《實用沖壓技術》 機工出版社 ５、《冷沖壓及塑料成型工藝與模具設計資料》 機工出版社 ６、《模具設計與制造簡明手冊》 馮炳堯等編 上海出版社 7、《沖壓工藝模具設計實用技術》　鄭家賢編　機械工業(yè)出版社 8、《實用板金沖壓工藝圖集》　梁炳文主編　機械工業(yè)出版社 9、《幾何量公差與檢測》甘永立主編　上?？茖W技術出版社 10、《機械制造專業(yè)英語》章躍主編　機械工業(yè)出版社 教研室 意見 年 月 日 系主管領導意見 年 月 日 離散應用數(shù)學 離散應用數(shù)學98(1999) 121-130 最小化模式下料問題 科林麥克迪爾米德 統(tǒng)計部門，牛津大學，南公園路一號，牛津大學OX1 3TG，英國收稿于1997年10月21日，接受于1999年2月8日 摘 要 在切割存量模式最小化問題，我們希望，以滿足盡可能少巨型卷軸卷軸切割各種客戶的需求，并進一步減少使用不同的切削模式的數(shù)量。我們專注于特殊情況，其中任何兩個客戶卷軸到一個巨型合適，但沒有三事：這個案件的興趣，部分是因為它是最簡單的情況是不平凡的，部分是因為它在實踐中可能會出現(xiàn)當一個嘗試一個解決方案，以改善迭代。 我們發(fā)現(xiàn)，該模式最小化問題是強NP難的，即使在這種特殊情況下，當inding最低廢液的基本問題是微不足道的。我們的分析主要論點集中在'均衡'的子集，并提出了涉及亞均衡的啟發(fā)式搜索方法的方法。 ? 1999 Elsevier科學BV公司保留所有權利。 關鍵詞：下料，切割模式;分區(qū); NP難;動態(tài)規(guī)劃 1 簡介 有些材料如紙，可制造性'巨無霸'卷，這是后來成為更窄輥切，以滿足客戶的需求。為了減少浪費，應選擇切割方式，以盡可能少的使用客機（見[4,7,8]）。 因此，下料問??題已基本輸入一個正整數(shù)j，不同的正整數(shù)r1的,..., Rn和D1的,...,正整數(shù)的DN，以及需要的任務是，以盡可能客機的寬度j的數(shù)為滿足客戶的卷筒寬度里迪需求對每個i = 1 ,...,，全這是其中的經(jīng)典OR問題之一。它包含了強烈的NP -完全問題三分區(qū)：因此即使巨幅大小J外面有一層氮、多項式滿足每個客戶的卷軸大小國際扶輪扶輪J / 4 < < J / 2 -看[6],p。224。因此我們不能指望在合理時間內總是能找到最優(yōu)解等問題的。 每一次不同的客戶卷軸模式是被削減，在切割機的刀需要重新設置。甲由Cn中Goulimis并在第29屆歐洲與產(chǎn)業(yè)調查研究組1996年3月有關如何找到辦法來解決上述料問題，這進一步減少了用于切割不同模式的數(shù)量問題 - 見[1,2,9] 。 一般情況下這當然是變得越來越難。為了探討擴展問題雪上加霜，我們在這里考慮一個特殊的案件中，盡量減少對客機（減少廢物），數(shù)量基本問題是微不足道的。 最小化格局： 輸入：D1的正整數(shù);的DN。 任務：在切割存量問題，即要求I型迪卷軸是，任何兩個卷軸到一個巨型做它，但沒有三，工業(yè)最低廢液，進一步減少了使用不同模式的數(shù)量。 這種特殊的情況是非常有限的部分原因是因為它似乎是最簡單的情況是完全不平凡的，部分是因為它可能會在實踐中產(chǎn)生的，當一個一個解決方案試圖改善迭代的興趣。例如，如果對目前使用的一些模式集合同意的大型卷軸和difer小卷軸而已，它在任何兩個小卷軸左邊的大型卷軸的寬度，那么當我們試圖重新分配小我們面臨的正是這種卷軸的特殊情況[16]。我們調查模式是否最小化問題還很難在這個特殊的情況，并簡要考慮辦法找到好的解決辦法。 很明顯，所需要的客機數(shù)量最少的是我的di / 2]，圓了總需求的一半，它是微不足道的一個相應的最低工業(yè)廢液。但是，它是多么容易躋身工業(yè)廢物最小的解決方案，一個能最大限度地降低使用的模式的數(shù)量，？對于這個問題的變體在沒有三個客戶卷軸它變成珍寶，但也有一些對可能不是，它是在[1]表明，問題是強NP -難問題。下面的定理加強這種不利的結果。 定理1：這個問題最小化模式是強NP -難問題。 對上述問題的理解關鍵是一個'平衡的一個子集'的概念。給定一個家庭d =(d1,dn)的非負整數(shù),表示x(d)的在任何解決方案中使用最少的廢物模式的最小數(shù)量。還有,另一個平衡的非空的子集{ 1,n } ,如果它能夠被分割成兩個集合A和B,t￡A di = 5^ieB di。因此,如果 di = 0然后單獨設置{i}是平衡的。讓v(d)是最大的數(shù)字的平衡子集兩兩相互無關的。 引理1：如果J2i di是偶數(shù),然后x(d)= n - v(d)。 如果i di 是奇數(shù)，令x(d) = i(d'),其中d1從D獲得通過增加一個額外的統(tǒng)籌的DN +1 = 1。]我們將在下一節(jié)中證明這個引理。 當與一個模式最小化所面臨的問題，我們領導的定理1和引理1以上考慮啟發(fā)式方法inding亞群平衡的好包裝。不幸的是NP -完全甚至是測試，如果一個家庭中的正整數(shù)格a1,...,an有一個平衡的一個子集。這就是問題稱為弱分區(qū)是大衛(wèi)約翰遜的NP完全列[10]，其中四分之三的NP完全獨立的證據(jù)被引用，最早在[13]。 我們希望工業(yè)亞群的平衡好包裝，但我們知道這是很難工業(yè)最佳包裝，的確是很難平衡的工業(yè)任何一個子集。自然啟發(fā)式的方法是反復尋找和刪除一個平衡的一個子集，最好是小的。其中尋求一個平衡的一個子集的方法是使用'diferencing'，這里我們再次取代其diference絕對值兩個數(shù)字 - 參見[5,12,15,17]。這種方法目前正在調查中最小的格局[16]中。另一種方法是使用一個還算快速算法，保證工業(yè)均衡的子集或子集的最小平衡：我們會看到，我們可以使用一個簡單的動態(tài)規(guī)劃方法來測試，如果有一個平衡的子集，均衡和IND一個最小的子集如果有一個，在偽多項式時間。最小的模式啟發(fā)式方法更普遍的情況下在降低庫存的問題被認為是[1,2,9,11]。 該論文的其余部分計劃如下。在下一節(jié)中，我們建立的模式之間的平衡亞群的數(shù)量和包裝的關系。接下來，我們證明我們的主要結果，這個問題最小化模式是強NP -難問題。在此之后，我們認為briely如何尋找平衡的子集，并inally我們做一些總結性發(fā)言。 2 模式，學位和平衡套 在這一節(jié)中，我們將證明引理1，其中涉及的圖案編號，包亞群平衡?英格斯。最小化的問題可以改寫格局在圖上。一個模式，涉及卷軸I型和J型卷筒之間將對應頂點頂點vi和vj的邊緣。我們將讓我們的圖，包含在任何頂點循環(huán)但不包含多個邊緣。 給定一個圖G =（V，E）對集V = {v1，....，v2}的頂點，連同非負整數(shù)重量的邊緣E，我們的家庭W時，頂點加權第六度過度的重量與我們六邊é事件的總和與任何循環(huán)，計數(shù)兩次。給定一個向量d =（d1..... dn）的正整數(shù)，我們呼吁d如果每個頂點Vi有兩人加權程度地代表公克WA網(wǎng)絡。考慮以下問題。 學位： 輸入：積極intergers d1…...甚至與dn。 任務：工業(yè)用盡可能少的邊緣一個代表網(wǎng)絡。 給定一個d組=（d1…... dn）的正整數(shù)，甚至與我二，有一個度之間的解決方案和模式MINIMI ? SATION這些自然的對應，特別是最小的邊數(shù)前者的可能等于 ×（d）項。 引理1：假設di是偶數(shù)。 設G w是任何代表工作，并考慮為G的K個節(jié)點集K表的組成部分。這當然必須有至少k - 1條邊，如果它有這個數(shù)目，因此是對K樹，那么三分之二的頂點著色表明，K是平衡的。因此，在G的邊數(shù)至少有n減去若干套組成部分的平衡。因此×（D）Jsn - 的v（d）。 為了證明反向不等式，考慮任何{V1......Vn}（Ki：i € I），其中一個最不均衡。我們將證明，有代表?怨恨網(wǎng)絡G，W使得圖G有組件（Gi：I € i）如已設立文基頂點，這些組件是這樣，如果文是平衡的，然后是一樹基如果沒有則Gi是一加一樹循環(huán)。這將完成該引理的證明。 考慮平衡集K，其中分區(qū)A U S使得YieA= ? igBdi國際能源署。我們必須表明，有對T邊緣E對K和非負權重，我們一樹T，使得對于每一個節(jié)點v€ K時，對事件邊的權重之和等于的dv（其中雙回路數(shù)）。我們使用\ K|表感應。如果A或B是空的，結果是微不足道的，因為我們必須為每個V€光那假設A和B都是非空的dv = 0。選擇任何一個和b€€阿B和不失一般性假設大^分貝。減少大的分貝?，F(xiàn)在K表\ {B}的是平衡的，我們可以感應工業(yè)適當?shù)募訖鄻?。然后加入與體重分貝邊緣抗體。 最后，考慮一個集K這是不均衡的，但就是這樣，相應的要求和是偶數(shù)。如上所述，我們可以隨時更換了使用成本的一個邊緣的diference兩個要求。因此，我們能滿足所有，但一用邊緣形成一個對K樹需求，然后添加一個循環(huán)結束的組成部分。 3 最小化模式是強NP -難 在本節(jié)中，我們證明定理1，這個問題最小化模式是強NP -難問題?？偨Y三（或舒爾三）是三，這樣的兩個之和等于第三個不同的整數(shù)集合。下面的問題可以得到更充分的描述，總結成獨特的整數(shù)分區(qū)的三倍作為。 總結三元 輸入：S1…...S3n不同的正整數(shù)。 問：能否輸入三元分割成總結？ 這個問題類似于數(shù)值匹配與目標款項，加里和Johnson [6]，第224，但額外的（令人驚訝的麻煩），條件是涉及的人數(shù)必須是不同的。 引理2：問題總結三元是強NP -完全的。 本節(jié)的大部分將用于證明上述引理，但首先，讓我們看到，它會產(chǎn)生定理1。 證明定理1（假設引理2）： 我們給一個總結，學位strightforward三倍，多項式時間減少?？紤]一個總結三元上述實例。以e =作為學位實例（2s1 …...2s3n）。由于硅是不同的正整數(shù)，也有規(guī)模不小于3套平衡。因此，（dHence由引理1，第十章x（d）^ 2n與x（d）為2n =當且僅如果s1 …...s3n可分為總結三倍 現(xiàn)在考慮的問題總結三倍，這顯然是在NP。我們將證明它是強NP -通過給從NP -完全問題限制X3C減少完成，下述，總結每個三元組在O（n3）的。 限制X3C： 輸入：一組第三季度的X元素和一個三元組集合C在十，這樣每個X的 元素完全相同3三元載。問：可以劃分為三元X是在C？ 引理3： 限制X3C問題是NP完全的。 證明 據(jù)了解，這個問題是NP完全問題，如果每個元素被限制在最多3三倍，而不是正好3 - 見加里和Johnson [6]，第221。這是很容易對注冊整潔'的實例X，?使每個元素恰好是3的三倍。 很明顯，我們能堅持，每個元素在2或3的三倍。我們可以在分區(qū)中的元素正好兩個三元組分為三個區(qū)塊的大小。對于每個塊{x，Y，Z}，添加新的元素三個x'，y'，z'及{x，y'，z'}，{x'，y，z'}，{x1， y'，z}，{x1，y，z'}。調用新的實例X'，C'的。顯然，每個X的元素是完全相同三三元在??C';和X可以被劃分在C到三倍，如果有僅當X'可以被劃分為三元在C。 引理2： 考慮一個實例X，C的限制X3C，其中| X \ = \ = CI=3q。 季度全令Y = X x {1 ,..., 7}。我們將建設一個'擴大'在Y D的收集，包含三元使得X可分為三元在C分區(qū)，當且僅當y可劃分為D中三元，接著我們將構造一個實例（秒（y）的：你們的Y總結三倍，其中每個尺寸S（y）的異O（n2），），這樣的總結恰恰三倍對應的三元組在D 形成一個二分圖G =（C，X，E）的頂點C部及X和頂點窄隙室和X GX的相鄰（即邊發(fā)射GE）的正是由于當x ?噸G中的每個頂點度是三，我們可以在多項式時間內找到一個合適的3邊染色：E - {1,2,3}。現(xiàn)在，我們每個元素x GX的分割成三份（x，1），（x，2）和（x，3）。鑒于一特里普爾T = {x，y，z}氣相色譜，令T'是三重 T= {（x，at+bt= | Ct|。 5 結束語 我們已經(jīng)看到，即使是在削減庫存問題非常有限的情況下，它是強NP -難，盡量減少使用不同模式的數(shù)量，因此，我們不能期望能夠解決偽多項式時間等問題，即使。關鍵的概念，是一個平衡的子集，我們被帶往亞群平衡的考慮包裝啟發(fā)式，從而考慮尋求這種子集NP難問題。 6 如需進一步閱讀 以下參考，也是讀者所關心的：[14]。 致 謝 我非常感謝其他參與在紅外警戒中討論的研究組成員。 參考文獻 [1] C. Aldridge, J. Chapman, R. Gower, R. Leese, C. McDiarmid, M. Shepherd, H. Tuenter, H. Wilson, A.Zinober, Pattern Reduction in Paper Cutting, Report of the 29th European Study Group with Industry,University of Oxford, March 1996. [2] J.M. Allwood, C.N. Goulimis, Reducing the number of patterns in the 1-dimensional cutting stockproblem, Internal Report of Control Section, Electrical Engineering Department, Imperial College, 1988. [3] N. Alon, O. Goldreich, J. Hastad, R. Peralta, Simple constructions of almost k-wise independent randomvariables, Random Structures and Algorithms 3 (1992) 289-304. [4] V. Chvatal, Linear Programming, Freeman, San Francisco, 1983, pp. 195-212. [5] E.G. Coffman, G.S. Lueker, Probabilistic Analysis of Packing and Partitioning Algorithms, Wiley, New York, 1991. [6] M.R. Garey, D.S. Johnson, Computers and Intractability, Freeman, San Francisco, 1979. [7] P.C. Gilmore, R.E. Gomory, A linear programming approach to the cutting-stock problem, Oper. Res. 9 (1961) 849-859. [8] P.C. Gilmore, R.E. Gomory, A linear programming approach to the cutting-stock probelem - Part II, Oper. Res. 11 (1963) 863-888. [9] C.N. Goulimis, Optimal solutions for the cutting stock problem, European J. Oper. Res. 44 (1990) 197-208. [10] D. Johnson, The NP-completeness column: an ongoing guide, J. Algorithms 3 (1982) 182-195. [11] R.E. Johnston, Rounding algorithms for cutting stock problems, J. Asian-Pacific Oper. Res. Soc. 3 (1986) 166-171. [12] N. Karmarkar, R.M. Karp, The differencing method of set partitioning, Technical Report UCB/CSD 82/113, Computer Science Division (EECS), University of California, Berkeley, 1982. [13] A. Shamir, On the cryptocomplexity of knapsack systems, Proc. 11th Ann. ACM Symp. on Theory of Computing, 1979, pp. 118-129. [14] P.E. Sweeney, E.R. Paternoster, Cutting and packing problems: a categorized, application-orientated research bibliography, J. Oper. Res. Soc. 43 (1992) 691-706. [15] L-H. Tsai, The modiied diferencing method for the set partitioning problem with cardinality conditions, Discrete Appl. Math. 63 (1995) 175-180. [16] H. Tuenter, Personal communication, 1996. [17] B. Yakir, The diferencing algorithm LDM for partitioning: a proof of a conjecture of Karmarkar and Karp, Math. Oper. Res. 21 (1996) 85-99. 16