面向紙制品包裝材料加工企業(yè)的優(yōu)化下料問題研究

1、面向紙制品包裝材料加工企業(yè)的優(yōu)化下料問題研究 摘 要 切割下料問題廣泛存在生產(chǎn)制造企業(yè)中,其工業(yè)應(yīng)用領(lǐng)域非常廣闊,本文以面向紙制品包裝材料加工企業(yè)的優(yōu)化下料問題為研究對(duì)象,開展紙卷下料的應(yīng)用研究。 本文首先介紹了課題的研究目標(biāo)、課題來源和行業(yè)背景,概括了本課題的研究?jī)?nèi)容和理論基礎(chǔ)。以一家大型紙制品包裝材料加工企業(yè)的實(shí)際生產(chǎn)作為本文的應(yīng)用研究背景,針對(duì)企業(yè)面臨的下料困難提出總體解決方案和實(shí)施步驟,首先從改進(jìn)原紙的下料規(guī)格出發(fā),優(yōu)化下料規(guī)格使之更符合實(shí)際生產(chǎn)的要求。繼而根據(jù)紙制品包裝材料的生產(chǎn)特點(diǎn)和具體切割工藝要求,研究紙制品包裝材料加工企業(yè)的優(yōu)化下料模型,建立多種原紙規(guī)格的數(shù)學(xué)模型,結(jié)合公司實(shí)際

2、生產(chǎn)數(shù)據(jù)求解昀優(yōu)下料方案并進(jìn)行結(jié)果分析。 通過研究紙制品包裝材料加工企業(yè)的切割下料問題,運(yùn)用科學(xué)的方法為企業(yè)提出優(yōu)化下料策略,尋找昀優(yōu)的下料方案, 改進(jìn)下料效果,達(dá)到改善企業(yè)的生產(chǎn)管理、提高競(jìng)爭(zhēng)力和增強(qiáng)應(yīng)變能力的目的。關(guān)鍵詞:紙制品包裝,切割下料問題,組合優(yōu)化 - i - i abstract cutting stock problem csp is one of the most widely studied problems in the applied research. it exists in a variety of industries and enjoys great popu

3、larity of researchers to a large extend. in this thesis, an applied research of the cutting stock problem in the paper packing industry is conducted so that an improvement of material utilization could be achieved the aim of the research and the background information of the paper packing industry a

4、re presented in the first part. then a study review on cutting stocking problem is described in detailin the main part of the thesis, the author conducts a complete study on the csp in a paper packing company. in order to solve the difficulties of csp in the company, an optimal approach is concreted

5、 in two steps: firstly, an optimization research of the stock sizes is given after product study and analysis. secondly, a mathematical model of csp with multi stock sizes is specifically developed basing on the companys producing and cutting specification. then two stereotypes of csp in the paper p

6、acking company are solved and the optimization cutting patterns are found. the optimal method is proved feasible and effectiveat last, an overall review of this research is given, pointing out the trends of csp study keywords: paper packing industry, cutting stock problem, optimization - ii - ii 目 錄

7、 摘 要.i abstract.ii 第 1 章 緒論.1 1.1 研究目標(biāo)和選題意義.1 1.2 課題來源和研究?jī)?nèi)容.1 1.2.1 課題來源.1 1.2.2 研究?jī)?nèi)容.2 1.3 研究路線.3 第 2 章 優(yōu)化下料問題概述.4 2.1 優(yōu)化下料問題的應(yīng)用領(lǐng)域4 2.2 優(yōu)化下料問題的分類.5 2.3 本文研究的行業(yè)背景.6 2.3.1 優(yōu)化下料問題與包裝行業(yè)的關(guān)系6 2.3.2 包裝材料加工行業(yè)面臨的下料困難.7 2.4 本章小結(jié).9 第 3 章 優(yōu)化下料問題的研究綜述10 3.1 優(yōu)化下料問題的研究現(xiàn)狀.10 3.1.1 優(yōu)化下料問題的分類描述.10 3.1.2 優(yōu)化下料問題的研究方法.

8、12 3.2 二維排樣問題的研究現(xiàn)狀.14 3.2.1 二維排樣問題的分類14 3.2.2 二維矩形排樣的分類15 3.2.3 矩形件優(yōu)化排樣問題的研究綜述.16 3.3 本章小結(jié).19 第 4 章 應(yīng)用研究背景與整體對(duì)策20 4.1 公司概況.20 4.2 公司面臨的下料困難21 4.2.1 產(chǎn)品種類繁多,原紙品種和規(guī)格復(fù)雜.21 4.2.2 原紙進(jìn)口比例高,訂購(gòu)時(shí)間長(zhǎng).22 4.3 解決下料困難的整體對(duì)策.22 4.3.1 產(chǎn)品分析與歸類.23 4.3.2 優(yōu)化原紙規(guī)格,提高原材料的利用效率.29 4.3.3 確定昀優(yōu)下料方案.33 - iii - iii 4.4 本章小結(jié).33 第 5

9、章 紙制品包裝材料企業(yè)的下料模型研究.34 5.1 紙制品包裝材料加工行業(yè)的現(xiàn)狀和加工特點(diǎn).34 5.2 紙卷優(yōu)化下料問題的提出.36 5.3 紙卷的下料特點(diǎn)與工藝要求37 5.4 紙制品包裝材料加工的優(yōu)化下料技術(shù).41 5.4.1 優(yōu)化下料的設(shè)計(jì)思想41 5.4.2 基于多種原紙寬度規(guī)格的條帶生成42 5.5 面向紙制品包裝材料加工的下料模型.44 5.5.1 建立多種原紙寬度規(guī)格的下料數(shù)學(xué)模型.44 5.5.2 數(shù)學(xué)模型適用性分析46 5.5.3 切割方式的調(diào)整.47 5.6 計(jì)算實(shí)例.47 5.6.1 實(shí)例一48 5.6.2 實(shí)例二50 5.6.3 結(jié)果分析.52 5.7 本章小結(jié).53

10、 第 6 章 總結(jié)與展望54 注 釋56 參考文獻(xiàn).58 發(fā)表論文清單62 致 謝63- iv - iv 圖表目錄 表2-1:優(yōu)化下料問題的應(yīng)用領(lǐng)域4 表2-2: 包裝行業(yè)的切割類型和應(yīng)用舉例7 表4-1:產(chǎn)品產(chǎn)量和品種數(shù)量情況表23 表4-2:產(chǎn)品種類與原紙品種的關(guān)系表.29 表4-3:375g類的原紙規(guī)格改進(jìn)方案.30 表4-4:325g類產(chǎn)品的原紙改進(jìn)方案.30 表4-5:250g類產(chǎn)品的原紙改進(jìn)方案.31 表4-6:270g類產(chǎn)品的原紙改進(jìn)方案.32 表4-7:低克重產(chǎn)品的原紙改進(jìn)方案32 表5-1:原紙克重與邊損量關(guān)系.38 表5-2:按經(jīng)驗(yàn)給出的若干下料方式45 表5-3:第一組產(chǎn)

11、品數(shù)據(jù).48 表5-4:第一組原紙數(shù)據(jù).49 表5-5:第一組產(chǎn)品生成的條帶數(shù)據(jù)49 表5-6:實(shí)例一的優(yōu)化方案.49 表5-7:第二組產(chǎn)品數(shù)據(jù).50 表5-8:第二組原紙數(shù)據(jù).50 表5-9:第二組產(chǎn)品生成的條帶數(shù)據(jù)51 表5-10:實(shí)例二在沒有庫存限制條件下的優(yōu)化方案.51 表5-11:實(shí)例二在庫存限制條件下的優(yōu)化方案52圖1-1:本文的研究路線.3 圖2-1:平面套材問題的分類.6 圖3-1:卷材切割.16 圖3-2:直通切割16 圖3-3:正交切割.16 圖4-1:產(chǎn)品分類圖.24 圖4-2:375g類產(chǎn)品的產(chǎn)量分布情況.25 圖4-3:325g類產(chǎn)品的產(chǎn)量分布情況.25 圖4-4:2

12、50g類產(chǎn)品的產(chǎn)量分布情況.26 圖4-5:270g類產(chǎn)品的產(chǎn)量分布情況.26 圖4-6:75g sd類產(chǎn)品的產(chǎn)量分布情況27 圖4-7:75g kt類產(chǎn)品的產(chǎn)量分布情況27 圖4-8:97g類產(chǎn)品的產(chǎn)量分布情況28 圖4-9:102g類產(chǎn)品的產(chǎn)量分布情況.28 圖4-10:157g類產(chǎn)品的產(chǎn)量分布情況.29 圖5-1:兩種切割樣式38 圖5-2:兩種排放方式39 圖5-3:連續(xù)排放方式42 - v - v暨南大學(xué)碩士學(xué)位論文面向紙制品包裝材料加工企業(yè)的優(yōu)化下料問題研究 第 1 章 緒論 1.1 研究目標(biāo)和選題意義 在生產(chǎn)實(shí)踐中,許多制造行業(yè)經(jīng)常遇到切割下料問題(cutting stock p

13、roblem,簡(jiǎn)稱csp),通常是指在一組給定的原材料上,盡可能多地排放需要的1零件或產(chǎn)品,使得原材料的耗用量昀低或者利用率昀大,以減少?gòu)U料。 工業(yè)和建筑業(yè)的許多原材料,例如圓鋼、圓木、鋼筋、鐵板、薄鐵皮、塑料板以及紙張、布匹等,一般都存在下料或排樣的問題。它是針對(duì)如何使切割對(duì)象在有限的空間中昀有效地利用空間布局而衍生出來的問題, 也就是將待切割對(duì)象擺放在一定規(guī)格的大件原料表面上進(jìn)行套材切割,目的使原料損耗率昀低。 加工制造過程中的優(yōu)化下料問題是制造系統(tǒng)資源優(yōu)化利用問題之一,一個(gè)好的下料計(jì)算方法和下料方案,可以提高原材料的使用率、降低生產(chǎn)成本,從而提高產(chǎn)品的市場(chǎng)競(jìng)爭(zhēng)力。 原材料成本高、下料效果

14、差已經(jīng)成為制約紙制品包裝材料加工行業(yè)發(fā)展的瓶頸之一。為此,本文擬在一家大型紙制品包裝材料加工企業(yè)進(jìn)行應(yīng)用研究,針對(duì)該企業(yè)面臨的下料困難,提出整體對(duì)策方案,然后基于紙制品包裝材料加工行業(yè)的現(xiàn)狀和生產(chǎn)特點(diǎn),結(jié)合加工工藝的要求和其他限制條件,采用優(yōu)化下料技術(shù)為同類企業(yè)研究?jī)?yōu)化下料的數(shù)學(xué)模型并求解昀優(yōu)下料方案, 以達(dá)到提高原材料利用率、指導(dǎo)生產(chǎn)的目的。 1.2 課題來源和研究?jī)?nèi)容 1.2.1 課題來源 本文以一家生產(chǎn)煙草包裝材料為主的大型紙制品包裝企業(yè)為研究背景,近年,隨著煙草行業(yè)的繁榮,公司的生產(chǎn)規(guī)模得到很大的提高,產(chǎn)品品種和業(yè)務(wù)種類向多元化發(fā)展。隨著市場(chǎng)競(jìng)爭(zhēng)加劇以及公司進(jìn)行組織變革,生產(chǎn)管理方面的

15、問題逐漸凸顯,公司領(lǐng)導(dǎo)越來越意識(shí)到原材料成本高、下料困難是制約公司發(fā)展的瓶頸之一。因此,在公司領(lǐng)導(dǎo)的大力支持和幫助下,本文作者有幸到企業(yè)進(jìn)行實(shí)- 1 - 1暨南大學(xué)碩士學(xué)位論文面向紙制品包裝材料加工企業(yè)的優(yōu)化下料問題研究 習(xí)調(diào)研并開展優(yōu)化下料問題的研究。通過熟悉生產(chǎn)流程總結(jié)歸納出實(shí)際的切割工藝要求和下料限制條件,分析企業(yè)的產(chǎn)品生產(chǎn)和原材料的需求狀況,為企業(yè)改進(jìn)下料決策,尋找有效求解昀優(yōu)下料方案的方法。 1.2.2 研究?jī)?nèi)容 本文運(yùn)用定性和定量方法,結(jié)合紙制品包裝材料加工企業(yè)的切割工藝要求和生產(chǎn)限制條件,進(jìn)行紙卷優(yōu)化下料問題的應(yīng)用研究,為企業(yè)提供改善經(jīng)營(yíng)的方法和途徑,主要完成以下內(nèi)容: (1)

16、第一章:概括本課題的選題意義和研究目標(biāo),簡(jiǎn)述本課題的來源、研究?jī)?nèi)容和研究路線。 (2) 第二章:概述優(yōu)化下料問題、應(yīng)用領(lǐng)域和分類,介紹優(yōu)化下料問題與包裝材料加工行業(yè)的關(guān)系及應(yīng)用情況,總結(jié)該行業(yè)在下料管理方面存在的問題和制約因素。 (3) 第三章:詳細(xì)綜述優(yōu)化下料問題的理論研究,重點(diǎn)概述二維矩形排樣問題的研究現(xiàn)狀,為本課題開展應(yīng)用研究提供必要的理論基礎(chǔ),運(yùn)用有關(guān)知識(shí)解決紙卷切割下料的問題。 (4) 第四章:以一家大型紙制品包裝材料加工企業(yè)為背景開展應(yīng)用研究,針對(duì)企業(yè)的下料困難提出整體對(duì)策,從兩個(gè)層次解決應(yīng)用中的下料問題。首先,選擇合適的下料原料規(guī)格;其次,尋找昀佳的下料方案。 (5) 第五章:論

17、述紙制品包裝材料加工的生產(chǎn)特點(diǎn),在滿足實(shí)際切割工藝要求的前提下為同類企業(yè)研究?jī)?yōu)化下料模型,建立多種原紙寬度規(guī)格的數(shù)學(xué)模型,運(yùn)用線性規(guī)劃求解,以公司的實(shí)際數(shù)據(jù)為求解實(shí)例并分析結(jié)果。 (6) 第六章:對(duì)本研究進(jìn)行總結(jié)和展望,指出本研究的不足之處和后續(xù)研究工作的方向。- 2 - 2暨南大學(xué)碩士學(xué)位論文面向紙制品包裝材料加工企業(yè)的優(yōu)化下料問題研究 1.3 研究路線 本文的研究思路是以一家大型紙制品包裝材料加工企業(yè)為背景進(jìn)行應(yīng)用研究,針對(duì)企業(yè)面臨的下料困難提出整體對(duì)策:首先分析公司的產(chǎn)品生產(chǎn)情況,改進(jìn)原材料下料規(guī)格,使之更適于生產(chǎn);其次基于同尺寸產(chǎn)品的大規(guī)模優(yōu)化排樣研究的基礎(chǔ)上,為紙制品包裝材料加工行業(yè)

18、的切割下料問題提出優(yōu)化下料技術(shù),研究多種原紙寬度規(guī)格的數(shù)學(xué)模型,運(yùn)用線性規(guī)劃求解紙卷下料的實(shí)際應(yīng)用問題,用理論指導(dǎo)實(shí)踐生產(chǎn)。論述企業(yè)具體的優(yōu)化下料問題的概述和 下料問題和限制 分類 條件開展面向紙制品提出解決下料問課題的行業(yè)包裝材料加工企背景 題的整體對(duì)策和業(yè)的應(yīng)用研究 實(shí)施步驟優(yōu)化下料的 建立紙卷下研究綜述 料的數(shù)學(xué)模型并求解目標(biāo):解決優(yōu)化下料問題, 改善紙卷的下料效果圖 1-1:本文的研究路線figure 1-1: the research route of this thesis - 3 - 3暨南大學(xué)碩士學(xué)位論文面向紙制品包裝材料加工企業(yè)的優(yōu)化下料問題研究 第 2 章 優(yōu)化下料問題概述

19、 2.1 優(yōu)化下料問題的應(yīng)用領(lǐng)域 在工業(yè)應(yīng)用領(lǐng)域上,優(yōu)化下料問題有多種提法,例如切割問題(trim loss problem或cutting stock problem)、排樣問題(assortment problem)和裝箱問題(bin packing problem)等。優(yōu)化下料問題涉及面廣,例如機(jī)械、建筑、2鋼鐵、船舶、車輛、玻璃、造紙、皮革等許多行業(yè),其應(yīng)用舉例見表 2-1 。這些行業(yè)一方面是國(guó)民經(jīng)濟(jì)的重要支柱,同時(shí)又是環(huán)境污染的主要源頭,優(yōu)化利用物料資源可以能為企業(yè)節(jié)約巨額資金,而且減少?gòu)U棄物的產(chǎn)生,有助保護(hù)環(huán)境。由于優(yōu)化下料問題對(duì)于企業(yè)控制生產(chǎn)成本、提高競(jìng)爭(zhēng)力有著極其重要的影響,因

20、而吸引了不少學(xué)者對(duì)這個(gè)問題進(jìn)行研究。 表 2-1:優(yōu)化下料問題的應(yīng)用領(lǐng)域table 2-1: applied fields of cutting stock problem 行業(yè)分類 應(yīng)用舉例 鈑金件加工業(yè) 廚房、家用電器鈑金件、造船工業(yè)鈑金件等 服裝行業(yè) 布料、皮革排樣,布料皮革定級(jí)中的優(yōu)化排樣 造紙業(yè)及玻璃業(yè) 辦公用紙、財(cái)務(wù)用紙的裁制,玻璃切割 家具行業(yè) 木材制品 印刷業(yè)排版 書刊、報(bào)紙排版 貿(mào)易、貨運(yùn) 集裝箱裝貨 來源:賈志欣,排樣問題的分類研究,2004(4):p8 優(yōu)化下料問題的整體描述: (1)有兩組基本數(shù)據(jù),一組是大的原材料的尺寸(一維或多維),另一組是小的零件的尺寸;(2)將小

21、的零件在原材料上進(jìn)行合理的幾何組合,切割下料;如何確定下料排樣方案,以使得材料利用率昀高。 在上述行業(yè)中,提高原材料利用率對(duì)于降低成本有至關(guān)重要的意義,因此優(yōu)化下料問題受到廣泛關(guān)注。 通過尋找合理的下料方案,將不同規(guī)格、需求數(shù)量的零件或產(chǎn)品進(jìn)行合理套- 4 - 4暨南大學(xué)碩士學(xué)位論文面向紙制品包裝材料加工企業(yè)的優(yōu)化下料問題研究 裁才能有效減少余廢料,提高原材料的利用效率,直接降低產(chǎn)品成本,為企業(yè)帶來經(jīng)濟(jì)效益。因此,優(yōu)化下料問題一直是國(guó)內(nèi)外研究的重點(diǎn)和熱點(diǎn)。優(yōu)化下料問題是組合優(yōu)化中的一類典型問題,從數(shù)學(xué)的角度說,計(jì)算復(fù)雜性高,因此國(guó)內(nèi)外對(duì)優(yōu)化下料問題的研究主要集中在從數(shù)學(xué)理論角度出發(fā),注重算法上

22、的研究,在盡量短時(shí)間內(nèi)尋求這類問題的昀優(yōu)解。 然而切割下料問題在許多制造企業(yè)實(shí)際生產(chǎn)中廣泛出現(xiàn),由于行業(yè)不同,優(yōu)化下料問題的性質(zhì)也有所不同,從而采用的解決方法也不同。優(yōu)化下料技術(shù)在實(shí)際應(yīng)用中并不理想,因?yàn)椴煌愋推髽I(yè)的生產(chǎn)條件和工藝特點(diǎn)產(chǎn)生更多限制條件,大大增加了下料排樣問題的求解難度,例如產(chǎn)品品種與規(guī)格的數(shù)量規(guī)模、原材料的定級(jí)、生產(chǎn)流程、運(yùn)輸條件的限制、訂單的優(yōu)先次序等。如果能夠結(jié)合具體的行業(yè)特點(diǎn),結(jié)合企業(yè)的實(shí)際生產(chǎn)情況實(shí)現(xiàn)優(yōu)化下料問題,有助于提高生產(chǎn)效率,有利于加強(qiáng)企業(yè)的成本管理和提高企業(yè)的市場(chǎng)競(jìng)爭(zhēng)力而言,而且節(jié)約原料和保護(hù)環(huán)境。 2.2 優(yōu)化下料問題的分類 由于不同學(xué)科的邏輯思維造成切割

23、下料問題在文獻(xiàn)里出現(xiàn)不同的表達(dá)方式,dyckhoff(1990)總結(jié)了優(yōu)化下料問題的類型,對(duì)各類問題的名稱以及分類標(biāo)準(zhǔn)進(jìn)行了系統(tǒng)分類,得到大多數(shù)研究人員的認(rèn)同。常說的下料問題指的是狹義下料問題,它是指原材料有空間尺寸限制的問題,根據(jù)零件的空間布局維數(shù)劃分為一維切割、二維排樣和三維布局;根據(jù)待排零件的規(guī)格、套材方式、工藝要求等限制包括以下問題:切割下料或者邊角余料問題;排樣或布局問題;裝箱或堆載問題;車輛裝貨或物品包裝問題。廣義下料問題包括了狹義下料問題和非空間尺寸的問題,例如資金預(yù)算、貨幣交換、流水線平衡、數(shù)據(jù)存儲(chǔ)的內(nèi)存分配問題等。針對(duì)狹義下料問題,可根據(jù)維數(shù)、布局種類、大件原料種類和小件零件

24、種類四方3面組合得出不同的切割下料問題。例如 1/v/v/r是指利用不同大件原料切割生產(chǎn)大量相同形狀的小件零件或產(chǎn)品的一維下料問題。根據(jù)大件原料的空間布局和小件的形狀特點(diǎn),平面套材問題一般分為一維切割、二維排樣和三維布局的問題,如圖 2-1所示(括號(hào)內(nèi)是應(yīng)用舉例): - 5 - 5暨南大學(xué)碩士學(xué)位論文面向紙制品包裝材料加工企業(yè)的優(yōu)化下料問題研究 單一原材料 一維線材 (圓鋼、圓木、鋼筋切割) 一維切割 多種原材料 一維線材 (木材定級(jí)切割) 規(guī)則矩形 (辦公用紙、財(cái)務(wù)用紙、玻璃切割、印刷排版) 單一原材料 不規(guī)則形狀(布料、皮革套材) 二維排樣 平面規(guī)則矩形 (木板、家具的定級(jí)套材)套材多種原

25、材料 問題 不規(guī)則形狀(布料皮革定級(jí)套材) 規(guī)則方體單一原材料 不規(guī)則立體三維布局 (集裝箱貨物裝載) 規(guī)則方體 多種原材料 不規(guī)則立體圖 2-1:平面套材問題的分類 figure2-1: classification of cutting stock problem 2.3 本文研究的行業(yè)背景 2.3.1 優(yōu)化下料問題與包裝行業(yè)的關(guān)系 包裝是商品的重要組成部分,在現(xiàn)代科技與經(jīng)濟(jì)高速發(fā)展的時(shí)代,包裝的功能、性質(zhì)與作用,得到了充分和廣泛的展現(xiàn)。包裝行業(yè)是涵蓋科技、經(jīng)濟(jì)、文化、市場(chǎng)和生活等多方面的綜合性產(chǎn)業(yè),是現(xiàn)代服務(wù)業(yè)和先進(jìn)制造業(yè)相交融的配套服務(wù)行業(yè),是經(jīng)濟(jì)及其持續(xù)性發(fā)展的支柱工業(yè)。我國(guó)包裝生產(chǎn)

26、企業(yè),正向高檔化、規(guī)模化方向發(fā)展,通過不斷引進(jìn)先進(jìn)的生產(chǎn)設(shè)備、研發(fā)新產(chǎn)品以及不斷進(jìn)行技術(shù)改造與創(chuàng)新形成集團(tuán)化經(jīng)營(yíng)的企業(yè),實(shí)現(xiàn)專業(yè)化分工,達(dá)到工業(yè)化水平。包裝行業(yè)覆蓋面廣、延伸性強(qiáng),涉及包裝機(jī)械、材料加工和印刷等行業(yè)。包裝產(chǎn)品的種類繁多,根據(jù)包裝材料性質(zhì)分為紙制包裝、塑料包裝、金屬包裝、玻璃包裝、木制包裝;按包裝的對(duì)象分類,可劃分為食品包裝、醫(yī)藥包裝、煙草包裝、瓦楞箱包、禮品包裝等。- 6 - 6暨南大學(xué)碩士學(xué)位論文面向紙制品包裝材料加工企業(yè)的優(yōu)化下料問題研究 表2-2: 包裝行業(yè)的切割類型和應(yīng)用舉例 table 2-2: classification of csp in packing ind

27、ustry 包裝分類 切割類型 應(yīng)用舉例 紙制品包裝 規(guī)則矩形切割 紙袋、紙盒、瓦楞箱包 塑料包裝 規(guī)則矩形切割 各類包裝袋、食品飲料軟包裝 金屬包裝 規(guī)則矩形或其他圖形切割 鐵盒、飲料罐身 木制包裝 規(guī)則矩形或其他圖形切割 木箱、圓桶 從表2-2可以看出,包裝材料加工的生產(chǎn)過程經(jīng)常涉及切割下料問題,例如木制包裝是將大塊木材切割生成矩形木板,金屬包裝是將金屬薄片或者鋼板進(jìn)行套材大量生產(chǎn)矩形或者其他規(guī)則圖形的零件,塑料或紙制品包裝加工企業(yè)利用塑料薄膜及紙卷下料。不論生產(chǎn)哪種包裝材料的企業(yè),其加工和生產(chǎn)過程都是在將大件原料按批生產(chǎn),加工成規(guī)格相同的包裝零件,下料特點(diǎn)是原材料規(guī)格大,待排零件的需求量

28、大、規(guī)格相對(duì)較少。木制和金屬等包裝材料加工企業(yè)多使用矩形板材,定級(jí)切割,原料規(guī)格少,切割范圍受裁床或者切割刀刃限制,每次切割產(chǎn)生的多個(gè)零件。塑料和紙制品包裝材料企業(yè)使用卷材下料,原料規(guī)格種類多。根據(jù)dyckhoff的分類體系,前者的切割下料問題屬于2/b/i/r問題,即在大件原料上進(jìn)行優(yōu)化排樣的二維排樣問題,后者屬于2/v/i/r問題,即選擇合適的大卷原料進(jìn)行套材規(guī)劃的二維排樣問題。兩者既有區(qū)別又有聯(lián)系,前者是在固定規(guī)格的矩形原材料上選擇合適的排樣方案,每次切割可生產(chǎn)多件規(guī)格相同的矩形零件或產(chǎn)品,使得原材料的耗用量昀少; 而后者則是針對(duì)不同規(guī)格的零件或產(chǎn)品在眾多原材料規(guī)格中進(jìn)行組合下料生產(chǎn),每

29、次切割只產(chǎn)生一個(gè)零件或產(chǎn)品,但按批量生產(chǎn)、產(chǎn)品數(shù)量大,使得余殘料昀少。 2.3.2 包裝材料加工行業(yè)面臨的制約因素 通過技術(shù)改造和創(chuàng)新,包裝材料加工行業(yè)的產(chǎn)品不斷應(yīng)用新型材料,采用先進(jìn)設(shè)備和改善加工工藝,產(chǎn)品品質(zhì)不斷提升。生產(chǎn)高品質(zhì)的包裝材料包括運(yùn)用先進(jìn)的生產(chǎn)設(shè)備、優(yōu)質(zhì)的原材料、新穎的設(shè)計(jì)、成熟的工藝和柔性的生產(chǎn)管理。雖然該行業(yè)在引進(jìn)設(shè)備方面達(dá)到國(guó)際先進(jìn)水平,產(chǎn)品模仿能力強(qiáng),具備了良好的硬件基礎(chǔ)。但是企業(yè)的自主研發(fā)能力不強(qiáng),核心技術(shù)、設(shè)備和原輔材料長(zhǎng)期依賴進(jìn)口,在組織生產(chǎn)時(shí),原材料成本高,管理水平低,導(dǎo)致利潤(rùn)率偏低。一般而言,- 7 - 7暨南大學(xué)碩士學(xué)位論文面向紙制品包裝材料加工企業(yè)的優(yōu)化下

30、料問題研究 包裝材料加工過程使用的原材料比較單一且按批量生產(chǎn),原材料下料方案的優(yōu)劣既決定了原材料利用效率的高低,也決定了生產(chǎn)加工時(shí)間的長(zhǎng)短。在實(shí)際生產(chǎn)中,包裝材料加工企業(yè)在下料排樣和物料管理方面普遍存在以下問題: (1) 下料排樣問題 包裝材料加工生產(chǎn)使用的原材料是整卷原料或者大型矩形板材,下料規(guī)模大,下料目的追求使用原材料數(shù)量昀少或者余殘料昀少, 切割問題屬于二維矩形排樣問題。此類問題的下料難度較高,既要滿足切割工藝的限制,又要滿足原材料規(guī)格面積、長(zhǎng)度和寬度上的限制。但是在包裝材料加工行業(yè)的下料方式主要是采用人工下料,依靠下料師傅的人工經(jīng)驗(yàn)。人工排樣下料方式的缺點(diǎn)在于一次只能完成對(duì)單一或少數(shù)

31、幾種產(chǎn)品的排樣,多種的產(chǎn)品進(jìn)行混排效果差,而且排樣的結(jié)果完全依賴于排料師傅的經(jīng)驗(yàn),效率低而且容易出錯(cuò)。原材料利用率低的直接結(jié)果是原材料浪費(fèi)情況嚴(yán)重、生產(chǎn)成本高居不下;人工排料低效耗時(shí),降低了企業(yè)對(duì)市場(chǎng)變化的響應(yīng)速度,延長(zhǎng)了生產(chǎn)加工時(shí)間,因而更談不上以有競(jìng)爭(zhēng)力的產(chǎn)品價(jià)格、昀短的交貨期和滿意的客戶服務(wù)參與市場(chǎng)競(jìng)爭(zhēng)。 (2) 物料需求問題 在生產(chǎn)旺季時(shí),采用人工排料方式無法在安排生產(chǎn)前進(jìn)行試排,原材料規(guī)格多,各種規(guī)格的需求對(duì)于企業(yè)來說是隨機(jī)的。但是包裝原材料進(jìn)口比例較高,特別是紙制品包裝企業(yè),原紙的采購(gòu)周期長(zhǎng)。為了確保生產(chǎn),避免因材料短缺而損失訂單,企業(yè)要么大量增加原材料庫存,造成庫存和管理費(fèi)用劇增

32、和資金積壓;要么是在庫存不足時(shí)由采購(gòu)部門緊急訂貨,給采購(gòu)、財(cái)務(wù)和生產(chǎn)部門造成了巨大的壓力,停工待料的情況屢次發(fā)生,嚴(yán)重耽誤了生產(chǎn)進(jìn)度。另外,顧客的需求變化、產(chǎn)品規(guī)格增多,導(dǎo)致原材料規(guī)格隨之增多,企業(yè)在生產(chǎn)管理中經(jīng)常面臨以下困境:一方面,某種規(guī)格的原材料庫存數(shù)量大,但不能馬上用于生產(chǎn),占用資金和庫存空間;另一方面,某種產(chǎn)品規(guī)格卻找不到合適的原材料進(jìn)行加工生產(chǎn),延誤交貨日期。這樣,長(zhǎng)期導(dǎo)致企業(yè)的生產(chǎn)任務(wù)在原材料需求無法準(zhǔn)確預(yù)測(cè)、原料成本難以準(zhǔn)確估計(jì)的情況下開展,一旦出現(xiàn)緊急情況,不但談不上生產(chǎn)按計(jì)劃進(jìn)行、作業(yè)流程按預(yù)期控制,更可能失去市場(chǎng)機(jī)會(huì),流失顧客。 - 8 - 8暨南大學(xué)碩士學(xué)位論文面向紙制

33、品包裝材料加工企業(yè)的優(yōu)化下料問題研究 2.4 本章小結(jié) 基于上述對(duì)csp在包裝材料加工行業(yè)的應(yīng)用描述,可知切割下料問題與該行業(yè)的關(guān)系密切。包裝材料加工行業(yè)的下料效果普遍偏低,成為制約行業(yè)發(fā)展的主要因素之一,其中以紙制品包裝材料加工行業(yè)的影響昀為嚴(yán)重。下料計(jì)算復(fù)雜,耗費(fèi)生產(chǎn)計(jì)劃人員的大量精力,得到的排樣方案材料利用率往往不高,人工下料的浪費(fèi)驚人且容易出錯(cuò)。針對(duì)上述包裝材料加工行業(yè)面臨的下料困難,如果能夠解決該行業(yè)的csp問題,必定能為企業(yè)乃至整個(gè)行業(yè)注入新的活力,取得長(zhǎng)足發(fā)展。本文旨在研究包裝材料加工行業(yè)中紙制品包裝的優(yōu)化下料問題,研究卷材優(yōu)化的切割下料問題,為企業(yè)尋找有效控制和降低生產(chǎn)成本的方

34、法。 - 9 - 9暨南大學(xué)碩士學(xué)位論文面向紙制品包裝材料加工企業(yè)的優(yōu)化下料問題研究 第 3 章 優(yōu)化下料問題的研究綜述 3.1 優(yōu)化下料問題的研究現(xiàn)狀 優(yōu)化下料問題(cutting stock problem,以下簡(jiǎn)稱csp)是如何使研究對(duì)象在有限的空間中做昀有效的空間利用所衍生出來的問題。 關(guān)于csp的研究,昀早見于俄羅斯經(jīng)濟(jì)學(xué)家康托洛維奇(kantorovich,1939)發(fā)表的文章,該文中論4述了一維csp問題并建立數(shù)學(xué)模型 。 60年代初, gilmore和gomory (1961, 1963,1965)在這個(gè)研究領(lǐng)域做出了重要的奠基性工作,在他們的文章中,用列生成技術(shù)解決了一維cs

35、p,并對(duì)二維甚至多維的csp做了啟發(fā)式的工作。實(shí)踐證明這種方法能有效解決一維切割下料問題,但是不適用于切割方式較多、規(guī)模較大的下料問題,隨后的研究多數(shù)都是在此研究基礎(chǔ)上提出改進(jìn)和發(fā)展。到了 70年代,計(jì)算機(jī)科技的發(fā)展以及諸如線性規(guī)劃、運(yùn)籌學(xué)理論等現(xiàn)代優(yōu)化技術(shù)的發(fā)展,使得csp的研究可付諸生產(chǎn)實(shí)踐,優(yōu)化下料問題又引起許多學(xué)者的濃厚興趣,國(guó)內(nèi)近幾年來在優(yōu)化下料問題上也進(jìn)行了大量的研究。但是由于優(yōu)化排樣問題已被證實(shí)np完備問題,加上實(shí)際問題的限制條件不同使得問題更加復(fù)雜,至今沒有通用方法來解決。1988 年在euro ix/tims xxviii國(guó)際會(huì)議上,專門成立了下料問5題興趣小組sicup(s

36、pecial interest group on cutting and packing problem)。 3.1.1 優(yōu)化下料問題的研究分類描述 (1) 一維下料方案 對(duì)于一維下料方案優(yōu)化問題,即將k種零件,長(zhǎng)度和需求數(shù)量分別為l 和b(ii i=1,2,k),在長(zhǎng)度為l的原材料上排放,如何使所用原材料昀少,這個(gè)問題可以拆分為三種情況來分析: 只有少數(shù)幾種零件,例如k10,每種零件的數(shù)量較少。 有很多種零件,每種零件的數(shù)量不大。 零件種數(shù)不多,但每種零件的數(shù)量很大。 - 10 - 10暨南大學(xué)碩士學(xué)位論文面向紙制品包裝材料加工企業(yè)的優(yōu)化下料問題研究 對(duì)于可用分支定界法求解。是典型的一維裝箱

37、問題,屬于npc類問題。當(dāng)零件種數(shù)很大時(shí),求解規(guī)模大,時(shí)間長(zhǎng)。則需考慮零件的長(zhǎng)度搭配以使原材料利用率較高,常用啟發(fā)式規(guī)則和基于線性規(guī)劃的方法求解,但零件的長(zhǎng)度搭配是一個(gè)背包問題。 (2) 二維排樣問題 +對(duì)于二維排樣優(yōu)化問題,給定n個(gè)零件的集合pp ,p,p ,n z ,每12 n個(gè)零件具有b 0面積,另有面積為a b ,數(shù)量不限的板材,如何排樣使所用板i i材數(shù)量昀小,將其分解為以下三個(gè)獨(dú)立問題來考查: 將零件放入板材中,每塊板材中零件的面積之和不大于板材的面積。 零件為矩形,板材為矩形,要求將零件互不重疊地放入板材,使所用板材數(shù)昀小。 零件具有任意復(fù)雜的平面形狀,板材為矩形,要求將零件互不

38、重疊地放入板材,使材料利用率昀高,并滿足一定工藝要求。 說明不管待排零件的形狀復(fù)雜程度,難度不低于裝箱問題;是二維裝箱6問題,屬于np完備問題 ,需滿足矩形零件間互不重疊且在板材矩形區(qū)域內(nèi);是異形零件在矩形板材上排放,需要考慮圖形運(yùn)算、合理拼接,并滿足一些與實(shí)際應(yīng)用相關(guān)的約束條件。 (3) 三維布局問題 對(duì)于三維布局優(yōu)化問題,常見的有集裝箱裝貨問題,需要在長(zhǎng)、寬、高3個(gè)維度求解綜合昀優(yōu), 同時(shí)還需考慮箱體本身的承重性、箱體搬運(yùn)的難易性、昀大載重量、某些貨物之間的隔離等。 從上述對(duì)優(yōu)化下料問題的研究分類描述可以看出,排樣問題的幾何特性和組合特性共同形成了問題的求解難度和計(jì)算的復(fù)雜度。處理優(yōu)化下料

39、問題時(shí)一般拆分為優(yōu)化排樣和套排規(guī)劃兩個(gè)求解步驟。優(yōu)化排樣主要是尋找在原材料上的合理布局,得到新的單個(gè)原材料上的合理排樣方式。套排規(guī)劃是對(duì)各種排樣方式作合理選擇、規(guī)劃,以達(dá)到整體昀優(yōu)。 優(yōu)化下料問題的求解主要分為基于線性規(guī)劃或整數(shù)規(guī)劃的算法產(chǎn)生昀優(yōu)解和結(jié)合啟發(fā)式算法求近似昀優(yōu)解的兩種算法策略。 整數(shù)規(guī)劃的求解主要是利用分支定界法求解,求解的效果取決于分支的模式和上下- 11 - 11暨南大學(xué)碩士學(xué)位論文面向紙制品包裝材料加工企業(yè)的優(yōu)化下料問題研究 7界的確定。 啟發(fā)式算法的主要思想是在解決問題之前沒有必要找出所有切割方式,通過求解另外一個(gè)優(yōu)化問題即背包問題來產(chǎn)生新的切割方式,以在較短時(shí)間內(nèi)找到可

40、行的切割方式和昀優(yōu)解。 一直以來,因?yàn)閿?shù)量巨大的初始切割方式的優(yōu)化組合問題與整數(shù)規(guī)劃計(jì)算中的收斂問題被公認(rèn)為優(yōu)化下料問題的兩大難題,所以國(guó)內(nèi)外對(duì)切割下料問題的研究集中在快速找到昀優(yōu)解或近似昀優(yōu)解的算法研究。 3.1.2 優(yōu)化下料問題的研究方法 優(yōu)化下料問題的研究理論涉及到了運(yùn)籌學(xué)、現(xiàn)代優(yōu)化算法、計(jì)算機(jī)圖形學(xué)等領(lǐng)域,由于實(shí)際下料問題是多約束多目標(biāo)的組合優(yōu)化問題,無法使用單一的數(shù)值優(yōu)化模型來表達(dá),求解下料問題的算法多樣,到目前為止仍然沒有人能夠給出一種精確的、有效的算法?？偨Y(jié)國(guó)內(nèi)外研究?jī)?yōu)化問題的求解方法,可以歸納為如下幾種:線性規(guī)劃(linear programming)、動(dòng)態(tài)規(guī)劃(dynamic

41、 programming)、模擬退火算法(simulated annealing) 、遺傳算法(genetic algorithm)、啟發(fā)式算法(heuristic algorithm)。 (1) 線性規(guī)劃 線性規(guī)劃(linear programming)是運(yùn)籌學(xué)的重要分支,線性規(guī)劃應(yīng)用及其廣泛,從解決技術(shù)問題的昀優(yōu)化設(shè)計(jì)到工業(yè)、農(nóng)業(yè)、商業(yè)、交通運(yùn)輸業(yè)、軍事、經(jīng)濟(jì)計(jì)劃和管理決策領(lǐng)域都可以發(fā)揮作用。線性規(guī)劃法在排料優(yōu)化中的應(yīng)用主要是通過對(duì)排料優(yōu)化問題建立一個(gè)整數(shù)規(guī)劃模型,采用基于枚舉思想的分枝定界8法、割平面法和 0-1 整數(shù)規(guī)劃法進(jìn)行求解。 這類方法雖然從理論上可以求得昀優(yōu)解,但其計(jì)算具有很大

42、的復(fù)雜性,計(jì)算時(shí)間通常無法限制在人們可接受的范圍內(nèi)。為了避免計(jì)算的復(fù)雜性,通常是在建立整數(shù)規(guī)劃模型后,舍棄約束變量為整數(shù)這一條件,優(yōu)選出下料方案后再進(jìn)行人工調(diào)整,這不但造成了浪費(fèi),而且,用“舍入取整”的方法得到的解有可能不是原問題的昀優(yōu)解, 甚至可能遠(yuǎn)遠(yuǎn)偏離昀優(yōu)解。即使是原問題的可行解也不會(huì)是昀優(yōu)解, 因此,這種方法很難獲得實(shí)際的應(yīng)用。更多情況下,在建立線性規(guī)劃模型后,采用一種列生成的方法或者通過排列組合確定零件套裁的組合方式來避免對(duì)排料方式的窮舉,從而得到排料優(yōu)化問9題的近似昀優(yōu)解。- 12 - 12暨南大學(xué)碩士學(xué)位論文面向紙制品包裝材料加工企業(yè)的優(yōu)化下料問題研究 (2) 動(dòng)態(tài)規(guī)劃 動(dòng)態(tài)規(guī)劃

43、是(dynamic programming)是 20 世紀(jì) 50 年代前后由美國(guó)數(shù)學(xué)家貝爾曼(richard bellman)等人建立和發(fā)展起來的一種解決多階段決策問題的優(yōu)化方法。多階段決策問題是指的是:該問題的決策過程是一種在多個(gè)相互聯(lián)系的階段分別做出決策以形成序列決策的過程,在每一個(gè)階段都要需要做出決策,其中每一個(gè)決策不僅決定了此階段的結(jié)果,而且決定了下一初始階段的初始30狀態(tài) 。用動(dòng)態(tài)規(guī)劃法求解排料優(yōu)化問題的基本思想是通過一定的降維處理技術(shù)將多維排料優(yōu)化問題轉(zhuǎn)化為一維排料優(yōu)化問題,從而建立動(dòng)態(tài)排料優(yōu)化問題的動(dòng)態(tài)規(guī)劃模型,然后對(duì)其進(jìn)行求解。但是,隨著排料優(yōu)化問題的規(guī)模的增大,動(dòng)態(tài)規(guī)劃法的計(jì)

44、算變得過于復(fù)雜,此方法一般比較適用于規(guī)模較小的排料優(yōu)化問題。 (3) 模擬退火算法 模擬退火算法(simulated annealing,sa)是局部搜索算法的擴(kuò)展,模擬退火算法的思想源于金屬物體退火過程:用一物質(zhì)系統(tǒng)的退火過程來模擬優(yōu)化問題的尋優(yōu)過程,當(dāng)物質(zhì)系統(tǒng)達(dá)到昀小能量狀態(tài)時(shí), 優(yōu)化問題的目標(biāo)函數(shù)也相應(yīng)地10達(dá)到全局昀優(yōu)值。 模擬退火算法的特性之一就是可根據(jù)一定的概率接收目標(biāo)函數(shù)值不太好的狀態(tài)即算法不但往好的方向走也可朝差的方向走;這使得算法即使落入局部昀優(yōu)的陷井中,經(jīng)過足夠長(zhǎng)的時(shí)間后也可跳出來從而收斂到全局昀優(yōu)解。在具體應(yīng)用時(shí),通常并不一定找尋昀優(yōu)解, 而只是求出一個(gè)滿意的近似昀優(yōu)解。

45、 (4) 遺傳算法 遺傳算法(generic algorithm,ga)是一種通過模擬生物在自然環(huán)境中的遺傳和進(jìn)化過程而形成的一種自適應(yīng)全局優(yōu)化概率搜索算法。它昀早由美國(guó)執(zhí)安大學(xué)的holland教授提出,起源于 60年代對(duì)自然和人工自適應(yīng)系統(tǒng)的研究。遺傳算法的運(yùn)算過程主要包括如下幾個(gè)步驟:初始化,設(shè)置進(jìn)化代數(shù)計(jì)數(shù)器及昀大進(jìn)化代數(shù),隨機(jī)生成一定數(shù)目的個(gè)體作為初始群體;對(duì)每個(gè)個(gè)體進(jìn)行評(píng)價(jià),計(jì)算群體中每個(gè)個(gè)體的適應(yīng)度;將選擇算子作用于群體,進(jìn)行選擇運(yùn)算;將交叉算子作用于群體,進(jìn)行交叉運(yùn)算;將變異算子作用于群體,進(jìn)行變異運(yùn)算。這樣,經(jīng)過選擇、交叉、變異運(yùn)算得到下一代群體,重復(fù)上述過程直到得到昀優(yōu)解。遺

46、傳算法具有較強(qiáng)的全局尋優(yōu)能力,由于遺傳算法搜索過程中保持群體規(guī)模- 13 - 13暨南大學(xué)碩士學(xué)位論文面向紙制品包裝材料加工企業(yè)的優(yōu)化下料問題研究 不變,具有潛在的并行性,所以從理論上來說,遺傳算法作為一種全局昀優(yōu)算法,比較適合于解決復(fù)雜的、大型的優(yōu)化問題。但是,利用遺傳算法求解二維排料優(yōu)化問題,由于其收斂速度太慢,問題模型建立困難,因而影響了其應(yīng)用的適用性。11(5) 啟發(fā)式算法 啟發(fā)式算法是相對(duì)于昀優(yōu)算法提出的, 一個(gè)問題的昀優(yōu)算法求得該問題的每個(gè)實(shí)例的昀優(yōu)解。 啟發(fā)式算法是指:一個(gè)基于直觀或經(jīng)驗(yàn)構(gòu)造的算法,在可接受的時(shí)間花費(fèi)(指計(jì)算時(shí)間、占用空間等)下給出待解決優(yōu)化問題的每一個(gè)實(shí)例的一個(gè)

47、可行解,該可行解與昀優(yōu)解的偏離程度不一定事先可以預(yù)計(jì)。 啟發(fā)式算法雖然不能保證求得昀優(yōu)解, 但是由于其簡(jiǎn)單易行、比較直觀,能夠克服傳統(tǒng)優(yōu)化算12法建模困難、求解復(fù)雜等缺點(diǎn),因而得到了廣泛的應(yīng)用。3.2 二維排樣問題的分類和研究現(xiàn)狀 在 3.1.1節(jié)所述的三類優(yōu)化下料問題中,二維下料在實(shí)際生活中應(yīng)用昀為廣泛,針對(duì)紙制品包裝材料加工過程中的下料問題是先將紙卷下料,繼而將紙卷切割成矩形紙張,使余殘料昀少,屬于二維優(yōu)化排樣中的矩形下料問題。 對(duì)于單件產(chǎn)品且零件種類和數(shù)量要求較少的情況下,可以使用人工排樣,而對(duì)于大規(guī)模生產(chǎn),人工排樣往往很難得到昀優(yōu)結(jié)果, 排樣所花的時(shí)間取決于排樣技師的人工經(jīng)驗(yàn),因人而異

48、。在紙制品包裝材料的實(shí)際生產(chǎn)應(yīng)用中,雖然待排零件或產(chǎn)品的需求數(shù)量多、規(guī)模大,但是對(duì)需求量是有約束,切割數(shù)量要求剛好滿足客戶的需求量,同次下料的零件規(guī)格相同。而且,利用卷材下料的過程中,可選擇的原料規(guī)格較多,在要求快速排樣的應(yīng)用中,人工下料的效果不穩(wěn)定,容易出錯(cuò),本文重點(diǎn)研究的在紙卷上切割矩形紙張的優(yōu)化排樣問題,屬于二維矩形的優(yōu)化排樣問題,在綜述二維矩形件優(yōu)化排樣的研究基礎(chǔ)上,提出本論文所需的理論基礎(chǔ)。 3.2.1 二維排樣問題的分類 13二維排樣問題一般分為以下三類:(1) 沖裁件優(yōu)化排樣 - 14 - 14暨南大學(xué)碩士學(xué)位論文面向紙制品包裝材料加工企業(yè)的優(yōu)化下料問題研究 同一個(gè)零件在矩形的板

49、材上或一條相對(duì)很長(zhǎng)的條料或卷板上應(yīng)該如何排放,使得排放下的零件的數(shù)量昀多,或者材料的利用率昀高。根據(jù)不同的加工工藝,零件可采用普通單排,普通雙排,對(duì)頭單排和對(duì)頭雙排四種不同的排放方式。同時(shí),零件可在一定的范圍內(nèi),按任意角度排放,但零件不能互相重疊,也不能排出板材以外,此優(yōu)化排樣就是在適合的范圍內(nèi),確定零件的昀優(yōu)排放方式, 并計(jì)算出該沖裁件的昀佳排放角度以及昀優(yōu)的沖裁步距的問題。 (2) 矩形件優(yōu)化排樣 將多種不同尺寸和數(shù)量要求的矩形零件排布在矩形的原材料板上,每種矩形件有一定的數(shù)量要求,如何在這些矩形件既不互相重疊,也沒有排出板材以外的條件下,用昀少的原料排下符合數(shù)量要求的零件, 以使得原材料

50、的利用率達(dá)到昀高。根據(jù)不同的加工工藝與加工方式,這些矩形件可被橫放或豎放,或者為了適應(yīng)某種加工工藝要求,它們必須按一定的條件排放到板材上,只能橫放或豎放,如對(duì)有紋理要求的家具零件的下料,同時(shí),如果還有多種不同規(guī)格的板材可供選擇時(shí),要求將它們分配到這些不同的板材上,使得總的原材料利用率昀高。 (3) 不規(guī)則形狀零件優(yōu)化排樣 有多種任意不同形狀的平面裝配件,每類裝配件需要若干個(gè),如何在這些裝配件既不互相重疊,也沒有排出板材以外的條件下,將它們排放到矩形的板材上,使得材料的利用率達(dá)到昀高, 根據(jù)不同的板材類型與加工方式,這些裝配件可以按任意方向排放到板材上(如鋼板或玻璃等,這些板材沒有紋路限制),或

51、它們只能按某些特定的方向被排放到板材上(如布料等,這些材料有紋路限制)。 3.2.2 二維矩形排樣問題的分類 二維矩形排樣問題是二維排樣問題中昀常見, 也是應(yīng)用范圍昀廣、 昀具實(shí)踐意義的一類優(yōu)化排樣問題,通常以利用率昀大或剩余料昀少為目標(biāo), 對(duì)于非矩形零件一般是通過計(jì)算機(jī)圖形處理技術(shù)將一個(gè)或幾個(gè)零件套排在一個(gè)包容矩形中進(jìn)行預(yù)先處理,然后對(duì)包容矩形按照矩形零件進(jìn)行優(yōu)化排樣,從而將其轉(zhuǎn)化為矩形件排樣問題。常見的矩形件優(yōu)化排樣問題根據(jù)原料和切割方式可分為以下幾種: - 15 - 15暨南大學(xué)碩士學(xué)位論文面向紙制品包裝材料加工企業(yè)的優(yōu)化下料問題研究 (1) “卷料切割”方式的矩形件排樣問題,原材料為無

52、限長(zhǎng)但固定寬度的帶狀,如:紙卷、布匹皮革、金屬卷料的切割等。如圖 3-1(a)所示。本文研究的是在紙卷上切割矩形件的問題,紙卷切割的示意圖如圖 3-1(b)所示。 (2) “直通切割(guillotine cutting)”方式的矩形件排樣問題,每一次切割的路徑都是貫通整個(gè)原料矩形的直線。如:報(bào)刊排版、板材排樣、玻璃切割等。如圖 3-2所示。 (3)“正交切割(non-guillotine cutting)”矩形件排樣問題,每一次切割的路徑可以是折線,每一刀可以在原料板內(nèi)預(yù)定的位置上終止。如:板材的激光切割,線切割,火焰切割,氣割等。如圖 3-3所示。(a):卷材切割 (b):紙卷切割 a: roll