耿佳燦，顧幸生

（華東理工大學(xué)化工過程先進(jìn)控制和優(yōu)化技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，上海 200237）

引 言

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

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

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

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

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

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

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

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

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

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

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

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

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

1.2 模型轉(zhuǎn)換

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

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

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

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

當(dāng)模糊數(shù)為三角模糊數(shù)時(shí)，式(10)、式(11)可簡(jiǎn)化為

2 求解 UTISBPS的改進(jìn)粒子群和分布估計(jì)混合算法

2.1 基于遺傳操作的改進(jìn)粒子群算法

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

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

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

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

圖3 兩點(diǎn)交叉操作示意圖Fig.3 Method of two-point crossover

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

2.2 分布估計(jì)算法

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

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

2.3 改進(jìn)粒子群和分布估計(jì)混合算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 仿真研究

3.1 仿真實(shí)驗(yàn)設(shè)置

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

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

3.2 算法參數(shù)討論

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

表1 正交實(shí)驗(yàn)因素和水平Table 1 Factors and levels for orthogonal experiment

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

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

表2 L9(34)正交表及實(shí)驗(yàn)結(jié)果Table 2 Orthogonal parameter table L9(34)and results

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

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

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

3.3 算法性能測(cè)試

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

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

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

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

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

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

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

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

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

5 結(jié) 論

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

符 號(hào) 說 明

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

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

m——設(shè)備總數(shù)

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

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

spread ——模糊最大完工時(shí)間的跨度

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

[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(李歧強(qiáng)). 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(化工學(xué)報(bào)), 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(華東理工大學(xué)學(xué)報(bào)), 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