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

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

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

中圖分類號(hào)：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ī)則裁剪為合適使用的尺寸。如何裁剪可使余料最少是一個(gè)有著直接經(jīng)濟(jì)價(jià)值的問題。傳統(tǒng)方法往往是人工安排，對(duì)安排者的能力依賴很大，往往費(fèi)時(shí)費(fèi)力。此類問題屬于組合優(yōu)化，通常是很難，即使存在最優(yōu)算法，也多為NP難的，很難找到多項(xiàng)式時(shí)間的最優(yōu)算法［1］。

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

1 問題的提出及基本假設(shè)

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

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

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

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

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

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

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

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

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

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

2 算法實(shí)現(xiàn)

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

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

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

函數(shù)實(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)品分別按長(zhǎng)邊沿橫向放置（簡(jiǎn)稱L放置）和寬邊沿橫向放置（簡(jiǎn)稱W放置）的個(gè)數(shù)（稱為橫向安排向量）。利用求解整數(shù)規(guī)劃的算法可以實(shí)現(xiàn)此函數(shù)。

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

任取一種規(guī)格的產(chǎn)品，設(shè)在由子函數(shù)一中計(jì)算出的這種產(chǎn)品L放置的個(gè)數(shù)為lx，M放置的個(gè)數(shù)為wx（總假設(shè)這兩個(gè)數(shù)不全為0），可排的產(chǎn)品最多只有m個(gè)。

入口參數(shù)：布坯剩余長(zhǎng)度Le、給定的規(guī)格的長(zhǎng)L和寬W、產(chǎn)量m及橫向安排量lx和wx。

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

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

此時(shí)，設(shè)置縱向安排量y1，y2的初始值為1。稱w×y1為L(zhǎng)放置高度，稱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有一個(gè)為0。

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

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

主函數(shù)：假設(shè)布坯的寬度Wid和長(zhǎng)度Len均為已知參數(shù)。

入口參數(shù)：規(guī)格要求的長(zhǎng)L、寬W，產(chǎn)量要求M。

具體實(shí)現(xiàn)：

Step 1.設(shè)置Le的初始值（如果沒有此前生產(chǎn)產(chǎn)生的剩料，置為L(zhǎng)en，否則置為剩料的長(zhǎng)度）。

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

Step 3.用子函數(shù)二依次計(jì)算橫向安排中用到的產(chǎn)品在這種安排下可能達(dá)到的最大長(zhǎng)度，取所得返回值中的最小值，記為L(zhǎng)enage。

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（其中.×表示對(duì)應(yīng)位置元素相乘），剔除M中分量為0所對(duì)應(yīng)的產(chǎn)品，同時(shí)剔除L和W中相應(yīng)的項(xiàng)。

Step 7.以新的參數(shù)重新回到Step 2，循環(huán)此過程直到M變成空數(shù)組（即表示所有的產(chǎn)品均生產(chǎn)完畢）。算法結(jié)束。

3 算例

假設(shè)我們的原料布坯的寬度Wid為2.1m，長(zhǎng)度Len為1000m?？蛻粢蟛眉粢韵乱?guī)格和數(shù)量的布料：

表1 產(chǎn)品規(guī)格和數(shù)量

規(guī)格12345678910

長(zhǎng)（英寸）L 471210122012

163020

寬（英寸）W45681010

12121516

數(shù)量（只）M600

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

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

4 結(jié)論

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

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

參考文獻(xiàn)

［1］堵丁柱等，計(jì)算復(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］.北京:中國(guó)科學(xué)院系統(tǒng)科學(xué)研究所，1983.

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