,,
(浙江工業(yè)大學(xué) 信息工程學(xué)院,杭州 310000)
服裝行業(yè)的裁剪優(yōu)化分床問(wèn)題是根據(jù)企業(yè)的生產(chǎn)條件和相應(yīng)訂單情況,將訂單中的號(hào)型種類、數(shù)量和顏色進(jìn)行合理搭配,科學(xué)的安排裁剪床數(shù)、鋪布層數(shù)和套排規(guī)格件數(shù)[1],使得分床床數(shù)達(dá)到最少、布料消耗達(dá)到最低、生產(chǎn)效率達(dá)到最高、裁剪數(shù)量誤差最小的優(yōu)化組合問(wèn)題[2]。裁剪優(yōu)化分床一直是制約服裝行業(yè)提高生產(chǎn)效率、節(jié)約布料的難題,同樣也出現(xiàn)在箱包、家居、鞋帽等行業(yè)中。同時(shí),勞動(dòng)力成本的提升以及服裝材料價(jià)格提高,使得服裝生產(chǎn)成本越來(lái)越高。因此,通過(guò)優(yōu)化分配以減少分床數(shù)量和裁剪誤差,從而減少人工工作量,提高原材料的利用率,降低生產(chǎn)成本,能夠產(chǎn)生巨大的經(jīng)濟(jì)效益,具有重大的現(xiàn)實(shí)意義[3]。
傳統(tǒng)的數(shù)學(xué)思維分床方法具有一定的規(guī)范性,但是效率比較低,分床結(jié)果誤差比較大,仍然得不到比較理想的分床方案。但相比于人工分床的效率有顯著提高,且分床結(jié)果誤差可顯著減少。傳統(tǒng)的數(shù)學(xué)思維分床方法主要有分組法、加減法、并床法、比例法[4-5]、取半法[6]、等量?jī)?yōu)化分床法[7]、試湊法等。這些方法對(duì)生產(chǎn)訂單的數(shù)據(jù)要求較高,各號(hào)型樣片數(shù)量之間必須具備某種特定的關(guān)系,具有一定的局限性,只適用于一些特定的訂單,并不適用于實(shí)際的分床訂單[7-8]。
因此,為了解決目前在裁剪分床領(lǐng)域遇到的這一難題,本文引入現(xiàn)代智能優(yōu)化算法,在經(jīng)典粒子群優(yōu)化算法(particle swarm optimization,PSO)的基礎(chǔ)上,設(shè)計(jì)一種基于自適應(yīng)加速因子粒子群優(yōu)化算法(SAPSO)的裁剪分床方法。利用SAPSO算法的簡(jiǎn)單易實(shí)現(xiàn)、參數(shù)個(gè)數(shù)少、收斂速度快等特點(diǎn),以各號(hào)型樣片裁剪數(shù)量誤差平方和為目標(biāo),建立裁剪優(yōu)化分配求解的數(shù)學(xué)模型。最后,通過(guò)分床實(shí)例驗(yàn)證了該方法的有效性。
服裝裁剪分床是根據(jù)生產(chǎn)訂單要求和企業(yè)生產(chǎn)條件,將生產(chǎn)訂單中各號(hào)型樣片件數(shù)、顏色進(jìn)行合理的組合搭配,科學(xué)地制定出裁剪分床床數(shù)、各床鋪布層數(shù)、各號(hào)型套排的配比,并降低布料損耗、減少工時(shí)消耗、提高生產(chǎn)效率的工藝設(shè)計(jì)過(guò)程,俗稱分床。裁剪分床主要包括以下幾個(gè)方面:(1)生產(chǎn)訂單裁剪分床床數(shù)。裁剪分床床數(shù)決定了裁剪工時(shí)的消耗;(2)每床需要鋪的號(hào)型種類,每個(gè)號(hào)型鋪布的件數(shù)。在生產(chǎn)條件允許的范圍內(nèi),套排號(hào)型種類越多越節(jié)約原材料;(3)每床需要鋪布料的層數(shù)。在生產(chǎn)條件允許的鋪布層數(shù)范圍內(nèi),鋪布層數(shù)越大,裁剪的效率就會(huì)越高。由于在同一床里具有不同號(hào)型,不同號(hào)型套排的件數(shù)也不一樣,因此需要進(jìn)行合理的優(yōu)化搭配。
設(shè)某服裝生產(chǎn)訂單有m種號(hào)型,每種號(hào)型的裁剪數(shù)量為Di(i=1,2,...,m)、每種號(hào)型允許的最大裁剪誤差數(shù)量ρ,裁床的鋪布層數(shù)Cnt的上限Cntmax和下限Cntmin,各號(hào)型樣片在每床上配比Pb的上限Pbmax,最佳的分床床數(shù)t。因此,裁剪分床求解的數(shù)學(xué)模型為:
(1)
約束條件為:
(2)
其中:Ai表示第i種號(hào)型樣片實(shí)際裁剪的件數(shù),Pbij表示第i種號(hào)型樣片在第j床上套排的件數(shù),Cntj表示第j床上的鋪布層數(shù),εi表示第i種號(hào)型的裁剪誤差件數(shù),F(xiàn)value表示各號(hào)型樣片實(shí)際裁剪件數(shù)與目標(biāo)裁剪件數(shù)之差的平方和。裁剪分床是在滿足約束條件的前提下,求解使目標(biāo)Fvalue最小的鋪布層數(shù)Cntj和對(duì)應(yīng)的配比Pbij。將上式表示成矩陣的形式:
A=Pb×Cnt
(3)
ε=A-D
(4)
A是各號(hào)型樣片實(shí)際裁剪數(shù)量矩陣;Pb是各號(hào)型樣片在各床上套排的件數(shù)組成的矩陣,也稱配比矩陣,其中每一行表示某種號(hào)型樣片在各床上套排的件數(shù);Cnt是各床鋪布層數(shù)的矩陣;ε是各號(hào)型樣片裁剪數(shù)量的誤差矩陣。
由于本模型是非線性的,采用常規(guī)的解析法無(wú)法進(jìn)行求解,因此引入現(xiàn)代智能優(yōu)化算法。現(xiàn)代智能優(yōu)化算法很多,但是其中很多算法參數(shù)比較多,復(fù)雜度較大,實(shí)現(xiàn)起來(lái)比較難。而粒子群優(yōu)化算法比較簡(jiǎn)單,參數(shù)較少,收斂速度快,實(shí)現(xiàn)起來(lái)比較容易,再結(jié)合本模型及裁剪分床的實(shí)際情況,優(yōu)先選擇粒子群優(yōu)化算法進(jìn)行求解。
2.1.1 PSO算法
經(jīng)典粒子群優(yōu)化算法(PSO)是由Kennedy和Eberhart于1995年提出的一種種群優(yōu)化算法[9-11],PSO算法具有概念簡(jiǎn)單、實(shí)現(xiàn)容易、精度高、收斂速度快和需要調(diào)整的參數(shù)少等優(yōu)點(diǎn),是一種啟發(fā)式算法[12-13]。該算法可表述如下:在K維的搜索空間ΩK內(nèi),種群的大小M(即粒子的數(shù)量),種群中第i個(gè)粒子的位置值αi={α1,α2,…,αM},速度向量值vi={v1,v2,…,vM},其中粒子的歷史最好位置Pbesti={Pbest1,Pbest2,…,PbestM},當(dāng)前整個(gè)種群的全局最好位置Gbest。每個(gè)粒子的速度向量值和位置向量值的更新公式分別為:
(5)
(6)
2.1.2 SAPSO算法
針對(duì)經(jīng)典粒子群優(yōu)化算法求解離散優(yōu)化問(wèn)題容易陷入局部最優(yōu)的問(wèn)題[14],在經(jīng)典粒子群優(yōu)化算法中引入自適應(yīng)加速因子,設(shè)計(jì)了一種基于自適應(yīng)加速因子粒子群優(yōu)化算法。其中自適應(yīng)加速因子與算法迭代次數(shù)成反比關(guān)系,迭代次數(shù)越大,自適應(yīng)加速因子越小。因此在算法搜索的前期,自適應(yīng)加速因子較大,算法的全局搜索能力較強(qiáng),在算法搜索的后期,自適應(yīng)加速因子較小,算法的局部搜索能力較強(qiáng),收斂速度更快,搜索效率更高。自適應(yīng)加速因子粒子群優(yōu)化算法(SAPSO)的速度和位置更新公式分別為:
(7)
(8)
自適應(yīng)加速因子為:
(9)
其中:γ為正整數(shù),n為當(dāng)前迭代次數(shù),N為最大迭代次數(shù)。
本文采用SAPSO算法進(jìn)行裁剪分床方案的設(shè)計(jì),其實(shí)現(xiàn)過(guò)程如圖1裁剪分床實(shí)現(xiàn)流程圖所示。
圖1 裁剪分床實(shí)現(xiàn)流程圖
第一步,設(shè)定裁剪分床過(guò)程中的初始條件,其中包括裁剪分床限制條件和SAPSO算法參數(shù);第二步,根據(jù)各號(hào)型所要裁剪的總件數(shù)、每床鋪布層數(shù)的上限和下限、每層布可裁剪服裝號(hào)型樣片件數(shù)上限和下限來(lái)計(jì)算可能的分床床數(shù);第三步,采用SAPSO算法搜索各床上的鋪布層數(shù):以各床上的鋪布層數(shù)作為粒子的位置,給各床在搜索空間內(nèi)隨機(jī)初始化一個(gè)層數(shù),同理初始化速度值,將第一個(gè)粒子的位置當(dāng)做局部最優(yōu)和全局最優(yōu)的初始值,并且將初始適應(yīng)值設(shè)置為正無(wú)窮大;第四步,再采用SAPSO算法搜索在對(duì)應(yīng)鋪布層數(shù)下,使配比粒子適應(yīng)值最小的配比;第五步,根據(jù)當(dāng)前鋪布層數(shù)及對(duì)應(yīng)的局部最優(yōu)值和全局最優(yōu)值,更新鋪布層數(shù)粒子的速度值和位置值,再計(jì)算鋪布層數(shù)更新后的適應(yīng)值,以更新鋪布層數(shù)粒子的局部最優(yōu)值和全局最優(yōu)值;第六步,若迭代次數(shù)達(dá)到設(shè)定值,則以最終搜索的各床鋪布層數(shù)和各號(hào)型在各床上最優(yōu)配比作為分床方案,否則轉(zhuǎn)到第四步繼續(xù)搜索。
1)首先由用戶根據(jù)實(shí)際的生產(chǎn)條件設(shè)定每床鋪布層數(shù)Cnt的上限Cntmax和下限Cntmin,每層布可裁剪樣片總件數(shù)T的上限Tmax和下限Tmin,每種號(hào)型樣片每床排的件數(shù)Pb的上限Pbmax,各號(hào)型樣片所需裁剪的件數(shù)Si;自適應(yīng)加速因子正整數(shù)參數(shù)γ,認(rèn)知因子c1,社會(huì)因子c2,算法迭代過(guò)程中層數(shù)粒子速度向量的最大限幅Vcmax、配比粒子速度向量的最大限幅Vbmax。
2)然后根據(jù)各號(hào)型樣片所需裁剪的件數(shù)計(jì)算出各號(hào)型樣片所需裁剪的數(shù)量總和:
(10)
平均每床鋪布層數(shù):
(11)
平均每層布裁剪的件數(shù):
(12)
根據(jù)以上結(jié)果計(jì)算出所需分床數(shù)量Bedi的上限:
(13)
所需的分床數(shù)量下限:
(14)
其中:ceil和floor分別表示向上取整和向下取整。
3)由于計(jì)算出來(lái)的分床床數(shù)Bed是在一個(gè)有限的范圍內(nèi),所以先搜索床數(shù)小的分床方案,如果床數(shù)小的方案不符合要求,再去搜索床數(shù)大的分床方案。在某一分床床數(shù)情況下,采用SAPSO算法搜索鋪布層數(shù),其算法搜索過(guò)程如圖2所示。
圖2 鋪布層數(shù)粒子搜索流程圖
4)以各床上的鋪布層數(shù)作為粒子的位置,給各床在搜索空間ΩK(鋪布層數(shù)限制范圍)內(nèi)隨機(jī)初始化一個(gè)層數(shù),同理初始化M個(gè)粒子{Cnt1,Cnt2,…,CntM},以及速度向量值{v1,v2,…,vM},以各號(hào)型樣片誤差平方和為適應(yīng)值Fvalue。令各個(gè)粒子的初始個(gè)體歷史最優(yōu)Pbesti=Cnti,粒子的全局最優(yōu)Gbest=Cnt1。
5)再采用SAPSO算法搜索在對(duì)應(yīng)鋪布層數(shù)下,使Fvalue最小的配比Pb:其搜索過(guò)程如圖3所示。
圖3 配比粒子搜索流程圖
(1)將第j種號(hào)型樣片在各床上的配比作為粒子的位置Pbi,在搜索空間ΨK(配比的限制范圍)內(nèi),給該號(hào)型樣片在各床上的配比隨機(jī)初始化一個(gè)值,同理初始化M個(gè)粒子{Pb1,Pb2,…,PbM},速度向量值{vb1,vb2,…,vbM}。令各個(gè)粒子的個(gè)體歷史最優(yōu)Pbest1i=Pbi,粒子的全局最優(yōu)Gbest1i=ceil(Pb1)。(2)根據(jù)配比粒子速度更新公式:
(15)
(16)
Fvalue1i=[ceil(Pbi)×Cnti-Dj]2
(17)
通過(guò)比較前后兩次適應(yīng)值的大小來(lái)更新粒子的歷史最優(yōu)配比Pbest1i,以及全局最優(yōu)配比Gbest1j。(5)迭代次數(shù)n1=n1+1,若迭代次數(shù)達(dá)到設(shè)定值N1,給出所有號(hào)型樣片對(duì)應(yīng)鋪布層數(shù)下的最優(yōu)配比Gbest1j,結(jié)束搜索;否則轉(zhuǎn)到步驟(2)繼續(xù)搜索。同理搜索其他號(hào)型樣片在各床上的配比。
6)再根據(jù)鋪布層數(shù)粒子的速度更新公式:
(18)
7)再根據(jù)位置更新公式:
(19)
8)然后計(jì)算所有粒子的適應(yīng)值Fvaluei:
(20)
通過(guò)比較前后兩次適應(yīng)值的大小來(lái)更新局部最優(yōu)Pbesti和全局最優(yōu)Gbest。
9)迭代次數(shù)n=n+1,若迭代次數(shù)達(dá)到設(shè)定值N,則輸出所有號(hào)型樣片最優(yōu)的鋪布層數(shù)Gbest和對(duì)應(yīng)的所有號(hào)型樣片的最優(yōu)配比Gbest1,結(jié)束搜索;否則轉(zhuǎn)到步驟5)繼續(xù)搜索。
本實(shí)驗(yàn)的配置環(huán)境:硬件配置為Intel Core i3-2310M,CPU主頻為2.40 GHz,4 GB內(nèi)存;軟件環(huán)境:64位Windows7操作系統(tǒng),安裝Microsoft Visual C++ 2013軟件開(kāi)發(fā)平臺(tái)。本方法選擇一個(gè)包含6種號(hào)型和一個(gè)包含5種號(hào)型的實(shí)際生產(chǎn)訂單進(jìn)行實(shí)驗(yàn)分析。通過(guò)與等量?jī)?yōu)化分床法分床結(jié)果進(jìn)行對(duì)比分析,在分床結(jié)果誤差和用料預(yù)算上進(jìn)行比較,對(duì)SAPSO算法的性能進(jìn)行測(cè)試,兩者分別針對(duì)相同的生產(chǎn)訂單進(jìn)行分床實(shí)驗(yàn);與經(jīng)典PSO算法進(jìn)行分床效率的比較。SAPSO算法分床過(guò)程中兩次的設(shè)置參數(shù)相同,算法參數(shù)設(shè)置如下:最大迭代次數(shù)N=N1=100,自適應(yīng)加速因子中正整數(shù)參數(shù)γ=100,認(rèn)知因子c1和社會(huì)因子c2都取值2,種群大小為M=20。算法迭代過(guò)程中層數(shù)粒子速度向量的最大限度Vcmax=20、配比粒子速度向量的最大限幅Vbmax=2。分別對(duì)兩個(gè)訂單進(jìn)行分床,兩種方法的分床結(jié)果如圖4和圖5所示。
圖4 訂單一兩種方法的分床結(jié)果
圖4為6種號(hào)型訂單兩種方法的分床結(jié)果,其中(a)為等量?jī)?yōu)化分床法結(jié)果,(b)為SAPSO算法分床結(jié)果;圖5為5種號(hào)型訂單兩種方法的分床結(jié)果,其中(a)為等量?jī)?yōu)化分床法結(jié)果,(b)為SAPSO算法分床結(jié)果。對(duì)比兩種分床方法的結(jié)果,在相同的約束條件與相同的生產(chǎn)訂單情況下,采用SAPSO算法進(jìn)行分床的結(jié)果明顯比等量?jī)?yōu)化分床法分床結(jié)果誤差??;在用料預(yù)算上,SAPSO算法分床結(jié)果比等量?jī)?yōu)化分床法用料預(yù)算更少,更節(jié)省原材料。雖然在用料預(yù)算上提高的不多,但對(duì)于訂單量上億的大型企業(yè)來(lái)說(shuō)帶來(lái)的經(jīng)濟(jì)效益也是不容忽視的。
圖6為經(jīng)典PSO算法與SAPSO算法的適應(yīng)度曲線,從兩者的適應(yīng)度曲線可以看出,SAPSO算法分床在迭代23次左右搜索到最優(yōu)解,PSO算法分床在迭代52次左右搜索到最優(yōu)解,從圖6中可以看出SAPSO算法收斂性比PSO算法更快,分床效率更高。
圖5 訂單二兩種方法的分床結(jié)果
圖6 PSO與SAPSO算法適應(yīng)度曲線(實(shí)線—SAPSO,虛線—PSO)
本文設(shè)計(jì)的基于SAPSO算法裁剪分床的方法,通過(guò)將裁剪分床的鋪布層數(shù)和各號(hào)型在各床上的配比抽象成SAPSO算法中的粒子進(jìn)行搜索,有效地減小裁剪誤差,從而提高原材料的利用率,給服裝行業(yè)的裁剪分床問(wèn)題提供了一種新的解決方法。該方法簡(jiǎn)單易行,需要調(diào)整的參數(shù)少,且收斂速度快。實(shí)驗(yàn)結(jié)果表明SAPSO算法分床的誤差比等量?jī)?yōu)化分床法小,并且在用料預(yù)算上SAPSO算法分床更少,更節(jié)約原材料。SAPSO算法收斂速度比PSO算法快、耗費(fèi)時(shí)間短,效率更高。
[1] 劉艷梅, 顏少聰, 紀(jì)楊建,等. 大批量定制服裝裁剪分床計(jì)劃的兩階段優(yōu)化方法[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2012,18(3):479-485.
[2] 劉吉慶. 制訂裁剪分配方案的研究[J]. 包裝世界, 2009(4):108-110.
[3] 庹 武, 鄭 攀, 常亭亭, 等. 基于層次分析法的服裝裁剪分床影響因素[J]. 紡織學(xué)報(bào), 2013,34(4):148-152.
[4] 師 華, 戴 鴻. 服裝企業(yè)裁剪分床案例分析與探討[J]. 山東紡織經(jīng)濟(jì), 2008(5):117-118.
[5] Degraeve Z, Gochet W, Jans R. Alternative formulations for a layout problem in the fashion industry[J]. European Journal of Operational Research, 2002,143(1):80-93.
[6] 姜 蕾. 服裝生產(chǎn)工藝與設(shè)備[M]. 北京:中國(guó)紡織出版社, 2004.
[7] 鄭 攀, 庹 武. 服裝裁剪自動(dòng)分床系統(tǒng)的研究與開(kāi)發(fā)[J]. 山東紡織經(jīng)濟(jì), 2013,(11):76-79.
[8] 王曉云, 黃珍珍, 張洪志, 等. 服裝裁剪工藝計(jì)劃優(yōu)化系統(tǒng)的開(kāi)發(fā)研究[J]. 價(jià)值工程, 2010,29(5):187-188.
[9] 李明陽(yáng), 嚴(yán) 華. 改進(jìn)粒子群算法在云計(jì)算負(fù)載均衡中的應(yīng)用研究[J]. 計(jì)算機(jī)測(cè)量與控制, 2016,24(10):219-221.
[10] 潘 峰. 粒子群優(yōu)化算法與多目標(biāo)優(yōu)化[M]. 北京:北京理工大學(xué)出版社, 2013.
[11] Kennedy J, Eberhart R. Particle swarm optimization[A]. IEEE International Conference on Neural Networks, Proceedings[C]. IEEE, 1995(4):1942-1948.
[12] 程 躍, 程文明, 鄭 嚴(yán). 基于改進(jìn)粒子群算法的中藥提取過(guò)程PID優(yōu)化控制[J]. 計(jì)算機(jī)測(cè)量與控制, 2010,18(3):533-534.
[13] Ma L, Forouraghi B. A Modified Particle Swarm Optimizer. Advances in Natural Computation[M]. Springer Berlin Heidelberg, 2012.
[14] 趙鴻圖, 劉 云. 改進(jìn)粒子群算法的小波神經(jīng)網(wǎng)絡(luò)語(yǔ)音去噪[J]. 計(jì)算機(jī)測(cè)量與控制, 2013,21(10):2799-2800.