邱紅喜 ，劉 林 ，2，裴 軍

（1.合肥工業(yè)大學(xué) 管理學(xué)院，安徽 合肥 230009；2.過(guò)程優(yōu)化與智能決策教育部重點(diǎn)實(shí)驗(yàn)室，安徽 合肥 230009）

當(dāng)今，企業(yè)之間的競(jìng)爭(zhēng)已發(fā)展成為供應(yīng)鏈與供應(yīng)鏈之間的競(jìng)爭(zhēng)。給供應(yīng)鏈環(huán)境下企業(yè)的下料問(wèn)題帶來(lái)了新的特點(diǎn)，供應(yīng)鏈下的下料問(wèn)題普遍呈現(xiàn)多目標(biāo)的特性，更注重供應(yīng)鏈中相關(guān)環(huán)節(jié)的利益平衡。

近年來(lái)許多學(xué)者對(duì)下料排產(chǎn)[1]各種問(wèn)題做了大量的研究。如參考文獻(xiàn)[2]采用離散變量?jī)?yōu)化方法對(duì)優(yōu)化目標(biāo)為廢料最短的下料模型優(yōu)化求解，并改進(jìn)了優(yōu)化下料的線性模型。參考文獻(xiàn)[3]建立了復(fù)雜約束狀態(tài)下，以綜合資源消耗最小為目標(biāo)函數(shù)的優(yōu)化下料問(wèn)題的數(shù)學(xué)模型；提出并實(shí)現(xiàn)了非定長(zhǎng)優(yōu)化和定長(zhǎng)優(yōu)化相結(jié)合的兩階段一維優(yōu)化下料方法。參考文獻(xiàn)[4]研究了余料最小和滿足顧客需求的多目標(biāo)下料問(wèn)題模型，把上述模型轉(zhuǎn)化成單目標(biāo)整數(shù)規(guī)劃模型用分支定界法求解。參考文獻(xiàn)[5]研究了由交貨時(shí)間限制較大規(guī)模的單一原材料下料問(wèn)題模型，針對(duì)該型提出DP貪婪算法發(fā)現(xiàn)下料問(wèn)題主要局限于單一的下料生產(chǎn)環(huán)節(jié)，建立的目標(biāo)和約束也沒(méi)有充分考慮復(fù)雜的生產(chǎn)環(huán)節(jié)。本文構(gòu)造一個(gè)基于余料和交貨期懲罰的多目標(biāo)模型。利用改進(jìn)的非支配排序遺傳算法來(lái)求解該模型的Pareto最優(yōu)解集。并通過(guò)實(shí)驗(yàn)仿真來(lái)驗(yàn)證算法的有效性，從而為改進(jìn)企業(yè)生產(chǎn)模式、提高企業(yè)整體競(jìng)爭(zhēng)力提供了一種新的途徑。

1 多目標(biāo)優(yōu)化的數(shù)學(xué)模型

1.1 模型假設(shè)

在充分了解并分析了實(shí)際情況后，對(duì)一維下料問(wèn)題提出如下假設(shè)：

（1）每種坯料都有各自的交貨期，若某種坯料無(wú)交貨期，則記該坯料交貨期為無(wú)窮大。

（2）每天下料的數(shù)量受到企業(yè)生產(chǎn)能力的限制，每天下料的數(shù)量等于最大下料能力。

（3）切割時(shí)由鋸縫、改換模具以及廢料處理問(wèn)題等一些因數(shù)產(chǎn)生的損耗在此不作考慮。

1.2 基于交貨期的一維下料模型

設(shè)某企業(yè)現(xiàn)有若干根長(zhǎng)為L(zhǎng)的原材料，需要截成m種不同長(zhǎng)度規(guī)格的坯料。每種坯料都有各自的交貨期tj，如何截取，從而使第一目標(biāo)是“余料最小”；其次，因企業(yè)一些特殊原因造成坯料不能按期交付，因此“不同交貨期的懲罰最小”成為第二目標(biāo)。

上述下料問(wèn)題的多目標(biāo)下料數(shù)學(xué)模型如下：

xij≥0 且 為整數(shù) ?i，j

其中：式（1）為余料最小的目標(biāo)函數(shù)；式（2）為交貨期滿意度最好的目標(biāo)函數(shù)；式（3）為原料長(zhǎng)度的約束條件；式（4）為下料的數(shù)量不能超過(guò)企業(yè)的生產(chǎn)能力的約束條件；i表示原材料的編號(hào)；j表示坯料種類編號(hào)；H表示原材料的使用數(shù)量；lj表示第 j種坯料的長(zhǎng)度；xij表示從 i號(hào)原料上截得第j種坯料的數(shù)量；dj表示第j種坯料的實(shí)際完工時(shí)間；T1～T2表示合理的交貨期區(qū)間；tmin表示最早的交貨期；tmax表示最遲的交貨期；max表示企業(yè)每天最大的生產(chǎn)能力。

2 模型求解

隨著問(wèn)題規(guī)模的增大，組合優(yōu)化問(wèn)題的搜索空間急劇擴(kuò)大，并且多為非線性規(guī)劃問(wèn)題，所以也是一個(gè)NPHard問(wèn)題。大多數(shù)對(duì)于這樣問(wèn)題，一般無(wú)法得到最優(yōu)結(jié)果或無(wú)法及時(shí)得到最優(yōu)結(jié)果。人們已意識(shí)到應(yīng)該把主要精力放在尋求其非劣解上。本文采用改進(jìn)的非支配排序遺傳算法[6]，求解該模型的優(yōu)化下料問(wèn)題不僅可以避免早熟收斂，還提高了收斂速度。

2.1 編碼

編碼方式也稱為基因表達(dá)方式，種群中的每個(gè)個(gè)體，即每個(gè)染色體是由基因構(gòu)成的。根據(jù)一維下料問(wèn)題的特點(diǎn)，選擇用坯料的一個(gè)全排列作為一個(gè)下料方案，構(gòu)成一個(gè)染色體，其中每個(gè)坯料作為基因。初始群體由需求的坯料隨機(jī)排列產(chǎn)生。例如：有待切的坯料5種，依次給每種坯料編號(hào)（1～5），這樣每個(gè)染色體的長(zhǎng)度都是固定的。原料要切出1個(gè)1號(hào)坯料，3個(gè)2號(hào)坯料，2個(gè)3號(hào)坯料，1個(gè)4號(hào)坯料，1個(gè) 5號(hào)坯料，隨機(jī)產(chǎn)生序列（5，2，1，4，3，3，2，2）就是群體中的一個(gè)個(gè)體。

2.2 擁擠距離

把非劣解集中的解（即每個(gè)個(gè)體）按某一維目標(biāo)函數(shù)降序排列，處于邊緣的個(gè)體分配給它以無(wú)窮大的距離，而剩下每個(gè)個(gè)體的擁擠距離可以通過(guò)計(jì)算同級(jí)別與其相連的兩個(gè)個(gè)體在每個(gè)目標(biāo)上的距離差之和來(lái)求取。擁擠距離大的個(gè)體參與繁殖和進(jìn)化的機(jī)會(huì)較多，從而維持種群的多樣性。擁擠距離的計(jì)算是為確保算法能收斂到一個(gè)均勻分布的Pareto曲面。

2.3 非支配排序

非支配排序的具體過(guò)程：首先找出當(dāng)前種群中非支配最優(yōu)解并分配等級(jí)1；然后將這些個(gè)體從種群中移出，在剩余個(gè)體中找出新的非支配解，再分配等級(jí)2；重復(fù)上述過(guò)程，直至種群中所有個(gè)體都被設(shè)定相應(yīng)的等級(jí)。

2.4 遺傳算子

（1）選擇算子

本文采用聯(lián)賽選擇的方法，即在群體中，隨機(jī)抽取（取值為2）個(gè)體，兩兩比較，非支配排序等級(jí)和擁擠距離皆優(yōu)者保留，直到滿足群體規(guī)模。如果兩個(gè)個(gè)體的非支配排序等級(jí)不同時(shí)，則優(yōu)先考慮等級(jí)低的個(gè)體；如果兩個(gè)個(gè)體等級(jí)相同，則優(yōu)先考慮較不擁擠的個(gè)體。

（2）交叉算子

交叉算子如果采用經(jīng)典的單點(diǎn)交叉算子，產(chǎn)生的新個(gè)體有可能出現(xiàn)重復(fù)或缺失某些基因，導(dǎo)致該個(gè)體不合法。因此交叉算子的設(shè)計(jì)采用順序交叉的方案，方法是由一染色體隨機(jī)選出一個(gè)子串，復(fù)制到一個(gè)空染色體中，形成原始后代，然后另一染色體去掉和子串重復(fù)的基因，按順序從左到右補(bǔ)齊原始后代染色體的空缺位置，這樣就得到了一個(gè)新的后代染色體。采用該方法可以防止后代染色體出現(xiàn)重復(fù)的基因或缺失基因，從根本上保證了該個(gè)體的合法性。

（3）變異算子

變異算子的設(shè)計(jì)采用K-交換變異的方案，即在每個(gè)染色體中以概率P隨機(jī)選取染色體上的兩點(diǎn)，進(jìn)行2-交換。文中采用的變異算子皆為2-交換變異。

2.5 算法流程

非支配排序遺傳算法步驟：

（1）隨機(jī)產(chǎn)生規(guī)模為 n初始化種群 P0，初始代數(shù)為g=0；

（2）非支配排序后，通過(guò)遺傳算法的選擇、交叉、變異三個(gè)基本操作得到第一代子代種群Q0；

（3）從第二代開始，將父代種群P0與子代種群Q0合并，此時(shí)種群規(guī)模變?yōu)?n，進(jìn)行快速非支配排序，同時(shí)對(duì)每個(gè)非支配層中的個(gè)體進(jìn)行擁擠距離計(jì)算；

（4）根據(jù)非支配關(guān)系以及個(gè)體的擁擠距離選擇合適的個(gè)體組成新的父代種群；

（5）采用順序交叉算子執(zhí)行交叉操作；

（6）采用2-交換變異方案執(zhí)行變異操作；

（7）判斷是否達(dá)到終止條件，達(dá)到則算法結(jié)束，否則返回步驟（3）。

3 算例

下面給出一個(gè)例子說(shuō)明上述算法的有效性。

例：下料所使用的原料長(zhǎng)度L=2 000 mm，按企業(yè)的實(shí)際生產(chǎn)規(guī)模，需要32種配切的坯料，各坯料的交貨期都為一周時(shí)間，最早交貨期期為3天，最遲交貨期為10天，產(chǎn)品合理的交貨期為5～6天。各坯料的長(zhǎng)度和需求量如表1所示。本算例中算法的種群規(guī)模為30～50，最大進(jìn)化代數(shù)為 100，交叉概率為 0.25，變異概率為0.001。

表1 坯料重量與需求量

使用Delphi7語(yǔ)言編程，經(jīng)單機(jī)運(yùn)行得出Pareto最優(yōu)解集如表2試驗(yàn)結(jié)果所示。

表2 試驗(yàn)結(jié)果

表3給出了改進(jìn)的非支配排序遺傳算法與非支配排序遺傳算法比較結(jié)果。各算法的種群規(guī)模均取30～50，進(jìn)化代數(shù)為均為100。利用參考文獻(xiàn)[7]中的公式來(lái)比較最大散布范圍、分布均勻性。最大散布范圍的值越大，則表示散布范圍越廣；分布均勻性的值越小，則表示散布越均勻。

表3 兩種算法比較

結(jié)果表明，改進(jìn)的非支配排序遺傳算法所獲得Pareto解集較為穩(wěn)定，解分布均勻，沒(méi)有出現(xiàn)過(guò)陷于局部最優(yōu)的情況。

改進(jìn)的非支配排序遺傳算法在解決多目標(biāo)優(yōu)化問(wèn)題中表現(xiàn)出較好的性能，但仍然存在理論體系不夠完善、實(shí)現(xiàn)方法不太成熟等問(wèn)題。本文的研究工作，今后可以從以下幾個(gè)方面進(jìn)一步深入研究：（1）對(duì)于非支配排序遺傳算法的繼續(xù)深入研究和改進(jìn)。（2）問(wèn)題優(yōu)化得到是一組Pareto解集，還需從這組Pareto解集中選出最滿意的解，幫助決策者選出最滿意的方案。

[1]HAESSLER R W，SWEENEY P E.Cutting stock problems and solution procedures[J].European Journal of Operation Research，1991，54：141-150.

[2]米潔.CAPP系統(tǒng)中優(yōu)化下料問(wèn)題的研究[J].機(jī)械，2001，28：30-32.

[3]閻春平，宋天峰，劉飛.面向可加工性的復(fù)雜約束狀態(tài)下一維優(yōu)化下料 [J].計(jì)算機(jī)集成制造系統(tǒng)，2010，16：195-201.

[4]林曉穎，王遠(yuǎn).多目標(biāo)優(yōu)化下料問(wèn)題的研究[J].哈爾濱師范大學(xué)自然科學(xué)學(xué)報(bào)，2003（5）：14-16.

[5]王輝，朱珠，張志敏.有交貨時(shí)間限制的大規(guī)模實(shí)用下料問(wèn)題[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2005，35：64-69.

[6]VARELA R， MU?OZ C， SIERRA M， et al.Improving cutting-stock plans with Multi-objective genetic algorithm[J].Communications in Computerand Information Science，2009， 22： 332-344.

[7]DEB K.Multi-objective optimization using evolutionary algorithms[M].New York： Jonh Wiley&sons Press， 2001：201-302.