陳宇航，劉階萍，秦智晗

（北京交通大學(xué)機械與電子控制工程學(xué)院，北京100044）

生產(chǎn)調(diào)度問題屬于NP-hard問題，是一種很難解決的理論難題。為了有效地解決生產(chǎn)調(diào)度問題，研究人員往往需要對復(fù)雜的問題進行理論分析，建立數(shù)學(xué)模型以求解不同的生產(chǎn)調(diào)度問題。但通過這類方法很難找到最優(yōu)解，效果不理想。近年來，人們運用仿生型智能優(yōu)化算法求解生產(chǎn)調(diào)度問題，如遺傳算法、模擬退火算法、蟻群算法、微粒群算法等。

在生產(chǎn)調(diào)度領(lǐng)域，因為微粒群算法的概念簡明、依賴的經(jīng)驗參數(shù)較少、收斂速度快、實現(xiàn)方便，所以短期內(nèi)得到了一定的發(fā)展與應(yīng)用，尤其是在離散型生產(chǎn)調(diào)度優(yōu)化方法研究方面的應(yīng)用越來越多[1~2]。但是微粒群算法容易陷入局部最優(yōu)解、后期收斂速度慢，本文基于此對微粒群算法提出改進，在離散型生產(chǎn)調(diào)度優(yōu)化中采用實際項目算例進行驗證[3~4]，在算法運行后期加快了群體的收斂速度，避免了容易陷入局部最優(yōu)的缺陷，使目標問題的解更加接近最優(yōu)解，提高了解的質(zhì)量。

1 數(shù)學(xué)模型

離散型調(diào)度問題，也被稱為非流水車間調(diào)度問題[5]，該問題研究n個任務(wù)在m臺機器上作業(yè)，已知各工序的作業(yè)時間和各工件的加工次序，而假設(shè)所有工件的工藝順序不完全相同。離散型調(diào)度的問題一般有：火箭、飛機、船舶、武器裝備、機械、玩具生產(chǎn)等行業(yè)[6]。對于此類問題，通常假定[7~8]：

（1）一個任務(wù)在同一時刻只能在一臺機器上加工；（2）每臺機器在同一時刻只能加工一個任務(wù)；（3）任務(wù)的加工時間在初始時確定，且在整個加工過程中保持不變；（4）任務(wù)的加工準備時間和運輸與順序無關(guān)，且包含在加工時中；（5）每臺機器上加工各任務(wù)的順序不完全一樣；（6）每個任務(wù)在所有機器上的加工順序是不完全一樣。

此類問題一般需要滿足以下2個約束條件：

（1）機器約束：每臺機器在同一時刻只能加工一個任務(wù)；（2）工藝約束：每道工序必須在它前置的工序加工完畢后再進入下一道加工。

離散型調(diào)度問題流程如圖1。將這一類問題的數(shù)學(xué)模型歸納如下[7]：

圖1 離散型調(diào)度問題流程圖

S.T.

cik－pik+M(1－aihk)≥cih，

i=1,2,…, n；h, k=1,2,…, m

cjk－cik+M(1－xijk)≥pik，

i,j=1,2,…, n；k=1,2,…, m

cik≥0, i=1,2,…, n；k=1,2,…, m

生產(chǎn)調(diào)度的目標即為產(chǎn)生一個優(yōu)化的工件調(diào)度序列，使得最大流程時間盡可能的小。

2 基于混沌的微粒群算法

微粒群算法，又稱粒子群優(yōu)化(Particle Swarm Optimization,PSO)，是一種演化計算技術(shù)，來源于對一個簡化社會模型的模擬[9]。該算法在圖像處理、模式識別和多目標優(yōu)化等領(lǐng)域得到廣泛應(yīng)用。

微粒群算法后期容易陷入局部最優(yōu)解且收斂速度慢，本文提出了基于混沌的微粒群算法（Chaotic Particle Swarm Optimization,CPSO）來求解復(fù)雜的調(diào)度離散問題[10]。利用混沌的遍歷性特點進行優(yōu)化搜索且能避免陷入局部極小，因此，混沌優(yōu)化搜索方法已成為一種新穎的優(yōu)化技術(shù)[11~12]，將該技術(shù)嵌入到微粒群算法，增強其功能。

混沌微粒群算法的優(yōu)化過程如下[13]：

（1）將所有微粒（種群規(guī)模為N）進行初始化，在一定的范圍內(nèi)隨機設(shè)置微粒的初始位置x和速度v，微粒群的進化代數(shù)genn。

（2）設(shè)定混沌搜索部分的參數(shù)。加速常數(shù)c1和c2；慣性權(quán)重wmin和wmax；混沌變量序列長度m；粒子飛行速度限制設(shè)置，該維的速度被限制為該維最大度vmax，即vid∈[-vmin,vmax] 。

（3）在一定的范圍內(nèi)隨機產(chǎn)生微粒的初始位置和速度，令迭代次數(shù)k=1。

（4）根據(jù)下式計算慣性權(quán)重。

（5）對每個微粒，將它的適應(yīng)值和它經(jīng)歷過的最好位置Pbest作比較，如果較好，則將其作為當(dāng)前的最好位置Pbest；對每個微粒，將它的適應(yīng)值和全局所經(jīng)歷最好位置Gbest作比較，如果較好，則將其作為全局的最優(yōu)解。

為了使得到的結(jié)果不要超出所允許的范圍，設(shè)定如果vk＜vmin，則vk=vmin；如果vk＞vmax，則vk=vmax；如果xk＜xmin，則xk=xmin；如果xk＞xmax，則xk=xmax。其中vmax和vmin為vk的取值范圍；而xmax和xmin為xk的取值范圍。

（6）在區(qū)間（0,1）內(nèi)任取值rand（0,1），根據(jù)公式（1-6）計算Pk，比較rand（0,1）與Pk的大小，如果rand(0,1)≤Pk，則根據(jù)以下步驟進行混沌搜索，否則轉(zhuǎn)到步驟（7）。

采用混沌搜索的概率計算公式：

其中k為迭代的次數(shù)。在算法初始，P值較小，整個程序以微粒群算法為主，以很小的概率調(diào)用混沌搜索，可以更好地保證搜索的速度。隨著迭代次數(shù)的增加，k值增大，即P值越來越趨近于1，算法以更大的概率采取混沌搜索。這主要是因為在算法搜索的初期，微粒群算法搜索速度快，且具有很好的收斂性，采用微粒群算法就可以獲得較好的搜索效果，但是隨著搜索的進行，到進化后期，微粒群搜索收斂性越來越慢，因而采用混沌搜索來彌補這一弱點。因此，在整個搜索尋優(yōu)的過程中既充分發(fā)揮了微粒子群算法簡單易實現(xiàn)、搜索速度快的優(yōu)點，又在進化后期有效地改進了微粒群算法，使得最后不會收斂到局部最優(yōu)值。

下面介紹混沌搜索的具體過程：

c.對xld進行混沌搜索：

e.重復(fù)b、c、d步驟，直到一定步數(shù)內(nèi)f*保持不變或達到給定的最大搜索步數(shù)，結(jié)束尋優(yōu)計算，此時的即為算法得到的最優(yōu)變量，f*為得到的最優(yōu)解。

（7）計算適應(yīng)度，確定全局最優(yōu)值。

（8）按照速度和位置更新方程(1-1)更新微粒的速度和位置。

（9）如果還沒有達到結(jié)束條件（通常為足夠好的適應(yīng)值或達到一個預(yù)設(shè)最大代數(shù)），令k=k+1則轉(zhuǎn)步驟（4）。如果達到條件，則輸出全局最優(yōu)值，程序結(jié)束。

混沌微粒群算法流程如圖2。

3 算例分析

3.1 項目背景

圖2 混沌微粒群算法流程圖

某航空發(fā)動機公司的精密件加工任務(wù)主要由某機械廠車間承擔(dān)。試驗車間布置和工件流動場景如圖3。精密件加工屬于典型的離散制造。

圖3 試驗的車間布置和工件流動場景圖

然而，在加工現(xiàn)場每類設(shè)備只有一臺，其他設(shè)備留作意外情況發(fā)生時（比如機器故障、生產(chǎn)任務(wù)增加等）使用，以保障整個生產(chǎn)任務(wù)的正常進行并完成。

在該車間，精密件整個加工制造流程主要包括生產(chǎn)任務(wù)接收、生產(chǎn)準備、工藝執(zhí)行、產(chǎn)品檢驗和產(chǎn)品交付5個環(huán)節(jié)。

3.2 編碼方式

工廠的生產(chǎn)任務(wù)是根據(jù)生產(chǎn)計劃下發(fā)的訂單分解后下達到各個車間。本次的研究基于某個項目的具體事例進行分析。其訂單包括5種類型的工件，根據(jù)以往的生產(chǎn)經(jīng)驗，調(diào)研并采集數(shù)據(jù)，將得到每道工序的平均加工時間以及每道工序?qū)?yīng)的時間如表1。

表1 項目某訂單作業(yè)時間表

對于n個任務(wù)m臺機器流程型生產(chǎn)調(diào)度，每個任務(wù)都要按照一定順序在m臺機器進行作業(yè)，因此，n個任務(wù)就有n×m道工序。采用基于工序的染色體編碼方式[7]，用自然數(shù)1,2,…, n表示每個任務(wù)，相同任務(wù)的不同工序均用同一個任務(wù)號表示，每個染色體包括n×m個代表工序的基因，從而形成所有任務(wù)的工序排列，其中每個任務(wù)m次出現(xiàn)在染色體中，每個基因只有上下依賴關(guān)系的工序。染色體的任意排列總能產(chǎn)生可行調(diào)度。解碼過程是先把染色體轉(zhuǎn)化為一個有序的工序表，然后根據(jù)工序表和生產(chǎn)任務(wù)的工藝約束，以最早允許作業(yè)時間對各任務(wù)逐個進行加工，從而得到調(diào)度方案。在編程過程中，設(shè)置w=3（程序運行次數(shù)），genn=50（最大代數(shù)），PS=50（種群規(guī)模），e=0.4（PSO算法慣性因子），針對這5種類型的工件，分別采用PSO、CPSO得到不同的生產(chǎn)調(diào)度結(jié)果。

3.3 CPSO算法結(jié)果

基于PSO與CPSO的適應(yīng)度收斂曲線如圖4。由圖可以看出，在前期，采用CPSO得到的收斂速度與PSO的幾乎相同。但是，在搜索后期采用CPSO收斂速度更快。而且CPSO得到的目標值比PSO得到的結(jié)果好，這表明了CPSO彌補了PSO在后期容易陷入局部最優(yōu)解及收斂速度慢的特點。基于CPSO的精密件加工作業(yè)甘特圖如圖5。結(jié)果如下：

圖4 基于PSO與CPSO的適應(yīng)度收斂曲線

minm=48

BestPosition=

機器1：J1→J4→J3→J5→J2；

機器2：J4→J1→J5→J2→J3；

機器3：J1→J3→J5→J4→J2；

機器4：J3→J1→J4→J5→J2；

機器5：J5→J4→J2→J1→J3；

機器6：J3→J1→J5→J2→J4

圖5 基于CPSO的精密件加工作業(yè)甘特圖

經(jīng)過計算得到基于CPSO的精密件加工的機器利用率分別為：M1：56.25%；M2：45.83%；M3：52.08%；M4：39.58%；M5：60.42%：M6：4.17%。用PSO與CPSO得出來的機器利用率對比如圖6，采用CPSO方法得到的機器利用率明顯增高。

4 結(jié)束語

對于離散型生產(chǎn)調(diào)度組合優(yōu)化問題，微粒群算法的改進對于目標解的尋找有著較大的幫助。基于混沌微粒群算法搜索速度較快，有助于調(diào)度工作效率的提高。在未來的研究中，可以充分利用基于混沌微粒群算法的優(yōu)勢，將其應(yīng)用于靜態(tài)和動態(tài)的生產(chǎn)調(diào)度領(lǐng)域，還可以用于流程型生產(chǎn)調(diào)度、混合流程型生產(chǎn)調(diào)度等領(lǐng)域。

圖6 基于PSO與CPSO的機器利用率對比

[1] 王凌，劉波. 微粒群優(yōu)化與調(diào)度算法[M] . 北京：清華大學(xué)出版社，2008.

[2] Lawler,Lenstra,Rinnooy Kan,Sequecing and Scheduling: Algorithms and Conplexity[J] .Operations Research and Management Science,Vol.4.

[3] 高立群，任蘋，李楠. 基于混沌粒子群算法的高速旅客列車優(yōu)化調(diào)度[J] . 東北大學(xué)學(xué)報，2007（2）.

[4] 吳月秋，紀昌明，王麗萍，李志勝. 基于混沌粒子群算法的水電站水庫優(yōu)化調(diào)度[J] . 人民黃河，2008，30（11）.

[5] 唐宇. 基于微粒群算法的車間調(diào)度問題研究[D] . 杭州：浙江工業(yè)大學(xué)，2007.

[6] 蘇成利，徐志成，王樹青. PSO算法在非線性系統(tǒng)模型參數(shù)估計中的應(yīng)用[J] . 信息與控制，2005，34（1）：123-125.

[7] 顧擎明，宋文忠. 混合遺傳算法在Job-shop調(diào)度問題中的應(yīng)用[J] . 信息與控制，1998，27（5）：369.

[8] ChengR.GenM.A Tutorial Survey of Job Shop Scheduling Problems Using Genetic Algorithms Representation[J] . Computers& Industrial Engineering. 1996, 30(4): 983-989.

[9] 崔志華，曾建潮.微粒群優(yōu)化算法[M] . 北京：科學(xué)出版社，2011.

[10] 曹蘊. 基于混沌搜索與粒子群算法的配電網(wǎng)規(guī)劃的研究[D] . 北京：華北電力大學(xué)，2008

[11] 石欣. 基于混沌粒子群算法的同步發(fā)電機最優(yōu)調(diào)速控制系統(tǒng)[D] . 天津：天津大學(xué)，2007.

[12] Lovbjerg,Rasmussen. Hybrid:Partical Swarm Optimizer With Breeding and subpopulation[C] .In:Proc of the third Genetic and Evolution Compution Conference,2001