離散粒子群優化算法在流水作業調度問題中的應用

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

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

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

1 流水作業調度問題描述

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

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

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

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

2 改進的PSO算法

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

其中λi（t＋1）＝ω?F0（xi（t））表示粒子速度.算法DPSO隨機生成［0，1］間的實數，如果r≤ω，則對xi（t）進行變異操作得λi（t＋1）＝F0（xi（t）），否則λi（t＋1）＝xi（t）.這樣粒子的各位置在相鄰時刻要么同時變，要么同時不變，不能體現各位置的差異.本文用速度向量vi（t）代替實數型常量ω，將粒子運動方程變為如下形式：

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

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

算法1 交叉算法.／＊對P1和P2執行交叉操作，結果賦給P1＊／

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

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

2）用Msubst代替P1中與Osubst中工序對應的工序處理機器，并保持P1中其他工序對應的機器不變.

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

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

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

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

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

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

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

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

設P為一個調度方案，其工序向量和相應的機器向量如下：

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

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

3 實驗結果

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

表1 不同算法的運行時間比較（工時）Table 1 Comparison of the running time（man－hour）with different algorithms

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

［1］關凇元，劉大有，金弟，等.基于局部搜索的遺傳算法求解自動組卷問題 ［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，Fukuyama 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.