離散粒子群優(yōu)化算法在流水作業(yè)調(diào)度問題中的應(yīng)用

付志軍，馮 麗，杜偉寧，凌振寶，楊鳳芹

（1.吉林大學 儀器科學與電氣工程學院，長春 130061；2.安陽師范學院 數(shù)學與統(tǒng)計學院，河南 安陽 455002；3.空軍航空大學 飛行訓練基地，長春 130062；4.東北師范大學 計算機科學與信息技術(shù)學院，長春 130117）

流水作業(yè)調(diào)度（scheduling）問題在生產(chǎn)生活中應(yīng)用廣泛.但精確求解調(diào)度問題已經(jīng)被證明是一個NP難問題.為了適應(yīng)大規(guī)模調(diào)度問題的求解，研究者開始考慮智能優(yōu)化算法［1－3］.文獻［4］通過對群體生物行為的模擬提出了粒子群優(yōu)化算法.該算法容易實現(xiàn)、參數(shù)少、具有較強的全局尋優(yōu)能力.但傳統(tǒng)的粒子群算法只能應(yīng)用于連續(xù)型問題，而流水作業(yè)調(diào)度問題是一個離散型問題.本文通過借鑒遺傳算法中交叉和變異的思想，改進了粒子群算法的變異機制，使其適應(yīng)于調(diào)度問題的求解.在兩個有代表性的標準測試問題上測試了該算法的求解性能，并將實驗結(jié)果與傳統(tǒng)的時序分解算法和經(jīng)典遺傳算法相比較［5－7］.結(jié)果表明，本文提出的算法所求解的質(zhì)量優(yōu)于傳統(tǒng)算法.

1 流水作業(yè)調(diào)度問題描述

在流水作業(yè)調(diào)度問題中，有m臺機器和n個作業(yè)，每個作業(yè)i包括m個必須依次處理的工序（Oi，1，Oi，2，…，Oi，m），其中Oi，k表示作業(yè)i的第k個工序.調(diào)度問題要求確定這n個作業(yè)的最優(yōu)加工順序，使總的加工所需時間最少.本文假設(shè)每個工序Oi，j可由機器集合Mij中任一臺機器處理，從而不但使問題便于研究，且更能反應(yīng)實際工業(yè)生產(chǎn)中的調(diào)度問題.

本文用兩個向量O和M對調(diào)度問題進行編碼.O的長度等于問題中工序的數(shù)量，它的每個位置都是｛1，2，…，n｝中的一個整數(shù)i，表示第i個作業(yè)的一個工序.如果第i個作業(yè)有ni個工序，則i在O中出現(xiàn)ni次，第k個i即表示第i個作業(yè)的第k個工序.M的長度與O相同，它的每個位置是處理O中對應(yīng)位置工序機器的標號［8－11］.

用TBi，j表示工序Oi，j的開始時間，TEi，j表示工序Oi，j的結(jié)束時間，則TBi，j的計算方式如下：

其中PM（i，j）表示工序Oi，j的前一個工序.

2 改進的PSO算法

文獻［12］給出了一個適用于無等待流水車間調(diào)度問題的離散粒子群優(yōu)化算法DPSO，其粒子運動方程如下：

其中λi（t＋1）＝ω?F0（xi（t））表示粒子速度.算法DPSO隨機生成［0，1］間的實數(shù)，如果r≤ω，則對xi（t）進行變異操作得λi（t＋1）＝F0（xi（t）），否則λi（t＋1）＝xi（t）.這樣粒子的各位置在相鄰時刻要么同時變，要么同時不變，不能體現(xiàn)各位置的差異.本文用速度向量vi（t）代替實數(shù)型常量ω，將粒子運動方程變?yōu)槿缦滦问剑?/p>

其他符號與文獻［12］中運動方程的含義相同.

由于調(diào)度問題中對工序和機器均有約束，因此方程（1）中如果采用常規(guī)的交叉和變異操作，可能產(chǎn)生不符合要求的調(diào)度方案.為了避免該問題，本文需要設(shè)計特殊的交叉和變異操作.在交叉算法中，對兩個父本P1和P2，首先隨機生成兩個交叉位s和t，1≤s＜t≤O的長度.對P1中的工序Oi，j，如果Oi，j在P2中的位置位于s和t間，則在P1中將處理Oi，j的機器換為P2中處理Oi，j的機器，并保持P1中其他工序?qū)?yīng)的機器不變，然后將交叉后的P1視為新的粒子.

算法1 交叉算法.／＊對P1和P2執(zhí)行交叉操作，結(jié)果賦給P1＊／

氣象導(dǎo)航誕生于20世紀50年代，發(fā)展到今天，已經(jīng)成為一門學科。實踐也證明氣象導(dǎo)航明顯地提高了船舶航行的安全性，其主要表現(xiàn)在以下幾個方面：

1）隨機生成兩個位置s和t，記P2中s和t間的工序集合為Osubst，其對應(yīng)的機器集合為Msubst；

2）用Msubst代替P1中與Osubst中工序?qū)?yīng)的工序處理機器，并保持P1中其他工序?qū)?yīng)的機器不變.

在變異算法中，首先隨機生成兩個位置s和t，1≤s＜t≤O的長度.設(shè)父本P中第s和t個位置對應(yīng)的分別是作業(yè)Js和Jt中的工序，變異算法將第s和t個位置對應(yīng)的工序分別變?yōu)樽鳂I(yè)Jt和Js中的工序，并保持作業(yè)Js和Jt中各工序的相對順序不變（不是簡單地將這兩個位置對應(yīng)的工序進行對換，否則可能改變作業(yè)工序順序，產(chǎn)生不符合要求的調(diào)度方案），同時調(diào)整M中機器的位置，使各工序?qū)?yīng)的機器保持不變.算法1描述了交叉的過程，可用下例說明.

算法2 變異算法.／＊變異后的工序向量為O′，機器向量為M′＊／

1）隨機生成兩個位置s和t，記O［s］＝Js，O［t］＝Jt，處理作業(yè)Js所有工序的機器序列為MOs，處理作業(yè)Jt所有工序的機器序列為MOt；

3）計算變異后的機器分配向量M′.

① 對所有的O′［i］≠Js且O′［i］≠Jt，置M′［i］＝M［i］；

②對所有的O′［i］＝Ji，將機器序列MOi中的機器編號按從前向后順序依次填入對應(yīng)的M′［i］中；

③對所有的O′［i］＝Jj，將機器序列MOj中的機器編號按從前向后順序依次填入對應(yīng)的M′［i］中.

算法2描述了變異的過程，可用下例說明.

設(shè)P為一個調(diào)度方案，其工序向量和相應(yīng)的機器向量如下：

隨機選取兩個變異位置，首先計算變異后的工序向量：

然后計算變異后的機器分配向量M′，從而得到新的調(diào)度方案：

3 實驗結(jié)果

采用文獻［7］中8×8的部分FJSP與10×10的完全FJSP對所提出的離散粒子群算法MDPSO進行測試.實驗參數(shù)設(shè)置為Psize＝80，c1＝c2＝0.5，算法最大迭代次數(shù)為300，優(yōu)化目標是使調(diào)度方案的完工時間（makespan）最短.將實驗結(jié)果與時序分解方法［5］和經(jīng)典的遺傳算法［6］相比較，各算法得到調(diào)度方案的完工時間列于表1.

表1 不同算法的運行時間比較（工時）Table 1 Comparison of the running time（man－h(huán)our）with different algorithms

對8×8的部分FJSP，MDPSO求得的調(diào)度方案只需要14工時，優(yōu)于時序分解算法的19工時和經(jīng)典遺傳算法的16工時；對10×10的完全FJSP，MDPSO求得的調(diào)度方案只需要7工時，與經(jīng)典算法相同，但遠優(yōu)于時序分解算法的16工時.

［1］關(guān)凇元，劉大有，金弟，等.基于局部搜索的遺傳算法求解自動組卷問題 ［J］.吉林大學學報：理學版，2009，47（5）：961－968.（GUAN Songyuan，LIU Dayou，JIN Di，et al.Genetic Algorithm with Local Search for Automatic Test Paper Generation［J］.Journal of Jilin University：Science Edition，2009，47（5）：961－968.）

［2］周屹，李海龍，王銳.遺傳算法求解物流配送中帶時間窗的VRP問題 ［J］.吉林大學學報：理學版，2008，46（2）：300－303.（ZHOU Yi，LI Hailong，WANG Rui.VRP Problem with Time Windows in the Logistics and Distribution Solved by Genetic Algorithm ［J］.Journal of Jilin University：Science Edition，2008，46（2）：300－303.）

［3］Ercan M F，LI Xiang.Particle Swarm Optimization and Its Hybrids［J］.International Journal of Computer and Communication Engineering，2013，2（1）：52－55.

［4］Kennedy J，Eberhart R C.Particle Swarm Optimization［C］／／Proceedings of the IEEE International Conference on Neural NetworksⅣ.Piscataway：IEEE Press，1995：1942－1948.

［5］Angeline P J.Evolutionary Optimization versus Particle Swarm Optimization：Philosophy and Performance Difference［C］／／Proc of the 7th Annual Conf on Evolutionary Programming.Berlin：Springer，1998：601－610.

［6］Yoshida H，Kawata K，F(xiàn)ukuyama Y，et al.A Particle Swarm Optimization for Reactive Power and Voltage Control Considering Voltage Security Assessment［J］.IEEE Trans on Power Systems，2000，15（4）：1232－1239.

［7］Kacem I，Hammadi S，Borne P.Approach by Localization and Multiobjective Evolutionaryoptimization for Flexible Job－Shop Scheduling Problems［J］.IEEE Transactions on Systems，Man，and Cybernetics，Part C：Applications and Reviews，2002，32（1）：1－13.

［8］Aarts E H L，Laarhoven P J M，Van，Lenstra J K，et al.A Computational Study of Local Search Algorithms for Job Shop Scheduling［J］.ORSA J on Comput，1994，6（2）：118－125.

［9］Nowicki E，Smutnicki C.An Advanced Tabu Search Algorithm for the Job Shop Problem ［J］.Journal of Scheduling，2005，8（2）：145－159.

［10］Danna E，Rothberg E，Pape C L.Exploring Relaxation Induced Neighborhoods to Improve MIP Solutions［J］.Mathematical Programming，2005，102（1）：71－90.

［11］Lourenco H R.Job－Shop Scheduling：Computational Study of Local Search and Large－Step Optimization Methods［J］.European Journal of Operational Research，1995，83（2）：347－367.

［12］PAN Quanke，Tasgetiren M F，LIANG Yunchia.A Discrete Particle Swarm Optimization Algorithm for the No－Wait Flowshop Scheduling Problem ［J］.Computers ＆ Operations Research，2008，35（9）：2807－2839.