考慮E/T懲罰的產品SERU數量優化

(浙江工業大學 經貿管理學院，浙江 杭州 310023)

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

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

1 SERU相關研究綜述

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

2 問題模型

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

Pi：第i個產品的加工時間。

Q：SERU的啟用成本。

Cj：SERU的加工能力。

di：第i個產品的交貨期。

Fi：第i個產品的完成時間。

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

N：SERU的最大加工能力。

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

Yj：SERU單元j內的所有產品加工完畢所需要的時間。

Vik：產品i和k之間的機器調整費用矩陣。

Ei：產品i的提前交貨懲罰成本。

Ti：產品i的拖期懲罰成本。

m：單元數量。

n：產品總數量。

(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)

數學模型中：式(1)表示目標函數是最小化SERU啟用數量、提前交貨懲罰、拖期交貨懲罰和不同產品加工機器的調整準備費用；式(2)表示緊后產品的完工時間是緊前產品的完工時間與緊后產品的加工時間的和(機器的調整時間整合到產品加工時間)；式(3)表示SERU單元j的完工時間是其內部最后完工產品的完工時間；式(4)表示SERU單元j的加工任務量不超過單元加工能力限制；式(5)表示一個產品只能在一個單元進行生產加工。

3 雞群算法

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

雞群算法的基本原理是雞群在進行覓食行為時會有一種傾向，通過錯誤的嘗試來獲得經驗和了解不同的情況。此外，它們還會根據經驗做出覓食決定，根據覓食經驗的多少，分成不同等級。不同等級的雞構成了一個完整的社會體系，即雞群。在獲取食物的過程中，經驗豐富的雞占主導地位，并有權利分配食物，與之同一社會體系的雞可以通過其分配或在其邊上覓食獲得食物，雞群中的雞可以偷吃其他雞群中的食物。根據各層次等級的雞在雞群中的覓食行為，實現如下設置：

1)所有子雞群一般由一只公雞、多只母雞和多只雛雞構成，并形成各自相對獨立的群體。

2)根據雞的適應度值，覓食能力最好的雞認定是公雞，最差的是雛雞。母親母雞和雛雞之間的親屬關系通過簡單的隨機組合確定。

3)群體中的各種關系將在特定的時間步驟中保持不變，所有特性值將在時間步長之后更新。

4)以公雞為中心點，其他的雞則圍繞在其周圍尋找食物，而它們可以避免其他組別的雞偷食。雛雞總是圍繞在母親母雞的身邊搜尋食物，占主導地位的母雞在公雞得到食物之后可以優先得到食物。

CSO算法在很多的領域得到了應用，發揮了算法的性能，CSO算法在短時間內發展迅速，逐漸完善成熟。目前，基本CSO算法及其改進算法已經在眾多的科研領域得到了廣泛且準確的應用，發揮了關鍵的作用。算法步驟為

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

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

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

4)個體位置更新。各個位置更新公式計算形成的最優值與原始值進行比較，如果經過覓食位置更新后的最優值較大，則更新個體位置，否則保持原來位置。

5)在達到最大迭代次數后停止迭代，同時輸出最優位置解，如果沒有達到最大迭代次數，則返回步驟3)進行迭代循環搜索。

4 教與學算法

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

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

1)初始化學生數目、學習方案和變量的取值范圍等參數。

2)計算每名學生的成績。

3)進入教學階段：確定學生群體中的教師，計算所有學生的折中學習方案；在教育階段，執行老師教授課程過程，更新學生學習方案。

4)進入學習階段：為每名學生隨機選擇班級內的另一名同伴；學生按照同伴的學習方案進行自身學習方案修正。

5)重復步驟2)～4)，直到滿足停止條件，輸出最優解。

5 混合算法設計

5.1 問題編碼

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

5.2 混合算法

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

而雞群算法則是根據覓食能力對群體進行分類，覓食最好的作為群里的領導者、指導者和教育者；覓食較好的作為群里的傳播者；覓食最差的作為跟隨者。從細的方面來說，每個學生所學的科目相當于SERU中每個產品，每條生產線的各個方案就相當于學生們的學習成績，而映射到雞群算法則是雞群中各種雞的覓食能力，基于兩種算法存在一定的可優化性，對兩種算法進行混合，可以進一步提升算法的效率，優化生產線。

所以本研究混合雞群算法和教與學算法，以雞群算法為主框架，結合教與學算法的教和學思想?；旌纤惴ㄔ趫绦谐跗诒３秩肿詈媒庾鳛椤敖處煛彪u，然后按照雞群算法分群方法，將1 只公雞、幾只母雞和幾只小雞隨機分配給每個雞群。在基本雞群算法中，公雞自身隨機搜索。在混合算法中，公雞除了自身隨機找食過程，同時也會接受全局最好解的經驗“教”授過程，可以認為公雞會偷吃其他公雞的食物?；旌纤惴ㄖ械哪鸽u除了采用基本雞群算法的位置更新公式之外，還增加本群公雞“教”母雞和母雞與所有群中隨機選擇的1 只公雞或母雞相互“學習”的過程。混合算法中的小雞除了跟隨母雞覓食，也加入公雞“教”小雞和小雞之間互相學習的過程。

圖1 混合雞群-教與學算法流程圖

6 數值算例

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

算法的停止準則為達到最大迭代次數，算法的效果評價在最好解、解平均值和達優率3 個方面跟基本教與學算法和基本雞群算法進行比較。算法采用小規模(產品個數分別為8，16，32，36，40)、中規模(產品個數分別為48，56，64，72，80)和較大規模(產品個數分別為85，90，95，98，100)算例進行算法性能驗證，每個規模包含5 組算例，每組算例獨立運行30 次，每個單元的啟用費用為100。

表1～2中給出了8 個產品的小規模算例產品間生產準備費用和產品基本數據。ei表示產品i的提前交貨懲罰費用，ti表示產品i拖期交貨的懲罰費用，pi表示產品i的加工時間，di表示產品i的約定交貨日期，Ji表示產品i(本文所有數據采用無量綱形式)。表3給出了不同規模、不同數量的產品所對應的單元加工能力。

表1 8 個產品的產品間生產準備費用表

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

產品J1J2J3J4J5J6J7J8J101010101010010J210001010101010J31000100101010J410101001010010J510100100101010J610101010100100J70101001010010J810101010100100

表2 8 個產品的基本數據表

表3 不同規模算例的單元連續工作限制表

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

圖2 8 個產品的生產調度圖

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

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

因此，綜合來看可以認為HA在大致相同的計算時間內取得的計算效果明顯好于CSO和TLBO算法，針對SERU單元數量優化問題，HA不失為一種有效和適用的求解工具。

7 結 論

針對日本式單元生產系統中SERU數量優化問題進行了研究，提出了問題的數學模型，并結合國際上比較新穎的兩類智能優化算法(CSO和TLBO)給出了問題的混合算法作為求解工具，取得了較為理想的效果。在后續的研究中，學者們可以考慮從問題復雜性入手，考慮多能工問題、車間調度理論以及庫存和運輸等相結合的集成優化問題，也可以考慮多個目標因素對問題的影響。從求解工具角度來看，可以考慮提出更加高效的編碼方式和更加便捷、有效的新穎智能優化算法。