不確定條件下中間存儲時間有限多產(chǎn)品間歇生產(chǎn)過程調(diào)度

耿佳燦，顧幸生

（華東理工大學化工過程先進控制和優(yōu)化技術教育部重點實驗室，上海 200237）

引 言

間歇過程適用于生產(chǎn)中小批量且高附加值的產(chǎn)品，廣泛應用于精細化工、食品飲料、生物醫(yī)藥等行業(yè)[1]。它固有的靈活性決定了可通過合理調(diào)度達到增產(chǎn)降耗和節(jié)能減排等目的[2]。

在間歇過程中，常需設立存儲設備用來暫存中間產(chǎn)品，以增加生產(chǎn)能力、提高生產(chǎn)柔性。目前，學者們對中間存儲容量有限(capacity-constrained intermediate storage)的調(diào)度問題已進行了廣泛研究[3]，而在許多間歇過程中也存在中間存儲時間有限(time-constrained intermediate storage)的情況，如在食品加工過程中，未包裝的食品容易變質，在中間儲罐中存儲一定時間后必須及時包裝出售或進入下級單元加工，否則會降低生產(chǎn)質量甚至造成浪費。目前對中間存儲時間有限的問題研究還較少[4]，因此，本文對中間存儲時間有限多產(chǎn)品間歇生產(chǎn)過程調(diào)度進行研究。

對間歇生產(chǎn)過程調(diào)度問題的研究集中在調(diào)度模型和優(yōu)化算法上[5-6]，這些研究一般假設生產(chǎn)過程是在靜態(tài)、確定的環(huán)境下進行的，所有的數(shù)據(jù)都是精確可知的。然而，企業(yè)實際生產(chǎn)運營活動是動態(tài)不確定的，客觀存在著許多不確定因素，如產(chǎn)品處理時間波動、交貨期不確定、設備突發(fā)故障等。忽略這些不確定因素會導致預定的生產(chǎn)調(diào)度方案性能降低甚至不可行，因此在制定調(diào)度方案時考慮不確定因素的影響顯然更符合實際情況。目前對不確定性調(diào)度的研究方法主要有隨機調(diào)度規(guī)劃和模糊調(diào)度規(guī)劃等[7-8]。由于在生產(chǎn)實際中根據(jù)歷史信息統(tǒng)計不確定參數(shù)的概率分布比較困難，而大致估計其區(qū)間則相對容易，因此本文采用模糊規(guī)劃理論處理生產(chǎn)調(diào)度問題中的不確定因素。

粒子群優(yōu)化算法(particle swarm optimization,PSO)[9]結構簡單、便于實施，已成功應用于生產(chǎn)調(diào)度問題。近年來，基于對概率模型學習和采樣的分布估計算法(estimation of distribution algorithm，EDA)[10]成為進化計算領域的研究熱點。本文在粒子群算法中引入遺傳操作和分布估計算法，提出一種基于改進粒子群和分布估計的混合算法(improved particle swarm optimization with estimation of distribution algorithm, IPSO-EDA)，并將其應用于解決產(chǎn)品處理時間不確定條件下中間存儲時間有限多產(chǎn)品間歇生產(chǎn)過程調(diào)度(time-constrained intermediate storage multiproduct batch process scheduling with uncertainty, UTISBPS)，取得了滿意的效果。

1 不確定條件下中間存儲時間有限多產(chǎn)品間歇生產(chǎn)過程調(diào)度

1.1 問題描述與數(shù)學模型

中間存儲時間有限多產(chǎn)品間歇生產(chǎn)過程調(diào)度可描述為：所有產(chǎn)品遵循相同的加工路徑，中間產(chǎn)品在中間儲罐內(nèi)存儲的時間不能超過某一有限值。為了保證滿足中間存儲時間有限的約束，產(chǎn)品在第1臺設備上的開始時間可以適當延遲。圖1為一般的中間存儲時間有限多產(chǎn)品間歇生產(chǎn)過程。

有n種產(chǎn)品要在m臺設備上處理，產(chǎn)品i在設備j上的處理時間是給定的，它包括裝配、傳輸、卸載、加工以及清洗時間等，是不確定量，本文采用三角模糊數(shù)對其進行描述。MSTij為第i種產(chǎn)品在設備j和j+1間的中間儲罐內(nèi)的最大存儲時間。定義和分別表示產(chǎn)品i在設備j上的開始處理時間和完工時間，模糊最大完工時間(fuzzy makespan)用表示。由于產(chǎn)品的處理時間是不確定量，開始處理時間和完工時間也是不確定量。為了更好地衡量模糊調(diào)度的好壞，本文以最小化模糊最大完工時間的值以及不確定度作為調(diào)度目標。

中間存儲時間有限多產(chǎn)品間歇過程調(diào)度問題的數(shù)學模型如下

圖1 中間存儲時間有限多產(chǎn)品間歇生產(chǎn)過程Fig.1 Time-constrained intermediate storage multiproduct batch process

其中，跨度spread是模糊最大完工時間的最大值和最小值之差，表示模糊完工時間的不確定程度，spread越大說明模糊完工時間的不確定度越大；?為加權系數(shù)。本文的調(diào)度目標是使模糊最大完工時間的平均值和不確定度同時最小。

式(2)～式(6)為約束條件。式(2)表示加工順序約束：產(chǎn)品i必須在j?1臺設備上完工后才能進入下一設備j進行加工，即任意時刻每種產(chǎn)品只能在一臺設備上進行處理。式(3)表示資源約束：產(chǎn)品i必須在其前一個產(chǎn)品i?1在某一設備完工后，才能進入該設備進行加工，即每臺處理設備只能同時處理一種產(chǎn)品。式(4)表示中間存儲時間有限約束：中間產(chǎn)品在中間儲罐的存儲時間不能超過規(guī)定的最大存儲時間。式(5)表示中間儲罐只能同時存放一種產(chǎn)品，產(chǎn)品不能混合存放，以免發(fā)生反應。式(6)表示產(chǎn)品的完工時間等于開始加工時間和加工處理時間之和。

另外，產(chǎn)品加工過程中不允許中斷，所有產(chǎn)品可以在零時刻投入生產(chǎn)。

1.2 模型轉換

隸屬度函數(shù)如圖2所示。其中，rL、rM、rU分別表示最小值、最可能值和最大值。

文獻[11]定義了用于模糊調(diào)度的模糊加法和模糊極大運算

圖2 三角模糊數(shù)的隸屬度函數(shù)Fig.2 Membership function of triangular fuzzy number

本文采用Lee等[12]提出的以模糊事件概率測量求算平均數(shù)及標準差的方法來實施模糊數(shù)排序，當模糊事件的概率分配服從比例分布時，其平均數(shù)和標準差為

當模糊數(shù)為三角模糊數(shù)時，式(10)、式(11)可簡化為

2 求解 UTISBPS的改進粒子群和分布估計混合算法

2.1 基于遺傳操作的改進粒子群算法

粒子群優(yōu)化算法是一種基于群體智能、模擬鳥群覓食活動的仿生算法，粒子群中的每個粒子都根據(jù)自身速度、自身最優(yōu)位置Pbest和全局最優(yōu)位置Gbest調(diào)整搜索方向，種群間粒子合作競爭實現(xiàn)對優(yōu)化問題的求解。PSO已成功應用于多個領域，表現(xiàn)出優(yōu)良的性能。

但標準PSO算法采用實數(shù)編碼，具有連續(xù)的本質，調(diào)度問題屬于離散域的組合優(yōu)化問題，直接用標準PSO算法求解存在困難。本文借鑒文獻[13]的思想，采用遺傳操作對粒子群算法的更新公式進行重新定義和改進，使之適用于求解調(diào)度問題。

基于遺傳操作的改進粒子群算法中每個粒子用一個可行的調(diào)度排序表示，如一個有8個產(chǎn)品的調(diào)度排序(2,5,3,4,7,8,1,6)表示一個粒子。粒子通過自身當前位置、自身最優(yōu)位置和全局最優(yōu)位置進行更新，更新公式如下

本文采用兩點交叉方式，隨機選擇兩個交叉點，位于兩個交叉點之間的信息來自于一個父代，位于交叉點之外的信息來自另一個父代。圖3給出了一個兩點交叉操作的例子。父代 1為(6,1,4,5,8,2,3,7)，父代 2為(3,5,2,6,1,7,4,8)，假設兩個隨機交叉點為3和6，則父代1交叉點之間的信息序列為(4,5,8,2)，這個序列保留到子代1中，父代2中除去這些信息的剩余信息序列為(3,6,1,7)，這兩個序列組合生成子代1為(3,6,4,5,8,2,1,7)，同理生成子代2為(4,5,2,6,1,7,8,3)。生成的兩個子代中的較優(yōu)個體作為交叉操作的后代進行下一步操作。

圖3 兩點交叉操作示意圖Fig.3 Method of two-point crossover

本文采用插入變異方式，隨機選擇兩個位置，將其中一個位置插入到另一個位置之前，如個體(2,5,3,4,7,8,1,6)經(jīng)過將第6個位置插入到第2個位置前生成變異個體(2,8,5,3,4,7,1,6)。

2.2 分布估計算法

分布估計算法是一種新興的進化算法，沒有傳統(tǒng)的交叉變異等遺傳操作，通過統(tǒng)計學習的手段建立解空間內(nèi)個體分布的概率模型，然后對概率模型隨機采樣產(chǎn)生新種群，如此反復進行，實現(xiàn)群體的進化。其基本步驟如下[10]：①隨機產(chǎn)生初始種群；②根據(jù)個體的適應度值選擇Q個較優(yōu)個體用于構建概率模型；③采用某種概率模型對優(yōu)質個體進行評估并構建概率模型；④根據(jù)概率模型采樣，生成M個新個體；⑤判斷是否滿足終止條件，滿足則輸出最優(yōu)解，否則返回步驟②。

EDA的核心操作是建模和采樣，通過選擇種群內(nèi)的優(yōu)質個體集合，評估它們的分布，建立優(yōu)質個體的概率模型，然后根據(jù)這種包含了優(yōu)質個體分布信息的概率模型采樣生成新種群。其中構建何種概率模型對EDA算法的性能影響很大，Jarboui等[14]考慮調(diào)度排序中產(chǎn)品的順序和相似模塊構建了一種針對Flow Shop調(diào)度問題的概率模型，Pan等[15]對Jarboui等提出的概率模型進行了補充和改進，本文應用Pan等提出的改進概率模型進行EDA操作。

2.3 改進粒子群和分布估計混合算法

粒子群算法是一種隨機性比較高的進化算法，且更新公式中對社會認知部分的信息包含得不夠全面。通過粒子自身最優(yōu)位置和全局最優(yōu)位置指導搜索，沒有利用到種群中非全局最優(yōu)位置的優(yōu)質粒子信息，隨著進化代數(shù)的增大，種群多樣性降低，易陷入局部最優(yōu)。

分布估計算法是統(tǒng)計學習和隨機優(yōu)化算法的結合，通過建立全局范圍內(nèi)優(yōu)質個體的概率模型，從宏觀的角度獲得優(yōu)質個體的分布信息，解決了許多傳統(tǒng)進化算法難以求解的復雜優(yōu)化問題。

本文考慮用基于所有粒子自身最優(yōu)位置的優(yōu)質個體分布信息引導粒子群進行更新。對粒子群中所有粒子的自身最優(yōu)位置進行評估選擇建模，并根據(jù)此模型采樣生成新種群。包含優(yōu)質個體分布信息的新種群和全局最優(yōu)位置共同指導粒子群搜索，可以改進粒子群的更新機制，提高算法的全局搜索能力。因此，本文提出一種基于改進粒子群和分布估計混合算法，并用于解決不確定條件下中間存儲時間有限多產(chǎn)品間歇生產(chǎn)過程調(diào)度問題，IPSO-EDA算法的流程如圖4所示。

圖4 IPSO-EDA算法流程Fig.4 Flowchart of IPSO-EDA algorithm

2.3.1 解的表達與初始化 本文采用基于工件排序的表達方式，一個可行的調(diào)度排序代表一個可行解。

為了保證初始種群的質量和多樣性，本文采用基于NEH啟發(fā)式算法[16]的初始化方法，NEH啟發(fā)式算法步驟如下：① 按各產(chǎn)品在所有設備上的處理時間總和遞減的順序排列n個產(chǎn)品；②取前兩個產(chǎn)品進行最優(yōu)調(diào)度；③依次將剩余產(chǎn)品插入已調(diào)度好的產(chǎn)品排序中的某個位置，使得子調(diào)度指標最小，直到所有產(chǎn)品調(diào)度完成。

由于本文的產(chǎn)品處理時間是不確定的，在采用NEH啟發(fā)式方法生成初始解時，本文對產(chǎn)品的最小處理時間、最可能處理時間和最大處理時間分別進行NEH操作，得到3個高質量的初始解，其余初始解隨機生成。

2.3.2 選擇與構建概率模型 對所有粒子的自身最優(yōu)位置進行評估，按調(diào)度目標值升序排列，選擇其中調(diào)度目標值最小的前Q個個體用于構建模型。此選擇方法相比輪盤賭和錦標賽的選擇方法更為迅速。

文獻[15]中將產(chǎn)品j分配在調(diào)度排序中的第i個位置進行處理的概率為

式中，ρij為在選擇的Q個優(yōu)質個體中，產(chǎn)品j出現(xiàn)在位置i及位置i以前的總次數(shù)，ρij的值代表了調(diào)度排序中產(chǎn)品處理順序的重要性；λj′,j為在選擇的Q個優(yōu)質個體中，所有位置上出現(xiàn)(j′,j)調(diào)度排序的總次數(shù)，j′為當前采樣個體在第i?1個位置上處理的產(chǎn)品，λj′,j的值代表了調(diào)度排序中相似模塊的重要性。Ω(i)為當前采樣個體中截止到位置i仍未被分配的產(chǎn)品集合。

以一個有4個待處理產(chǎn)品的調(diào)度問題為例進行說明，假設選擇的優(yōu)質個體為(1,3,4,2)、(2,1,4,3)、(3,4,2,1)，則

假設產(chǎn)品1被安排在第一個位置進行處理，則

2.3.3 采樣與種群更新 首先計算概率模型中每一行的累積概率P，Pij表示概率模型中的第i行上第j列之前的概率之和；然后生成0～1之間的一個隨機數(shù)ε，若Pi(j?1)<ε≤Pij，則第i個位置選擇產(chǎn)品j進行處理；并將概率模型的第j列全部設為零，同時更新每一行的非零元素，使每行的所有元素之和仍為 1，以保證采樣產(chǎn)生的新個體中每個產(chǎn)品只出現(xiàn)一次；重復上述操作直至對所有位置分配產(chǎn)品，即采樣生成了一個新個體。

本文提出的IPSO-EDA算法的更新公式如下其中，S(t)為基于對所有粒子的自身最優(yōu)位置進行選擇建模采樣生成的包含優(yōu)質個體分布信息的新種群。改進的更新公式中粒子在S(t)、全局最優(yōu)位置pg(t)以及當前粒子位置x(t)這3個因素的引導下進行更新，粒子群的更新機制中包含的信息更加全面，提高了算法的全局搜索能力。

2.3.4 局部搜索 采用局部搜索策略可以增強算法的局部搜索能力，提高算法的性能?；诓迦豚徲蚝徒粨Q鄰域的局部搜索是常用的有效局部搜索方法。本文采用一種基于插入操作的 NEH局部搜索策略對最優(yōu)解進行局部搜索。經(jīng)過實驗發(fā)現(xiàn)，NEH局部搜索的效果要好于交換以及插入局部搜索。NEH局部搜索步驟如下：首先將當前最優(yōu)解的排序作為初始排序，其余步驟同 NEH啟發(fā)式算法的步驟②、③，得到一個當前最優(yōu)解的鄰域解，判斷此解是否具有更好的調(diào)度目標，是則對最優(yōu)解進行更新?？紤]到局部搜索比較費時，本文設置一個參數(shù)L表示算法的最優(yōu)調(diào)度目標值連續(xù)L代沒有發(fā)生變化，此時對算法最優(yōu)解進行上述局部搜索，這樣可以在保證算法性能的同時提高算法的搜索速度。

3 仿真研究

3.1 仿真實驗設置

為了驗證IPSO-EDA算法在解決不確定條件下中間存儲時間有限多產(chǎn)品間歇生產(chǎn)過程調(diào)度時的有效性，本文進行了一系列的仿真實驗，仿真硬件環(huán)境為Intel(R)Core(TM)i7-2006 CPU/3.4GHz/4.0GB。仿真軟件平臺為Windows 7系統(tǒng)，所涉及的算法均采用Matlab R2011b編寫。

對于不確定多產(chǎn)品間歇過程調(diào)度問題，沒有合適的標準算例，本文采用文獻[17]提出的方法對Reeves[18]設計的標準算例進行模糊化。將標準算例中每一個確定數(shù)據(jù)x轉變?yōu)橐粋€三角模糊數(shù)，三角模糊數(shù)最左邊的值為[δ1x,x]之間的一個隨機數(shù)，0＜δ1＜1，三角模糊數(shù)最右邊的值為[x,δ2x]之間的一個隨機數(shù)，δ2>1。本文設置δ1=0.9，δ2=1.2。而對于中間存儲時間有限的調(diào)度問題，為了方便起見，設中間存儲時間均為 MST個時間單元。在算法參數(shù)討論和算法性能測試中，所有算法運行終止條件都設為達到最大進化代數(shù)Gen。

3.2 算法參數(shù)討論

算法參數(shù)對算法的性能有很大的影響，需要對算法的參數(shù)進行調(diào)節(jié)，以保證算法在其最優(yōu)狀態(tài)下運行。本文提出的IPSO-EDA算法涉及以下4個關鍵參數(shù)：最大進化代數(shù)Gen(在m×n附近取值較好[19])、種群規(guī)模M(在20～50之間取值較好[20])、優(yōu)質個體規(guī)模Q(用q%×M并取整表示)、最優(yōu)解連續(xù)L(用l%×Gen表示)代不發(fā)生變化。對每個參數(shù)設置 3個不同值進行實驗，采用全面實驗共需要34=81組參數(shù)組合，本文采用因子設計(factorial design，F(xiàn)D)[21]方法對參數(shù)進行選擇，只需要 32=9組參數(shù)組合就能找到較好的算法參數(shù)。表1給出了正交實驗因素和水平。

表1 正交實驗因素和水平Table 1 Factors and levels for orthogonal experiment

對Rec系列算例中不同規(guī)模的算例各取一個進行正交實驗，表2為以正交設計表L9(34)為基礎的正交實驗結果，圖5給出了每個參數(shù)在不同水平下的趨勢。表2中包含了9組參數(shù)組合，其中每組參數(shù)組合運行 5次取平均值，則共需要 7×9×5=315組實驗。將根據(jù)式(17)求得的相對百分偏差(relative percentage deviation, RPD)列于表的最后一列。表中第10～12行、第j列的ki表示參數(shù)j在i水平上3組實驗結果的平均值，第j列的SD表示參數(shù)j的k1到k3的標準差(standard deviation，SD)。對于每個參數(shù)，最小的ki對應的i水平所對應的參數(shù)值最好。SD越大說明該參數(shù)對算法的影響越大。表2中每一列最小的ki值被加粗，并給出SD的降序排序。

式中，ci是第i組參數(shù)組合的最大完工時間，c*是所有參數(shù)組合中最小的最大完工時間。

表2 L9(34)正交表及實驗結果Table 2 Orthogonal parameter table L9(34)and results

圖5 IPSO-EDA算法參數(shù)變化趨勢Fig.5 Trend graph of parameters in IPSO-EDA

從表2和圖5可以看出，最大進化代數(shù)Gen對IPSO-EDA算法的性能影響最大。Gen過小會導致算法終止時還沒有完全收斂，很大程度上降低算法的收斂精度，而隨著Gen逐漸增大，其對算法收斂精度的影響逐漸降低，算法完全收斂后，再增大Gen算法的收斂精度將不再提高，因此合理設置Gen可以保證算法的收斂性。參數(shù)M對算法的影響排在第2位，較大的種群規(guī)模M可以包含較多的信息，從圖5中可以看出M過小或過大都會降低算法的收斂精度，本文中M取30時算法的收斂精度最高。參數(shù)l對算法影響排在第3位，l越小對最優(yōu)解的局部搜索越多，越可能跳出局部極值，算法的收斂精度也越高，但是局部搜索次數(shù)太多即l過小時對算法收斂精度的影響趨于不明顯，且會花費較多的運行時間，因此需綜合考慮運行時間和算法精度，合理設置參數(shù)l。參數(shù)q對算法影響最小，較小的優(yōu)質個體規(guī)模q可以建立更加準確的優(yōu)質個體分布信息模型，從而提高算法的收斂精度。

根據(jù)上述分析，本文選擇Gen=500，M=30，q=25，l=5時算法有較高的收斂精度，能夠取得較好的效果，因此在3.3節(jié)的算法性能測試中參數(shù)取值如上。下文與其他算法進行對比的實驗結果也驗證了本文算法具有較好的收斂精度和收斂速度。

3.3 算法性能測試

MST=0時為零等待的情況，MST=∞時為中間存儲無限的情況。本文分別取MST={0,10,50,100,500}，研究不同 MST情況下的調(diào)度問題。以 Rec29為例，對每個 MST值，IPSO-EDA算法獨立運行10次，取平均值，繪制了如圖6所示的不同MST情況下模糊最大完工時間的變化趨勢。由圖6可以看出，MST越小，中間產(chǎn)品在中間儲罐中的可停留時間越小，限制越多，完工時間越大；MST越大，中間產(chǎn)品在中間儲罐中的可停留時間越大，限制越少，完工時間也越?。划擬ST達到某一值后，調(diào)度問題的完工時間迅速減小，之后將趨于穩(wěn)定，說明MST達到某一閾值后對調(diào)度問題的影響將大大減小，找到這一閾值并合理利用可以幫助企業(yè)提高生產(chǎn)效率。在之后的對比實驗中選擇MST=10的調(diào)度情況進行實驗。

圖6 不同MST情況下最大完工時間趨勢Fig.6 Trend graph of fuzzy makespan with different MST

通過選擇不同的權重系數(shù)?可以調(diào)整調(diào)度目標中對完工時間的值和不確定程度的側重，本文對?={0,0.5,1} 3種不同情況下的調(diào)度問題進行研究。?=0表示只最小化最大完工時間的值，不考慮完工時間的不確定度；?=0.5和?=1時同時考慮了最小化最大完工時間的值和不確定度，其中?=1時對不確定度的側重更大。以Rec29為例，表3給出了不同?下的調(diào)度結果，對每個?獨立運行10次，取其最小值(min)和平均值(avg)列于表3中?？梢钥闯鲭S著?增大，調(diào)度目標的值也會增大，主要是由于對完工時間的不確定度的側重增大。?取何值要依賴不同的生產(chǎn)環(huán)境，如在時間代價比較大的生產(chǎn)環(huán)境中，應該選擇較小的?值；而在不確定性較大的生產(chǎn)環(huán)境中，則應該選擇較大的?值。在之后的對比實驗中選擇?=0.5的情況進行實驗。

表3 不同?情況下的調(diào)度問題Table 3 Scheduling problems with different ?

本文通過將提出的IPSO-EDA算法與一種改進粒子群算法(GPSO)[13]和一種有效的分布估計算法(EDA)[22]進行比較以測試IPSO-EDA算法的性能。每個算法獨立運行10次，10次結果的最小值記為min，平均值記為avg，平均運行時間記為time。

表4給出了IPSO-EDA算法與其他各算法的比較結果，其中每一行中最優(yōu)的min、avg和time被加粗?？梢钥闯?，在大多數(shù)規(guī)模較小的算例上，IPSO-EDA算法優(yōu)勢不明顯，優(yōu)化性能不如 GPSO算法，但優(yōu)于 EDA算法，且運行時間最短。而在規(guī)模較大的算例上，所提出的IPSO-EDA算法優(yōu)勢明顯，在解的性能、穩(wěn)定性以及運算時間上均好于其他算法。這是因為本文提出的IPSO-EDA算法是考慮調(diào)度排序中產(chǎn)品順序和相似模塊構建的針對多產(chǎn)品間歇過程調(diào)度問題的概率模型，是對實際模型的簡化，當問題規(guī)模較大時，每個解中包含的信息較多，使用的模型更接近實際模型，算法的尋優(yōu)性能更好。本文提出的算法只在最優(yōu)解連續(xù)L代沒有發(fā)生變化時對其進行簡單有效的NEH局部搜索，對局部搜索的依賴不大，大大提高了算法的運行速度。

表4 IPSO-EDA算法與其他各算法的比較Table 4 Comparisons of IPSO-EDA with other algorithms

以Rec29為例，圖7給出了上述3種算法的收斂曲線對比。從圖7可以看出，在相同的最大進化代數(shù)終止條件下，IPSO-EDA算法收斂到的值最小，搜索精度最高，GPSO算法其次，EDA算法最終得到的結果較差。從圖中還可以看出EDA算法收斂速度較慢，GPSO較IPSO-EDA算法的收斂速度稍快但陷入了局部最優(yōu)，IPSO-EDA算法的收斂速度較快，而且搜索精度最高。綜上可以看出IPSO-EDA算法相比于其他兩種算法的優(yōu)越性。

圖7 算例Rec29的各算法收斂曲線對比Fig.7 Convergence curves of instance Rec29

5 結 論

本文研究不確定條件下中間存儲時間有限多產(chǎn)品間歇生產(chǎn)過程調(diào)度問題，該問題廣泛應用在許多實際生產(chǎn)過程中，且考慮不確定的處理時間，更符合實際情況，可以指導實際生產(chǎn)。用模糊排序的方法對模糊完工時間的值和不確定程度進行評估，將模糊完工時間的平均值和標準差進行加權作為調(diào)度目標，建立了一個清晰的調(diào)度規(guī)劃模型。提出了一種適用于求解上述調(diào)度模型的IPSO-EDA算法。通過在粒子群算法中引入遺傳操作和分布估計思想，改進了算法的更新機制，同時采用基于 NEH的初始化和局部搜索提高算法的性能。實驗結果證明了IPSO-EDA算法有較快的求解速度和較好的尋優(yōu)性能。對不確定間歇過程調(diào)度還需進一步研究中間存儲時間約束只存在于部分任務中以及多目標間歇過程調(diào)度等問題。

符 號 說 明

——模糊最大完工時間的平均數(shù)

MSTij——第i種產(chǎn)品在設備j和j+1間的中間儲罐內(nèi)的最大存儲時間

m——設備總數(shù)

n——產(chǎn)品總數(shù)

,——分別為產(chǎn)品i在設備j上的開始處理時間和完工時間，均為模糊數(shù)

spread ——模糊最大完工時間的跨度

——產(chǎn)品i在設備j上的模糊處理時間

[1]Yue D, You F. Sustainable scheduling of batch processes under economic and environmental criteria with MINLP models and algorithms [J].Computers & Chemical Engineering, 2013, 54: 44-59

[2]Liang Tao(梁濤), Li Qiqiang(李歧強). Self-organizing approach to multistage batch scheduling with batching optimization [J].Control and Decision(控制與決策), 2011, 26(12): 1818-1823

[3]Pan Q K, Wang L, Gao L, Li W D. An effective hybrid discrete differential evolution algorithm for the flow shop scheduling with intermediate buffers [J].Information Sciences, 2011, 181(3): 668-685

[4]Akkerman R, Van Donk D P, Gaalman G. Influence of capacity-and time-constrained intermediate storage in two-stage food production systems [J].International Journal of Production Research, 2007,45(13): 2955-2973

[5]Belaid R, T’kindt V, Esswein C. Scheduling batches in flowshop with limited buffers in the shampoo industry [J].European Journal of Operational Research, 2012, 223(2): 560-572

[6]Zhou Xiaohui(周曉慧), Chen Chun(陳純), Wu Peng(吳鵬), Zheng Junling(鄭駿玲). Optimized scheduling of production process based on continuous-time in printing and dyeing industry [J].CIESC Journal(化工學報), 2010, 61(8): 1877-1881

[7]Li Z, Ierapetritou M. Process scheduling under uncertainty: review and challenges [J].Computers & Chemical Engineering, 2008, 32(4):715-727

[8]Gu Xingsheng(顧幸生). A survey of production scheduling under uncertainty [J].Journal of East China University of Science and Technology(華東理工大學學報), 2000, 26(5): 441-446

[9]Kennedy J, Eberhart R C. Particle swarm optimization//Proceeding of IEEE International Conference on Neural Networks[C]. Perth,Australian, 1995: 1942-1948

[10]Larra?aga P, Lozano J A. Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation[M]. Boston: Kluwer Academic Publishers, 2002

[11]Sakawa M, Kubota R. Fuzzy programming for multiobjective job shop scheduling with fuzzy processing time and fuzzy duedate through genetic algorithms [J].European Journal of Operational Research, 2000, 120(2): 393-407

[12]Lee E S, Li R J. Comparison of fuzzy numbers based on the probability measure of fuzzy events [J].Computers & Mathematics with Applications, 1988, 15(10): 887-896

[13]Niu Q, Jiao B, Gu X. Particle swarm optimization combined with genetic operators for job shop scheduling problem with fuzzy processing time [J].Applied Mathematics and Computation, 2008,205(1): 148-158

[14]Jarboui B, Eddaly M, Siarry P. An estimation of distribution algorithm for minimizing the total flowtime in permutation flowshop scheduling problems [J].Computers & Operations Research, 2009, 36(9):2638-2646

[15]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

[16]Nawaz M, Enscore E, Ham I. A heuristic algorithm for them-machine,n-job flow-shop sequencing problem [J].The International Journal of Management Sciences, 1983, 11(1): 91-95

[17]Omar A G. A bi-criteria optimization: minimizing the integral value and spread of the fuzzy makespan of job shop scheduling problems[J].Applied Soft Computing, 2003, 2(3): 197-210

[18]Reeves C R. A genetic algorithm for flowshop sequencing [J].Computers & Operations Research, 1995, 22(1): 5-13

[19]Wang L, Zhang L, Zheng D Z. An effective hybrid genetic algorithm for flow shop scheduling with limited buffers [J].Computers &Operations Research, 2006, 33(10): 2960-2971

[20]Eberhart R C, Shi Y. Particle swarm optimization: developments,applications and resources//Proceedings of the IEEE Congress on Evolutionary Computation [C]. Seoul, Korea, 2001: 81-86

[21]Montgomery D C. Design and Analysis of Experiments[M]. New York: Wiley, 2008

[22]Wang S Y, Wang L, Liu M, Xu Y. An effective estimation of distribution algorithm for solving the distributed permutation flow-shop scheduling problem [J].International Journal of Production Economics, 2013, 145(1): 387-396