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

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

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

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

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

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

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

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

2 改進(jìn)的PSO算法

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

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

其他符號與文獻(xiàn)［12］中運(yùn)動方程的含義相同.

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

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

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

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

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

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

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

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

3）計(jì)算變異后的機(jī)器分配向量M′.

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

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

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

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

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

隨機(jī)選取兩個(gè)變異位置，首先計(jì)算變異后的工序向量：

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

3 實(shí)驗(yàn)結(jié)果

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

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

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

［1］關(guān)凇元，劉大有，金弟，等.基于局部搜索的遺傳算法求解自動組卷問題 ［J］.吉林大學(xué)學(xué)報(bào)：理學(xué)版，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］周屹，李海龍，王銳.遺傳算法求解物流配送中帶時(shí)間窗的VRP問題 ［J］.吉林大學(xué)學(xué)報(bào)：理學(xué)版，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.