矩陣式編碼智能算法在生產(chǎn)批量計(jì)劃中的應(yīng)用

（中國(guó)計(jì)量大學(xué) 質(zhì)量與安全工程學(xué)院，杭州 310018）

生產(chǎn)批量計(jì)劃問(wèn)題是確定最優(yōu)的生產(chǎn)批量計(jì)劃，使得生產(chǎn)、生產(chǎn)準(zhǔn)備和庫(kù)存費(fèi)用綜合指標(biāo)最小或利潤(rùn)最大[1-2]。受到資源約束的情況下，為消除各種資源間的沖突，需要同時(shí)對(duì)項(xiàng)目、時(shí)間和數(shù)量這三維變量進(jìn)行調(diào)整[3-4]，隨著求解問(wèn)題規(guī)模的增大，精確解的計(jì)算量也增大。

遺傳算法在求解大規(guī)模問(wèn)題時(shí)易陷入局部最優(yōu)解中，從而難以得到符合預(yù)期的解[5-7]。在研究生產(chǎn)批量計(jì)劃問(wèn)題時(shí)，也有學(xué)者將粒子群算法和遺傳算法相結(jié)合，一定程度上彌補(bǔ)了GA局部搜索能力弱的缺陷，但可能以損失種群多樣性為代價(jià)降低算法搜索效率，最終搜索得到的解不易滿足預(yù)期要求。利用蟻群算法求解生產(chǎn)批量問(wèn)題的相關(guān)研究較少，少數(shù)學(xué)者進(jìn)行了一些研究，并將研究成果應(yīng)用在固定的模型與生產(chǎn)實(shí)例中[8]。

本文對(duì)求解算法進(jìn)行創(chuàng)新性的改進(jìn)以提升算法性能。通過(guò)矩陣式編碼的智能算法尋到近似最優(yōu)的生產(chǎn)批量計(jì)劃并將所求的結(jié)果與基本遺傳算法和遺傳粒子群算法進(jìn)行對(duì)比，以證明改進(jìn)算法提升了算法性能。

1 生產(chǎn)批量計(jì)劃問(wèn)題的數(shù)學(xué)模型

本文所考慮有能力約束的多級(jí)生產(chǎn)批量CMLLS（constrained multilevel lot-sizing）問(wèn)題，問(wèn)題描述為在給定的計(jì)劃時(shí)間范圍內(nèi)，確定全部項(xiàng)目在不同時(shí)間段上的生產(chǎn)數(shù)量，使得總費(fèi)用之和最小。CMLLS問(wèn)題與實(shí)際生產(chǎn)計(jì)劃更加貼近，是生產(chǎn)批量問(wèn)題研究的重點(diǎn)。本文采用的數(shù)學(xué)模型為[9-10]

式（1）為總費(fèi)用，包括生產(chǎn)準(zhǔn)備費(fèi)用及庫(kù)存費(fèi)用；式（2）為物流守衡方程；式（3）為需求公式，如果物料i是最終項(xiàng)目，則需求為外部需求，否則需求由當(dāng)前物料i的所有后繼物料的生產(chǎn)量決定；式（4）為資源約束條件；式（5）為只有在生產(chǎn)數(shù)量大于0時(shí)才能進(jìn)行生產(chǎn)調(diào)整；式（6）為二進(jìn)制決策變量，1表示生產(chǎn)，0表示不生產(chǎn)；式（7）為生產(chǎn)量和庫(kù)存量不能為負(fù)數(shù)。

2 遺傳算法的改進(jìn)策略

2.1 改進(jìn)方法

遺傳算法求解過(guò)程本質(zhì)上是隨機(jī)尋優(yōu)過(guò)程，但是遺傳算法是按照概率隨機(jī)進(jìn)行的尋優(yōu)操作，在大多數(shù)情況下只能得到全局范圍的次優(yōu)解，不易獲得最優(yōu)解，這是因?yàn)樗乃阉魇请S機(jī)的，帶有一定的盲目性[12]。

粒子群算法對(duì)自身參數(shù)的依賴很大，且初始粒子群是隨機(jī)生成的，通常具有收斂速度慢、易陷入局部收斂等方面的缺陷[13]。

蟻群算法雖然通用性、魯棒性較好，以及在各個(gè)領(lǐng)域的廣泛應(yīng)用近些年來(lái)受到越來(lái)越多的關(guān)注，但是把傳統(tǒng)蟻群算法應(yīng)用于求解涂料生產(chǎn)調(diào)度時(shí)，難以滿足所有的約束條件[14]。

鑒于遺傳算法、蟻群算法和粒子群算法存在一定的不足，本文將遺傳算法、蟻群算法和粒子群算法融合以便于生產(chǎn)批量計(jì)劃的求解，具體的計(jì)算步驟為

步驟1隨機(jī)生成粒子位置，并按照上述算法得到初始種群（粒子群）。初始化全局極值和個(gè)體極值為第一個(gè)個(gè)體（粒子）的適應(yīng)度函數(shù)值；

步驟2對(duì)當(dāng)前種群（粒子群）的各個(gè)個(gè)體（粒子）描述求解適應(yīng)度函數(shù)值；

步驟3按照適應(yīng)度函數(shù)值對(duì)當(dāng)前種群 （粒子群）進(jìn)行排序，找出個(gè)體極值和全局極值；

步驟4選擇：用5個(gè)隨機(jī)的新個(gè)體替換種群（粒子群）中適應(yīng)度函數(shù)值較差的5個(gè)個(gè)體（粒子）；

步驟5交叉：以輪盤賭博方式，改變種群（粒子群）中的部分個(gè)體（粒子）的特性；

步驟6變異：采用粒子群算法的更新規(guī)則對(duì)種群（粒子群）中的所有個(gè)體（粒子）進(jìn)行更新；

步驟7變異：采用蟻群算法的信息素全局更新規(guī)則中的所有個(gè)體（粒子）進(jìn)行更新；

步驟8變異：采用蟻群算法的信息素局部更新規(guī)則中的所有個(gè)體（粒子）進(jìn)行更新；

步驟9查看是否達(dá)到最大迭代次數(shù)，如果是則轉(zhuǎn)步驟8，否則轉(zhuǎn)步驟2；

步驟10仿真結(jié)束。

具體的改進(jìn)結(jié)合蟻群算法的遺傳粒子群算法的計(jì)算流程如圖1所示。

2.2 編碼方式

為使用本文提出的粒子群、蟻群和遺傳算法結(jié)合的智能算法，我們將生產(chǎn)批量進(jìn)行編碼作為個(gè)體（粒子），其目的是讓計(jì)算機(jī)能夠利用矩陣計(jì)算以大幅提高計(jì)算效率。個(gè)體（粒子）選擇1～2048之間的隨機(jī)整數(shù)。具體的某粒子矩陣式編碼表如表1所示。

為了使用粒子群算法的位置和速度更新公式，需要對(duì)粒子速度進(jìn)行編碼。具體的某粒子速度矩陣式編碼表如表2所示。其中，粒子速度選擇-128～128之間的隨機(jī)整數(shù)。

定義粒子在粒子群算法中的更新算法。更新的粒子位置矩陣由舊的粒子位置矩陣和粒子速度矩陣相加，當(dāng)新的粒子編碼矩陣中的元素越界時(shí)，越界元素由新的1～2048之間的隨機(jī)整數(shù)進(jìn)行替換。

圖1 改進(jìn)的智能算法流程Fig.1 Flow chart of improved intelligent algorithm

表1 某粒子矩陣式編碼表Tab.1 A particle matrix encoding table

表2 某粒子速度矩陣式編碼表Tab.2 A particle velocity matrix encoding table

本文在計(jì)算過(guò)程中采用矩陣計(jì)算。顯然，相較于簡(jiǎn)單的數(shù)字計(jì)算，矩陣計(jì)算具有計(jì)算速度敏捷的優(yōu)點(diǎn)。

3 實(shí)例測(cè)試

3.1 仿真實(shí)例

小型機(jī)是一種輕量型的計(jì)算機(jī)。本文收集到某計(jì)算機(jī)生產(chǎn)廠家接到一批2016年度的小型機(jī)訂單，該訂單要在一年內(nèi)交付897臺(tái)小型機(jī)，各月至少需要的交付數(shù)量為 51、8、45、98、86、57、6、181、139、57、27、142。生產(chǎn)1件小型機(jī)需要事先生產(chǎn)得到7個(gè)小型機(jī)箱體A和9件小型機(jī)外包裝。由于電子器件壽命、員工工資變化、生產(chǎn)和裝配造成的機(jī)器耗損和廠房維修等各種因素每月各異，小型機(jī)處理器、箱體和外包裝的生產(chǎn)費(fèi)用、裝配費(fèi)用、庫(kù)存費(fèi)用每月各異，具體如表3～表5所示。

表3 小型機(jī)單件生產(chǎn)費(fèi)用月度表（單位：元，每月平均值）Tab.3 Minicomputer piece production cost monthly report（Unit：Yuan，monthly average）

表4 小型機(jī)裝配費(fèi)用月度表（單位：元，每月平均值）Tab.4 Minicomputer assembly cost monthly report（Unit：Yuan，monthly average）

表5 小型機(jī)單件庫(kù)存費(fèi)用月度表（單位：元，每月平均值）Tab.5 Minicomputer piece inventory cost monthly report（Unit：Yuan，monthly average）

裝配和生產(chǎn)小型機(jī)需要對(duì)小型機(jī)處理器、箱體和外包裝的外側(cè)噴塑（一層輕薄的塑料薄膜，生產(chǎn)和裝配前貼住，生產(chǎn)和裝配完成時(shí)揭下）以形成保護(hù)層，防止小型機(jī)處理器、箱體和外包裝意外受損。由于溫度、濕度等各種因素每月各異，每件部件的噴塑損失每月各異，具體如表6～表7所示。

表6 小型機(jī)裝配過(guò)程噴塑損失月度表（單位：cm3/件，每月平均值）Tab.6 Minicomputer spraying plastics losses monthly report in the assembling process（Unit：cm3/piece，monthly average）

表7 小型機(jī)庫(kù)存過(guò)程噴塑損失月度表（單位：cm3/件，每月平均值）Tab.7 Minicomputer spraying plastics losses monthly report in the inventory process（Unit：cm3/piece，monthly average）

廠家根據(jù)環(huán)境保障局的相關(guān)規(guī)定，計(jì)劃生產(chǎn)該批次小型機(jī)造成的噴塑損失不超過(guò)645000 cm3。

廠家希望結(jié)合生產(chǎn)需求給出較為合理的生產(chǎn)批量計(jì)劃以盡可能小的成本生產(chǎn)該批量897臺(tái)小型機(jī)，即在上述條件下，尋求每個(gè)月的生產(chǎn)小型機(jī)的數(shù)量以使生產(chǎn)費(fèi)用、裝配費(fèi)用和庫(kù)存費(fèi)用的綜合成本費(fèi)用盡可能的省。

3.2 仿真結(jié)果

對(duì)于上述實(shí)際應(yīng)用算例，采用矩陣式編碼的遺傳算法、蟻群算法和粒子群算法結(jié)合的智能算法連續(xù)仿真20次可以得到下述仿真結(jié)果。具體的20次仿真過(guò)程中最優(yōu)結(jié)果的當(dāng)前代最優(yōu)解與進(jìn)化代數(shù)的關(guān)系曲線如圖2所示。

圖2 當(dāng)前代最優(yōu)解與進(jìn)化代數(shù)的關(guān)系Fig.2 Relation curve between the optimal solution of current generation and the evolutionary algebra

具體的20次仿真過(guò)程中最優(yōu)解函數(shù)值和收斂代數(shù)與進(jìn)化代數(shù)的關(guān)系曲線如圖3所示。

圖3 最優(yōu)解函數(shù)值和收斂代數(shù)與進(jìn)化代數(shù)的關(guān)系Fig.3 Relation curve between the optimal solution and the convergence algebra of current generation and the evolutionary algebra

由圖3可知，20次仿真過(guò)程中每一次計(jì)算得到的最優(yōu)解函數(shù)值Y∈（2.2×106，2.3×106）元，收斂代數(shù)小于200代。證明了本文提出的智能算法具有良好的收斂性能，適于解決多級(jí)有資源約束生產(chǎn)批量計(jì)劃問(wèn)題。

本文基于上述實(shí)際應(yīng)用算例對(duì)提出的矩陣式編碼的智能算法和普通粒子群（PSO）算法和遺傳算法進(jìn)行對(duì)比測(cè)試。具體的測(cè)試結(jié)果如圖4所示。

圖4 實(shí)際應(yīng)用算例的數(shù)學(xué)模型的測(cè)試結(jié)果Fig.4 Results of mathematical model of practical application example

由圖4可知，本文提出的矩陣式編碼的智能算法較優(yōu)，得到的最優(yōu)解更接近于實(shí)際最優(yōu)解且收斂速度更快。最優(yōu)解函數(shù)值Y＜2.25×106元。

為了驗(yàn)證本文提出的智能算法相比于基本粒子群算法收斂性更好，采用相同算例，多次試驗(yàn)仿真結(jié)果如表8所示。

表8 改進(jìn)的算法與粒子群算法的結(jié)果比較Tab.8 Comparison of the results of improved algorithm and particle swarm optimization algorithm

由表8可知，改進(jìn)后的算法相比于基本粒子群算法，計(jì)算時(shí)間減少了一半左右，計(jì)算結(jié)果的適應(yīng)度值也有明顯改善。

4 結(jié)語(yǔ)

如何實(shí)現(xiàn)生產(chǎn)費(fèi)用、生產(chǎn)準(zhǔn)備費(fèi)用和庫(kù)存費(fèi)用綜合指標(biāo)最小或利潤(rùn)最大，是關(guān)系企業(yè)生存與發(fā)展的重要課題。本文提出的一種新型的矩陣式編碼的蟻群算法、遺傳算法和粒子群算法相結(jié)合的智能算法有高速的計(jì)算性能、便于搜索近似最優(yōu)解，可以得到比傳統(tǒng)算法更好的計(jì)算效果，能滿足當(dāng)代企業(yè)對(duì)生產(chǎn)批量精確的要求。

[1]梁海峰.基于仿真的柔性自動(dòng)化鋼料加工車間規(guī)劃設(shè)計(jì)研究[D].大連：大連理工大學(xué)，2005.

[2]屈國(guó)強(qiáng).求解流水車間調(diào)度問(wèn)題的瓶頸指向啟發(fā)式算法[J].計(jì)算機(jī)集成制造系統(tǒng)，2012，18（2）：356-363.

[3]Ruiz R，V-R J A.The hybrid flowshop scheduling problem[J]. European Journal of Operational Research，2010，205（1）：1-18.

[4]周輝仁，唐萬(wàn)生，魏穎輝.柔性Flow-Shop調(diào)度的遺傳算法優(yōu)化[J].計(jì)算機(jī)工程與應(yīng)用，2009，45（30）：224-226.

[5]唐海波，葉春明，劉長(zhǎng)平，等.基于知識(shí)進(jìn)化粒子群算法的模糊交貨期流水車間調(diào)度問(wèn)題[J].計(jì)算機(jī)集成制造系統(tǒng)，2012，18（4）：807-812.

[6]王圣堯，王凌，許燁，等.求解混合流水車間調(diào)度問(wèn)題的分布估計(jì)算法[J].自動(dòng)化學(xué)報(bào)，2012，38（3）：437-443.

[7]M N，Hansen P.Variable neighborhood search[J].Computers&Operations Research，1997，24（11）：145-184.

[8]李英俊，陳志祥.蟻群算法在單級(jí)多時(shí)段多資源約束的生產(chǎn)批量問(wèn)題的應(yīng)用研究[J].中國(guó)機(jī)械工程，2012，23（19）：2326-2330.

[9]Pan Q K，Ruiz R.An estimation of distribution algorithm for lot-streaming flow shop problems with setup times[J].Omega，2012，40（2）：166-180.

[10]周云鵬，題正義.遺傳算法在組合優(yōu)化中的應(yīng)用[J].遼寧工程技術(shù)大學(xué)學(xué)報(bào)：自然科學(xué)版，2005，24（z1）：283-285.

[11]Xu Y，Wang L，Zhou G，et al.An effective shuffled frog leaping algorithm for solving hybrid flow-shop scheduling problem[C]// Proceedings of the International Conference on intelligent Computing，Zhengzhou，China：Springer，2011.

[12]唐立新，楊自厚，王夢(mèng)光，等.CIMS中帶多資源的CLMS問(wèn)題的遺傳啟發(fā)式算法[J].系統(tǒng)工程理論與實(shí)踐，1997，17（4）：39-44.

[13]馬慧民，柳毅，葉春明.基于粒子群算法求解單級(jí)多資源約束生產(chǎn)批量計(jì)劃問(wèn)題[J].工業(yè)工程與管理，2005，10（6）：66-70.

[14]馬艷，黃玲，蘇受寶.含再制造的受限批量問(wèn)題求解的蟻群算法[J].計(jì)算機(jī)應(yīng)用與軟件，2011，28（2）：96-99.