基于智能優化算法的車間調度問題研究?

袁亮，袁逸萍，馮歡歡，孫文磊

(新疆大學 機械工程學院，新疆 烏魯木齊 830049)

0 引言

車間調度[1]是制造系統的一個研究熱點，也是理論研究中最為困難的問題之一.調度的任務是根據生產目標和約束，為每個加工對象確定具體的加工路徑、時間、機器和操作.

目前，對車間調度理論的研究已受到廣泛的關注，并取得了較大的進展，但還很不成熟.其中，對調度問題的復雜性研究已成為工程背景很強的一個應用數學分支.在算法研究方面，基于知識的方法和算法技術相結合的趨勢正變得日益顯著，概率分析方法在算法效率和性能方面的研究也日漸增多.對于難以求得最優解的問題，給出多項式時間的搜索方法具有很大的現實意義，同樣，算法的隨機性能分析也是比較有效的分析手段.算法研究中，最優化性能的漸近性分析具有理論指導性，而基于啟發式算法的誤差估計來確定次優度則無疑同樣具有很大的意義.

近年來，隨著人們研究生產調度問題的復雜性越來越高，問題規模越變越大，鑒于精確算法的局限性，越來越多的學者把精力放在近似算法的研究上.近似算法由于其可在合理的時間范圍內給出問題的近優或次優解而被廣泛關注和研究，最典型的一類近似算法為啟發式算法.啟發式算法又可分為構造性啟發式算法和元啟發式算法.構造式啟發式算法是根據問題信息或一組規則來對問題進行求解，這類算法往往能在較短時間內求出問題的近優解，其高效的運行速度是很多學者研究構造啟發式算法的動力.最早的構造啟發式算法是基于分派規則的算法，例如：1960年Gimer提出了一種優先分則框架.1977年Panwalker[2]總結了一百多種調度規則，著名的調度規則有最短作業優先加工(SPT)、先來先服務(FIFO)、最早交貨期優先加工(EDD)等等.對調度規則的應用即有利用基本調度規則來求解的，也有利用基本調度規則的組合或加權組合來求解問題.Vepsalainen[3]針對加權拖期的調度問題提出了一組調度規則.金鋒赫等[4]為了設計自動和手控設備混合的裝配作業車間啟發式調度算法，設計了裝配作業和設備特性相結合的生產調度規則，經過在模具生產車間的仿真實驗表明，所設計的組合調度規則對平均延期時間等目標具有好的優化結果.

迄今為止，計算復雜性理論表明，大多數調度問題都屬于NP難題，目標解的搜索涉及解空間的組合爆炸.線性規劃、動態規劃、分支定界和梯度下降等傳統方法，或是需要目標函數的特殊信息，或是復雜度大，或是優化性能差，因而一般只能處理小規模問題，難以高效高質量地求解復雜的調度問題.正是由于意識到基于計算和數值式的優化技術的弱點，以及調度問題的約束性、非線性、多極小性、不確定性、大規模性、多目標性等復雜性，人們努力研究和發展了統計式全局搜索技術和人工智能的方法，例如模擬退火、遺傳算法、禁忌搜索、進化規劃、進化策略、神經網絡方法和混沌優化等.研究將這些優化算法應用于車間調度問題，已成為一個研究熱點.

1 車間調度問題描述

車間調度問題可以描述為：設有N個工件在M臺機器上加工，由于工件的加工工藝的要求，每個工件使用機器的順序及其每道工序所花時間已給定，調度問題就是如何安排在每臺機器上工件的加工順序，使得某種指標最優.產品每道工序加工的機器號，用矩陣M表示，其中mij表示i產品的第j道工序加工的機器號.產品每道工序加工所需時間，用矩陣T表示，其中tij表示i產品的第j道工序加工所需的時間.具體滿足下面條件：

(1)每一工件在機器上的加工順序一定；

(2)每一臺機器每次只能加工一個工件；

(3)每一工件在機器上的加工被稱為一道工序，工序加工時間是固定的；

(4)工件在機器上被加工時不允許被打斷；

(5)機器與工件可能開始時間都為0.

此例子運用遺傳算法的具體設計，主要包括染色體編碼設計、目標函數選擇、遺傳算子設計、參數選擇等.約束條件如下：

（1）每件產品必須按規定的工序加工；

（2）每一臺機器同一時間只能加工一個產品.

優化目標是安排每臺機器上所應加工產品的加工順序，使得在盡可能短時間內完成所有產品的加工任務.數學模型為：

Min（maxfi)

其中fij表示產品i第j道工序的完成時間，fi表示產品i的最終完成時間，tij表示產品i的第j道工序加工所需的時間，A(t)表示在t時刻正在被加工的產品集合，當產品在被機器j加工時yij=1，否則yij=0.

2 車間調度問題的智能優化算法研究現狀

智能優化算法包括遺傳算法、模擬退火算法、人工神經網絡算法、蟻群算法、粒子群算法、人工免疫算法等.智能優化算法發展至今，已出現了各種不同的算法，不同的算法有不同的特點，在實際運用中采取何種算法，要根據具體所求解的問題的特點來選擇.文章主要對模擬退火算法、遺傳算法和蟻群算法給予介紹.

2.1 模擬退火算法

模擬退火算法[5]是近幾年提出的一種適合解大規模組合優化問題，特別是解NP完全問題的通用有效近似算法.它與以往的近似算法相比，具有描述簡單，使用靈活運用廣泛，運行效率高和較少受初始條件限制等優點，而且特別適合并行計算，因此不僅具有很高的實用價值，而且對推動并行計算的研究也有著重要的理論意義.

模擬退火算法最早見于IBM托馬斯[6].J.沃森研究中心S.Kirkpatrick[7]等人的文章，他們在對組合優化進行研究后，根據迭代改進的思提出了“模擬退火算法”，模擬退火算法具有很強的局部搜索能力.模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其緩慢降溫(即退火）使之達到能量最低點.反之，如果急速降溫(即淬火)則不能達到最低點.加溫時固體內部粒子隨溫升變為無序狀，內能增大，而緩慢降溫時粒子漸趨有序，在每個溫度上都達到平衡態，最后在常溫時達到基態，內能減為最小.Metropolis準則，粒子在溫度T時趨于平衡的概率為exp(?E/(kT))，其中E為溫度T時的內能，E為其改變量，k為Boltzman常數.用固體退火模擬組合優化問題，將內能E模擬為目標函數值f，溫度T演化成控制參數t，即得到解組合優化問題的模擬退火算法.

2.2 遺傳算法

遺傳算法[7,8]是近年來迅速發展起來的一種全新的隨機搜索與優化算法，其基本思想是基于Darwin的進化論和Mendel的遺傳學說.該算法由密執安大學教授Hol2land及其學生于1975年創建.此后，遺傳算法的研究引起了國內外學者的關注.1985年以來，國際上已召開了多次遺傳算法學術會議和研討會，國際遺傳算法學會組織召開的ICGA會議和FOGA會議，為研究和應用遺傳算法提供了國際交流的機會.遺傳算法流程圖（如圖1）.

圖1 遺傳算法流程圖

遺傳算法主要通過交叉、變異、選擇運算實現.交叉或變異運算生成下一代染色體，稱為后代.染色體的好壞用適應度來衡量.根據適應度的大小從上一代和后代中選擇一定數量的個體，作為下一代群體，再繼續進化，這樣經過若干代后，算法收斂于最好的染色體，它很可能就是問題的最優解或次優解.遺傳算法中使用適應度這個概念來度量群體中各個個體在優化計算中有可能到達最優解的優良程度.

2.3 蟻群算法

蟻群算法[9]是一種本質并行的算法，它是根據螞蟻群在外處在一個陌生環境尋找食物時，總是能找到一條最優路徑而受到啟示得到的.蟻群算法是由意大利學者M.Dorigo于20世紀90年代提出的一種啟發式進行算法.蟻群算法流程圖（如圖2）.

用EDD（優先選擇最早交貨期的工件）、EODD（優先選擇最早交貨期的工序）、FCFS（優先選擇服務先到達的工序）3種簡單啟發式調度規則的組合規則對此算例進行調度，使用相同的各參數：工件數N=4，機器數M=10，工人數W=7，所得的解為64 h.仿真得到的最佳生產周期的調度結果如圖2所示.

圖2 蟻群算法流程圖

3 遺傳算法在車間多目標智能調度優化中的應用

3.1 問題描述

本文研究的是受工人和設備雙資源約束的柔性JSP調度問題，該調度問題可以描述為：W個工人在M臺機床上加工N個工件，每個工件包含一道或多道工序，工件的工序順序是預先確定的，但每個工件可能有一條或幾條可行的加工路線，每道工序可以由不同的工人在多臺不同的機床上加工，工序加工時間和加工費用隨工人的技術水平和機床的性能不同而不同.工人的數量少于機床的數量，每一個工人會操作多臺機床，工人的加工費用隨其技術水平不同而變化.作業調度任務是制定出一個生產計劃，該計劃不僅要確定每個工件的具體加工路線、各機床上工序的加工順序及操作機床的工人，而且要在滿足約束條件的同時，使得生產周期、設備負載和生產費用指標取得最優值[8].

對工件、機床和工人有下面的約束條件：(1)每臺機床一次只能加工一個工件，一個工件不能在同一臺機床上加工多次；(2)各工件必須按工藝路線以指定的次序在機床上加工；(4)工序的加工時間是預知的，輔助加工時間被考慮到加工時間內；(5)工人可操作的機床集合是確定的，每個工人一次只能操作一臺機床；（6）考慮工人操作機床的熟練程度.

3.2 種群初始化

為使初始種群最大限度地分布于解空間且盡可能產生較優良的個體，本文對初始種群部分個體的資源采用最短加工時間指配法，其余個體資源采用隨機生成法.

以下是采用最短加工時間資源指配法生成部分種群的初始化步驟：

（1）令循環數k=1；

（2）將Chrom(k).z（Chrom為種群，z為個體，z=1,2,···Z）種群第一行置0；

（3）根據各工件i的工序數J，在Chrom(k).z的第一行隨機尋找J個還未被占用的空位（0位），將i賦給該空位；

（4）從左到右遍歷Chrom(k).z的第一行，計算各工件出現的序號，賦給Chrom(k).z的第四行；

（5）從左到右，根據各工件i及其工序號j，從可選機床集JmNumber中選擇一個加工時間最短的機床號、并從可選工人集HmNumber中選擇一個技術水平最高的工人號，分別賦給Chrom(k).z的第二行和第三行；

（6）令k=k+1；

（7）若k≤Popsize（種群規模），則轉步驟2，否則退出循環.

采用隨機生成法生成部分種群的方法步驟和以上采用最短加工時間資源指配法類似，區別于步驟5的是：從可選機床集JmNumber中隨機選擇一個機床號、并從可選工人集HmNumber中隨機選擇一個工人號.

3.3 遺傳算子設計

3.3.1 交叉操作

為保證交叉后的個體仍是可行解，本文只對工序號進行交叉操作，而保存交叉前的機床號和工人號.

算法采用工件的集合分解法，既便于操作，又保證了同一集合中的工件在父染色體中與子染色體中具有相同的順序.算法如下:

（1）隨機選取幾個工件放入集合s1，剩余的工件放入集合s2；

（2）令循環次數k=0；

（3）檢查父染色體parent1工序鏈的第k個工序，如該工序屬于集合s1，則進入子染色體offspring1.同樣，檢查父染色體parent2工序鏈的第k個工序，如該工序屬于集合s2，則進入子染色體offspring1；

（4）k=k+1，如k小于染色體的長度，重復（3），否則進行步驟（5）；

（5）交換集合s1與s2，重復（2）、（3）和（4）.

3.3.2 變異操作

為確保變異后的個體也是可行的，變異操作采用分段方式，包括加工順序變異、加工機床和工人變異.

（1）加工順序變異

從種群中任意選取一個體，隨機選擇兩變異點λ1，λ2，且λ1=λ2，交換λ1，λ2所在位置上的兩工序號，為保證子代的可行性，保存變異前的機床號和工人號.

（2）加工機床和工人變異

針對在多臺機床上由不同工人加工的工件i的工序號j的變異，為增大性能好的機床和操作能力強的工人的選中概率，采用輪盤賭選擇方式重新從JmNumber中隨機獲取可用機床號，并從HmNumber中隨機獲取可用工人號，分別替換j對應的機床號和工人號.

3.4 實驗仿真

此算例中仿真使用的各參數為：工件數N=4，機器數M=10，工人數W=7，種群個體數Z=50，迭代次數MAXGEN=100，選擇概率GGAP=0.9，交叉概率Pc=0.8，變異概率Pm=0.1.對這批零件的加工過程重復仿真10次，得到的最優解或近似最優解為51 h.該調度結果只是較優解之一，調度人員可以根據車間實際情況從多個非劣解選擇偏好解.

用EDD（優先選擇最早交貨期的工件）、EODD（優先選擇最早交貨期的工序）、FCFS（優先選擇服務先到達的工序）3種簡單啟發式調度規則的組合規則對此算例進行調度，使用相同的各參數：工件數N=4，機器數M=10，工人數W=7，所得的解為64 h.仿真得到的最佳生產周期的調度結果如圖3所示.

圖3 啟發式規則調度Gantt圖

4 結論

智能優化算法的發展和研究對解決車間調度問題有重大的意義.合理的優化算法對改進車間調度有很大的幫助，不僅能夠提高人與機器配合的效率，還能有效提高機器的利用率，從而為企業帶來更大的利益.

車間調度問題是對于生產環境中復雜的、動態的多目標的一種抽象和簡化.在對調度問題進行研究的方法上最初是集中在整數規劃、仿真和簡單的規則上，這些方法不是調度不理想就是難以解決復雜的問題.因此，隨著各種新的相關科學與優化技術的建立與發展，在調度問題上也出現了很大的進展.并且，以柔性車間調度問題為例，顯示了遺傳算法在解決受工人和機器雙資源約束的柔性車間調度問題上的魯棒性.

對車間調度問題的研究雖有幾十年的歷史，但至今尚未形成一套系統的方法和理論，理論研究與實際應用之間還存在著很大差距.今后研究者可從以下幾個方面進行深入的研究.進一步深入實際，找出車間管理與調度諸多因素的內部關系，建立最能反映生產需要的調度模型.進一步研究車間計劃與車間調度之間的關系，建立計劃與調度的集成模型，從整體上進行優化研究.進一步研究先進制造系統模式，探索快速實用的智能調度算法.總之，隨著調度研究的深入，調度算法必然會進一步與生產實踐相結合，向集成化、動態化、高效化、實用化、智能化的方向發展.