王 玉，朱凱燕，成谞虓WANG Yu,ZHU Kai-yan,CHENG Xu-xiao

（1.廣東商學(xué)院 信息學(xué)院，廣東 廣州 510320；2.同濟大學(xué) 管理學(xué)院，上海 200092）

(1.School of Information Science,Guangdong University of Business Studies,Guangzhou 510320,China;2.School of Economics and Management,Tongji University,Shanghai 200092,China)

0 引 言

大規(guī)模定制企業(yè)的客戶需求多變，如何根據(jù)客戶的定制需求制定出合適的生產(chǎn)計劃，及時對客戶需求做出反應(yīng)是大規(guī)模定制企業(yè)需要解決的關(guān)鍵問題之一。大規(guī)模定制是大規(guī)模生產(chǎn)和定制生產(chǎn)的有機結(jié)合，其供應(yīng)鏈是推式供應(yīng)鏈與拉式供應(yīng)鏈的結(jié)合，即推拉相結(jié)合的供應(yīng)鏈。推拉供應(yīng)鏈的分界點為客戶訂單分離點 （customer order decoupling point，CODP）。CODP分離的上游計劃是基于預(yù)測，下游計劃是基于訂單。這就意味著上游的活動運作可通過主生產(chǎn)計劃 （master production schedule，MPS），而下游通過車間調(diào)度 （job shop schedule）來管理和控制其生產(chǎn)活動[1]。由于MPS調(diào)度問題通常存在眾多的約束，使之成為非常難解的NP完全性復(fù)雜的優(yōu)化問題。本文就結(jié)合廣州某大規(guī)模定制企業(yè)的汽輪機生產(chǎn)過程，建立大規(guī)模定制企業(yè)的生產(chǎn)調(diào)度優(yōu)化模型，并用粒子群算法進行了求解。

1 大規(guī)模定制的生產(chǎn)調(diào)度模型

大規(guī)模定制供應(yīng)鏈中，CODP定位處是基于預(yù)測與基于訂單驅(qū)動生產(chǎn)的結(jié)合，在特定的時期內(nèi)，產(chǎn)品種類、數(shù)量都是動態(tài)變化的，具有不確定性。但是，由于產(chǎn)品結(jié)構(gòu)的模塊化、規(guī)范化，使得其生產(chǎn)在一定程度上呈現(xiàn)出工藝的相似性與產(chǎn)品的同質(zhì)性，這樣該節(jié)點的生產(chǎn)在一段時期具有一定的連續(xù)性及相關(guān)性，如生產(chǎn)主要集中在幾種產(chǎn)品上，而其到達時間與需求量是不確定的。因此該節(jié)點的生產(chǎn)任務(wù)通常由兩部分組成，一是基于預(yù)測的已有任務(wù)，二是隨機到來的訂單，但隨機到來的訂單產(chǎn)品又具有一定的規(guī)律性。因此，要根據(jù)大規(guī)模定制的特性來安排訂單的生產(chǎn)。大規(guī)模定制中，客戶一旦下訂單，就要在承諾的時間內(nèi)提交產(chǎn)品和服務(wù)。交貨時間的變動是按一定時間周期的，如交貨時間是n天、n周、n月等，其變動周期為天、周、月。因此，必然有很多訂單的交貨期在同一周期內(nèi)。如同一天，同一周，或同一月。由于在同一周期內(nèi)交貨，對這些訂單的生產(chǎn)就可以按優(yōu)化的生產(chǎn)順序，而不是按下訂單的先后順序。把同一周期內(nèi)的訂單生產(chǎn)的優(yōu)化，稱為同一時間窗口的優(yōu)化。而跨周期的生產(chǎn)訂單，由于交貨期的限制，因此，必須先下訂單的先生產(chǎn)。下面針對同一時間窗口的訂單進行調(diào)度分析。

大規(guī)模定制生產(chǎn)商將同一時間窗口T內(nèi)接到的訂單進行分類、合并，并對生產(chǎn)過程進行調(diào)度。調(diào)度過程包括企業(yè)任務(wù)排序及各子任務(wù)開工時間確定。這里調(diào)度的例子是某MC機械廠汽輪機的生產(chǎn)過程。汽輪機是技術(shù)密集型產(chǎn)品，產(chǎn)品結(jié)構(gòu)比較復(fù)雜，可靠性要求很高，主要零部件要求耐高溫、耐沖擊和高精度。平均每臺汽輪機有近5000個零部件。汽輪機的BOM有多層結(jié)構(gòu)，這里主要分析兩層。第一層主要由汽缸、油箱底盤、主汽門、前軸承座、前軸承、汽封管路、調(diào)節(jié)閥、轉(zhuǎn)子部套、隔板部套組成。第二層中汽缸主要由前汽缸、后汽缸、管接頭組成；油箱底盤主要由濾網(wǎng)、通汽裝置、蓋板組成；主汽門主要由管接頭、濾網(wǎng)組成；前軸承座主要由蓋、除汽器組成；前軸承主要由軸承蓋、前徑向軸承瓦組成；汽封管路主要由前汽封、排汽管組成；轉(zhuǎn)子部套核心是轉(zhuǎn)子，由汽封環(huán)、白銅絲、接長軸、螺釘、螺栓、銷等組成；隔板部套主要由隔板1A、隔板2A、隔板3A組成。汽輪機采用了組合產(chǎn)品的設(shè)計原理，將產(chǎn)品分解成不同的標準模塊，如同搭積木一樣，可以根據(jù)客戶的個性化需求，將有限數(shù)量的標準模塊組合起來，形成不同的定制產(chǎn)品。如圖1是一種汽輪機的定制產(chǎn)品圖。

該廠汽輪機的生產(chǎn)主要有5個車間組成，隔板車間、汽缸車間、轉(zhuǎn)子裝配車間、箱體車間和總裝車間。對汽輪機的生產(chǎn)加工點進行簡化后，可以用圖2來表示汽輪機的整個生產(chǎn)過程。

圖2 汽輪機的生產(chǎn)鏈

根據(jù)圖2，可以將汽輪機的生產(chǎn)根據(jù)某類定制訂單的生產(chǎn)分解為18個子任務(wù)。其中隔板車間的子任務(wù)經(jīng)過P1、P2、P3、P4的加工過程；汽缸車間的子任務(wù)經(jīng)過P5、P6、P7的加工過程；轉(zhuǎn)子車間的子任務(wù)經(jīng)過P8、P9、P10的加工過程；箱體車間的子任務(wù)經(jīng)過P11、P12、P13的加工過程；總裝車間的子任務(wù)經(jīng)過P14、P15、P16、P17、P18的加工過程。當(dāng)考慮同一時間窗口下多個訂單的綜合調(diào)度時，各訂單子任務(wù)之間約束關(guān)系復(fù)雜，任何選擇及調(diào)度偏差都將導(dǎo)致訂單生產(chǎn)時間、生產(chǎn)成本及庫存成本的變化，影響生產(chǎn)鏈效率。

調(diào)度模型的假設(shè)如下：

·在建立的模型中對于定制子任務(wù)，加工成本及加工時間固定且已知。由于所有調(diào)度方案的加工成本是相同的，所以在模型里不考慮加工成本。

·忽略企業(yè)之間的訂貨、運輸時間及成本，僅考慮庫存成本、加工時間、訂單延遲損失與訂單的優(yōu)先級別。

·MC生產(chǎn)商的生產(chǎn)目標是，在盡可能滿足各訂單交貨時間約束的條件下，盡量滿足優(yōu)先級順序，之后盡早完成全部訂單任務(wù)，并降低生產(chǎn)及在制品庫存成本。

·當(dāng)交貨周期≤生產(chǎn)周期時，生產(chǎn)商需要大于正常生產(chǎn)能力才能完成交貨，此時可能產(chǎn)生拖期交貨現(xiàn)象，產(chǎn)生缺貨成本。αi表示為定制產(chǎn)品i拖期生產(chǎn)單位時間內(nèi)的懲罰因子；βi表示沒有滿足定制品i的單位時間內(nèi)的懲罰因子[2]。

設(shè)MC生產(chǎn)商在時間域值T內(nèi)接到M個訂單，每個訂單都可以分解為Ni（i=1,2,…,M）個子任務(wù)，每個訂單的最遲交貨期為的Di（i=1,2,…,M）。

為便于描述進行如下定義：

定義1：矩陣Ci為一個結(jié)構(gòu)矩陣，是描述訂單i各子任務(wù)可選方案參數(shù)的集合：

則MC的生產(chǎn)調(diào)度優(yōu)化模型為：

調(diào)度模型 （公式1）中的第一部分為庫存成本評價因子；第二部分為時間評價因子；第三部分為訂單延期懲罰項，第四部分為優(yōu)先權(quán)懲罰因子。公式 （2）為同一訂單各子任務(wù)之間的時間約束；公式 （3）表示延期懲罰遠大于優(yōu)先權(quán)懲罰約束。

2 基于粒子群算法的生產(chǎn)計劃調(diào)度模型求解

2.1 粒子群優(yōu)化算法概述

粒子群優(yōu)化算法 （Particle Swarm Optimization，PSO）最早是由1995年由Eberhart和Kennedy共同提出的，其基本思想是受他們早期對許多鳥類的群體行為進行建模與仿真研究結(jié)果的啟發(fā)[4]。算法模擬鳥群飛行覓食的行為,通過鳥之間的集體協(xié)作使群體達到最優(yōu)。與遺傳算法類似，它也是基于群體迭代，但沒有交叉、變異算子，群體在解空間中追隨最優(yōu)粒子進行搜索。其數(shù)學(xué)描述如下：設(shè)zi=（zi1,zi1,…,ziD）為第i個粒子 （i=1,2,…,m ）的D維位置矢量，根據(jù)具體研究背景下事先設(shè)定的適應(yīng)函數(shù)計算zi的適應(yīng)值，以此來衡量粒子位置的優(yōu)劣。在每次迭代中，粒子根據(jù)以下式子更新速度和位置：

（4）式中的第1式的第二部分是 “認知”部分，代表了粒子的自身學(xué)習(xí)能力。第三部分是 “社會”部分，代表著粒子間的協(xié)作。兩個式子表示粒子根據(jù)以上此迭代的速度、當(dāng)前位置和自身最好經(jīng)驗與群體最好經(jīng)驗之間的距離來更新速度，然后粒子飛向新的位置[5]。

PSO的優(yōu)勢在于算法簡單有效，容易實現(xiàn)，沒有很多參數(shù)需要調(diào)整，且不需要梯度信息、收斂快等。PSO是非線性連續(xù)優(yōu)化問題、組合優(yōu)化問題和混合整數(shù)非線性優(yōu)化問題的有效優(yōu)化工具，因此本文同一時間窗口的調(diào)度優(yōu)化采用粒子群算法來求解。

2.2 相關(guān)定義

為便于MC供應(yīng)鏈下同一時間窗口訂單優(yōu)化調(diào)度問題的粒子群算法求解，通過以下定義將生產(chǎn)調(diào)度優(yōu)化模型映射到圖中。

定義2：圖G為表示MC供應(yīng)鏈動態(tài)調(diào)度問題的有向圖，G（ N,A）。

定義3：虛擬起始點sPoint為不占用任何操作時間的節(jié)點，是所有粒子的出發(fā)點。由sPoint出發(fā)的弧指向圖中所有對應(yīng)規(guī)則庫中無前置任務(wù)的節(jié)點。

2.3 算法描述

模型映射到圖中后，即可運用類似TSP的搜索方法對問題進行求解。以下是具體算法步驟：

步驟1：初始化各參數(shù)。

步驟1.1：確定種群規(guī)模。

步驟1.2：確定學(xué)習(xí)因子c1和c2，初始代數(shù)k=0。

步驟1.3：初始化粒子的速度和位置，Vi（0）， Xi（0），同時定義速度和方向兩個維度。隨機產(chǎn)生第一代例子，即隨機生成第一代粒子的遍歷結(jié)果。

步驟2：構(gòu)造遍歷規(guī)則。運用JESS專家系統(tǒng)定義每個工序的前置工序，建立基本的遍歷規(guī)則。調(diào)用JESS專家系統(tǒng)，根據(jù)已訪問的節(jié)點和規(guī)則庫中的訪問規(guī)則，生成粒子可訪問的節(jié)點集合。如果粒子的可訪問節(jié)點集合為空，則說明粒子完成遍歷。在數(shù)組中記錄粒子的遍歷結(jié)果。每個工序都有其前置工序，雖然粒子在遍歷時存在一定的隨機性，但是一定要符合流程規(guī)則。

步驟3：計算粒子的適應(yīng)值。

步驟3.1：在粒子完成遍歷后，采用順推的方法確定找出各個子任務(wù)的最早開工時間和各個訂單的最早完工時間。對于任何一個新取出的子任務(wù)j，通過JESS查詢它的前置任務(wù)，取其前置任務(wù)完工時間的最大值trMax；查找遍歷排序在它之前的最后一個相同子任務(wù) （其它訂單）完工時間rrSam。取max（ trMax,rrSam,0）作為子任務(wù)j的開工時間，并計算其完工時間。

步驟3.2：根據(jù)遍歷順序，從數(shù)組中讀出各個節(jié)點相對應(yīng)的成本。

步驟3.3：粒子完成一條路徑的遍歷，并計算出各節(jié)點的完工時間后，根據(jù)其遍歷的各個節(jié)點，將各參數(shù)代入（1）公式計算其適應(yīng)值。

步驟4：根據(jù)各個粒子的適應(yīng)值找出局部最優(yōu)pbest和全局最優(yōu)gbest。由于學(xué)因子的存在，根據(jù)新速度的方向更新，粒子群體會向最優(yōu)位置飛翔。

步驟5：更新速度和位置。產(chǎn)生新一代的粒子。

步驟5.1：粒子根據(jù)以下公式更新速度和位置。

步驟5.2：根據(jù)新的適應(yīng)值，如果優(yōu)于原來的pbest和gbest，則替換為pbest（k）， gbest（k）。對于子群內(nèi)所有個體均為不可行的解，或有多個個體同為最優(yōu)解時，隨機取其中一個為子群的當(dāng)前最優(yōu)解。

步驟6：判斷粒子是否到達最大迭代數(shù)，是則退出循環(huán)，輸出結(jié)果；否則，轉(zhuǎn)入下一步。

步驟7：回到步驟2。

粒子群求解算法流程如圖3和4所示。

圖3 主程序圖

圖4 粒子遍歷程序圖

3 仿真算例與結(jié)果分析

這里的算例，繼續(xù)采用廣州某MC機械廠的汽輪機生產(chǎn)的例子來說明。為了簡化計算過程，便于調(diào)度結(jié)果優(yōu)劣分析，這里抽取該機械廠汽輪機某一段定制生產(chǎn)過程數(shù)據(jù)，選擇其中6個訂單數(shù)據(jù)進行驗證分析。這6個訂單具有相同的訂單分解結(jié)構(gòu) （如圖2所示），表1為訂單子任務(wù)在各企業(yè)內(nèi)的處理時間；表2為生產(chǎn)能力表；表3為訂單的生產(chǎn)成本，每單位時間的庫存成本以在制品生產(chǎn)成本的0.5%計；表4為訂單的最遲交貨期和定制優(yōu)先權(quán)。

表1 訂單任務(wù)加工表

表2 生產(chǎn)能力表

算例為6個訂單，每個訂單需要18個加工來完成，因此，每個訂單各有18個子任務(wù)，不同子任務(wù)對應(yīng)不同的加工點，即子任務(wù)j對應(yīng)加工點j（ 0＜j＜=18），每個子任務(wù)對應(yīng)的加工時間如下 （T_matrix ij代表加工第i個訂單的第j個子任務(wù)的加工時間）：

表3 生產(chǎn)成本表

表4 交貨期與定制優(yōu)先權(quán)表

采用 [2.3]描述的算法，選取w1=0.015,w2=0.985,c1=2,c2=0.5,α=5,β=0.02得出最終的適應(yīng)值為E=351.74。圖5所示為某次調(diào)度優(yōu)化過程中前200代的各代最優(yōu)路徑變化曲線。橫坐標是迭代次數(shù)，縱坐標是目標函數(shù)數(shù)值。適應(yīng)值在154代內(nèi)的最優(yōu)解為351.74，此時，庫存的成本為2355.01（百元），完成訂單任務(wù)共用時135天，6個訂單共延遲33天，由于設(shè)置了對于延遲交貨的懲罰因子α=5，所以在評價中，因延遲交貨而產(chǎn)生的成本為165。優(yōu)先勸懲罰因子β為0.02，所以因優(yōu)先權(quán)產(chǎn)生的成本為11.9。多次實驗結(jié)果均收斂于135個時間單位。50次試驗中46次收斂于137個時間單位，2次收斂于134個時間單位，2次收斂于136個時間單位。

該算例的優(yōu)化調(diào)度方案如圖6所示。橫坐標代表加工時間，縱坐標代表18個加工點，矩形框Pij（0＜i＜=6,0＜j＜=18）代表第i個訂單的第j個子任務(wù)，如編號為P513則代表第5個訂單的第13個子任務(wù)，矩形的長度則代表了子任務(wù)加工時間。如甘特圖的左下角矩形P31，它的含義為：第3個訂單的第1個子任務(wù)在加工點1上進行加工，為7個單位加工時間。

4 結(jié) 論

大規(guī)模定制是綜合提升客戶個性化需求與企業(yè)生產(chǎn)或服務(wù)效率的有效生產(chǎn)模式，是21世紀的主流生產(chǎn)模式，其生產(chǎn)與調(diào)度是實現(xiàn)企業(yè)大規(guī)模定制能力相當(dāng)重要的一環(huán)，基于定制點分離思想，結(jié)合大規(guī)模定制生產(chǎn)的應(yīng)用實踐，本文構(gòu)建了大規(guī)模定制同一時間窗口的訂單優(yōu)化調(diào)度模型，并以汽輪機生產(chǎn)的算例對模型進行了驗證。對今后進一步研究大規(guī)模定制生產(chǎn)調(diào)度問題的提供了一定的幫助，對企業(yè)實施大規(guī)模定制的可行性研究也有一定的借鑒意義。

[1]季建華，趙平，顧巧論.基于大規(guī)模定制的流程工業(yè)生產(chǎn)計劃優(yōu)化方法及應(yīng)用研究[J].信息與控制，2008,37(6)：362-365.

[2]孫靖，林杰.基于蟻群算法的大規(guī)模定制供應(yīng)鏈調(diào)度優(yōu)化研究[J].計算機應(yīng)用，2006,26(11)：2631-2634.

[3]孫靖，林杰.信息不完全共享下MC供應(yīng)鏈動態(tài)調(diào)度模型研究[J].系統(tǒng)仿真學(xué)報，2007,19(9)：1943-1949.

[4]J Jerald,P Asokan,G Prabaharan,et al.Scheduling optimization of flexible manufacturing systems using particle swarm optimizational gorithm[J].International Journal of Advanced Manufacturing Technology,2005,25(9)：964-971.

[5]F van den Bergh,A P Engelbrecht.A study of particle swarm optimization particle trajectories[J].Information Sciences,2006,176(8)：937-971.

[6]王玉，林杰，潘建玲.MC下基于多CODP的生產(chǎn)調(diào)度體系及其仿真研究[J].管理科學(xué)，2008,21(4)：17-25.

[7]WANG Yu,LIN Jie.Supply Chain Model Based on Multi-CODP in Mass Dynamic Customization[C]//Proceedings of the International Conference on Information Management,Innovation Management and Industrial Engineering.Los Alamitos：Inst.of Elec.and Elec.Eng.Computer Society,2008：252-255.

[8]王玉，林杰.大規(guī)模動態(tài)定制系統(tǒng)研究[J].計算機工程與應(yīng)用，2010,46(5)152-155.

[9]WANG Yu.Supply chain optimization system of mass customization based on multi-CODP[C]//2009 Chinese Conference of Control and Decision.Singapore：IEEE Industrial Electronics,2009：3452-3457.

[10]王玉.大規(guī)模定制中客戶訂單解耦點定位的專家系統(tǒng)[J].計算機集成制造系統(tǒng)，2011,17(5)：924-934.