布料剪裁中用料優化的貪婪算法

摘 要：在布產品生產過程中，通常要把原料按照一定規則裁剪為合適使用的尺寸。如何剪裁以使余料最少是一個有著直接經濟價值的問題。在對問題參數分析的基礎上，建立了該問題對應的整數規劃模型。在模型求解的具體實現過程中，基于貪婪算法的思想提出了一種求解此優化問題的近似算法，根據近似算法進行合理的組合設計。通過具體算例的計算表明了算法的有效性和可行性，鑒于參數設置的普遍性，所提出的算法具有廣泛的實際應用潛力。

關鍵詞：近似算法；貪婪算法；優化；組合設計

中圖分類號：TP301.6 文獻標志碼：A

Greedy Algorithm on Optimization of Material Cost in Cloth Cutting

GUO Jing-shi

(Shenyang Polytechnic College，Shenyang Liaoning 110045，China)

Abstract: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 material-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 generality of the parameters， the presented algorithm has an extensive potential of actual application.

Key words:approximation algorithm; greedy algorithm; optimization; combinatorial design

在布產品生產過程中，往往要把原料按照一定規則裁剪為合適使用的尺寸。如何裁剪可使余料最少是一個有著直接經濟價值的問題。傳統方法往往是人工安排，對安排者的能力依賴很大，往往費時費力。此類問題屬于組合優化，通常是很難，即使存在最優算法，也多為NP難的，很難找到多項式時間的最優算法［1］。

貪婪算法求解優化問題的常用算法［2］，起源于背包問題的求解。其基本思想是用局部最優代替整體最優，使問題得到大大簡化。多數情況下，只要局部最優條件選取的比較適當，這種替代都是合理的，因此應用貪婪算法的思想可以得到求解很多很難的優化問題的比較好的近似算法。本文中我們基于貪婪算法的思想給出解決此類優化問題的一個近似算法。

1 問題的提出及基本假設

本文中我們考慮如下問題：假設現有一個訂單，要求剪裁矩形布料，有N種規格的剪裁要求，每種剪裁要求的規格分別長為L寬為W（L和W均為長為n的數組，它們的第i個位置的元素分別對應第i種規格的長和寬），而且每種剪裁要求又分別要求剪裁M份（M也是一個n元數組，分量分別對應每一種規格）。原料（也稱為布坯）的寬度為Wid，每一卷布坯的長度為Len。我們的主要問題是在完成訂單的前提下，如何裁剪才能使余料最少，也可以說使用掉的原料即布坯最少。

在考慮上述實際問題時，我們還要考慮到裁剪的難易度。如果裁剪線過于復雜，具體操作起來也很難實現。因此，我們總可以假設裁剪線都是直線，并且一直到底。

稱沿布坯寬的方向為橫向，長的方向為縱向。一卷布坯的長度Len往往要比寬度Wid大很多，因此在上述裁剪原則限制下，我們總可以認為影響余料多少的主要因素是在橫向安排的剩余寬度。據此我們在安排過程中也是優先進行橫向安排，使橫向余量最小。

綜合起來，在制定裁剪計劃時，我們首先確定一個橫向的安排方案，使橫向余量盡量小。在縱向安排上，我們總是使同一列上產品都一樣。在確定了橫向安排方案后，計算滿足產量限制的前提下這種安排方案需要的最大長度（同時還須考慮原料布坯的長度，具體的請參看后面的具體算法）。我們給出圖2.1作為裁剪方式的示例。

一般的總是可以假設面積大的產品規格可能造成的最小余量要大，因此在安排時，我們總是優先安排面積大的產品。

為了簡化問題，適當的選取單位，我們總可以假設問題中出現的都是整數形變量。

圖1 布坯一次裁剪方案示意圖

（注：上述圖形中所示的裁剪方案中，相同數字代表的是同一種規格的產品，裁剪時優先裁剪長劃線對應的線，然后是點劃線對應的線，最后是短劃線對應的線。）

由上面的分析可知，要解決上述問題，我們只需確定橫向的安排和縱向安排的長度。易知每一次安排只與參與此次安排的產品的放置方式和個數有關，而根具體的放置位置無關，所以本文中我們可以用向量X₁，X₂表示一次安排。具體X₁(i)=k來講，我們用向量表示橫向安排。其中表示第i種規格的產品在此次橫向排列中按長邊沿橫向放置出現了k次；X₂(i)表示第i種規格的產品在此次橫向排列中按寬邊沿橫向放置出現了k次。用Y1，Y2表示縱向安排，含義類似。

在計算X₁，X₂時，我們把問題轉化為一個整數規劃問題（具體問題見子函數一的實現），求解整數規劃已有很多成熟的算法，在很多文獻中均有介紹，如文獻［3-5］等。本文中不再詳細介紹。

2 算法實現

在具體實現過程中，我們把算法分成三個部分：兩個子函數，一個主函數。其中的兩個子函數分別用來計算橫向最優排列和縱向排列的。下面來分別介紹三個函數的具體實現過程。

子函數一：計算一次最優橫向安排向量X₁，X₂。

入口參數：布坯寬度Wid、規格的長L、寬W及產量M。

函數實現：上述問題轉化為求解如下的整數規劃問題：

minWid-LTX₁-WTX₂

s.t.:X₁，X₂∈Nn

Wid-LTX₁-WTX₂≥0

X₁+X₂M

其中的X₁，X₂表示在此次橫向安排中各種規格的產品分別按長邊沿橫向放置（簡稱L放置）和寬邊沿橫向放置（簡稱W放置）的個數（稱為橫向安排向量）。利用求解整數規劃的算法可以實現此函數。

子函數二：一種產品在已知橫向排列下可能達到的縱向最大長度。

任取一種規格的產品，設在由子函數一中計算出的這種產品L放置的個數為lx，M放置的個數為wx（總假設這兩個數不全為0），可排的產品最多只有m個。

入口參數：布坯剩余長度Le、給定的規格的長L和寬W、產量m及橫向安排量lx和wx。

函數實現：分如下兩種情況：

情形一：lx和wx均不為0。

此時，設置縱向安排量y1，y2的初始值為1。稱w×y1為L放置高度，稱l×y2為W放置高度。若L放置高度比W放置高度大，則把y2增加1；若W放置高度比L放置高度大，則把y1增加1；若兩者相等，則把y1，y2一起增加1。重復上述過程直到達到產量m的限制。返回Lenage=min{max{w×y1，l×y2}，Le}。

情形二：lx和wx有一個為0。

若lx=0，則取，返回Lenage=min{Le，l×y2}；

若wx=0，則取，返回Lenage=min{Le，w×y1}。

主函數：假設布坯的寬度Wid和長度Len均為已知參數。

入口參數：規格要求的長L、寬W，產量要求M。

具體實現：

Step 1.設置Le的初始值（如果沒有此前生產產生的剩料，置為Len，否則置為剩料的長度）。

Step 2.用子函數一以Wid、L、W、M為入口參數計算出第一次的橫向安排向量X₁，X。

Step 3.用子函數二依次計算橫向安排中用到的產品在這種安排下可能達到的最大長度，取所得返回值中的最小值，記為Lenage。

Step 4.取，Y1(i)=，若X₁（i)≠0

0，其它（1-2）

Y2（i）=，若X₂(i)≠0

0，其它。

Step 5.輸出Lenage，X₁，X₂，Y1，Y2（第一次的裁剪方案）。

Step 6.置，Le=Le-Lenage，Le-LenageminiW(i)

Len，其它（1-3）

M=M-X₁.×Y1-X₂.×Y2（其中.×表示對應位置元素相乘），剔除M中分量為0所對應的產品，同時剔除L和W中相應的項。

Step 7.以新的參數重新回到Step 2，循環此過程直到M變成空數組（即表示所有的產品均生產完畢）。算法結束。

3 算例

假設我們的原料布坯的寬度Wid為2.1m，長度Len為1000m。客戶要求裁剪以下規格和數量的布料：

表1 產品規格和數量

規格12345678910

長（英寸）L 471210122012

163020

寬（英寸）W45681010

12121516

數量（只）M600

在處理上述問題中，我們選取長度單位為英寸。因為規格中的長和寬都是整數，所以無論怎樣安排，橫向余量至少是0.74英寸。按照我們的裁剪原則，我們總可以假設這0.74英寸集中在布坯的一端，因此不妨取布坯的寬度Wid為82（英寸）。取布坯的長度Len為3940（英寸）。

應用上述算法計算，我們需要使用3卷布坯。在所有的余料中，有一塊余料的規格為917（英寸）×2.1（米），此塊余料可留待以后生產中繼續使用，不列入廢料。因此，我們使用的原料面積為（英寸2），而產品的總面積為882600英寸2，原料利用率為。

4 結論

通過對算例的仿真實驗表明了我們多提出的基于貪婪算法的近似算法是有效的。同時，在我們所提出的算法中，所有參數都是用字母表示，可以代入任意數值，具有一定的普遍性和較強的實用性。我們輸出的剪裁方案均用向量表示，便于機器閱讀。如與數控切割機搭配，更可以實現自動化操作。

我們多提出的算法具有很強的普遍使用性，因而可以被廣泛的應用于實際的原料裁剪加工中，有助于工廠提高生產效率和布料利用率。同時，算法對于實際工業生產中的鋼板、板坯等多種金屬以及塑料、布料等材料的裁剪工藝都有很好的推廣價值和指導意義，有助于提高各種代裁剪原材料的利用率。

參考文獻

［1］堵丁柱等，計算復雜性導論［M］.北京:高等教育出版社，2002.

［2］辛運幃， 劉璟， 陳有祺，數據結構與算法［M］.北京:高等教育出版社 2006.

［3］利奧尼德#8226;尼森#8226;瓦澤斯坦等，線性規劃導論［M］.北京:機械工業出版社，2005.

［4］馬仲蕃，整數規劃［M］.北京:中國科學院系統科學研究所，1983.

［5］趙鳳治，線性規劃計算方法［M］.北京:科學出版社 1981.