布料剪裁中用料優(yōu)化的貪婪算法

1、布料剪裁中用料優(yōu)化的貪婪算法Greedy Algorithm on Optimization of Material Cost inCloth CuttingGUO Jing-shi(Shenyang Polytechnic College,Shenyang Liaoning 110045,China):It is always required to cut the original material into small pieces of given size in cloth production. Based on the analysis of the of the materia

2、l-cutting problem, an integer programming model is established. And an greedy algorithm using integral programming is given to solve this optimization problem. The experimental results of the computation instance demonstrate the effectiveness and feasibility of the proposed algorithm. As for the gen

3、erality of the parameters, the presented algorithmhasan extensive potential of actual application.在布產(chǎn)品生產(chǎn)過程中， 往往要把原料按照一定規(guī)則裁剪為合 適使用的尺寸。 如何裁剪可使余料最少是一個有著直接經(jīng)濟價值 的問題。傳統(tǒng)方法往往是人工安排，對安排者的能力依賴很大， 往往費時費力。此類問題屬于組合優(yōu)化，通常是很難，即使存在 最優(yōu)算法，也多為NP難的，很難找到多項式時間的最優(yōu)算法1。貪婪算法求解優(yōu)化問題的常用算法 2，起源于背包問題 的求解。 其基本思想是用局部最優(yōu)代替整體最優(yōu)， 使問題得到大

4、大簡化。多數(shù)情況下，只要局部最優(yōu)條件選取的比較適當，這種 替代都是合理的， 因此應(yīng)用貪婪算法的思想可以得到求解很多很 難的優(yōu)化問題的比較好的近似算法。 本文中我們基于貪婪算法的 思想給出解決此類優(yōu)化問題的一個近似算法。1 問題的提出及基本假設(shè)本文中我們考慮如下問題： 假設(shè)現(xiàn)有一個訂單， 要求剪裁矩 形布料，有N種規(guī)格的剪裁要求，每種剪裁要求的規(guī)格分別長為 L寬為W（ L和 W勻為長為n的數(shù)組，它們的第i個位置的元素 分別對應(yīng)第 i 種規(guī)格的長和寬） ，而且每種剪裁要求又分別要求 剪裁皿份（M也是一個n元數(shù)組，分量分別對應(yīng)每一種規(guī)格）。 原料（也稱為布坯）的寬度為 Wid，每一卷布坯的長度為 L

5、en。 我們的主要問題是在完成訂單的前提下， 如何裁剪才能使余料最 少，也可以說使用掉的原料即布坯最少。在考慮上述實際問題時， 我們還要考慮到裁剪的難易度。 如 果裁剪線過于復(fù)雜，具體操作起來也很難實現(xiàn)。因此，我們總可 以假設(shè)裁剪線都是直線，并且一直到底。稱沿布坯寬的方向為橫向， 長的方向為縱向。 一卷布坯的長 度Len往往要比寬度 Wid大很多，因此在上述裁剪原則限制下， 我們總可以認為影響余料多少的主要因素是在橫向安排的剩余 寬度。據(jù)此我們在安排過程中也是優(yōu)先進行橫向安排， 使橫向余 量最小。綜合起來， 在制定裁剪計劃時， 我們首先確定一個橫向的安 排方案，使橫向余量盡量小。在縱向安排上，

6、我們總是使同一列 上產(chǎn)品都一樣。 在確定了橫向安排方案后， 計算滿足產(chǎn)量限制的 前提下這種安排方案需要的最大長度 (同時還須考慮原料布坯的 長度，具體的請參看后面的具體算法)。我們給出圖 2.1 作為裁 剪方式的示例。一般的總是可以假設(shè)面積大的產(chǎn)品規(guī)格可能造成的最小余 量要大，因此在安排時，我們總是優(yōu)先安排面積大的產(chǎn)品。為了簡化問題， 適當?shù)倪x取單位， 我們總可以假設(shè)問題中出 現(xiàn)的都是整數(shù)形變量。圖1 布坯一次裁剪方案示意圖 (注：上述圖形中所示的裁剪方案中，相同數(shù)字代表的是同 一種規(guī)格的產(chǎn)品， 裁剪時優(yōu)先裁剪長劃線對應(yīng)的線， 然后是點劃 線對應(yīng)的線，最后是短劃線對應(yīng)的線。)由上面的分析可知，

7、 要解決上述問題， 我們只需確定橫向的 安排和縱向安排的長度。 易知每一次安排只與參與此次安排的產(chǎn) 品的放置方式和個數(shù)有關(guān)， 而根具體的放置位置無關(guān)， 所以本文 中我們可以用向量 X1，X2 表示一次安排。具體 X1(i)=k 來講， 我們用向量表示橫向安排。 其中表示第 i 種規(guī)格的產(chǎn)品在此次橫 向排列中按長邊沿橫向放置出現(xiàn)了 k 次； X2(i) 表示第 i 種規(guī)格 的產(chǎn)品在此次橫向排列中按寬邊沿橫向放置出現(xiàn)了 k 次。用Y1,Y2 表示縱向安排，含義類似。在計算 X1,X2 時，我們把問題轉(zhuǎn)化為一個整數(shù)規(guī)劃問題 （具 體問題見子函數(shù)一的實現(xiàn)） ，求解整數(shù)規(guī)劃已有很多成熟的算法， 在很多文

8、獻中均有介紹，如文獻 3-5 等。本文中不再詳細介 紹。2 算法實現(xiàn)在具體實現(xiàn)過程中， 我們把算法分成三個部分： 兩個子函數(shù)， 一個主函數(shù)。 其中的兩個子函數(shù)分別用來計算橫向最優(yōu)排列和縱 向排列的。下面來分別介紹三個函數(shù)的具體實現(xiàn)過程。子函數(shù)一：計算一次最優(yōu)橫向安排向量X1,X2。入口參數(shù)：布坯寬度 Wid、規(guī)格的長L、寬W及產(chǎn)量M 函數(shù)實現(xiàn)：上述問題轉(zhuǎn)化為求解如下的整數(shù)規(guī)劃問題： minWid-LTX1-WTX2s.t.:X1,X2 NnWid-LTX1 -WTXZOX1+X2M其中的X1,X2表示在此次橫向安排中各種規(guī)格的產(chǎn)品分別 按長邊沿橫向放置（簡稱 L放置）和寬邊沿橫向放置（簡稱 W

9、放 置）的個數(shù)（稱為橫向安排向量）。利用求解整數(shù)規(guī)劃的算法可 以實現(xiàn)此函數(shù)。子函數(shù)二： 一種產(chǎn)品在已知橫向排列下可能達到的縱向最大 長度。任取一種規(guī)格的產(chǎn)品， 設(shè)在由子函數(shù)一中計算出的這種產(chǎn)品L放置的個數(shù)為lx , M放置的個數(shù)為wx （總假設(shè)這兩個數(shù)不全為 0）,可排的產(chǎn)品最多只有 m個。入口參數(shù)：布坯剩余長度Le、給定的規(guī)格的長L和寬W 產(chǎn)量m及橫向安排量lx和wxo函數(shù)實現(xiàn)：分如下兩種情況：情形一：lx和wx均不為0o此時，設(shè)置縱向安排量y1,y2的初始值為1。稱wx yl為L 放置高度，稱I x y2為W放置高度。若L放置高度比 W放置高度 大，則把y2增加1 ；若W放置高度比L放置高

10、度大，則把yl增 加 1；若兩者相等，則把 y1,y2 一起增加 1。重復(fù)上述過程直到 達到產(chǎn)量 m的限制。返回 Lenage=minmaxwxy1,l x y2,Le。情形二：lx和wx有一個為0o若 lx=0 ，則取，返回 Lenage=minLe, l x y2；若 wx=0,貝V取，返回 Lenage=minLe,w x y1。主函數(shù)：假設(shè)布坯的寬度 Wid 和長度 Len 均為已知參數(shù)。入口參數(shù)：規(guī)格要求的長 L、寬W產(chǎn)量要求M。具體實現(xiàn)：Step 1. 設(shè)置 Le 的初始值（如果沒有此前生產(chǎn)產(chǎn)生的剩料, 置為Len,否則置為剩料的長度）。Step 2.用子函數(shù)一以 Wid、L、W

11、M為入口參數(shù)計算出第一 次的橫向安排向量 X1,X。Step 3. 用子函數(shù)二依次計算橫向安排中用到的產(chǎn)品在這種 安排下可能達到的最大長度，取所得返回值中的最小值，記為 Lenage。Step 4.取，Y1(i)=,若 X1 (i)豐 00, 其它( 1-2 )Y2 (i )=，若 X2(i)豐 00，其它。Step 5.輸出 Lenage, X1, X2, Y1, Y2(第一次的裁剪方案)。Step 6. 置， Le=Le-Lenage,Le-LenageminiW(i)Len, 其它( 1-3)M=MX1. X Y1-X2. X Y2 (其中.X表示對應(yīng)位置元素相乘)， 剔除M中分量為0所

12、對應(yīng)的產(chǎn)品，同時剔除 L和W中相應(yīng)的項。Step 7.以新的參數(shù)重新回到 Step 2，循環(huán)此過程直到 M變 成空數(shù)組(即表示所有的產(chǎn)品均生產(chǎn)完畢)。算法結(jié)束。3 算例假設(shè)我們的原料布坯的寬度 Wid為2.1m，長度Len為1000m 客戶要求裁剪以下規(guī)格和數(shù)量的布料：表 1 產(chǎn)品規(guī)格和數(shù)量規(guī)格 12345678910長(英寸) L 471210122012163020寬(英寸) W4568101012121516數(shù)量（只） M600在處理上述問題中， 我們選取長度單位為英寸。 因為規(guī)格中 的長和寬都是整數(shù)，所以無論怎樣安排，橫向余量至少是 0.74 英寸。按照我們的裁剪原則，我們總可以假設(shè)這 0.74 英寸集中 在布坯的一端，因此不妨取布坯的寬度 Wid 為 82（英寸）。取 布坯的長度Len為3940 （英寸）。應(yīng)用上述算法計算， 我們需要使用 3 卷布坯。在所有的余料中，有一塊余料的規(guī)格為 917 （英寸）X 2.1 （米），此塊余料 可留待以后生產(chǎn)中繼續(xù)使用，不列入廢料。因此，我們使用的原 料面積為（英寸 2），而產(chǎn)品的總面積為 882600 英寸 2，原料利 用率為。4 結(jié)論 通過對算例的仿真實驗表明了我們多提出的基于貪婪算法 的近似算法是有效的。同時，在我們所提出的算法中，所有參數(shù) 都是用字母表示， 可以代入任意數(shù)