(浙江工業(yè)大學(xué) 經(jīng)貿(mào)管理學(xué)院，浙江 杭州 310023)

在當(dāng)前的世界經(jīng)濟(jì)大環(huán)境下，客戶(hù)對(duì)產(chǎn)品的需求日趨個(gè)性化、迅速化和多樣化(比如：蘋(píng)果公司在設(shè)計(jì)出新的iPhone手機(jī)后，便要求遍布全球的生產(chǎn)商快速進(jìn)行各部分零部件的生產(chǎn)。除了手機(jī)之外，相關(guān)配套充電器和耳機(jī)等附屬產(chǎn)品也要同時(shí)生產(chǎn)。部件生產(chǎn)出來(lái)后，中國(guó)和東南亞的裝配商迅速組裝產(chǎn)品并第一時(shí)間發(fā)貨給蘋(píng)果公司，由其在全世界范圍內(nèi)進(jìn)行統(tǒng)一發(fā)售)。很多國(guó)家的生產(chǎn)企業(yè)為了適應(yīng)當(dāng)前的經(jīng)濟(jì)形勢(shì)，調(diào)整了自身的傳統(tǒng)流水線生產(chǎn)模式，改為采用更為先進(jìn)和便捷的生產(chǎn)模式。自1960年開(kāi)始，日本豐田公司采用U型生產(chǎn)線進(jìn)行多品種、小批量化產(chǎn)品生產(chǎn)實(shí)踐和改革。20世紀(jì)90年代，日本電子行業(yè)中的Sony公司將豐田的精益理念和索尼的單人生產(chǎn)結(jié)合起來(lái)，拆除冗長(zhǎng)的裝配式傳送帶，構(gòu)建了SERU生產(chǎn)系統(tǒng)。隨后，松下、佳能、東芝、日電顯示器和理光公司等企業(yè)開(kāi)始采用SERU生產(chǎn)方式進(jìn)行產(chǎn)品生產(chǎn)。美國(guó)戴爾和韓國(guó)三星等世界知名企業(yè)也相繼效仿這種先進(jìn)的生產(chǎn)模式。20世紀(jì)60年代，部分中國(guó)企業(yè)逐漸采用了單元生產(chǎn)(Cell manufacturing，CM)或成組技術(shù)(Group technology，GT)進(jìn)行傳統(tǒng)流水線的改造。SERU和CM生產(chǎn)方式既有相同點(diǎn)，又存在一些差異。SERU和CM都是基于產(chǎn)品或工件的加工工藝進(jìn)行零部件的分族之后，再將相關(guān)機(jī)器分配給相應(yīng)的零部件族并按U型進(jìn)行機(jī)器布置。對(duì)于CM[1-2]來(lái)講，由于機(jī)器有限導(dǎo)致某個(gè)U型加工單元不能滿(mǎn)足單元內(nèi)產(chǎn)品族所有產(chǎn)品的加工需求，因此經(jīng)常出現(xiàn)跨單元加工的現(xiàn)象。對(duì)于SERU而言，盡量保證每個(gè)加工單元有足夠的機(jī)器，使得每個(gè)加工單元可以保證加工一個(gè)或多個(gè)產(chǎn)品族，因此基本不存在跨單元現(xiàn)象。CM和SERU雖然都強(qiáng)調(diào)工人的靈活性，但是對(duì)交叉培訓(xùn)的重視程度不一樣，SERU更加看重工人的技能，所有采用SERU的企業(yè)都鼓勵(lì)工人進(jìn)行交叉培訓(xùn)，從而使工人獲得更多技能。SERU和CM中主要有3 種單元類(lèi)型：屋臺(tái)式、逐兔式和分割式。屋臺(tái)式是來(lái)源于日本街頭的流動(dòng)小吃車(chē)運(yùn)作模式，十幾種小吃都由老板一人按客人需求制作完成。屋臺(tái)式的生產(chǎn)特點(diǎn)是整個(gè)單元的工作由一個(gè)人完成，加工機(jī)器的數(shù)量充足，工人具備全部技能。屋臺(tái)式的優(yōu)點(diǎn)是工序間的調(diào)整時(shí)間較小，工人的個(gè)人成就感強(qiáng)；缺點(diǎn)是個(gè)人移動(dòng)距離相對(duì)較長(zhǎng)，設(shè)備需要量大，工人掌握全部技能的時(shí)間長(zhǎng)。逐兔式的生產(chǎn)特點(diǎn)是單元內(nèi)部同時(shí)有幾個(gè)工人進(jìn)行工作，每個(gè)工人單獨(dú)完成所有加工任務(wù)，一個(gè)工人完成了當(dāng)前機(jī)器上的加工任務(wù)就立刻轉(zhuǎn)到下一個(gè)機(jī)器上進(jìn)行操作，從而讓出當(dāng)前的機(jī)器給后面的工人使用，工作過(guò)程類(lèi)似于你追我趕的狀態(tài)。逐兔式的優(yōu)點(diǎn)是單元得到充分利用，生產(chǎn)效率提高，節(jié)省了單元構(gòu)建成本；缺點(diǎn)是整個(gè)單元的效率受制于最慢的工人的工作速度，對(duì)于生產(chǎn)節(jié)拍的一致性要求高，同樣需要掌握全面技能的工人。分割式的生產(chǎn)特點(diǎn)是一個(gè)單元內(nèi)部有幾個(gè)工人同時(shí)作業(yè)，每個(gè)工人負(fù)責(zé)幾臺(tái)機(jī)器，一個(gè)完整的加工任務(wù)由幾個(gè)工人共同協(xié)作完成。分割式的優(yōu)點(diǎn)是不需要全技能工人，交叉培訓(xùn)時(shí)間短；缺點(diǎn)是需要工人相互協(xié)作保證生產(chǎn)節(jié)拍一致性。

在考慮加工單元能力有限、產(chǎn)品的提前期和拖期懲罰以及不同產(chǎn)品間前后加工工具轉(zhuǎn)換成本的前提下，筆者研究了在SERU系統(tǒng)中如何保證產(chǎn)品的按時(shí)交貨且SERU使用數(shù)量最少的問(wèn)題。研究的意義是在滿(mǎn)足產(chǎn)品交貨期的情況下，以最小的代價(jià)(機(jī)器和人員)快速生產(chǎn)所有產(chǎn)品。SERU數(shù)量越少意味著節(jié)約的機(jī)器和人員越多，從而可以使企業(yè)在最短的時(shí)間內(nèi)，以最低的成本滿(mǎn)足客戶(hù)需求。在問(wèn)題求解方面，筆者設(shè)計(jì)了混合雞群-教與學(xué)算法，通過(guò)與基本雞群算法和教與學(xué)算法的比較，驗(yàn)證了混合算法的適用性和有效性。

1 SERU相關(guān)研究綜述

近年來(lái)，學(xué)者們逐漸認(rèn)識(shí)到SERU系統(tǒng)涵蓋并擴(kuò)展了CM系統(tǒng)的各個(gè)方面，開(kāi)始轉(zhuǎn)向?qū)ERU系統(tǒng)的研究。Yin等[3]給出了高成本環(huán)境下SERU系統(tǒng)對(duì)制造業(yè)競(jìng)爭(zhēng)力的啟示。通過(guò)案例研究表明SERU系統(tǒng)是對(duì)精益生產(chǎn)、敏捷生產(chǎn)和單元制造的擴(kuò)展，解釋了索尼和佳能如何應(yīng)用SERU來(lái)提高生產(chǎn)力、改善產(chǎn)品質(zhì)量和增加生產(chǎn)靈活性，從而使企業(yè)能夠保持全球競(jìng)爭(zhēng)力。Yu等[4-5]闡述了SERU生產(chǎn)所帶來(lái)的利益，給出了傳統(tǒng)裝配線轉(zhuǎn)換為SERU和短生產(chǎn)線系統(tǒng)的基本原理，針對(duì)如何構(gòu)造混合SERU系統(tǒng)以及如何在混合SERU系統(tǒng)上進(jìn)行生產(chǎn)調(diào)度提供了一些啟示。Liu等[6]研究了如何將傳送帶裝配線重新配置為SERU系統(tǒng)的問(wèn)題。Zhang等[7]針對(duì)目前SERU研究主要關(guān)注經(jīng)濟(jì)績(jī)效，而忽視了環(huán)境和社會(huì)績(jī)效的現(xiàn)象，研究了SERU生產(chǎn)關(guān)鍵技術(shù)對(duì)可持續(xù)性發(fā)展的影響。Kaku[8]對(duì)SERU是否是一種可持續(xù)自造系統(tǒng)進(jìn)行了詳細(xì)的論述，通過(guò)實(shí)證研究明確了SERU可持續(xù)發(fā)展的特點(diǎn)。Liu等[9]也對(duì)如何在帶有可持續(xù)發(fā)展措施的SERU生產(chǎn)系統(tǒng)中進(jìn)行生產(chǎn)計(jì)劃進(jìn)行了相關(guān)研究。Lian等[10]以SERU生產(chǎn)系統(tǒng)為背景，在考慮工人技能集差異和熟練水平差異的情況下，解決了多技能工人分配問(wèn)題。在多目標(biāo)問(wèn)題上，Yu等[5]建立了一個(gè)多目標(biāo)優(yōu)化模型，研究了總吞吐量時(shí)間(TTPT)和總工時(shí)(TLH)兩種性能，通過(guò)對(duì)雙目標(biāo)模型的分析，給出解空間、組合復(fù)雜性和非凸性等問(wèn)題數(shù)學(xué)特性—。Villa等[11]對(duì)SERU系統(tǒng)和CM的異同進(jìn)行了理論分析和闡述。Suer等[12]研究了在SERU系統(tǒng)加工單元能力有限情況下，采用啟發(fā)式算法解決SERU系統(tǒng)單元數(shù)量最小化問(wèn)題。國(guó)內(nèi)也有很多學(xué)者關(guān)注到了這一點(diǎn)，如2009年劉晨光等[13]概括總結(jié)了日本式單元制造SERU的背景、優(yōu)劣勢(shì)、與普通單元制造的區(qū)別以及本質(zhì)特征，最后給出了研究方向。廉潔[14]對(duì)設(shè)備的SERU構(gòu)建與生產(chǎn)任務(wù)分配的協(xié)同進(jìn)行了決策研究，根據(jù)產(chǎn)品需求和機(jī)器加工能力將各類(lèi)同質(zhì)機(jī)器分成了若干相互獨(dú)立的SERU，同時(shí)解決了每個(gè)SERU中的任務(wù)生產(chǎn)順序。同樣，吳旭輝等[15]針對(duì)SERU的優(yōu)點(diǎn)，提出了一種協(xié)同改進(jìn)算法，將SERU構(gòu)建和SERU調(diào)度子問(wèn)題進(jìn)行協(xié)同優(yōu)化，改進(jìn)了已有算法的不足。

2 問(wèn)題模型

黃德才[16]研究了交貨期限制下的多機(jī)調(diào)度問(wèn)題，主要是針對(duì)如何合理地調(diào)整機(jī)器加工順序進(jìn)行調(diào)度。本研究考慮企業(yè)在產(chǎn)品交貨期限制下，以最少的加工單元數(shù)量完成訂單。如果產(chǎn)品不是嚴(yán)格滿(mǎn)足交貨時(shí)間(即產(chǎn)品被提前生產(chǎn)或拖期生產(chǎn)(Earliness/Tardiness))，則產(chǎn)生懲罰成本。此外，考慮各個(gè)產(chǎn)品生產(chǎn)過(guò)程中，不同產(chǎn)品之間的生產(chǎn)準(zhǔn)備時(shí)間(Setup time)不同，同時(shí)考慮每個(gè)SERU的加工能力相同。問(wèn)題的變量和數(shù)學(xué)模型為

Pi：第i個(gè)產(chǎn)品的加工時(shí)間。

Q：SERU的啟用成本。

Cj：SERU的加工能力。

di：第i個(gè)產(chǎn)品的交貨期。

Fi：第i個(gè)產(chǎn)品的完成時(shí)間。

Aik：0～1變量，表示產(chǎn)品k是否在產(chǎn)品i緊后加工。

N：SERU的最大加工能力。

Xij：0～1變量，表示產(chǎn)品i是否在SERU單元j中加工。

Yj：SERU單元j內(nèi)的所有產(chǎn)品加工完畢所需要的時(shí)間。

Vik：產(chǎn)品i和k之間的機(jī)器調(diào)整費(fèi)用矩陣。

Ei：產(chǎn)品i的提前交貨懲罰成本。

Ti：產(chǎn)品i的拖期懲罰成本。

m：?jiǎn)卧獢?shù)量。

n：產(chǎn)品總數(shù)量。

(1)

s.t.Fk=Fi×Aik+Pk?k,?i

(2)

Yj=max(Fi×Xij|i∈1，2，…，n) ?j

(3)

Yj≤N?j

(4)

(5)

數(shù)學(xué)模型中：式(1)表示目標(biāo)函數(shù)是最小化SERU啟用數(shù)量、提前交貨懲罰、拖期交貨懲罰和不同產(chǎn)品加工機(jī)器的調(diào)整準(zhǔn)備費(fèi)用；式(2)表示緊后產(chǎn)品的完工時(shí)間是緊前產(chǎn)品的完工時(shí)間與緊后產(chǎn)品的加工時(shí)間的和(機(jī)器的調(diào)整時(shí)間整合到產(chǎn)品加工時(shí)間)；式(3)表示SERU單元j的完工時(shí)間是其內(nèi)部最后完工產(chǎn)品的完工時(shí)間；式(4)表示SERU單元j的加工任務(wù)量不超過(guò)單元加工能力限制；式(5)表示一個(gè)產(chǎn)品只能在一個(gè)單元進(jìn)行生產(chǎn)加工。

3 雞群算法

雞群算法(Chicken swarm optimization, CSO)是由Meng等[17]于2014年10月在第5次國(guó)際群體智能會(huì)議(ICSI)上提出的一種新的仿生算法，CSO算法模擬了雞群的層次結(jié)構(gòu)和雞群覓食行為。整個(gè)雞群分為很多個(gè)由公雞帶領(lǐng)的子群，每個(gè)子群包括一只公雞、幾只母雞和幾只雛雞。不同層次等級(jí)的雞按照不同的覓食移動(dòng)規(guī)律覓食，在完整的等級(jí)層次結(jié)構(gòu)制度下，競(jìng)爭(zhēng)不斷發(fā)生在不同的雞群之間，所以不同的雞群都會(huì)有自己一定的覓食能力。該算法具有較快的收斂速度和較好的計(jì)算精度。

雞群算法的基本原理是雞群在進(jìn)行覓食行為時(shí)會(huì)有一種傾向，通過(guò)錯(cuò)誤的嘗試來(lái)獲得經(jīng)驗(yàn)和了解不同的情況。此外，它們還會(huì)根據(jù)經(jīng)驗(yàn)做出覓食決定，根據(jù)覓食經(jīng)驗(yàn)的多少，分成不同等級(jí)。不同等級(jí)的雞構(gòu)成了一個(gè)完整的社會(huì)體系，即雞群。在獲取食物的過(guò)程中，經(jīng)驗(yàn)豐富的雞占主導(dǎo)地位，并有權(quán)利分配食物，與之同一社會(huì)體系的雞可以通過(guò)其分配或在其邊上覓食獲得食物，雞群中的雞可以偷吃其他雞群中的食物。根據(jù)各層次等級(jí)的雞在雞群中的覓食行為，實(shí)現(xiàn)如下設(shè)置：

1)所有子雞群一般由一只公雞、多只母雞和多只雛雞構(gòu)成，并形成各自相對(duì)獨(dú)立的群體。

2)根據(jù)雞的適應(yīng)度值，覓食能力最好的雞認(rèn)定是公雞，最差的是雛雞。母親母雞和雛雞之間的親屬關(guān)系通過(guò)簡(jiǎn)單的隨機(jī)組合確定。

3)群體中的各種關(guān)系將在特定的時(shí)間步驟中保持不變，所有特性值將在時(shí)間步長(zhǎng)之后更新。

4)以公雞為中心點(diǎn)，其他的雞則圍繞在其周?chē)鷮ふ沂澄?，而它們可以避免其他組別的雞偷食。雛雞總是圍繞在母親母雞的身邊搜尋食物，占主導(dǎo)地位的母雞在公雞得到食物之后可以?xún)?yōu)先得到食物。

CSO算法在很多的領(lǐng)域得到了應(yīng)用，發(fā)揮了算法的性能，CSO算法在短時(shí)間內(nèi)發(fā)展迅速，逐漸完善成熟。目前，基本CSO算法及其改進(jìn)算法已經(jīng)在眾多的科研領(lǐng)域得到了廣泛且準(zhǔn)確的應(yīng)用，發(fā)揮了關(guān)鍵的作用。算法步驟為

1)初始化種群參數(shù)。初始配置算法參數(shù)，主要是初始化雞群的種群數(shù)量大小、迭代更新次數(shù)、種群各層級(jí)關(guān)系的更新速度、個(gè)體位置的維度以及比例。

2)初始化雞群。根據(jù)公雞的數(shù)量將雞群分成RN組，并將母雞隨機(jī)分配給每組。母雞是隨機(jī)選擇產(chǎn)生的，并根據(jù)母雞中母親母雞的數(shù)量，依照概率確定母親母雞與雛雞之間的關(guān)系。

3)迭代開(kāi)始，如果滿(mǎn)足層級(jí)更新要求，則更新雞群分組和他們之間的關(guān)系；否則，根據(jù)各自的覓食位置更新公式按等級(jí)制度高低進(jìn)行有序更新，然后計(jì)算更新位置后的適應(yīng)度值。

4)個(gè)體位置更新。各個(gè)位置更新公式計(jì)算形成的最優(yōu)值與原始值進(jìn)行比較，如果經(jīng)過(guò)覓食位置更新后的最優(yōu)值較大，則更新個(gè)體位置，否則保持原來(lái)位置。

5)在達(dá)到最大迭代次數(shù)后停止迭代，同時(shí)輸出最優(yōu)位置解，如果沒(méi)有達(dá)到最大迭代次數(shù)，則返回步驟3)進(jìn)行迭代循環(huán)搜索。

4 教與學(xué)算法

教與學(xué)算法(TLBO)是在2011年Rao等[18]為了解決機(jī)械設(shè)計(jì)中的優(yōu)化問(wèn)題而提出的一種人工智能算法，該算法主要是通過(guò)教師的教育來(lái)有效影響班級(jí)學(xué)生，以提高學(xué)生學(xué)習(xí)成績(jī)，通過(guò)這種模擬方式進(jìn)行尋優(yōu)操作。與其他受自然啟發(fā)的算法一樣，TLBO也是一種基于群體的優(yōu)化方法，它使用群體中的多個(gè)個(gè)體來(lái)進(jìn)行全局優(yōu)化[19]。

教與學(xué)算法假設(shè)一個(gè)班級(jí)的學(xué)生學(xué)習(xí)多門(mén)課程，學(xué)習(xí)最好的學(xué)生作為老師。學(xué)生的學(xué)習(xí)過(guò)程受到老師教學(xué)方案Xteacher、班級(jí)折中方案Xmean和教學(xué)因子TF=(1+rand(0,1))成績(jī)的差值影響Xnew=Xold+r×(Xteacher-TF×Xmean)，r=rand(0,1)。此外，學(xué)生的學(xué)習(xí)方案也受到同伴的影響，如果同伴的成績(jī)不如該學(xué)生的學(xué)習(xí)方案，則新的學(xué)習(xí)方案Xnew=Xold+r×(Xold-X)；如果同伴的學(xué)習(xí)方案優(yōu)于該學(xué)生的方案，則新的學(xué)習(xí)方案Xnew=Xold+r×(X-Xold)。在教學(xué)過(guò)程中，教的過(guò)程和學(xué)的過(guò)程之后，都要更新每個(gè)學(xué)生的學(xué)習(xí)方案。算法執(zhí)行步驟為

1)初始化學(xué)生數(shù)目、學(xué)習(xí)方案和變量的取值范圍等參數(shù)。

2)計(jì)算每名學(xué)生的成績(jī)。

3)進(jìn)入教學(xué)階段：確定學(xué)生群體中的教師，計(jì)算所有學(xué)生的折中學(xué)習(xí)方案；在教育階段，執(zhí)行老師教授課程過(guò)程，更新學(xué)生學(xué)習(xí)方案。

4)進(jìn)入學(xué)習(xí)階段：為每名學(xué)生隨機(jī)選擇班級(jí)內(nèi)的另一名同伴；學(xué)生按照同伴的學(xué)習(xí)方案進(jìn)行自身學(xué)習(xí)方案修正。

5)重復(fù)步驟2)～4)，直到滿(mǎn)足停止條件，輸出最優(yōu)解。

5 混合算法設(shè)計(jì)

5.1 問(wèn)題編碼

本研究針對(duì)日本式單元制造系統(tǒng)中SERU單元數(shù)量?jī)?yōu)化問(wèn)題，采用自然數(shù)編碼方式對(duì)產(chǎn)品加工序列進(jìn)行表示，如X=(5, 4, 6, 3, 2, 1, 7, 15, 10, 13, 8, 14, 9, 12, 11)。序列X表示產(chǎn)品安排在生產(chǎn)單元里進(jìn)行生產(chǎn)的順序，產(chǎn)品5首先安排到第1個(gè)生產(chǎn)單元，接下來(lái)安排產(chǎn)品4，如果產(chǎn)品4加入生產(chǎn)單元后超出了單元的生產(chǎn)能力，則產(chǎn)品4安排到新的生產(chǎn)單元。隨后的產(chǎn)品6到產(chǎn)品11，首先試探安排在第1個(gè)生產(chǎn)單元，如果生產(chǎn)能力不超出單元能力，則安排產(chǎn)品到該單元進(jìn)行生產(chǎn)，否則依次試探其他生產(chǎn)單元。如果所有的已經(jīng)安排產(chǎn)品加工的生產(chǎn)單元都超出能力限制，則安排當(dāng)前產(chǎn)品到新的生產(chǎn)單元進(jìn)行加工。因此，某個(gè)加工方案可能為(5, 4, 2, 1 | 6, 3, 7 | 15, 10, 9, 12 | 13, 8, 14, 11)。根據(jù)方案得到SERU數(shù)量為4，再檢驗(yàn)每個(gè)產(chǎn)品的交付期限，如果產(chǎn)品提前或者拖期交付，則產(chǎn)生相關(guān)費(fèi)用。

5.2 混合算法

由于教與學(xué)算法主要用于在求解時(shí)計(jì)算量比較小并且一致性較高的連續(xù)的非線性函數(shù)的全局解，而在SERU最開(kāi)始應(yīng)用中，是將一條很長(zhǎng)的流水加工線逐漸進(jìn)行拆分，形成多條短生產(chǎn)線，類(lèi)似于教與學(xué)算法中老師教育班級(jí)里的學(xué)生。在進(jìn)行一段時(shí)間的教學(xué)以后老師會(huì)根據(jù)學(xué)生學(xué)習(xí)的好壞進(jìn)行分類(lèi)，形成多個(gè)不同的學(xué)習(xí)圈，將學(xué)習(xí)圈假定為一條條短生產(chǎn)線，但是教與學(xué)算法中的學(xué)習(xí)圈則是由一位班里學(xué)習(xí)較好的學(xué)生帶領(lǐng)學(xué)習(xí)，學(xué)習(xí)圈的其他成員由班里成績(jī)較差的學(xué)生組成。

而雞群算法則是根據(jù)覓食能力對(duì)群體進(jìn)行分類(lèi)，覓食最好的作為群里的領(lǐng)導(dǎo)者、指導(dǎo)者和教育者；覓食較好的作為群里的傳播者；覓食最差的作為跟隨者。從細(xì)的方面來(lái)說(shuō)，每個(gè)學(xué)生所學(xué)的科目相當(dāng)于SERU中每個(gè)產(chǎn)品，每條生產(chǎn)線的各個(gè)方案就相當(dāng)于學(xué)生們的學(xué)習(xí)成績(jī)，而映射到雞群算法則是雞群中各種雞的覓食能力，基于兩種算法存在一定的可優(yōu)化性，對(duì)兩種算法進(jìn)行混合，可以進(jìn)一步提升算法的效率，優(yōu)化生產(chǎn)線。

所以本研究混合雞群算法和教與學(xué)算法，以雞群算法為主框架，結(jié)合教與學(xué)算法的教和學(xué)思想?；旌纤惴ㄔ趫?zhí)行初期保持全局最好解作為“教師”雞，然后按照雞群算法分群方法，將1 只公雞、幾只母雞和幾只小雞隨機(jī)分配給每個(gè)雞群。在基本雞群算法中，公雞自身隨機(jī)搜索。在混合算法中，公雞除了自身隨機(jī)找食過(guò)程，同時(shí)也會(huì)接受全局最好解的經(jīng)驗(yàn)“教”授過(guò)程，可以認(rèn)為公雞會(huì)偷吃其他公雞的食物。混合算法中的母雞除了采用基本雞群算法的位置更新公式之外，還增加本群公雞“教”母雞和母雞與所有群中隨機(jī)選擇的1 只公雞或母雞相互“學(xué)習(xí)”的過(guò)程?；旌纤惴ㄖ械男‰u除了跟隨母雞覓食，也加入公雞“教”小雞和小雞之間互相學(xué)習(xí)的過(guò)程。

圖1 混合雞群-教與學(xué)算法流程圖

6 數(shù)值算例

筆者算法的計(jì)算環(huán)境為Windows 10操作系統(tǒng)、AMD 2.2 GHz CPU、4 G內(nèi)存和500 G硬盤(pán)，算法采用C語(yǔ)言進(jìn)行編碼實(shí)現(xiàn)，編譯環(huán)境為VC++6.0。算法采用了C語(yǔ)言中的結(jié)構(gòu)體和數(shù)組的概念，構(gòu)建雞群的結(jié)構(gòu)體數(shù)組、子群的結(jié)構(gòu)體數(shù)組、公雞群的結(jié)構(gòu)體數(shù)組、母雞群的結(jié)構(gòu)體數(shù)組和母雞與公雞組合群的結(jié)構(gòu)體數(shù)組，每只雞的結(jié)構(gòu)Chicken{}包括雞的類(lèi)別{type: 1表示公雞；2表示母雞；3表示小雞}、雞的“教師”編號(hào){teacher: 小雞的教師是各自的母親雞；母雞的教師為本群的公雞}、雞所在的群編號(hào){group: 指出當(dāng)前的雞所在的子群}和雞的編碼結(jié)構(gòu)數(shù)組{Code: 根據(jù)產(chǎn)品個(gè)數(shù)決定的多位自然數(shù)編碼}。算法的參數(shù)為種群大小為50(分為5 個(gè)雞群，每個(gè)雞群1 只公雞、3 只母雞和6 只小雞，每只母雞帶2 只小雞)，最大迭代次數(shù)為產(chǎn)品個(gè)數(shù)的30倍，算法的學(xué)習(xí)因子、雞群算法基本公式參數(shù)參考文獻(xiàn)[17-18]。

算法的停止準(zhǔn)則為達(dá)到最大迭代次數(shù)，算法的效果評(píng)價(jià)在最好解、解平均值和達(dá)優(yōu)率3 個(gè)方面跟基本教與學(xué)算法和基本雞群算法進(jìn)行比較。算法采用小規(guī)模(產(chǎn)品個(gè)數(shù)分別為8，16，32，36，40)、中規(guī)模(產(chǎn)品個(gè)數(shù)分別為48，56，64，72，80)和較大規(guī)模(產(chǎn)品個(gè)數(shù)分別為85，90，95，98，100)算例進(jìn)行算法性能驗(yàn)證，每個(gè)規(guī)模包含5 組算例，每組算例獨(dú)立運(yùn)行30 次，每個(gè)單元的啟用費(fèi)用為100。

表1～2中給出了8 個(gè)產(chǎn)品的小規(guī)模算例產(chǎn)品間生產(chǎn)準(zhǔn)備費(fèi)用和產(chǎn)品基本數(shù)據(jù)。ei表示產(chǎn)品i的提前交貨懲罰費(fèi)用，ti表示產(chǎn)品i拖期交貨的懲罰費(fèi)用，pi表示產(chǎn)品i的加工時(shí)間，di表示產(chǎn)品i的約定交貨日期，Ji表示產(chǎn)品i(本文所有數(shù)據(jù)采用無(wú)量綱形式)。表3給出了不同規(guī)模、不同數(shù)量的產(chǎn)品所對(duì)應(yīng)的單元加工能力。

表1 8 個(gè)產(chǎn)品的產(chǎn)品間生產(chǎn)準(zhǔn)備費(fèi)用表

Table 1 Schedule of inter-product preparation costs for 8 products

產(chǎn)品J1J2J3J4J5J6J7J8J101010101010010J210001010101010J31000100101010J410101001010010J510100100101010J610101010100100J70101001010010J810101010100100

表2 8 個(gè)產(chǎn)品的基本數(shù)據(jù)表

表3 不同規(guī)模算例的單元連續(xù)工作限制表

算例部分給出了小規(guī)模問(wèn)題中8 個(gè)產(chǎn)品的問(wèn)題基本參數(shù)和相關(guān)費(fèi)用，其他算例的基本參數(shù)和相關(guān)費(fèi)用隨機(jī)生成。根據(jù)表1～2的相關(guān)數(shù)據(jù)，經(jīng)過(guò)計(jì)算得到其中一個(gè)最好解的自然數(shù)序列為(5, 3, 4, 7, 8, 6, 1, 2)，根據(jù)這個(gè)自然數(shù)序列，可以得到生產(chǎn)計(jì)劃安排如圖2所示。其中，產(chǎn)品5，3和2在第1個(gè)單元，產(chǎn)品4，7和1在第2個(gè)單元，產(chǎn)品8和6在第3個(gè)單元，因此得出單元的啟用數(shù)量為3 個(gè)，由于按此調(diào)度計(jì)劃安排，每個(gè)產(chǎn)品都不存在提前或拖期交付的情況，因此提前和拖期懲罰費(fèi)用為0。再查看產(chǎn)品間生產(chǎn)費(fèi)用表，產(chǎn)品間生產(chǎn)準(zhǔn)備費(fèi)用也為0。綜合以上情況，可以明確最好的目標(biāo)函數(shù)值為300。

圖2 8 個(gè)產(chǎn)品的生產(chǎn)調(diào)度圖

通過(guò)大量仿真算例計(jì)算，計(jì)算結(jié)果列于表4，表中列出了產(chǎn)品數(shù)量、最好解、解平均值、算法的30 次獨(dú)立運(yùn)行中達(dá)到最好解的效率、算法的30 次獨(dú)立運(yùn)行中平均每次的計(jì)算時(shí)間以及最好解所對(duì)應(yīng)的單元啟用數(shù)量。從表4可以看出：針對(duì)小規(guī)模、中規(guī)模和較大規(guī)模算例，HA都取得了不錯(cuò)的效果；從最好解方面來(lái)看，HA的計(jì)算結(jié)果取得了所有算例的最好解，而CSO和TLBO針對(duì)小規(guī)模算例和部分中規(guī)模算例取得了最好解，但是對(duì)于較大規(guī)模算例，CSO和TLBO的計(jì)算效果不夠理想；從平均值角度來(lái)看，CSO和TLBO的計(jì)算結(jié)果相差不大，無(wú)論是小規(guī)模、中規(guī)模還是大規(guī)模，HA的計(jì)算結(jié)果都明顯優(yōu)于CSO和TLBO；從達(dá)優(yōu)率方面來(lái)看，HA的魯棒性也全面優(yōu)于CSO和TLBO，HA在小規(guī)模問(wèn)題中的平均達(dá)優(yōu)率高于90%，在中規(guī)模問(wèn)題中的平均達(dá)優(yōu)率近于85%，在較大規(guī)模問(wèn)題中的平均達(dá)優(yōu)率近于80%；從平均計(jì)算時(shí)間方面來(lái)看，HA的計(jì)算時(shí)間要稍微高于CSO和TLBO算法，這一點(diǎn)可以從HA的特性中看出。由于HA結(jié)合兩個(gè)基本算法的公式，因此在算法執(zhí)行過(guò)程中會(huì)多執(zhí)行一些公式步驟，導(dǎo)致了算法的時(shí)間損失。

表4 混合雞群-教與學(xué)算法(HA)計(jì)算性能比較表

因此，綜合來(lái)看可以認(rèn)為HA在大致相同的計(jì)算時(shí)間內(nèi)取得的計(jì)算效果明顯好于CSO和TLBO算法，針對(duì)SERU單元數(shù)量?jī)?yōu)化問(wèn)題，HA不失為一種有效和適用的求解工具。

7 結(jié) 論

針對(duì)日本式單元生產(chǎn)系統(tǒng)中SERU數(shù)量?jī)?yōu)化問(wèn)題進(jìn)行了研究，提出了問(wèn)題的數(shù)學(xué)模型，并結(jié)合國(guó)際上比較新穎的兩類(lèi)智能優(yōu)化算法(CSO和TLBO)給出了問(wèn)題的混合算法作為求解工具，取得了較為理想的效果。在后續(xù)的研究中，學(xué)者們可以考慮從問(wèn)題復(fù)雜性入手，考慮多能工問(wèn)題、車(chē)間調(diào)度理論以及庫(kù)存和運(yùn)輸?shù)认嘟Y(jié)合的集成優(yōu)化問(wèn)題，也可以考慮多個(gè)目標(biāo)因素對(duì)問(wèn)題的影響。從求解工具角度來(lái)看，可以考慮提出更加高效的編碼方式和更加便捷、有效的新穎智能優(yōu)化算法。