引言

當(dāng)前,定制化家具企業(yè)面臨著訂單種類(lèi)和數(shù)量逐漸增加的問(wèn)題,而排樣是企業(yè)生產(chǎn)加工的首要工序,其好壞程度直接影響生產(chǎn)成本。定制化家具排樣可理解為企業(yè)利用機(jī)械設(shè)備從一定規(guī)格的原板材中切割出組裝成整套家具的矩形零件,從生產(chǎn)成本的角度來(lái)說(shuō),板材利用率越高,所需板材越少,成本越低。

基于此種情況,部分學(xué)者采用不同方法對(duì)矩形件排樣問(wèn)題展開(kāi)了研究。Sanchez等人將模擬退火算法和遺傳算法相結(jié)合,一定程度上提高了板材利用率:羅強(qiáng)等人提出了一種改進(jìn)的十進(jìn)制灰狼算法,根據(jù)排樣圖形狀設(shè)計(jì)定位算法,求解矩形件排樣問(wèn)題:王莉結(jié)合模擬退火算法和基于匹配度的最低水平線排樣算法,求解以利用率最大化為目標(biāo)的問(wèn)題模型:郭文文等人考慮工藝約束和機(jī)器刀縫限制,設(shè)計(jì)不同切割規(guī)則求解,以提高利用率?；依撬惴ㄊ且环N群智能算法,由于其較為良好的全局搜索和局部搜索能力,受到廣泛關(guān)注,目前,在聚類(lèi)分析、路徑規(guī)劃、車(chē)間調(diào)度[7]等諸多領(lǐng)域得到應(yīng)用。

本文擬基于定制化家具矩形件排樣問(wèn)題中零件差異性較大的特點(diǎn),以板材利用率最大化為求解目標(biāo),應(yīng)用改進(jìn)的灰狼算法進(jìn)行求解,提高板材利用率,減少板材數(shù)量消耗,降低生產(chǎn)成本,提高企業(yè)的經(jīng)濟(jì)效益。

1數(shù)學(xué)模型

1.1問(wèn)題描述

本文以定制化家具矩形件排樣問(wèn)題為研究對(duì)象,排樣問(wèn)題是定制化家具生成的首道工序,直接影響整個(gè)訂單的后續(xù)生產(chǎn)加工。該排樣問(wèn)題可描述為:將長(zhǎng)度和寬度分別為"i和wi的待切割矩形件排布在長(zhǎng)寬固定且為H和w的原板材上,零件的排放位置不能超出板材的邊界,零件在排放的過(guò)程中不能互相重疊。針對(duì)定制化家具,采用木材作為原板材,其尺寸固定,而訂單中待排零件尺寸不一,所以每張板材上排放的零件數(shù)b亦不相同,如何合理安排零件的排布順序和位置,盡可能實(shí)現(xiàn)每張?jiān)宀牡睦寐首畲蠡?減少?gòu)U料和余料的生成,從而實(shí)現(xiàn)整體利用率最大化,是本文要考慮的關(guān)鍵問(wèn)題。

1.2模型建立

模型主要基于以下假設(shè):

(1)排樣過(guò)程中,考慮零件紋理,矩形件不能旋轉(zhuǎn)90o;

(2)實(shí)際排樣時(shí),不考慮異形零件;

(3)排樣過(guò)程中,原板材的尺寸固定,數(shù)量充足。

其中,約束條件(1)表示原板材利用率最大化,Ha表示最后一張板材所使用的高度,以板材的左下角為坐標(biāo)原點(diǎn),(xi,yi)表示零件排入板材后零件左下角的坐標(biāo)。約束條件(2)和(3)表示零件不超出原板材的邊界,約束條件(4)和(5)不同時(shí)成立,表示原板材上的零件互相不重疊。

2改進(jìn)的灰狼算法

排樣問(wèn)題在實(shí)際求解過(guò)程中,可以分為零件的定序和定位問(wèn)題。定序問(wèn)題為第一步,決定零件的排布順序,考慮運(yùn)用改進(jìn)的灰狼算法,并調(diào)整游走和奔襲策略,實(shí)現(xiàn)從全局優(yōu)化到局部?jī)?yōu)化的過(guò)程;定位問(wèn)題為第二步,確定待排零件序列在原板材上的排布位置,該過(guò)程考慮使用改進(jìn)的最低水平線算法,適當(dāng)調(diào)整零件在板材上的排布位置和順序,實(shí)現(xiàn)排樣利用率最大化。

2.1改進(jìn)的最低水平線定位算法

改進(jìn)的最低水平線算法是一種更有效的排樣定位算法,其主要思想是:找到板材上的最低水平線,判斷其寬度w和當(dāng)前待排零件的寬度l的大小,若w<l,則判斷下一個(gè)零件的寬度與水平線寬度的大小,找到可排零件排入,否則更新水平線序列,尋找最低水平線,繼續(xù)排放零件,直到零件全部排完。

改進(jìn)的最低水平線定位算法流程如下:

(1)初始化參數(shù);

(2)選取第i張板材,初始化水平線序列;

(3)從待排零件中選取第一個(gè)可排入零件;

(4)若step3中存在可排入零件,則排入零件,返回step3,否則進(jìn)入下一步;

(5)判斷此時(shí)的水平線序列是否為一條,若是,則i=i＋1,返回step2,否則進(jìn)入下一步;

(6)提升水平線序列,更新最低水平線,若零件未排完,則返回step3,否則結(jié)束;

(7)排樣完成,輸出排樣結(jié)果。

2.2灰狼定序算法

灰狼優(yōu)化算法也稱"狼群算法",是基于狼群群體智能,模擬狼群捕食行為及其獵物分配方式,抽象出游走、召喚、圍攻三種智能行為以及"勝者為王"的頭狼產(chǎn)生規(guī)則和“強(qiáng)者生存"的狼群更新機(jī)制而提出的一種新的群體智能算法。

本文將改進(jìn)的灰狼定序算法與最低水平線定位算法相結(jié)合,一個(gè)在解空間中不斷地搜索更優(yōu)解,另一個(gè)解碼計(jì)算當(dāng)前利用率,每次迭代都保存最佳排樣方案,不斷更新迭代,直到達(dá)到最大利用率或者最大迭代次數(shù)。對(duì)算法中根據(jù)狼群行為抽象出來(lái)的游走和奔襲策略進(jìn)行簡(jiǎn)單更改,盡量使游走過(guò)程中種群的差異性增大,提升全局搜索范圍。在奔襲過(guò)程中,重新定義種群和頭狼之間的距離,并不斷讓種群向頭狼靠近,實(shí)現(xiàn)局部搜索。

(1)編碼。結(jié)合矩形件排樣問(wèn)題,采用十進(jìn)制的編碼方式對(duì)零件序列進(jìn)行編碼,例如(1,3,5,2,4)表示在原板材上依次排入零件1、零件3、零件5、零件2和零件4。

(2)初始種群。采用十進(jìn)制的編碼方式對(duì)所有的待排零件進(jìn)行編碼,形成一個(gè)從數(shù)字1開(kāi)始的連續(xù)不重復(fù)十進(jìn)制整數(shù)零件序列,從而得到一個(gè)灰狼個(gè)體。按照該方式,隨機(jī)生成不同的零件序列,形成初始種群。

(3)游走。即將一個(gè)灰狼中的某一個(gè)編碼位向左或向右移動(dòng)一個(gè)較大的距離,例如將灰狼Zi=(1,3,5,2,4)中的第一個(gè)編碼位的:i1向右移動(dòng)4個(gè)單位長(zhǎng)度變?yōu)閆i'=(3,5,2,4,1)?；谄髽I(yè)加工情況調(diào)研,大部分零件在實(shí)際切割時(shí)有紋理要求,本文不進(jìn)行旋轉(zhuǎn)。定義游走策略為r(Zi,0,s,d),表示從第i個(gè)灰狼Zi=(:i1,:i2,:i3,…,:in)的可編碼位0=(1,2,3,…,n)中選擇連續(xù)的s個(gè)編碼位進(jìn)行位移為d的操作。在文本中,若連續(xù)的s個(gè)編碼位的起始位置小于(1+n)/2,則向右位移,否則向左位移,盡可能增大游走范圍,實(shí)現(xiàn)游走過(guò)程中的全局搜索。

(4)奔襲。即灰狼向頭狼靠近的過(guò)程,用灰狼與頭狼對(duì)應(yīng)編碼位的值不同的個(gè)數(shù)體現(xiàn)其距離,例如灰狼Zi=(1,3,5,2,4),頭狼Z=(1,2,3,4,5),灰狼和頭狼的編碼位2、編碼位3、編碼位4和編碼位5對(duì)應(yīng)的數(shù)都不相同,則定義兩者的距離為4。奔襲策略R(Zi,L1,L2,d)表示選擇第i個(gè)灰狼Zi=(:i1,:i2,:i3,…,:in)中與頭狼編碼位不同的前d個(gè)編碼位,用頭狼中對(duì)應(yīng)位置替代,例如若L1=(2,3,4,5),L2=(2,3,4,5),則R(Zi,L1,L2,1)表示用頭狼Z中第2個(gè)編碼位中的數(shù)將灰狼Zi中數(shù)進(jìn)行替代,得到奔襲后的灰狼Zi'=(1,2,5,3,4)。

(5)解碼。解碼是運(yùn)用改進(jìn)的最低水平線算法將一串有序、不重復(fù)、代表矩形件的十進(jìn)制整數(shù)序列轉(zhuǎn)化為零件排布圖。整個(gè)解碼過(guò)程中,會(huì)對(duì)序列進(jìn)行簡(jiǎn)單調(diào)整,為保證編碼的有效性,該十進(jìn)制整數(shù)序列不存在兩個(gè)相等的數(shù)且不遺漏任何一個(gè)整數(shù)。

3算例分析

3.1某批次訂單零件尺寸

根據(jù)某制定化企業(yè)的生產(chǎn)情況,選取了5個(gè)不同批次的生產(chǎn)訂單,為滿足零件排樣要求,將所有訂單數(shù)據(jù)按照零件尺寸、材料進(jìn)行整理,表1為其中一個(gè)批次的部分訂單數(shù)據(jù)信息。

基于訂單數(shù)據(jù)信息可知,由于單個(gè)訂單中零件數(shù)量一般較少,對(duì)訂單零件進(jìn)行排樣前,會(huì)將訂單按照其交貨期合并到一個(gè)批次,從而減少生產(chǎn)過(guò)程中的切換頻率,在一定程度上提高利用率,本文中每一個(gè)批次零件的材質(zhì)、顏色和厚度相同,所有零件均可排布在尺寸為2440mm×1220mm的原板材上。

3.2實(shí)例計(jì)算

根據(jù)矩形件排樣問(wèn)題的數(shù)學(xué)模型,結(jié)合各批次的零件尺寸,以原板材的利用率最大化為目標(biāo)進(jìn)行求解。對(duì)比訂單分批后的經(jīng)驗(yàn)算法,將算法運(yùn)行50次,得到不同批次的利用率及其所需板材數(shù)量,如表2所示。

在不同的排樣批次中,為了較充分地比較算法的有效性,分別選取了不同零件規(guī)模的算例,零件個(gè)數(shù)從42個(gè)到196個(gè)不等,將本文中的改進(jìn)灰狼算法和企業(yè)訂單分批后所使用的經(jīng)驗(yàn)算法進(jìn)行比較,板材利用率均有不同程度的提升,分別提升了8.58%、5.23%、7.13%、9.36%和7.31%,對(duì)應(yīng)批次所需板材的數(shù)量分別減少2、3、1、4和4塊。改進(jìn)的灰狼算法較經(jīng)驗(yàn)算法利用率有較大的提升,減少了企業(yè)生產(chǎn)成本,提高了企業(yè)的生產(chǎn)效益。

部分零件的排布情況如圖1所示。

4總結(jié)與展望

本文應(yīng)用改進(jìn)的灰狼算法求解定制化家具矩形件排樣問(wèn)題,針對(duì)排樣優(yōu)化中的零件定序和定位問(wèn)題,改進(jìn)灰狼定序算法中游走、奔襲策略和最低水平線定位策略,實(shí)現(xiàn)從全局求解到局部求解的優(yōu)化過(guò)程,并與實(shí)際的經(jīng)驗(yàn)排樣算法對(duì)比,利用率有較大程度的提升。但文中都是單個(gè)批次分別排樣,未考慮整個(gè)排樣過(guò)程中廢料與余料再利用的情況,且文中待排零件都是已分類(lèi)完成的,未考慮零件本身的尺寸情況對(duì)排樣利用率的影響,以上兩個(gè)方面還有待進(jìn)一步研究。