杜守信，毋 濤

西安工程大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，西安710048

裁剪分床計(jì)劃（Cut Order Planning，COP）的制定是服裝企業(yè)生產(chǎn)過程中難以避免的問題。該問題旨在尋找多尺碼、不規(guī)則數(shù)量的生產(chǎn)訂單在多個(gè)裁床上排布的最佳搭配，來滿足服裝企業(yè)低成本、高效率的生產(chǎn)需求。當(dāng)下的服裝企業(yè)訂單大多以短交期、多款式多尺碼、中小批量為主，在客戶的生產(chǎn)訂單到達(dá)后，迅速制定裁剪方案并投入生產(chǎn)，能提高企業(yè)的生產(chǎn)效率，帶來利潤(rùn)的顯著提升。COP 的制定是整個(gè)生產(chǎn)過程中重要的一環(huán)，對(duì)生產(chǎn)效率和生產(chǎn)成本都有著關(guān)鍵的影響。COP制定過程又受到企業(yè)生產(chǎn)環(huán)境中眾多因素的影響，在實(shí)際生產(chǎn)中可以使用層次分析法[1]來對(duì)影響裁剪分床的因素進(jìn)行分類，并確定影響重大的因素作為裁剪分床數(shù)學(xué)模型的約束條件。COP 制定時(shí)綜合考慮企業(yè)的生產(chǎn)環(huán)境，將生產(chǎn)需求訂單分到多個(gè)裁床，確定裁床鋪布層數(shù)，并對(duì)每個(gè)裁床中的尺碼進(jìn)行合理搭配，在較短的時(shí)間內(nèi)尋找最優(yōu)方案并完成裁剪，達(dá)到原材料的最大利用和生產(chǎn)成本的最小化，對(duì)當(dāng)下服裝生產(chǎn)企業(yè)的競(jìng)爭(zhēng)與生存有著重要意義。

傳統(tǒng)的裁剪分床方法要求生產(chǎn)訂單不同尺碼之間的數(shù)量配比具有一定的規(guī)律性，或者人為地增減需求數(shù)量而產(chǎn)生一定的規(guī)律，這種以經(jīng)驗(yàn)為主的分床方法需要進(jìn)行大量的計(jì)算，并且結(jié)果有著較大的誤差，造成了很多不必要的浪費(fèi)。隨著市場(chǎng)需求不斷改變，生產(chǎn)訂單的尺寸、風(fēng)格、面料和顏色等越來越多樣化，導(dǎo)致COP 問題愈加復(fù)雜[2]。為了有效地解決該問題，國(guó)內(nèi)外學(xué)者進(jìn)行了眾多理論研究，其中ünal等為獲取最佳解決方案，使用了混合整數(shù)非線性規(guī)劃的方法來建立模型，并使用計(jì)算機(jī)求解[3]。在智能算法的使用方面，Nascimento 和Casali等提出了一種基于狀態(tài)空間的啟發(fā)式搜索算法來解決裁剪分床問題[4]。M’Hallah 和Bouziri 對(duì)裁剪分床中的COP 和TDL（Two-Dimensional Layout）問題進(jìn)行了整體考慮，使用構(gòu)造啟發(fā)式和元啟發(fā)式方法實(shí)現(xiàn)最小化織物長(zhǎng)度的目的[5]。國(guó)內(nèi)學(xué)者王學(xué)驥等[6]、江麗林等[7]分別在不同的方向上改進(jìn)了粒子群優(yōu)化算法，并用來解決裁剪分床實(shí)際問題。實(shí)際應(yīng)用過程中，單一的啟發(fā)式算法往往會(huì)存在一定的問題，使得結(jié)果不總是優(yōu)秀的，為此一些學(xué)者開始考慮結(jié)合多種算法來彌補(bǔ)單一算法的缺陷。劉艷梅等提出一種針對(duì)大批量定制服裝裁剪分床計(jì)劃的兩階段優(yōu)化算法，分階段尋優(yōu)得到符合要求的最優(yōu)解[8]。Xu 和Thomassey 等在遺傳算法尋優(yōu)的基礎(chǔ)上提出一種基于整數(shù)編程的裁剪訂單模型來完成訂單的裁剪計(jì)劃[9]。Abeysooriya 和Fernando 則將傳統(tǒng)的啟發(fā)式算法與遺傳算法相結(jié)合來優(yōu)化裁剪分床計(jì)劃，并提升算法的執(zhí)行效率[10]。而Tsao 和Liao 等在混合算法的基礎(chǔ)上，結(jié)合基于退火的遺傳算法和基于禁忌搜索的遺傳算法，并以降低總成本為目的來進(jìn)一步解決COP問題[11]。

綜合上述情況，在現(xiàn)有理論中一些單一算法改進(jìn)的方式已經(jīng)被混合算法所替代，而在混合算法研究中部分算法沒有從實(shí)際生產(chǎn)環(huán)境的整體情況來考慮，只在相應(yīng)的具體情境下進(jìn)行算法的改進(jìn)來提升效率，并不能適用于大多數(shù)生產(chǎn)過程，還有部分在改進(jìn)算法的同時(shí)增加了算法復(fù)雜度，增大了時(shí)間成本。

本文對(duì)實(shí)際服裝生產(chǎn)過程進(jìn)行綜合、全面的考慮，由于不同類型的生產(chǎn)訂單需求迥異，提出了圍繞多個(gè)目標(biāo)建立的優(yōu)化數(shù)學(xué)模型，企業(yè)可以通過調(diào)整權(quán)重參數(shù)選擇最符合生產(chǎn)的模型。模型求解利用遺傳算法和粒子群算法兩者的優(yōu)勢(shì)，將算法優(yōu)化過程分為兩個(gè)種群進(jìn)行，遺傳算法帶來群體多樣性的同時(shí)，將優(yōu)秀的個(gè)體組成精英群體再使用粒子群算法優(yōu)化求解，以較快的速度篩選出最優(yōu)方案?；旌纤惴ㄔ谔嵘阉餍实耐瑫r(shí)又減小了陷入局部最優(yōu)的可能。

1 裁剪分床問題模型

1.1 問題描述

假設(shè)某服裝生產(chǎn)企業(yè)現(xiàn)接收到一批訂單需要生產(chǎn)，已知該訂單共有n個(gè)尺碼，且每個(gè)尺碼的需求數(shù)量為A={a1,a2,…,an}，考慮企業(yè)生產(chǎn)情況，需要制定一個(gè)裁剪分床計(jì)劃方案，使得生產(chǎn)時(shí)間較小，面料利用率較高，裁剪時(shí)不可少裁，超出數(shù)量也要在一定范圍內(nèi)，設(shè)置各尺碼最大超裁數(shù)量為G={g1,g2,…,gn} 。為了更好地進(jìn)行套排分布，裁床上各尺碼最大鋪設(shè)數(shù)量設(shè)置為S={s1,s2,…,sn} 。

1.2 多維度數(shù)學(xué)模型的建立

裁剪分床計(jì)劃的數(shù)學(xué)模型，要以生產(chǎn)訂單的尺碼和需求數(shù)量為基準(zhǔn)，裁床的長(zhǎng)度、裁刀的長(zhǎng)度、訂單織物的幅寬和厚度、訂單的需求款式等為約束條件，企業(yè)實(shí)際需求為目標(biāo)來建立。為了充分利用原材料，減少生產(chǎn)成本和裁剪時(shí)間，裁剪分床計(jì)劃制定時(shí)會(huì)盡可能選擇大小尺碼套排的方式。

參照如圖1所示的實(shí)際生產(chǎn)裁剪分床流程，從企業(yè)的需求出發(fā)，分別在超裁數(shù)量、裁剪時(shí)間、面料利用率三個(gè)維度上建立數(shù)學(xué)模型。

圖1 裁剪分床流程圖Fig.1 Flow chart of cut order planning

在裁剪分床計(jì)劃制定時(shí)，同一個(gè)裁床上不同的套排配比會(huì)產(chǎn)生不同的面料使用長(zhǎng)度，鋪設(shè)尺碼時(shí)要在面料的長(zhǎng)寬方向進(jìn)行取整，則第i個(gè)裁床面料使用長(zhǎng)度的計(jì)算公式為：

式中，Cij是裁床i上尺碼j的鋪設(shè)數(shù)量；w1是待裁剪面料的幅寬；w2是產(chǎn)生裁片的標(biāo)準(zhǔn)寬度；L是最大鋪布長(zhǎng)度。

1.2.1 超裁目標(biāo)函數(shù)

超裁數(shù)量是制定裁剪分床計(jì)劃時(shí)的一個(gè)必要參數(shù)，也是大多數(shù)企業(yè)生產(chǎn)中主要參考的目標(biāo)。超裁數(shù)量過大會(huì)使生產(chǎn)成本上升，整體效率下降，還有可能導(dǎo)致庫(kù)存堆積引起大量浪費(fèi)。但是由于尺碼數(shù)量不一致，難免會(huì)造成裁剪誤差，在實(shí)際裁剪中要使得各尺碼裁片裁剪的誤差盡量小。設(shè)進(jìn)行裁剪時(shí)需要的裁床數(shù)量為m，為減少整體誤差使用了方差作為目標(biāo)值，則訂單的裁剪數(shù)量誤差目標(biāo)函數(shù)可表示為：

式（3）作為尺碼j裁剪誤差的一個(gè)條件函數(shù)，生產(chǎn)中裁剪數(shù)量不可小于需求數(shù)量，因此添加約束來避免少裁。其中，Hi是裁床i的鋪布層數(shù)，其數(shù)值在裁床鋪布層數(shù)最大值Hmax和最小值Hmin之間。

1.2.2 裁剪時(shí)間

裁剪時(shí)間目標(biāo)函數(shù)主要分為裁剪時(shí)間和拉布時(shí)間。裁剪時(shí)間與裁床臺(tái)數(shù)、鋪布長(zhǎng)度有關(guān)，拉布時(shí)間受拉布機(jī)速度和用布總長(zhǎng)度影響。目標(biāo)函數(shù)公式為：

式中，v1是裁床上裁刀的行進(jìn)速度；v2是拉布機(jī)拉布速度。

1.2.3 面料利用率

面料利用率考慮的是在每個(gè)裁床上盡可能地實(shí)現(xiàn)多尺碼套排分布，并最大地占用鋪設(shè)面料長(zhǎng)度。目標(biāo)函數(shù)公式為：

2 混合的多種群粒子群-遺傳算法

2.1 算法選擇

根據(jù)所建模型的非線性特點(diǎn)，引入了現(xiàn)代智能算法進(jìn)行模型求解?，F(xiàn)代智能算法種類豐富，不同算法又有著不同的適應(yīng)能力，從模型與算法的相關(guān)特性考慮，選擇了粒子群優(yōu)化算法混合遺傳算法的方式來求解問題模型。

遺傳算法是一種模擬自然進(jìn)化中的自然選擇和遺傳學(xué)機(jī)理來搜索最優(yōu)解的方法[12]，具有較強(qiáng)的全局搜索優(yōu)化能力，但常規(guī)的遺傳算法在求解復(fù)雜模型時(shí)存在收斂速度慢、優(yōu)化精度低的缺點(diǎn)。粒子群算法（Particle Swarm Optimization，PSO）是1995 年由Eberhart 博士和Kennedy 博士共同提出的一種模擬鳥類捕食行為的群智能算法，與其他算法相比有著參數(shù)少、易實(shí)現(xiàn)、收斂速度快的特點(diǎn)[13]。

為了能夠提高算法的全局搜索能力，降低陷入局部最優(yōu)的可能，并適當(dāng)提升算法的收斂速度，提出使用多種群的粒子群-遺傳混合算法，將粒子群算法快速收斂能力與遺傳算法的全局多樣性優(yōu)勢(shì)結(jié)合起來，并對(duì)內(nèi)部進(jìn)化機(jī)制做出一定的改進(jìn)。

2.2 多目標(biāo)數(shù)學(xué)模型的處理

對(duì)于多個(gè)目標(biāo)函數(shù)的處理，一般是使用線性組合將多個(gè)不同的目標(biāo)函數(shù)按照一定的權(quán)重疊加，得到一個(gè)最終的函數(shù)進(jìn)行求解。

由于多目標(biāo)函數(shù)尺度不同，要先進(jìn)行歸一化處理，其中超裁數(shù)量目標(biāo)函數(shù)使用訂單尺碼設(shè)定的最大超裁數(shù)量平方和進(jìn)行歸一化處理，時(shí)間目標(biāo)中使用了當(dāng)前情況下的最大裁剪時(shí)間進(jìn)行歸一化處理。

對(duì)處理后的目標(biāo)函數(shù)進(jìn)行線性組合為：

式中α,β,γ≥0 且α ＋β ＋γ=1,是不同目標(biāo)函數(shù)在實(shí)際生產(chǎn)中的權(quán)重參數(shù)。

在模型求解時(shí)，算法需要解決的關(guān)鍵問題是尋找最優(yōu)的鋪布層數(shù)配比Hi和各尺碼鋪布數(shù)量配比Cij，目標(biāo)函數(shù)的尋找過程中使用以下公式：

2.3 混合的雙種群算法設(shè)計(jì)

采用混合的雙種群粒子群-遺傳算法來解決裁剪分床問題的主要步驟可描述為：第一步，企業(yè)根據(jù)生產(chǎn)訂單、設(shè)備等信息初始化參數(shù)，結(jié)合生產(chǎn)現(xiàn)狀設(shè)定需求模型；第二步，根據(jù)已有條件計(jì)算合適的分床數(shù)量區(qū)間并確定算法目標(biāo)函數(shù)；第三步，取可用分床數(shù)量M進(jìn)行算法種群初始化，設(shè)定算法最大進(jìn)化世代數(shù)；第四步，使用遺傳算法進(jìn)化普通群體，進(jìn)化過程每一代取兩個(gè)最優(yōu)個(gè)體加入到精英種群，對(duì)種群進(jìn)行交叉和變異；第五步，等到精英種群數(shù)量滿足時(shí)，暫停遺傳算法，使用粒子群算法對(duì)精英種群進(jìn)行進(jìn)化；第六步，記錄粒子群算法進(jìn)化過程中的局部和全局最優(yōu)并更新粒子；第七步，粒子群算法進(jìn)化結(jié)束，記錄最優(yōu)個(gè)體，排序并選擇優(yōu)秀個(gè)體替換到普通種群，開始新一輪的混合算法迭代；第八步，算法達(dá)到最大迭代次數(shù)后比較算法進(jìn)化結(jié)果，取最優(yōu)個(gè)體作為當(dāng)前分床數(shù)M下的最優(yōu)方案；第九步，當(dāng)前分床數(shù)M=M ＋1，如果仍在可用區(qū)間內(nèi)，轉(zhuǎn)到第三步繼續(xù)使用算法求解，否則比較不同分床數(shù)下的最優(yōu)方案，選擇最符合目標(biāo)需求的即為最終方案。具體的混合雙種群算法設(shè)計(jì)流程如圖2。

圖2 混合的雙種群算法設(shè)計(jì)流程圖Fig.2 Flow chart of double population hybrid genetic algorithm

2.4 算法的實(shí)現(xiàn)

2.4.1 編碼方案

算法中個(gè)體方案包括各裁床鋪布層數(shù)與各裁床各尺碼的數(shù)量配比，由于裁床鋪布層數(shù)是比較大的實(shí)數(shù)，使用二進(jìn)制編碼會(huì)導(dǎo)致編碼過長(zhǎng)過大，不利于計(jì)算，而實(shí)數(shù)編碼意義明確，且減少了編碼和解碼的步驟，提高了算法效率[14]，為此混合算法編碼時(shí)使用了實(shí)際數(shù)值作為編碼。而算法的求解過程是對(duì)裁床鋪布層數(shù)矩陣和裁床各尺碼數(shù)量配比矩陣同時(shí)尋優(yōu)，會(huì)導(dǎo)致嵌套過深而丟失性能，混合算法中考慮兩矩陣的相同維度，尋優(yōu)過程中將兩者編碼在同一矩陣中，計(jì)算時(shí)再將結(jié)果解碼成兩個(gè)獨(dú)立矩陣，有效降低了算法的時(shí)間復(fù)雜度。編碼形式為：

2.4.2 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)通常是根據(jù)目標(biāo)函數(shù)進(jìn)行設(shè)計(jì)的，混合算法進(jìn)化時(shí)使用目標(biāo)函數(shù)作為個(gè)體適應(yīng)度進(jìn)行計(jì)算，滿足約束條件時(shí)，適應(yīng)度越小代表當(dāng)前方案越優(yōu)秀。模型的適應(yīng)度函數(shù)為：

2.4.3 選擇機(jī)制

算法進(jìn)化過程涉及三處選擇，即普通種群進(jìn)化時(shí)選取精英個(gè)體更新精英種群，遺傳算法進(jìn)化中進(jìn)行交叉?zhèn)€體的選擇，精英群體進(jìn)化完成后選擇個(gè)體替換普通種群。從普通種群中選擇更新精英群體時(shí)，在普通種群按照適應(yīng)度排序，選擇最優(yōu)的兩個(gè)加入到精英種群；遺傳算法進(jìn)化時(shí)和精英種群反向優(yōu)化普通種群時(shí)，均使用輪盤賭的機(jī)制選擇個(gè)體；保證優(yōu)秀個(gè)體有更大概率選中的同時(shí)又保存了個(gè)體多樣性。輪盤賭選擇時(shí)被選中的概率使用其適應(yīng)度占比：

式中，fiti為個(gè)體適應(yīng)度，pop代表混合算法的種群大小。

2.4.4 交叉

算法的交叉操作是選擇兩個(gè)染色體進(jìn)行配對(duì)，配對(duì)染色體的基因片段相互交換形成新的個(gè)體，增加種群多樣性。為了在進(jìn)化時(shí)有更好的全局搜索能力，算法中的交叉機(jī)制采用隨機(jī)交叉的方式進(jìn)行，在個(gè)體矩陣的全索引區(qū)間內(nèi)隨機(jī)生成一個(gè)整數(shù)r，針對(duì)選擇的配對(duì)個(gè)體，交換r后的基因片段。對(duì)于選擇機(jī)制產(chǎn)生的新種群，令其奇數(shù)位置個(gè)體與偶數(shù)位置個(gè)體進(jìn)行配對(duì)交叉，最終獲得一個(gè)新的基因種群。具體交叉流程如圖3。

圖3 混合算法交叉機(jī)制流程圖Fig.3 Flow chart of hybrid algorithm crossover mechanism

當(dāng)交叉位置r=n時(shí)，如下所示為選擇個(gè)體s1、s2進(jìn)行配對(duì)交叉，產(chǎn)生兩個(gè)新的子代s3、s4的過程：

2.4.5 變異

變異操作是對(duì)種群中一些個(gè)體產(chǎn)生隨機(jī)的變化來使個(gè)體能夠更加適應(yīng)進(jìn)化的需求。算法進(jìn)化的前期過程主要靠交叉操作來產(chǎn)生多樣性，后期則依賴于變異操作，因此算法中采用一種隨進(jìn)化次數(shù)增多而逐漸增加的自適應(yīng)變異概率，并對(duì)選擇的個(gè)體生成一個(gè)（0，1）內(nèi)分布的概率矩陣P，所有概率元素與p相比較，如果該基因片段對(duì)應(yīng)的概率大于變異概率不發(fā)生變異，小于則發(fā)生變異。自適應(yīng)的變異概率公式為：

式中，p0是初始設(shè)定的變異概率；μ是自適應(yīng)概率的最大尺度；maxIter是算法最大進(jìn)化代數(shù)。

變異算子選取時(shí)，在文獻(xiàn)[15]中的變異算子基礎(chǔ)上，結(jié)合粒子群算法進(jìn)化機(jī)制，提出了一種基因片段近優(yōu)趨勢(shì)的變異方式。對(duì)于個(gè)體xk的變異過程公式如下：

式中，ρ是慣性系數(shù)；P是變異概率矩陣；σ和θ是兩個(gè)學(xué)習(xí)率。

圖4為算法具體變異流程。

圖4 混合算法變異機(jī)制流程圖Fig.4 Flow chart of hybrid algorithm mutation mechanism

2.4.6 粒子群優(yōu)化算法

精英種群進(jìn)化時(shí)使用一種改進(jìn)的慣性權(quán)重自適應(yīng)的粒子群優(yōu)化算法來快速收斂找到最優(yōu)解，對(duì)于精英種群的個(gè)體粒子，初始位置已經(jīng)確定，初始化粒子的速度，并根據(jù)速度和位置公式不斷更新粒子狀態(tài)，直至達(dá)到最大迭代次數(shù)或者最優(yōu)解不再發(fā)生變化。進(jìn)化時(shí)更新公式為：

式中，c1、c2是學(xué)習(xí)因子；r1、r2是隨機(jī)數(shù)值。

參數(shù)對(duì)算法的優(yōu)化性能影響很大，因此在使用中要選擇合適的參數(shù)值[16]。慣性權(quán)重ω較大時(shí)有利于算法跳出局部最優(yōu)，較小時(shí)有利于局部尋優(yōu)，結(jié)合文獻(xiàn)[17]中慣性權(quán)重的改進(jìn)思想，設(shè)置一個(gè)在進(jìn)化過程中自適應(yīng)的慣性權(quán)重因子：

式中，ω0是初始設(shè)定的慣性因子；ω1是進(jìn)化過程減小的最大尺度。

2.4.7 混合算法的交叉影響機(jī)制

在文獻(xiàn)[18]算法的基礎(chǔ)上，調(diào)整種群結(jié)構(gòu)，將改進(jìn)的遺傳算法和粒子群優(yōu)化算法結(jié)合，提出了交叉影響雙種群的混合算法。將個(gè)體分為普通種群和精英種群，普通種群使用遺傳算法進(jìn)化保留種群的多樣性，精英群體使用粒子群優(yōu)化算法進(jìn)化提高收斂速度，在進(jìn)化過程中雙種群之間交叉影響，相互促進(jìn)。雙種群影響關(guān)系如圖5。

圖5 混合算法進(jìn)化兩種群交叉影響關(guān)系圖Fig.5 Relationship graph of hybrid algorithm evolution of two groups

算法交叉進(jìn)化時(shí)具體流程如圖6。

圖6 混合算法種群交叉進(jìn)化流程圖Fig.6 Flow chart of hybrid algorithm population cross evolution

3 實(shí)驗(yàn)結(jié)果

根據(jù)某服裝生產(chǎn)企業(yè)的實(shí)際需求訂單以及企業(yè)生產(chǎn)條件，進(jìn)行了算法的實(shí)用性測(cè)試。實(shí)驗(yàn)環(huán)境為英特爾Core i5-9300H，2.4 GHz 主頻，16 GB 內(nèi)存，GTX 1660 Ti 6 GB 顯卡；算法運(yùn)行環(huán)境為PyCharm2017.1。實(shí)驗(yàn)過程選擇了手工計(jì)算方法、遺傳算法、粒子群算法與本文算法進(jìn)行對(duì)比。

根據(jù)訂單信息表1可知，該訂單所有尺碼總的需求數(shù)量為5 016 件，由企業(yè)生產(chǎn)條件及生產(chǎn)設(shè)備參數(shù)可以得到裁床適宜鋪布層數(shù)范圍為[50，250]，每層面料最大可以裁剪各尺碼總數(shù)量為15，計(jì)算出裁床數(shù)量的適用區(qū)間是[4，8]，設(shè)定尺碼套排時(shí)每種尺碼數(shù)量不超過3 件，尺碼最大允許超裁比例為2%，結(jié)合生產(chǎn)需求建立模型并使用混合算法求解。

表1 生產(chǎn)訂單詳情Table 1 Production order details

由圖7 中三種算法的進(jìn)化曲線可以看出：（1）粒子群算法在進(jìn)化過程中種群收斂速度較快，卻容易陷入局部最優(yōu)而停止搜索。（2）遺傳算法更為穩(wěn)定，在進(jìn)化過程中能保證種群多樣性，但是算法進(jìn)化緩慢，需要進(jìn)行較多的進(jìn)化世代才能尋找到最優(yōu)解。（3）混合算法進(jìn)化速度有顯著提升，圖中混合算法在200代以內(nèi)便已經(jīng)尋得最優(yōu)解并停止了搜索，且最優(yōu)解也與遺傳算法最優(yōu)解相當(dāng)。

圖7 多種算法的適應(yīng)度和迭代次數(shù)的關(guān)系曲線圖Fig.7 Relationship graph between fitness and number of iterations of multiple algorithms

使用雙種群粒子群-遺傳混合算法最終獲取最優(yōu)裁剪分床方案為：

使用人工經(jīng)驗(yàn)計(jì)算的方式得到一組裁剪分床方案為：

對(duì)比算法和人工計(jì)算裁剪方案可以得到：智能算法遍歷尋找最優(yōu)解，滿足裁剪要求的同時(shí)會(huì)盡可能地套排尺碼來減少裁床的使用數(shù)量并降低目標(biāo)函數(shù)值。而人工計(jì)算由于不能進(jìn)行所有可能的枚舉，只能根據(jù)經(jīng)驗(yàn)及需求數(shù)量的規(guī)律性來進(jìn)行分床和排布，套排情況較差且增加1個(gè)裁床的成本。

表2 是使用四種不同算法求解同一訂單模型時(shí)的結(jié)果比較。人工計(jì)算的方法多使用1個(gè)裁床，超裁數(shù)量為59 件，且個(gè)別尺碼超裁數(shù)量超過了2%，由于裁床數(shù)量多，裁剪時(shí)間也最長(zhǎng)。智能算法結(jié)果比人工計(jì)算要提高很多，PSO 算法收斂速度快，遺傳算法進(jìn)化比較穩(wěn)定?；旌纤惴ㄔ诟鞣矫鏀?shù)據(jù)均優(yōu)于其他算法，且裁剪超出數(shù)量比人工計(jì)算減少50%以上，時(shí)間縮短了5 min；與單個(gè)改進(jìn)遺傳算法相比，裁剪超出數(shù)量少了6 件，裁剪時(shí)間提升了0.24 min，算法執(zhí)行時(shí)間加快了16.2%，面料的利用率也保持在較高水平。

表2 多種算法的裁剪分床方案最優(yōu)結(jié)果Table 2 Results of cut order planning schemes based on multiple algorithms

從表3中比較結(jié)果可以看出，在使用不同維度的目標(biāo)函數(shù)模型時(shí)，算法優(yōu)化的方向是不同的。與考慮三種目標(biāo)的結(jié)果相比，不考慮裁剪時(shí)間和面料利用率得到了超出數(shù)量為18 的結(jié)果，而裁剪時(shí)間增加了7.96 min，面料利用率則下降了3 個(gè)百分點(diǎn)；考慮其中兩個(gè)目標(biāo)時(shí)，則剩余目標(biāo)會(huì)造成較大的浪費(fèi)。

表3 不同維度目標(biāo)函數(shù)情況下的結(jié)果Table 3 Results under different dimensional objective functions

4 結(jié)束語(yǔ)

本文針對(duì)服裝生產(chǎn)企業(yè)的裁剪分床問題，充分考慮生產(chǎn)條件，提供了一個(gè)動(dòng)態(tài)的多維目標(biāo)函數(shù)模型，使企業(yè)可以根據(jù)自身生產(chǎn)需求調(diào)整裁剪方案，提出了使用一種基于雙種群的混合粒子群-遺傳算法來求解多目標(biāo)模型的流程方法。使用混合算法對(duì)企業(yè)生產(chǎn)的一個(gè)具體訂單信息進(jìn)行了裁剪分床計(jì)劃的制定，并與當(dāng)下的人工計(jì)算方法、粒子群優(yōu)化算法、遺傳算法進(jìn)行了對(duì)比。

結(jié)果表明，雙種群粒子群混合遺傳算法進(jìn)化過程結(jié)合了粒子群和遺傳算法的優(yōu)勢(shì)，提升了算法執(zhí)行效率的同時(shí)能穩(wěn)定尋優(yōu)。與手工計(jì)算結(jié)果相比，裁床數(shù)量減少1個(gè)，超出裁剪數(shù)量降低了60%左右，實(shí)際裁剪時(shí)間減少5 min。同時(shí)分析了實(shí)際生產(chǎn)中需求目標(biāo)不同對(duì)裁剪方案的影響，針對(duì)不同的目標(biāo)模型尋求最適宜的裁剪分床方案。證明了本文混合算法有著優(yōu)秀的尋優(yōu)能力，且表現(xiàn)穩(wěn)定，能夠適應(yīng)不同的生產(chǎn)環(huán)境，滿足多種生產(chǎn)需求。

后續(xù)研究可以將進(jìn)化種群進(jìn)行更系統(tǒng)的分類，突出層次結(jié)構(gòu)，深度結(jié)合兩種優(yōu)化算法，進(jìn)一步提升裁剪分床過程中的效率和生產(chǎn)利潤(rùn)。