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

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

0 引言

車間調(diào)度[1]是制造系統(tǒng)的一個(gè)研究熱點(diǎn)，也是理論研究中最為困難的問題之一.調(diào)度的任務(wù)是根據(jù)生產(chǎn)目標(biāo)和約束，為每個(gè)加工對(duì)象確定具體的加工路徑、時(shí)間、機(jī)器和操作.

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

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

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

1 車間調(diào)度問題描述

車間調(diào)度問題可以描述為：設(shè)有N個(gè)工件在M臺(tái)機(jī)器上加工，由于工件的加工工藝的要求，每個(gè)工件使用機(jī)器的順序及其每道工序所花時(shí)間已給定，調(diào)度問題就是如何安排在每臺(tái)機(jī)器上工件的加工順序，使得某種指標(biāo)最優(yōu).產(chǎn)品每道工序加工的機(jī)器號(hào)，用矩陣M表示，其中mij表示i產(chǎn)品的第j道工序加工的機(jī)器號(hào).產(chǎn)品每道工序加工所需時(shí)間，用矩陣T表示，其中tij表示i產(chǎn)品的第j道工序加工所需的時(shí)間.具體滿足下面條件：

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

(2)每一臺(tái)機(jī)器每次只能加工一個(gè)工件；

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

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

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

此例子運(yùn)用遺傳算法的具體設(shè)計(jì)，主要包括染色體編碼設(shè)計(jì)、目標(biāo)函數(shù)選擇、遺傳算子設(shè)計(jì)、參數(shù)選擇等.約束條件如下：

（1）每件產(chǎn)品必須按規(guī)定的工序加工；

（2）每一臺(tái)機(jī)器同一時(shí)間只能加工一個(gè)產(chǎn)品.

優(yōu)化目標(biāo)是安排每臺(tái)機(jī)器上所應(yīng)加工產(chǎn)品的加工順序，使得在盡可能短時(shí)間內(nèi)完成所有產(chǎn)品的加工任務(wù).數(shù)學(xué)模型為：

Min（maxfi)

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

2 車間調(diào)度問題的智能優(yōu)化算法研究現(xiàn)狀

智能優(yōu)化算法包括遺傳算法、模擬退火算法、人工神經(jīng)網(wǎng)絡(luò)算法、蟻群算法、粒子群算法、人工免疫算法等.智能優(yōu)化算法發(fā)展至今，已出現(xiàn)了各種不同的算法，不同的算法有不同的特點(diǎn)，在實(shí)際運(yùn)用中采取何種算法，要根據(jù)具體所求解的問題的特點(diǎn)來選擇.文章主要對(duì)模擬退火算法、遺傳算法和蟻群算法給予介紹.

2.1 模擬退火算法

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

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

2.2 遺傳算法

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

圖1 遺傳算法流程圖

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

2.3 蟻群算法

蟻群算法[9]是一種本質(zhì)并行的算法，它是根據(jù)螞蟻群在外處在一個(gè)陌生環(huán)境尋找食物時(shí)，總是能找到一條最優(yōu)路徑而受到啟示得到的.蟻群算法是由意大利學(xué)者M(jìn).Dorigo于20世紀(jì)90年代提出的一種啟發(fā)式進(jìn)行算法.蟻群算法流程圖（如圖2）.

用EDD（優(yōu)先選擇最早交貨期的工件）、EODD（優(yōu)先選擇最早交貨期的工序）、FCFS（優(yōu)先選擇服務(wù)先到達(dá)的工序）3種簡(jiǎn)單啟發(fā)式調(diào)度規(guī)則的組合規(guī)則對(duì)此算例進(jìn)行調(diào)度，使用相同的各參數(shù)：工件數(shù)N=4，機(jī)器數(shù)M=10，工人數(shù)W=7，所得的解為64 h.仿真得到的最佳生產(chǎn)周期的調(diào)度結(jié)果如圖2所示.

圖2 蟻群算法流程圖

3 遺傳算法在車間多目標(biāo)智能調(diào)度優(yōu)化中的應(yīng)用

3.1 問題描述

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

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

3.2 種群初始化

為使初始種群最大限度地分布于解空間且盡可能產(chǎn)生較優(yōu)良的個(gè)體，本文對(duì)初始種群部分個(gè)體的資源采用最短加工時(shí)間指配法，其余個(gè)體資源采用隨機(jī)生成法.

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

（1）令循環(huán)數(shù)k=1；

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

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

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

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

（6）令k=k+1；

（7）若k≤Popsize（種群規(guī)模），則轉(zhuǎn)步驟2，否則退出循環(huán).

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

3.3 遺傳算子設(shè)計(jì)

3.3.1 交叉操作

為保證交叉后的個(gè)體仍是可行解，本文只對(duì)工序號(hào)進(jìn)行交叉操作，而保存交叉前的機(jī)床號(hào)和工人號(hào).

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

（1）隨機(jī)選取幾個(gè)工件放入集合s1，剩余的工件放入集合s2；

（2）令循環(huán)次數(shù)k=0；

（3）檢查父染色體parent1工序鏈的第k個(gè)工序，如該工序?qū)儆诩蟬1，則進(jìn)入子染色體offspring1.同樣，檢查父染色體parent2工序鏈的第k個(gè)工序，如該工序?qū)儆诩蟬2，則進(jìn)入子染色體offspring1；

（4）k=k+1，如k小于染色體的長(zhǎng)度，重復(fù)（3），否則進(jìn)行步驟（5）；

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

3.3.2 變異操作

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

（1）加工順序變異

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

（2）加工機(jī)床和工人變異

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

3.4 實(shí)驗(yàn)仿真

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

用EDD（優(yōu)先選擇最早交貨期的工件）、EODD（優(yōu)先選擇最早交貨期的工序）、FCFS（優(yōu)先選擇服務(wù)先到達(dá)的工序）3種簡(jiǎn)單啟發(fā)式調(diào)度規(guī)則的組合規(guī)則對(duì)此算例進(jìn)行調(diào)度，使用相同的各參數(shù)：工件數(shù)N=4，機(jī)器數(shù)M=10，工人數(shù)W=7，所得的解為64 h.仿真得到的最佳生產(chǎn)周期的調(diào)度結(jié)果如圖3所示.

圖3 啟發(fā)式規(guī)則調(diào)度Gantt圖

4 結(jié)論

智能優(yōu)化算法的發(fā)展和研究對(duì)解決車間調(diào)度問題有重大的意義.合理的優(yōu)化算法對(duì)改進(jìn)車間調(diào)度有很大的幫助，不僅能夠提高人與機(jī)器配合的效率，還能有效提高機(jī)器的利用率，從而為企業(yè)帶來更大的利益.

車間調(diào)度問題是對(duì)于生產(chǎn)環(huán)境中復(fù)雜的、動(dòng)態(tài)的多目標(biāo)的一種抽象和簡(jiǎn)化.在對(duì)調(diào)度問題進(jìn)行研究的方法上最初是集中在整數(shù)規(guī)劃、仿真和簡(jiǎn)單的規(guī)則上，這些方法不是調(diào)度不理想就是難以解決復(fù)雜的問題.因此，隨著各種新的相關(guān)科學(xué)與優(yōu)化技術(shù)的建立與發(fā)展，在調(diào)度問題上也出現(xiàn)了很大的進(jìn)展.并且，以柔性車間調(diào)度問題為例，顯示了遺傳算法在解決受工人和機(jī)器雙資源約束的柔性車間調(diào)度問題上的魯棒性.

對(duì)車間調(diào)度問題的研究雖有幾十年的歷史，但至今尚未形成一套系統(tǒng)的方法和理論，理論研究與實(shí)際應(yīng)用之間還存在著很大差距.今后研究者可從以下幾個(gè)方面進(jìn)行深入的研究.進(jìn)一步深入實(shí)際，找出車間管理與調(diào)度諸多因素的內(nèi)部關(guān)系，建立最能反映生產(chǎn)需要的調(diào)度模型.進(jìn)一步研究車間計(jì)劃與車間調(diào)度之間的關(guān)系，建立計(jì)劃與調(diào)度的集成模型，從整體上進(jìn)行優(yōu)化研究.進(jìn)一步研究先進(jìn)制造系統(tǒng)模式，探索快速實(shí)用的智能調(diào)度算法.總之，隨著調(diào)度研究的深入，調(diào)度算法必然會(huì)進(jìn)一步與生產(chǎn)實(shí)踐相結(jié)合，向集成化、動(dòng)態(tài)化、高效化、實(shí)用化、智能化的方向發(fā)展.