楊煜俊，龍傳澤，陶 宇

（廣東工業(yè)大學(xué) 廣東省計(jì)算機(jī)集成制造重點(diǎn)實(shí)驗(yàn)室，廣東 廣州 510006）

1 問題的提出

隨著計(jì)算機(jī)集成制造技術(shù)的快速發(fā)展，傳統(tǒng)的制造業(yè)發(fā)生了重大而深刻的變革。社會(huì)的發(fā)展使人工成本越來越昂貴，為了應(yīng)對市場環(huán)境的變化，企業(yè)開始大量采用工業(yè)機(jī)器人與自動(dòng)化技術(shù)提高生產(chǎn)效率、降低人工成本。搬運(yùn)機(jī)器人是工業(yè)機(jī)器人的一種，它能靈活快速地實(shí)現(xiàn)物體的轉(zhuǎn)運(yùn)，因而被廣泛應(yīng)用于制造業(yè)。機(jī)器人制造單元是由搬運(yùn)機(jī)器人、機(jī)床、搬運(yùn)導(dǎo)軌等硬件和控制軟件組成的新型智能制造系統(tǒng)（如圖1），它能顯著提高生產(chǎn)效率。近年來智能柔性制造單元也成為學(xué)術(shù)研究和工業(yè)應(yīng)用的熱點(diǎn)，特別是單元調(diào)度問題。目前，國內(nèi)外大多相關(guān)研究集中在制造單元流水車間類型調(diào)度問題［1-2］，文獻(xiàn)［3］研究了帶搬運(yùn)約束的流水車間作業(yè)調(diào)度問題，文獻(xiàn)［4］使用一種新的編碼方法設(shè)計(jì)了兩種解決經(jīng)典作業(yè)車間調(diào)度問題的粒子群算法，該方法在求解傳統(tǒng)作業(yè)車間調(diào)度問題上有較好的效果，但沒有考慮搬運(yùn)時(shí)間。文獻(xiàn)［5］構(gòu)造了一個(gè)新的領(lǐng)域結(jié)構(gòu)，使用改進(jìn)禁忌搜索算法解決帶單臺(tái)搬運(yùn)機(jī)器人的作業(yè)車間調(diào)度問題，但沒有擴(kuò)展考慮帶多臺(tái)搬運(yùn)機(jī)器人情況下搬運(yùn)任務(wù)的分配，在較大規(guī)模的制造單元內(nèi)往往有多臺(tái)搬運(yùn)設(shè)備，而任務(wù)的分配策略將影響制造單元的生產(chǎn)效率。文獻(xiàn)［6］探討了使用混合整數(shù)線性規(guī)劃方法來解決含自動(dòng)導(dǎo)向小車（Automated Guided Vehicle，AGV）的柔性制造系統(tǒng)（Flexible Manufacturing System，F(xiàn)MS）調(diào)度問題，這種整數(shù)規(guī)劃方法只能解決較小規(guī)模的作業(yè)車間調(diào)度問題。文獻(xiàn)［7-8］研究了考慮單元布局影響的三臺(tái)機(jī)床組成的柔性制造單元純周期時(shí)間優(yōu)化調(diào)度問題，該方法局限于由三臺(tái)機(jī)床與一臺(tái)搬運(yùn)設(shè)備組成的制造單元。文獻(xiàn)［9］用遺傳算法解決了帶單臺(tái)搬運(yùn)機(jī)器人、有限緩存區(qū)的作業(yè)車間制造單元調(diào)度問題，但傳統(tǒng)的遺傳算法收斂速度慢、局部搜索能力差，難以在有限時(shí)間內(nèi)找到全局最優(yōu)解。文獻(xiàn)［10］提出一種并行策略來提高優(yōu)化效率，按照順序和倒序規(guī)則構(gòu)建兩個(gè)初始解，使用并行禁忌搜索算法求解單臺(tái)機(jī)器人制造單元調(diào)度問題，但禁忌搜索算法對初始解的要求較高，單一的局部搜索算法很難跳出局部最優(yōu)解。西北工業(yè)大學(xué)車阿大教授課題組主要針對流水車間調(diào)度問題，對機(jī)器人制造單元調(diào)度模型與算法進(jìn)行了深入研究［11-12］。

總體來看，國內(nèi)外學(xué)者大多的研究集中在經(jīng)典的流水車間和作業(yè)車間問題上，這類研究大部分建立在不考慮搬運(yùn)時(shí)間的假設(shè)基礎(chǔ)上，只有少數(shù)研究考慮了搬運(yùn)時(shí)間，但也只考慮了單臺(tái)搬運(yùn)設(shè)備的情況。為此，本文將重點(diǎn)研究考慮搬運(yùn)時(shí)間的作業(yè)車間多機(jī)器人制造單元調(diào)度問題。

2 問題描述

作業(yè)車間多機(jī)器人制造單元的調(diào)度問題可描述為：n個(gè)加工工件J=｛J1，…，Jn｝在m臺(tái)機(jī)床M=｛M1，…，Mm｝上加工。有r臺(tái)搬運(yùn)機(jī)器人R=｛R1，…，Rr｝為加工工件在機(jī)床間提供搬運(yùn)。滿足以下約束條件：

（1）每個(gè)加工工件Ji有ni道加工工序，用Oi1，Oi2，…，Oin表示，每道加工工序的加工時(shí)間已知且只能在指定的機(jī)床上加工，每個(gè)工件在每臺(tái)機(jī)床上只加工一次。

（2）每臺(tái)機(jī)床同一時(shí)間只能加工一個(gè)工件，每臺(tái)機(jī)器人同一時(shí)間只能搬運(yùn)一個(gè)工件。

（3）如果工序Oij與工序Oij+1不在同一臺(tái)機(jī)床上加工，則當(dāng)工序Oij加工完成時(shí)，在執(zhí)行下一道工序Oij+1之前，必須由指定的一臺(tái)機(jī)器人完成搬運(yùn)工序，機(jī)器人搬運(yùn)時(shí)間與機(jī)床間距離成正比。

（5）開始調(diào)度時(shí)，每個(gè)工件都處于其第一道加工工序機(jī)床的輸入緩存區(qū)。

另外，假設(shè)機(jī)床的輸入輸出緩存區(qū)的負(fù)載能力是無限的。即：

（1）機(jī)床的輸入緩存區(qū)有足夠多的位置存放機(jī)器人搬運(yùn)過來的待加工工件。

（2）機(jī)床的輸出緩存區(qū)有足夠多的位置存放加工完成后待搬運(yùn)的工件。

（3）工件在輸入緩存區(qū)、加工工位、輸出緩存區(qū)之間的切換自動(dòng)完成，且不考慮其切換時(shí)間。

本問題目標(biāo)是求解一個(gè)可行的調(diào)度方案，使最大完工時(shí)間最小，目標(biāo)函數(shù)可表示為Cmax=min｝，其數(shù)學(xué)模型表示如下：

其中：

式（1）為目標(biāo)函數(shù)，Cik為工件Ji的最后一道工序在機(jī)床Mk的完工時(shí)間；

式（2）表示在同一臺(tái)機(jī)床上加工的工件的時(shí)間約束，Pjk為工件Jj在機(jī)床Mk上加工的一道工序的加工時(shí)間，Cjk為工件Jj在機(jī)床Mk上的完工時(shí)間，A為一個(gè)足夠大的整數(shù)；

式（3）表示同一個(gè)工件不同工序的加工時(shí)間約束，Cik為工件Ji在機(jī)床Mk上的加工完成時(shí)間；

3 析取圖模型

作業(yè)車間多機(jī)器人制造單元調(diào)度問題析取圖模型可以用公式G=（VM∪Vr，E∪DM∪DR）表示。其中：VM為加工工序節(jié)點(diǎn)集合（包括0和＊兩個(gè)虛節(jié)點(diǎn)）；VR為機(jī)器人搬運(yùn)工序TRrij的集合；E為工件的加工工序約束；DM為機(jī)床的析取弧集合，DR為搬運(yùn)機(jī)器人的析取弧集合。機(jī)床與機(jī)器人的所有析取弧都確定方向后組成完全選集S=SM∪SR，其中：SM為機(jī)床選集，SR為機(jī)器人選集。完全選集S可通過三個(gè)向量MS，TS和RA表示。

機(jī)床選集SM用向量MS表示，一個(gè)工件Jj有nj道加工工序，因此MS包含nj次工件號j。MS中第一次出現(xiàn)的工件號j代表工件Jj的第一道加工工序Oj1，下一次出現(xiàn)的工件號代表工件Jj的第二道加工工序Oj2，以此類推。加工工序在向量MS中的位置代表該工序的加工順序。MS可以充分確定機(jī)床上工件的加工順序，因此MS可以充分代表機(jī)床選集SM。

機(jī)器人搬運(yùn)選集SR由加工工件號重復(fù)排列組成的向量TS確定。工件加工完后搬運(yùn)至卸載站的時(shí)間不考慮，加工工件Jj有nj-1道搬運(yùn)工序TRrij，因此TS包含nj-1個(gè)數(shù)字j。

RA是由分配給搬運(yùn)工序的機(jī)器人編號重復(fù)組成的向量。向量RA的每個(gè)位與向量TS一一對應(yīng)。TS（i）=j，RA（i）=P表示向量在位置i的工件Jj的搬運(yùn)工序分配給機(jī)器人P。

例如：四個(gè)加工工件、每個(gè)工件四道工序（四臺(tái)機(jī)床）、三臺(tái)搬運(yùn)機(jī)器人組成的4×4×3調(diào)度問題。由上述模型描述可知，本問題有十六道加工工序和十二個(gè)搬運(yùn)工序（不計(jì)搬運(yùn)機(jī)器人空載工序）。加工時(shí)間和加工機(jī)床安排如表1所示。

表1 4×4×3調(diào)度問題描述

圖2 給出了一個(gè)可行調(diào)度方案的三向量MS，TS和RA表示。機(jī)床上工件的加工順序由向量MS定義，根據(jù)向量MS的編碼和表1的描述可知各機(jī)床上工序的加工順序?yàn)椋孩贆C(jī)床1：O12→O42→O33→O23，②機(jī)床2：O41→O21→O13→O34，③機(jī)床3：O11→O31→O22→O43，④機(jī)床4：O32→O44→O14→O24；結(jié)合向量TS和RA可知機(jī)器人的搬運(yùn)順序?yàn)椋孩贆C(jī)器人1：T11→T12→T42→T13，②機(jī)器人2：T31→T32→T22→T23，③機(jī)器人3：T41→T21→T43→T33。該調(diào)度問題對應(yīng)的析取圖和甘特圖如圖3和圖4所示。

圖3中標(biāo)注出了一條從起點(diǎn)0到終點(diǎn)＊、耗時(shí)最長且機(jī)床加工工序間和機(jī)器人搬運(yùn)工序間無時(shí)間間隔的路徑，稱為關(guān)鍵路徑。在這條關(guān)鍵路徑上的加工工序和搬運(yùn)工序稱為關(guān)鍵工序。所有工件中最后一道工序的完工時(shí)間就是該調(diào)度問題的最大完工時(shí)間Cmax，因此關(guān)鍵路徑的長度可以完全決定最大完工時(shí)間Cmax，關(guān)鍵路徑上關(guān)鍵工序的微調(diào)可以改變最大完工時(shí)間Cmax。本文基于關(guān)鍵路徑上的機(jī)床塊和機(jī)器人塊的微調(diào)來構(gòu)造鄰域結(jié)構(gòu)：

（1）在關(guān)鍵路徑上，無時(shí)間間隔相鄰的兩道以上機(jī)床的加工工序組成一個(gè)機(jī)床塊。

（2）在關(guān)鍵路徑上，無時(shí)間間隔（空載時(shí)間不算時(shí)間間隔）相鄰的兩道以上機(jī)器人的搬運(yùn)工序組成一個(gè)機(jī)器人塊。

（3）在關(guān)鍵路徑上，前后沒有相鄰加工工序的獨(dú)立的一道加工工序作為獨(dú)立機(jī)床工序。

（4）在關(guān)鍵路徑上，前后沒有相鄰搬運(yùn)工序的獨(dú)立的一道搬運(yùn)工序作為獨(dú)立機(jī)床工序。

（1）選集S關(guān)鍵路徑Ps上某些機(jī)床塊內(nèi)的某些加工工序的相對位置發(fā)生轉(zhuǎn)變。

（2）選集S關(guān)鍵路徑Ps上某些機(jī)器人塊內(nèi)的兩道搬運(yùn)工序的相對位置發(fā)生轉(zhuǎn)變。

（3）選集S關(guān)鍵路徑Ps上獨(dú)立機(jī)器人工序分配的機(jī)器人發(fā)生變化。

4 算法設(shè)計(jì)

在上述析取圖構(gòu)建的鄰域搜索結(jié)構(gòu)的基礎(chǔ)上，結(jié)合遺傳算法的全局搜索能力，設(shè)計(jì)本調(diào)度問題的算法。

4.1 遺傳算法簡介

遺傳算法是由美國Holland教授首次提出的，之后由其他學(xué)者進(jìn)行了完善和改進(jìn)。遺傳算法是根據(jù)自然界的優(yōu)勝劣汰、適者生存的遺傳機(jī)制演化而來的隨機(jī)搜索算法，其主要特點(diǎn)是能根據(jù)群體中的個(gè)體對環(huán)境的適應(yīng)度自動(dòng)指導(dǎo)搜索方向。良好的全局搜索能力使遺傳算法被廣泛應(yīng)用于組合優(yōu)化、機(jī)器學(xué)習(xí)、車間作業(yè)調(diào)度等領(lǐng)域。應(yīng)用遺傳算法時(shí)首先對種群進(jìn)行初始化；然后對種群個(gè)體的適用度進(jìn)行評價(jià)；最后經(jīng)過選擇、交叉和變異操作，得到下一代群體。

4.2 算法設(shè)計(jì)

根據(jù)上述模型的表述，本調(diào)度問題需要同時(shí)考慮工件的加工順序、機(jī)器人的搬運(yùn)順序和搬運(yùn)工序的分配，比一般的作業(yè)車間調(diào)度問題復(fù)雜很多。針對這類涉及多層調(diào)度的問題，采取分層調(diào)度的方式可以將問題分步簡化，本文采用三層調(diào)度方案：

第一層：機(jī)床加工工序調(diào)度，即不考慮搬運(yùn)工序的情況下，通過調(diào)度算法求得一組使完工時(shí)間最小的加工方案。

第二層：機(jī)器人搬運(yùn)工序調(diào)度，即根據(jù)機(jī)床加工順序，安排機(jī)器人在機(jī)床間的搬運(yùn)順序。

第三層：使用啟發(fā)式規(guī)則將每道搬運(yùn)工序分配給各臺(tái)機(jī)器人，使總完工時(shí)間最小。

4.2.1 個(gè)體編碼

本問題的編碼方式有很多種，其中最直接的是工序編號編碼，這種編碼方式在進(jìn)化過程中容易產(chǎn)生不可行解，因此每一次進(jìn)化都需對個(gè)體編碼進(jìn)行可行性判斷。為保證每個(gè)編碼在遺傳算子操作中的可行性，本文采用重復(fù)的序列編碼方式，在第一層調(diào)度中用基于工序約束的個(gè)體編碼方式，編碼中的每個(gè)基因代表工件號，同一個(gè)工件的所有工序用同一個(gè)工件號表示，相同的工件號出現(xiàn)的先后次序代表該工件的加工工序號。假設(shè)一個(gè)4×4（四個(gè)不同的工件在四臺(tái)不同的機(jī)床上加工）的第一層編碼MS可表示為：4 3 4 2 3 1 2 4 2 3 1 2 1 3 4 1，所代表的加工先后次序?yàn)椋汗ぜ?的第一道工序、工件3的第一道工序、工件4的第二道工序，以此類推。

機(jī)器人的搬運(yùn)工序順序是根據(jù)先完成先搬運(yùn)的啟發(fā)式規(guī)則確定的，即在確定了加工順序的基礎(chǔ)上插入機(jī)器人搬運(yùn)工序，再根據(jù)相鄰搬運(yùn)工序分配給不同機(jī)器人的啟發(fā)式規(guī)則為各臺(tái)機(jī)器人分配搬運(yùn)工序。例如：在確定機(jī)床工序MS：1 3 2 3 2 1 2 1 3后，根據(jù)先完成先搬運(yùn)的規(guī)則可確定機(jī)器人搬運(yùn)順序?yàn)門S：3 1 2 3 1 2，再根據(jù)相鄰搬運(yùn)工序分配給不同機(jī)器人的啟發(fā)式規(guī)則，如果機(jī)器人的數(shù)量為2可得RA：1 2 1 2 1 2，對應(yīng)的搬運(yùn)順序?yàn)椋簷C(jī)器人1搬運(yùn)工件3，機(jī)器人2搬運(yùn)工件1，機(jī)器人1搬運(yùn)工件2，機(jī)器人2搬運(yùn)工件3，機(jī)器人1搬運(yùn)工件1，機(jī)器人2搬運(yùn)工件2。同理如果機(jī)器人數(shù)量為3，則RA：1 2 3 1 2 3。

4.2.2 算子設(shè)計(jì)

遺傳算子的設(shè)計(jì)將影響算法的性能和收斂，重要的遺傳算子有選擇、交叉和變異三種。

（1）適應(yīng)函數(shù)

適用度函數(shù)一般與目標(biāo)函數(shù)直接相關(guān)，可以通過目標(biāo)函數(shù)評估適用度，適用度大的個(gè)體有較大的生存機(jī)會(huì)。作業(yè)車間類型機(jī)器人制造單元的調(diào)度問題以最小化最大完工時(shí)間為目標(biāo)函數(shù)，完工時(shí)間越小，該個(gè)體的適用度越好。因此通過目標(biāo)函數(shù)Cmin的尺度轉(zhuǎn)換確定適用度函數(shù)為：。

（2）選擇操作

遺傳算法根據(jù)個(gè)體對環(huán)境的適用度，通過優(yōu)勝劣汰法則選擇子代，本算法根據(jù)輪盤賭法選擇子代，適用度大的個(gè)體進(jìn)化到下一代的概率大，適用度小的個(gè)體進(jìn)化到下一代的概率相對較小。這種選擇方式既保證了下一代中基因的質(zhì)量，又保證了基因的多樣性。對規(guī)模為N的種群，如果其中個(gè)體i的適應(yīng)度值為fi，則個(gè)體i能進(jìn)化到下一代的概率。

（3）交叉操作

交叉是指兩個(gè)父代染色體的部分基因片斷交叉互換、生成新的子代的操作，是種群內(nèi)部個(gè)體之間的信息交流。本文使用一種新的基于工序編碼操作的交叉方式，它產(chǎn)生的子代能夠很好地繼承父代的優(yōu)良基因，使目標(biāo)值更接近最優(yōu)值。該交叉操作的示意圖如圖5所示，圖中＊為去除指定的標(biāo)號片段，首先選擇父代1染色體中的一個(gè)編號（如圖5中的編號3），將該編號及其位置保持不變并進(jìn)化到子代1中；然后在另一個(gè)父代2中標(biāo)記出該編號，將去除該編號的父代2中的其他編號依次填入子代1中，得到完整的子代1。同理得到子代2。

（4）變異操作

通過一定概率的變異運(yùn)算可以防止算法陷入局部極值，找到全局最優(yōu)值，常用的變異方式有插入變異、交換變異和反序變異。反序變異算子在搜索空間中搜索到的領(lǐng)域聚集度較高，因此在遺傳算中使用反序變異，具體操作如圖6所示。

4.2.3 局部搜索

局部搜索算法搜索鄰域通過關(guān)鍵路徑Ps構(gòu)建，根據(jù)關(guān)鍵路徑上的搬運(yùn)工序或加工工序是否連續(xù)，將關(guān)鍵路徑上的工序分為四種片段類型：機(jī)床塊Bm、機(jī)器人塊Br、獨(dú)立機(jī)器人工序Ir、獨(dú)立機(jī)床工序Im。針對不同的類型片段采用不同的操作方法來構(gòu)建鄰域：

（1）機(jī)床塊Bm內(nèi)移動(dòng) 移動(dòng)機(jī)床塊Bm內(nèi)加工工序的相對位置，機(jī)床塊內(nèi)非第一道加工工序移動(dòng)到所有加工工序之前加工（改變向量MS）。

（2）機(jī)器人塊Br內(nèi)互換 機(jī)器人塊Br位置的i（1≤i≤｜Br｜-1）的搬運(yùn)工序分別與其后面某位置的j（i≤j≤｜Br｜）搬運(yùn)工序互換位置（改變向量TS）。

（3）獨(dú)立機(jī)器人工序重分配 將該道搬運(yùn)工序分配給另一臺(tái)機(jī)器人（改變向量RA）。

（4）獨(dú)立機(jī)床工序不變 工序位置保持不變。

這種領(lǐng)域搜索方式將遺傳算法的個(gè)體編碼作為局部搜索的初始解，通過調(diào)整關(guān)鍵路徑上的工序來更新向量MS、TS和RA，大大縮小了搜索空間，提高了效率。局部搜索算法流程圖如圖7所示。

4.3 算法流程

將遺傳算法與局部搜索算法相結(jié)合，得到作業(yè)車間多機(jī)器人制造單元調(diào)度問題的混合遺傳算法流程，如圖8所示。

5 算例分析

引入OR-Library 上40 個(gè)不同規(guī)模的FT、LA、ABZ、ORB 系列基 準(zhǔn)算例 和文獻(xiàn)［17］中 的Philippe算例，加入機(jī)器人搬運(yùn)工序，假設(shè)機(jī)器人在機(jī)床間的空載移動(dòng)時(shí)間為1，機(jī)器人對每道工序的搬運(yùn)時(shí)間按TRij=D（i-j）計(jì)算，其中：i-j為機(jī)床間的距離，D為距離系數(shù)，R為搬運(yùn)機(jī)器人數(shù)量。遺傳算法的參數(shù)選定為：種群規(guī)模60、最大迭代次1 000、代溝0.8、交叉率0.7、變異率0.09。在MATLAB R2010 軟件下運(yùn)行，系統(tǒng)運(yùn)行環(huán)境為Window 7 2.5GHz／4G RAM PC。分別使用本文提出的混合遺傳算法與傳統(tǒng)遺傳算法在不同的參數(shù)下對各個(gè)算例進(jìn)行仿真，每個(gè)算例分別運(yùn)行10次，對實(shí)驗(yàn)結(jié)果進(jìn)行統(tǒng)計(jì)，結(jié)果如表2所示。

混合遺傳算法與傳統(tǒng)遺傳算法的平均收斂代數(shù)與平均收斂時(shí)間對比如圖9和圖10所示，當(dāng)D=3、R=2時(shí)兩種算法求得的最優(yōu)值對比如圖11所示。由此可知，將鄰域搜索算法與遺傳算法相結(jié)合組成混合算法，雖然增加了單代的運(yùn)算時(shí)間，但混合算法的收斂速度明顯快于傳統(tǒng)遺傳算法，因此混合算法不管是從運(yùn)算時(shí)間還是從運(yùn)算結(jié)果上看，都優(yōu)于傳統(tǒng)遺傳算法。

表2 FT、LA、ABZ、ORB系列算例實(shí)驗(yàn)結(jié)果

續(xù)表2

在表2中，不考慮搬運(yùn)時(shí)間即D=0時(shí)，混合遺傳算法對82.9%的算例都求得了已知的最優(yōu)解，其余17.1%也求得了近似最優(yōu)解?？紤]搬運(yùn)時(shí)間即D≠0 的可參考算例很少，將本算法的實(shí)驗(yàn)結(jié)果與文獻(xiàn)［17］中Philippe提出的算例結(jié)果進(jìn)行對比，結(jié)果如表3所示，通過對比可知，本算法優(yōu)于Philippe提出的算法。

在表3中，當(dāng)距離系數(shù)D相同時(shí)，隨著搬運(yùn)機(jī)器人的數(shù)量從1增加到3，最大完工時(shí)間逐漸減小，當(dāng)D=3時(shí)，最大完工時(shí)間平均減小13.0%。由此可知，通過增加搬運(yùn)機(jī)器人的方式，可以提高作業(yè)車間機(jī)器人制造單元的生產(chǎn)效率，且搬運(yùn)時(shí)間越長，效果越明顯。

表3 Philippe算例對比

單獨(dú)對作業(yè)車間知名算例FT06 進(jìn)行深入分析，距離系數(shù)D分別取1，3，5，機(jī)器人數(shù)量R從1遞增到5，實(shí)驗(yàn)結(jié)果如表4 所示。當(dāng)D=1 和D=2時(shí)，搬運(yùn)機(jī)器人數(shù)量達(dá)到3后，即使再增加搬運(yùn)機(jī)器人求得的最優(yōu)值也不變；當(dāng)D=3，搬運(yùn)機(jī)器人數(shù)量達(dá)到4后，即使再增加機(jī)器人求得的最優(yōu)值也不變。這種情況表明機(jī)器人數(shù)量處于“飽和狀態(tài)”，再增加機(jī)器人只會(huì)增加成本，而無法提高生產(chǎn)效率。

表4 FT06算例

續(xù)表4

6 結(jié)束語

本文建立了作業(yè)車間多機(jī)器人制造單元的數(shù)學(xué)優(yōu)化模型和析取圖模型，用帶局部鄰域搜索策略和啟發(fā)式任務(wù)分配規(guī)則的混合遺傳算法對問題進(jìn)行求解。通過OR-Library上40個(gè)不同規(guī)模的FT、LA、ABZ、ORB系列基準(zhǔn)算例及Philippe算例對混合遺傳算法進(jìn)行了驗(yàn)證，實(shí)驗(yàn)結(jié)果證實(shí)了混合遺傳算法從運(yùn)算時(shí)間和運(yùn)算結(jié)果上都優(yōu)于傳統(tǒng)遺傳算法和Philippe算法。通過實(shí)驗(yàn)數(shù)據(jù)分析得出結(jié)論：當(dāng)搬運(yùn)時(shí)間相對于加工時(shí)間很小時(shí)，搬運(yùn)工序?qū)ψ畲笸旯r(shí)間幾乎無影響；當(dāng)搬運(yùn)時(shí)間較大時(shí)，將顯著增加完工時(shí)間，增加搬運(yùn)機(jī)器人數(shù)量可以提高作業(yè)車間機(jī)器人制造單元的生產(chǎn)效率，且搬運(yùn)時(shí)間越長，效果越明顯。未來工作中將對考慮機(jī)器柔性、工序柔性的機(jī)器人制造單元調(diào)度問題進(jìn)行研究。

［1］DAWANDE M W，GEISMAR H N，SETHI S P，et al.Sequencing and scheduling in robotic cells：recent developments［J］.Journal of Scheduling，2005，8（5）：387-426.

［2］DAWANDE M W，GEISMAR H N，SETHI S P，et al.Throughput optimization in robotic cells［M］.Berlin，Germany：Springer-Verlag，2007：1-413.

［3］HURINK J，KNUST S.A fast tabu search algorithm for the job shop problem［J］.Management Science，1996，42（6）：797-813.

［4］HURINK J，KNUST S.Makespan minimization for flop-shop problems with transport time［J］.Discrete Applied Mathematics，2001，112（3）：199-216.

［5］HURINK J，KNUST S.Tabu search algorithms for Job-Shop problems with a single transport robot［J］.European Journal of Operational Research，2005，162（1）：99-111.

［6］CAUMOND A，LACOMME P，MOUKRIM A，TCHERNEV N.An MILP for scheduling problem in an FMS with one vehicle［J］.European Journal of Operational Research，2009，199（3）：706-722.

［7］GULTEKIN H，KARASAN O E，AKYURK M S.Pure cycles in flexible robotic cells［J］.Computers &Operations Re-search，2009，36（2）：329-343.

［8］GULTEKIN H，AKTURK M S，KARASAN O E.Scheduling in a three-machine robotic flexible manufacturing cell［J］.Computers &Operations Research，2007，34（8）：2463-2477.

［9］LACOMME P，TCHERNEV N.Resolution of a job-shop problem with a single transport robot and buffer facilities［C］／／Proceedings of 2006International Conference on Service Systems and Service Management.Washington，D.C.，USA：IEEE，2006，2：1108-1113.

［10］HE Zhizhou，YANG Yujun，CHEN Xindu.Parallel tabu search scheduling algorithm for job-shop with transport robot［J］.Industrial Engineering Journal，2013，16（4）：122-125（in Chinese）.［何之洲，楊煜俊，陳新度.帶搬運(yùn)機(jī)器人的Job-Shop問題的并行禁忌搜索算法［J］.工業(yè)工程，2013，16（4）：122-125.］

［11］YAN Pengyu，CHE Ada，LI Peng，YANG Naiding.Scheduling model and its algorithm for no-wait robotic cell with mul-tiple robots［J］.Computer Intergrated Manufacturing Systems，2010，16（2）：404-410（in Chinese）.［晏鵬宇，車阿大，李鵬，楊乃定.具有柔性加工時(shí)間的機(jī)器人制造單元調(diào)度問題改進(jìn)遺傳算法［J］.計(jì)算機(jī)集成制造系統(tǒng)，2010，16（2）：404-410.］

［12］CHE Ada，WANG Yuan.Scheduling model and its algorithm for no-wait robotic cell with multiple robots［J］.Computer Intergrated Manufacturing Systems，2008，14（3）：525-534（in Chinese）.［車阿大，王 遠(yuǎn).無等待多機(jī)器人制造單元調(diào)度模型和算法研究［J］.計(jì)算機(jī)集成制造系統(tǒng)，2008，14（3）：525-534.］

［13］LACOMME P，LARABI M.A disjunctive graph for the jobshop with several robots［EB／OL］.［2014-10-26］.http：／／www.mistaconference.org／2007／papers／A%20Disjunctive%20Graph% 20for% 20the% 20Job% 20Shop% 20with%20Several%20Robots.pdf.