摘要：提出了求解車間調(diào)度問題的離散粒子群優(yōu)化算法，該方法綜合考慮最小化平均完成時間、最小化完成時間以及作業(yè)安裝時間的作業(yè)性能指標。采用離散粒子群算法進行求解最小化平均完成時間和最小化完成時間，并對作業(yè)安裝時間進行分離出來單獨處理。仿真實驗數(shù)據(jù)表明該算法能較好的解決作業(yè)調(diào)度問題，具有一定的有效性和實用性。
　　關(guān)鍵詞：粒子群；車間調(diào)度；安裝時間
　　中圖分類號：TP399 文獻標識碼：A 文章編號：1009-3044（2012）28-6787-03
　　1 概述
　　車間調(diào)度和控制是提高企業(yè)生產(chǎn)效率的有效手段。車間調(diào)度和車間計劃是實現(xiàn)生產(chǎn)任務(wù)和生產(chǎn)計劃的重要手段。通常車間調(diào)度是指在有效計劃時間內(nèi)將滿足 多個性能指標的待加工作業(yè)按照一定的工序安排到多臺機器上加工和處理。一般車間調(diào)度問題分為兩大類即作業(yè)車間調(diào)度和流水線車間調(diào)度。在車間調(diào)度問題中，有許多性能指標，如平均完成時間、完成時間以及延遲時間等。其中完成時間是最能反映客戶的需求，也是反映資源利用效率。許多學者對車間調(diào)度的不同標準進行了研究，如Birbil S I， Fang S 等[1]采用最小化延遲時間來提高車間調(diào)度效率。Allahverdi，Al-Anzi等[2]采用最小化平均完成時間和 最小化完成時間雙重標準進行車間調(diào)度問題。以上這些研究都集中單一目標或未考慮加工過程中作業(yè)安裝時間。這在實際中一般不存在。
　　在粒子群算法中，已有的粒子群算法針對連續(xù)型空間進行求解的，無法直接應用于離散型數(shù)據(jù)。Qian B， Wang L等[3]提出一個隨機鍵實現(xiàn)連續(xù)空間與離散空間的轉(zhuǎn)換。周馳， 高亮等[4]針對連續(xù)空間和離散空間轉(zhuǎn)換問題提出最小位置值來進行求解車間調(diào)度問題。以上算法都是通過轉(zhuǎn)換進行直接使用已有粒子群算法，但這種隨機鍵或最小位置值變換都存在一個明顯的弊端，即粒子位置的輕微變化 可能會導致對應的 作業(yè)加工順序產(chǎn)生很大的變化。針對以上問題，本文將作業(yè)加工順序進行編碼，每個作業(yè)對應一種編碼。同理在求解粒子群體最優(yōu)和個體最優(yōu)時也采用相同的編碼方式[4]。這種編碼方式 直觀、表述簡單，且容易理解。針對已有的最小化平均完成時間和最小化完成時間雙重標準，以及考慮單一標準的作業(yè)安裝時間。本文將最小化平均完成時間和最小化完成時間雙重標準采用離散粒子群算法進行求解，并對作業(yè)安裝時間 進行分離出來 單獨處理。
　　2 問題描述
　　3 離散粒子群算法
　　在已有粒子群算法的基礎(chǔ)上，根據(jù)粒子的速度進行實時修改粒子的移動。采用對粒子的變異和強度來控制粒子發(fā)生自適應變異。其算法的描述如下：
　　離散粒子群算法偽代碼描述：
　　輸入：測試數(shù)據(jù)；粒子群體大小K 及其參數(shù)；
　　輸出：作業(yè)最佳排列和 最小完成時間[FOmax]
　　4 實驗仿真與結(jié)果分析
　　本文的實驗數(shù)據(jù)采用均勻分布的隨機生成。計算機配置為windows xp，處理器2.8Ghz，內(nèi)存1G，實驗中作業(yè)的處理時間由U[1，80]生成。作業(yè)個數(shù)n取20，40，60，80。不是一般性將作業(yè)第一階段機器數(shù) 設(shè)置為2，4，6，8。作業(yè)安裝時間 系數(shù)K設(shè)置0.3，0.6，0.9，1.2。加權(quán) 系數(shù)[α]設(shè)置為0.2，0.5，0.8。作業(yè)加工 由機器數(shù)、作業(yè)數(shù)、安裝時間進行組合，若每種組合測試用例為10，則共有1920個測試用例。用[n_m_k_α_u]來表示一個具體的測試用例，其中n表示作業(yè)個數(shù)，m表示機器數(shù)，u表示第u個測試用例。采用相對誤差（PE）、平均相對誤差（APE）以及局部搜索次數(shù)（LSC）來測試算法的性能。其中相對誤差的公式為：
　　其中[soli]表示第i次獲得的最優(yōu)解，[bestsol]表示算法執(zhí)行中獲得的最優(yōu)解。則停滯代數(shù)（maxstop）取不同值時的實驗數(shù)據(jù)如下：
　　從表2可以得到如下結(jié)論：停滯代數(shù) 與局部搜索次數(shù) 成反比即停滯代數(shù) 越大則局部搜索次數(shù) 越少，表明 所求解的質(zhì)量越低。這里因為求解問題規(guī)模越大，停滯代數(shù)相對減少，則局部搜索的次數(shù)也相對減少的緣故。從表1的數(shù)據(jù)也發(fā)現(xiàn)在停滯代數(shù)為20、30時，局部搜索的次數(shù)下降的幅度最大，而解的質(zhì)量沒有明顯的下降，綜合解的質(zhì)量和局部搜索的次數(shù)，我們可以得出當停滯代數(shù)=30時可以得到群體最優(yōu)解。
　　5 結(jié)束語
　　本文綜合考慮最小化平均完成時間、最小化完成時間以及作業(yè)安裝時間的作業(yè)性能指標。采用離散粒子群算法進行求解最小化平均完成時間和最小化完成時間，并對作業(yè)安裝時間進行分離出來單獨處理。實驗仿真數(shù)據(jù)可以得出，當停滯代數(shù)=30時，綜合解的質(zhì)量和局部搜索的次數(shù)得到群體最優(yōu)解即為最優(yōu)調(diào)度的作業(yè)順序。因此所提出的離散粒子群算法能較好解決作業(yè)調(diào)度問題。下階段要解決的是將更多作業(yè)性能指標標準加入進來，如作業(yè)等待時間，作業(yè)懲罰時間等。
　　參考文獻：
　　[1] Birbil S I，F(xiàn)ang S.Differential evolution algorithm for permutation flowshop sequencing problem with makespan criterion[C].Proceedings of the 4th International symposium on intelligent manufacturing systems （IMS2004）， Sakarya，Turkey， 2004：442-452.
　　[2] Allahverdi A，Al-Anzi.A self-adaptive differential evolution heuristic for two-stage assembly scheduling problem to minimize maximum lateness with setup times[J].European Journal of Operational Research（Discrete Optimization）， 2007，182（1）：80-94.
　　[3] Qian B，Wang L，Hu R，Wang W L，Huang D X，Wang X.A hybrid differential evolution method forpermutation flow-shop scheduling[J].International Journal Advanced Manufacturing Technology，2008，38（7-8）：757-777.
　　[4] 周馳，高亮，高海兵.基于 PSO 的置換流水車間調(diào)度算法[J].電子學報，2006， 34（11）：2008-2011.
　　[5] 張長勝，孫吉貴，歐陽丹彤.一種自適應離散粒子群算法及其應用研究[J].電子學報， 2009，37（2）：299-30