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

關(guān)鍵詞：近似算法；貪婪算法；優(yōu)化；組合設(shè)計

中圖分類號：TP301.6 文獻(xiàn)標(biāo)志碼：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

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

貪婪算法求解優(yōu)化問題的常用算法［2］，起源于背包問題的求解。其基本思想是用局部最優(yōu)代替整體最優(yōu)，使問題得到大大簡化。多數(shù)情況下，只要局部最優(yōu)條件選取的比較適當(dāng)，這種替代都是合理的，因此應(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份（M也是一個n元數(shù)組，分量分別對應(yīng)每一種規(guī)格）。原料（也稱為布坯）的寬度為Wid，每一卷布坯的長度為Len。我們的主要問題是在完成訂單的前提下，如何裁剪才能使余料最少，也可以說使用掉的原料即布坯最少。

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

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

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

一般的總是可以假設(shè)面積大的產(chǎn)品規(guī)格可能造成的最小余量要大，因此在安排時，我們總是優(yōu)先安排面積大的產(chǎn)品。

為了簡化問題，適當(dāng)?shù)倪x取單位，我們總可以假設(shè)問題中出現(xiàn)的都是整數(shù)形變量。

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

（注：上述圖形中所示的裁剪方案中，相同數(shù)字代表的是同一種規(guī)格的產(chǎn)品，裁剪時優(yōu)先裁剪長劃線對應(yīng)的線，然后是點(diǎn)劃線對應(yīng)的線，最后是短劃線對應(yīng)的線。）

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

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

2 算法實現(xiàn)

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

子函數(shù)一：計算一次最優(yōu)橫向安排向量X₁，X₂。

入口參數(shù)：布坯寬度Wid、規(guī)格的長L、寬W及產(chǎn)量M。

函數(shù)實現(xiàn)：上述問題轉(zhuǎn)化為求解如下的整數(shù)規(guī)劃問題：

minWid-LTX₁-WTX₂

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

Wid-LTX₁-WTX₂≥0

X₁+X₂M

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

子函數(shù)二：一種產(chǎn)品在已知橫向排列下可能達(dá)到的縱向最大長度。

任取一種規(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和wx。

函數(shù)實現(xiàn)：分如下兩種情況：

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

此時，設(shè)置縱向安排量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。重復(fù)上述過程直到達(dá)到產(chǎn)量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}。

主函數(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、M為入口參數(shù)計算出第一次的橫向安排向量X₁，X。

Step 3.用子函數(shù)二依次計算橫向安排中用到的產(chǎn)品在這種安排下可能達(dá)到的最大長度，取所得返回值中的最小值，記為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（其中.×表示對應(yīng)位置元素相乘），剔除M中分量為0所對應(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 471210122012

163020

寬（英寸）W45681010

12121516

數(shù)量（只）M600

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

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

4 結(jié)論

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

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

參考文獻(xiàn)

［1］堵丁柱等，計算復(fù)雜性導(dǎo)論［M］.北京:高等教育出版社，2002.

［2］辛運(yùn)幃， 劉璟， 陳有祺，數(shù)據(jù)結(jié)構(gòu)與算法［M］.北京:高等教育出版社 2006.

［3］利奧尼德#8226;尼森#8226;瓦澤斯坦等，線性規(guī)劃導(dǎo)論［M］.北京:機(jī)械工業(yè)出版社，2005.

［4］馬仲蕃，整數(shù)規(guī)劃［M］.北京:中國科學(xué)院系統(tǒng)科學(xué)研究所，1983.

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