類電磁機(jī)制算法求解模糊流水車間調(diào)度問題＊

邵 揚(yáng) 王曉娟

（武漢理工大學(xué)物流工程學(xué)院 武漢 430063）

0 引 言

很多調(diào)度優(yōu)化問題都針對(duì)的是靜態(tài)環(huán)境下的，但是實(shí)際生產(chǎn)過(guò)程中，由于設(shè)備、環(huán)境和人為因素的影響，工件的加工時(shí)間、交貨期等參數(shù)通常是不確定的值.不確定環(huán)境下的流水車間調(diào)度問題（flow shop scheduling problem，F(xiàn)FSP）已經(jīng)引起了國(guó)內(nèi)外一些學(xué)者的關(guān)注，Balasubramanian和Grossmann［1］提出了一種新型的分支定界方法求解了加工時(shí)間不確定的流水車間調(diào)度問題，Nezhad和Assadi［2］提出了一種改進(jìn)的CDS算法求解了模糊流水車間調(diào)度問.Javadi等［3］針對(duì)多目標(biāo)無(wú)等待的流水車間調(diào)度問題提出了一種模糊多目標(biāo)的線性規(guī)劃模型.Hong和Wang［4］研究了加工時(shí)間不確定的柔性流水車間調(diào)度問題.Wu［5］給予遺傳算法求解了加工時(shí)間和交貨期不確定的流水車間調(diào)度問題.類電磁機(jī) 制（electromagnetism－like mechanism，EM）算法由Birbil在2002 年提出［6］，是一種基于群體的全局優(yōu)化算法，它通過(guò)模擬電磁場(chǎng)中的吸引－排斥機(jī)制，來(lái)實(shí)現(xiàn)對(duì)全局最優(yōu)值的搜索.該算法已在函數(shù)優(yōu)化［7］、神經(jīng)網(wǎng)絡(luò)訓(xùn)練［8］等優(yōu)化問題中獲得成功應(yīng)用.本文采用模糊數(shù)來(lái)表示不確定的加工時(shí)間和交貨期，通過(guò)引入隨機(jī)鍵的表達(dá)方式，采用了EM 算法對(duì)模糊流水車間調(diào)度問題進(jìn)行了求解.

1 類電磁機(jī)制（EM）算法簡(jiǎn)介

1.1 EM 算法的基本原理

類電磁機(jī)制算法是一種基于種群的優(yōu)化算法，將每個(gè)解比作一個(gè)帶電粒子，每個(gè)粒子的電荷的多少由該粒子對(duì)應(yīng)的目標(biāo)函數(shù)值確定，而電荷的多少?zèng)Q定了該粒子對(duì)種群其他粒子的吸引或者排斥的強(qiáng)弱，目標(biāo)函數(shù)值越優(yōu)，吸引或排斥力就越大.然后通過(guò)吸引或排斥力確定每個(gè)粒子下一步的移動(dòng)方向，使搜索粒子都向著較優(yōu)解所在區(qū)域移動(dòng).

1.2 EM 算法的基本步驟

EM 算法主要由4個(gè)基本步驟組成：初始化、局部搜索、計(jì)算合力和移動(dòng)粒子.下面以函數(shù)優(yōu)化為例，介紹該算法的基本步驟，求目標(biāo)函數(shù)f（x）在可行域中的最小值.

1.2.1 初始化 從已知可行域中隨機(jī)選取m 個(gè)點(diǎn)作為初始粒子，然后計(jì)算出每個(gè)粒子的目標(biāo)函數(shù)值f（xi），并將目標(biāo)函數(shù)值最優(yōu)的粒子記為xbest，也稱其為當(dāng)前最優(yōu)粒子.

1.2.2 局部搜索 局部搜索主要用來(lái)在單個(gè)粒子的領(lǐng)域范圍內(nèi)改進(jìn)當(dāng)前種群已搜索到的解.實(shí)驗(yàn)表明，當(dāng)只對(duì)當(dāng)前最優(yōu)粒子進(jìn)行局部搜索時(shí)，能較好地維持速度和精度的平衡.

1.2.3 計(jì)算每個(gè)粒子的合力 首先根據(jù)每個(gè)粒子的目標(biāo)函數(shù)值計(jì)算每個(gè)粒子所帶的電荷量，電荷的計(jì)算公式為

然后計(jì)算作用在粒子i上的合力Fi，根據(jù)下式計(jì)算.

根據(jù)這個(gè)公式，目標(biāo)函數(shù)值較優(yōu)的粒子將擁有較大的電荷數(shù)，具有更強(qiáng)的吸引或者排斥力力；另外，目標(biāo)函數(shù)值較優(yōu)的粒子將吸引其他粒子，反之，目標(biāo)函數(shù)值較差的粒子將排斥其他粒子.

1.2.4 移動(dòng)粒子 粒子i將沿著合力Fi的方向移動(dòng)，步長(zhǎng)λ為一個(gè)在［0，1］上均勻分布的隨機(jī)值.在式（3）中，RNG 為一個(gè)向量，其分（向）量表示對(duì)應(yīng)的朝上邊界uk或者下邊界lk移動(dòng)的可行步長(zhǎng).粒子每一步移動(dòng)為：

2 模糊數(shù)相關(guān)理論

2.1 模糊數(shù)和操作

本文用模糊數(shù)來(lái)表示不確定的加工時(shí)間和交貨期，用三角模糊數(shù)表示不確定的加工時(shí)間，三角模糊數(shù)如圖1所示.用梯形模糊數(shù)來(lái)表示不確定的交貨期，如圖2所示.

圖1 三角模糊數(shù)

圖2 梯形模糊數(shù)

模糊調(diào)度問題中，模糊數(shù)的操作是很重要的問題，它包括模糊數(shù)的求和、取大以及模糊數(shù)的比較.

1）求和 對(duì)于三角模糊數(shù)和梯形模糊數(shù)，求和操作為

2）取大 三角模糊數(shù)的取大操作為

2.2 模糊數(shù)的比較

模糊數(shù)間的比較操作，采用Sakawa等人提出的準(zhǔn)則進(jìn)行［9］.

3 EM 求解模糊流水車間調(diào)度問題

3.1 優(yōu)化目標(biāo)

1）最大化平均滿意度

圖3 滿意度（AI）

2）最小化最大模糊完工時(shí)間

3.2 求解流程

通過(guò)引入隨機(jī)鍵的編碼方式，將離散型的工件排序編碼轉(zhuǎn)換成能用EM 算法直接求解的連續(xù)型編碼.基于EM 的模糊流水車間調(diào)度算法的步驟如下.

步驟1 將每個(gè)粒子通過(guò)隨機(jī)鍵的編碼方式映射成調(diào)度問題的一個(gè)解，初始化粒子.

步驟2 利用模糊數(shù)的求和與取大操作，計(jì)算出各粒子的目標(biāo)函數(shù)值.

步驟3 進(jìn)行局部搜索.

步驟4 根據(jù)式（1），（2）計(jì)算合力.

步驟5 根據(jù)式（3）計(jì)算位移，移動(dòng)粒子.

步驟6 若算法達(dá)到最大迭代次數(shù)，則算法停止；否則，返回步驟2繼續(xù)迭代.

4 測(cè)試與結(jié)果比較

1）最大化平均滿意度 本文采用了文獻(xiàn)［10］和［11］中的測(cè)試實(shí)例，以最大化平均滿意度為優(yōu)化目標(biāo)進(jìn)行了測(cè)試，結(jié)果如表1所列，與文獻(xiàn)中的結(jié)果相比，本文的測(cè)試結(jié)果要優(yōu).

表1 文獻(xiàn)［10］和［11］中的實(shí)例測(cè)試結(jié)果

2）最小化最大模糊完工時(shí)間 在以最小化最大模糊完工時(shí)間為優(yōu)化目標(biāo)的測(cè)試?yán)?，采用了文獻(xiàn)［12］，［13］和［14］中的實(shí)例進(jìn)行測(cè)試.因?yàn)槲墨I(xiàn)［13］和［14］中的問題是無(wú)等待模糊置換流水車間調(diào)度問題，所以這里只是用到了文中數(shù)據(jù)，未對(duì)結(jié)果進(jìn)行比較.EM 算法的參數(shù)設(shè)置如下：種群數(shù)為20，算法的迭代次數(shù)為100，測(cè)試結(jié)果如表2 所列.

表2 文獻(xiàn)［12］，［13］和［14］中的實(shí)例測(cè)試結(jié)果

為了測(cè)試算法的收斂速度，這里給出了迭代次數(shù)和目標(biāo)函數(shù)值之間的關(guān)系，依次如圖4所示，從圖4可以看到，針對(duì)這3個(gè)問題，本算法都有較快的收斂速度，針對(duì)文獻(xiàn)［12］和［13］中的問題，當(dāng)?shù)螖?shù)在10左右時(shí)，算法就已經(jīng)收斂.對(duì)于文獻(xiàn)［14］中的問題，當(dāng)?shù)螖?shù)不到30時(shí)算法也已收斂.

圖4 文獻(xiàn)［12］，［13］，［14］中算例的收斂圖

5 結(jié)束語(yǔ)

本文通過(guò)引入隨機(jī)鍵的方法，采用了一種元啟發(fā)式算法——類電磁機(jī)制（EM）算法求解了模糊流水車間調(diào)度問題，優(yōu)化目標(biāo)有最大化平均滿意度和最小化最大模糊完工時(shí)間.測(cè)試實(shí)例和結(jié)果顯示，類電磁機(jī)制算法能較好地求解模糊流水車間調(diào)度問題.在以后的研究中，將采用更多的測(cè)試實(shí)例進(jìn)行驗(yàn)證，并進(jìn)一步提高EM 算法的優(yōu)化性能.

［1］BALASUBRAMANIAN J，GROSSMANN I E.A novel branch and bound algorithm for scheduling flowshop plants with uncertain processing times［J］.Computers and Chemical Engineering，2002，26（1）：41－57.

［2］NEZHAD S，ASSADI R.Preference ratio－based maximum operator approximation and its application in fuzzy flow shop scheduling［J］.Applied Soft Computing，2008，8（1）：759－766.

［3］JAVADI B，MEHRABAD M S，HAJI A，et al.No－wait flow shop scheduling using fuzzy multi－objective linear programming［J］.Journal of the Franklin Institute，2008，345（5）：452－467.

［4］ HONG Tzungpei，WANG Tzutin.Fuzzy flexible flow shops at two machine centers for continuous fuzzy domains［J］.Information Sciences，2000，129（1－4）：227－237.

［5］WU Hsienchung.Solving the fuzzy earliness and tardiness in scheduling problems by using genetic algorithms［J］.Expert Systems with Applications，2010，37（7）：4860－4866.

［6］BIRBIL?˙I.Stochastic global optimization techniques［D］.Raleigh Thesis：North Carolina State University，NC，USA，2002.

［7］BIRBIL?˙I，F(xiàn)ANG S C.An electromagnetism－like mechanism for global optimization［J］.Journal of Global Optimization，2003，25（3）：263－282.

［8］WU Peitsang，YANG Wenhung，WEI Naichieh.An electromagnetism algorithm of neural network analysis－an application to textile retail operation［J］.Journal of the Chinese Institute of Industrial Engineers，2004，21（1）：59－67.

［9］SAKAWA M，KUBOTA R.Fuzzy programming for multi－objective job shop scheduling with fuzzy pro－cessing time and fuzzy duedate through genetic algorithm［J］.European Journal of Operational Research，2000，120（2）：393－407.

［10］GENG Zhaoqiang，ZOU Yiren，Using genetic algorithm to solve fuzzy flow－shop scheduling problem［J］.Systems Engineering and Electronics，2002，24（6）：5－7.

［11］LAI Pengjen，SHU Minghung.Tardiness in fuzzy flow shop scheduling problems based on possibility and necessity measures［J］.Eighth International Conference on Intelligent Systems Design and Applications，Kaohsiung City，Taiwan，2008（26－29）：437－441.

［12］XU Zhenhao，GU Xingsheng.Flow shop scheduling problems under uncertainty based on fuzzy cut－set［C］∥International Conference on Natural Computation，Changsha，China，2005：880－889.

［13］徐震浩，顧幸生.不確定條件下具有零等待的流水車間免疫調(diào)度算法［J］.計(jì)算機(jī)集成制造系統(tǒng)，2004（10）：1247－1251.

［14］鄭 璐，顧幸生.含零等待模塊的存儲(chǔ)時(shí)間有限型混合模糊Flow shop生產(chǎn)調(diào)度問題［C］∥第五屆全球智能控制與自動(dòng)化大會(huì)會(huì)議論文集（4），2004：2909－2913.