李曉輝,楊 晰,趙 毅

(長(zhǎng)安大學(xué) 電子與控制工程學(xué)院,西安 710064)

隨著制造業(yè)自動(dòng)化、信息化、智能化地發(fā)展,工業(yè)機(jī)器人的應(yīng)用越來(lái)越廣泛.為了應(yīng)對(duì)市場(chǎng)環(huán)境的變化,企業(yè)生產(chǎn)車(chē)間開(kāi)始大量采用搬運(yùn)機(jī)器人與自動(dòng)化技術(shù)提高生產(chǎn)效率、降低人工成本.隨著時(shí)代的變遷,用戶(hù)的需求也從“批量化”逐漸走向了“小型化”、“定制化”,生產(chǎn)排成系統(tǒng)作為制造業(yè)的核心,作業(yè)車(chē)間更適合當(dāng)前的工業(yè)制造加工廠.作業(yè)車(chē)間調(diào)度問(wèn)題是一個(gè)典型的NP 難優(yōu)化問(wèn)題,通常可以描述為:生產(chǎn)車(chē)間內(nèi)有N個(gè)加工工件,M臺(tái)加工機(jī)器,每個(gè)工件都有特定的若干加工工序.調(diào)度的目標(biāo)是將工件合理地安排到各個(gè)加工機(jī)器以及合理地使用其它生產(chǎn)資源,并合理地安排工件加工順序與工件加工時(shí)間,使約束條件被滿(mǎn)足,同時(shí)優(yōu)化一些生產(chǎn)性能指標(biāo).因此帶有機(jī)器人制造單元的作業(yè)車(chē)間優(yōu)化問(wèn)題更有現(xiàn)實(shí)意義與應(yīng)用價(jià)值,所以如何找到可以達(dá)成生產(chǎn)目標(biāo)的最優(yōu)解是研究的中心.

作業(yè)車(chē)間調(diào)度問(wèn)題普遍的的優(yōu)化目標(biāo)是最小化完工時(shí)間,即在滿(mǎn)足相應(yīng)約束的前提下優(yōu)化加工周期(Makespan).然而實(shí)際生產(chǎn)過(guò)程中,由于不確定性,特別是帶有存貨的加工單元,要求工件的完工時(shí)間在一個(gè)時(shí)間窗內(nèi),而不是一個(gè)特定的時(shí)間點(diǎn),因此針對(duì)此情況的作業(yè)車(chē)間,優(yōu)化目標(biāo)為最小化提前量與延遲量的總權(quán)重.

目前,求解作業(yè)車(chē)間調(diào)度優(yōu)化問(wèn)題的主要方法是使用精確算法和近似算法.Caumond 等[1]研究的帶有搬運(yùn)小車(chē)的柔性作業(yè)車(chē)間調(diào)度問(wèn)題,提出了一個(gè)混合整數(shù)線性規(guī)劃的解決方法來(lái)是最小化完工時(shí)間.張曉玲等[2]提出用正交實(shí)驗(yàn)的方法來(lái)設(shè)置蟻群算法在求解車(chē)間調(diào)度問(wèn)題的參數(shù).根據(jù)對(duì)參數(shù)的設(shè)置,調(diào)節(jié)蟻群算法的收斂速度并且得到不同的解.杜兆龍等[3]根據(jù)柔性車(chē)間調(diào)度問(wèn)題提出基于解空間距離聚類(lèi)和變鄰域搜索的粒子群算法.調(diào)整關(guān)鍵路徑上最大關(guān)鍵工序的機(jī)器位置來(lái)加強(qiáng)局部搜索能力;并根據(jù)機(jī)器加工工序的空間距離,采用K-means 聚類(lèi)得到機(jī)器加工工序“優(yōu)良個(gè)體”,加大局部搜索性能.晏鵬宇等[4]為克服傳統(tǒng)遺傳算法在求解具有柔性加工時(shí)間的機(jī)器人制造單元調(diào)度問(wèn)題時(shí),易出現(xiàn)早熟熟練、冗余迭代等缺陷,提出了改進(jìn)遺傳算法.李宏芳等[5]為了解決車(chē)間作業(yè)調(diào)度效率低的難題,提出了一種粒子群算法的車(chē)間作業(yè)調(diào)度方法.該方法將每個(gè)粒子代表一種作業(yè)調(diào)度方案,以最小化加工時(shí)間作為算法的優(yōu)化目標(biāo),通過(guò)粒子群之間的協(xié)作來(lái)獲得最優(yōu)作業(yè)調(diào)度方案.劉瑩等[6]針對(duì)置換流水線車(chē)間調(diào)度問(wèn)題進(jìn)行綜述,并詳細(xì)地對(duì)比各種算法.龍傳澤[7]對(duì)帶有機(jī)器柔性的作業(yè)車(chē)間類(lèi)型多機(jī)器人制造單元調(diào)度問(wèn)題,提出了一種改進(jìn)離散粒子群算法,設(shè)計(jì)了算法的分段編碼方法與兩種啟發(fā)式初始化方法,并設(shè)計(jì)了粒子的局部搜索算法,通過(guò)算例結(jié)果分析驗(yàn)證了算法的有效性.申麗娟等[8]為提高車(chē)間作業(yè)優(yōu)化調(diào)度的效率,采用基于輪盤(pán)賭的方式對(duì)粒子進(jìn)行編碼,運(yùn)用混沌思想對(duì)粒子群基本參數(shù)進(jìn)行混沌優(yōu),加入變異操作以提高種群的多樣性,設(shè)計(jì)了一種模擬退火算法的混合粒子群優(yōu)化算法.近年來(lái),隨著智能優(yōu)化算法的發(fā)展,來(lái)越多的算法與作業(yè)車(chē)間調(diào)度優(yōu)化問(wèn)題相結(jié)合在一起,例如:蟻群算法[9]、改進(jìn)粒子群算法[10]、基因算法[11]等,不僅得出了有效的結(jié)果,還展現(xiàn)出了近似算法的優(yōu)異之處.

本文提出一種改進(jìn)的元啟發(fā)式算法,將文化基因算法與一種強(qiáng)大的鄰域搜索技術(shù)(變鄰域下降搜索)結(jié)合.文化基因算法是一個(gè)將傳統(tǒng)全局搜算算法與局部搜索算法結(jié)合在一起的算法框架,在之前研究基礎(chǔ)[12]上,將遺傳算法與變鄰域下降搜索相組合,在變鄰域下降搜索中進(jìn)一步融合多樣的鄰域搜索結(jié)構(gòu),在加快文化基因算法收斂性的同時(shí)又避免陷入局部最優(yōu).最后對(duì)帶有機(jī)器人制造單元的作業(yè)車(chē)間調(diào)度問(wèn)題進(jìn)行仿真實(shí)驗(yàn),結(jié)果表明了該算法的有效性.

1 問(wèn)題描述

N個(gè)工件在M臺(tái)機(jī)器上進(jìn)行加工,每個(gè)工件有特定的加工工序及順序,并且每個(gè)工件各工序在機(jī)器上的加工時(shí)間已知.帶有機(jī)器人制造單元的作業(yè)車(chē)間調(diào)度系統(tǒng)由加工站、機(jī)器人和引導(dǎo)網(wǎng)絡(luò)(guidance network)3 個(gè)主要部分組成.機(jī)器人將工件從裝卸載站搬運(yùn)至各個(gè)加工機(jī)器,所有工件通過(guò)裝卸載站進(jìn)出系統(tǒng).加工站由加工機(jī)器、輸入緩沖區(qū)和輸出緩沖區(qū)3 部分組成.基本流程如下:工件j從裝載站出發(fā),由機(jī)器人搬運(yùn)至其第一道加工工序所在的加工機(jī)器Mj上進(jìn)行加工,加工完后由機(jī)器人再將其搬運(yùn)至下道工序所在的機(jī)器上,直至加工完工件j的所有工序,由機(jī)器人搬運(yùn)至卸載站完成.每個(gè)工件j預(yù)計(jì)在時(shí)間間隔[aj,bj]之間完成,其中aj和bj分別代表最早的到期日和最晚的到期日.要求確定給定各工件在各機(jī)器上的加工順序及機(jī)器人在各站之間的搬運(yùn)順序,使某些加工性能指標(biāo)達(dá)到最優(yōu).

一般作業(yè)車(chē)間調(diào)度問(wèn)題需要考慮如下約束條件:

1)所有機(jī)器在t= 0 時(shí)刻都可用,所有工件在t=0 時(shí)刻都可被加工;

2)每道工序必須在指定的機(jī)器上加工,且必須在其前一道工序加工完成后才能開(kāi)始加工;

3)某一時(shí)刻,一臺(tái)機(jī)器只能加工一個(gè)工件,每個(gè)工序在加工期間不能中途停止;

4)只有一個(gè)搬運(yùn)機(jī)器人(同一時(shí)刻,機(jī)器人只能搬運(yùn)一個(gè)工件);

5)一個(gè)工件在加工過(guò)程中采取平行移動(dòng)方式,轉(zhuǎn)移時(shí)間忽略不計(jì)或計(jì)入加工時(shí)間;

6)機(jī)器人只能在輸入輸出緩沖區(qū)進(jìn)行裝卸載.

針對(duì)帶有機(jī)器人制造單元的作業(yè)車(chē)間調(diào)度問(wèn)題,目標(biāo)是找到一個(gè)最優(yōu)的機(jī)器人搬運(yùn)順序,此順序可以最小化工件完工提前量和延遲量的總權(quán)重.參考使用文獻(xiàn)[1]中的問(wèn)題模型,改變其目標(biāo)值并加入時(shí)間窗約束.

本文中的目標(biāo)函數(shù)為最小化工件完工提前量和延遲量的總權(quán)重,可以用下列數(shù)學(xué)公式表示:

其中,α和β分別代表總提前量與總延遲量的權(quán)重.

時(shí)間窗約束的數(shù)學(xué)公式如下:

其中,Ej和Tj分別代表工件j的提前量與延遲量.Cj是工件j的完工時(shí)間.

2 文化基因算法

文化基因算法是一種基于種群的全局搜索和基于個(gè)體的局部啟發(fā)式搜索的結(jié)合體.它是一個(gè)框架,在這個(gè)框架下,采用不同的搜索策略可以構(gòu)成不同的文化基因算法.本文提出的元啟發(fā)式算法以遺傳算法為基礎(chǔ)進(jìn)行全局搜索,結(jié)合變鄰域下降搜索進(jìn)行局部搜索.融合多樣的鄰域結(jié)構(gòu)加速整個(gè)算法的收斂性,并且避免其陷入局部最優(yōu).

2.1 解的表示

在設(shè)計(jì)元啟發(fā)式方法時(shí),最重要的決策之一是如何表示解,并且以一種有效的方式將它們與搜索空間聯(lián)系起來(lái).用一個(gè)(nk×2)的矩陣表示染色體,其中nk是每個(gè)工件的總工序數(shù),每個(gè)工件號(hào)在排列中出現(xiàn)m次.按照從左到右的排列順序,工件號(hào)出現(xiàn)的第k次就代表這個(gè)工件的第k個(gè)加工工序.例如,個(gè)體[3 1 2 2 3 1 1 2 3],每個(gè)工件有3 個(gè)加工工序.在這個(gè)例子中,個(gè)體的第5 個(gè)位置是“3”,代表工件3,“32”表示工件3 的第2 個(gè)加工工序,因?yàn)閿?shù)字3 出現(xiàn)了2 次.如果將工件號(hào)重復(fù)出現(xiàn)的次數(shù)作為該工件的加工工序數(shù),這個(gè)方法總是可行的.

2.2 全局搜索

本文提出的元啟發(fā)式算法以遺傳算法為基礎(chǔ)進(jìn)行全局搜索,遺傳算法是一類(lèi)借鑒生物界的進(jìn)化規(guī)律(適者生存,優(yōu)勝劣汰遺傳機(jī)制)演化而來(lái)的隨機(jī)化搜索方法.其主要包含3 部分:選擇,交叉,變異.首先,所有初始解都是隨機(jī)生成的,然后計(jì)算它們的適應(yīng)度值.在生成過(guò)程中,選擇、交叉和變異被用于生成新的個(gè)體.以下是各操作的簡(jiǎn)單描述:

選擇操作采用輪盤(pán)賭選擇法來(lái)選擇兩個(gè)個(gè)體作為雙親,這是遺傳算法和進(jìn)化算法等算法中常用的一種選擇方法.

交叉操作采用PTL 交叉技術(shù)[13],此交叉方法即使在兩個(gè)相同雙親的情況下,依然可以產(chǎn)生一對(duì)不同的子代.在PTL 交叉中,在第一個(gè)父代中隨機(jī)產(chǎn)生兩個(gè)切割點(diǎn)產(chǎn)生一個(gè)工件序列塊,將此塊移動(dòng)到子代排列的右角或左角,然后將工件序列塊中出現(xiàn)的數(shù)字從第二個(gè)父代中刪去,將其剩余的工件操作數(shù)填充道子代中.交叉操作完成后,需要對(duì)工序的排列進(jìn)行修復(fù)來(lái)恢復(fù)新的工件加工順序.

變異操作在種群中引入了一些額外的變異性,可用來(lái)增強(qiáng)種群的多樣性.文中使用轉(zhuǎn)置變異操作:隨機(jī)產(chǎn)生兩個(gè)位置,將兩個(gè)位置中間的操作序列倒置排列,產(chǎn)生新的加工序列,并在之后修復(fù)工件的加工工序.通過(guò)迭代求解,完成遺傳算法,選擇最優(yōu)解進(jìn)入局部搜索.

2.3 變鄰域下降搜索

局部搜索可以加快算法的收斂性,本文使用變鄰域下降搜索技術(shù)進(jìn)行局部搜索.其基本思想是在搜索過(guò)程中系統(tǒng)地改變鄰域結(jié)構(gòu)集來(lái)拓展搜索范圍,獲得局部最優(yōu)解,再基于此局部最優(yōu)解重新系統(tǒng)地改變鄰域結(jié)構(gòu)集拓展搜索范圍找到另一個(gè)局部最優(yōu)解的過(guò)程.在前期的研究基礎(chǔ)上[12],本文提出3 個(gè)鄰域結(jié)構(gòu),分別是:段插入鄰域結(jié)構(gòu),節(jié)點(diǎn)插入鄰域結(jié)構(gòu)和根據(jù)延遲量與提前量交換工序的變換鄰域結(jié)構(gòu).從上述具有相同概率的鄰域結(jié)構(gòu)中隨機(jī)選擇一個(gè)進(jìn)行局部搜索并更新.其中,段插入:在解中隨機(jī)產(chǎn)生兩個(gè)位置,將兩個(gè)位置間的工序數(shù)隨機(jī)插入某個(gè)工序之后.節(jié)點(diǎn)插入:在解中隨機(jī)產(chǎn)生一個(gè)位置,將此位置的工序數(shù)隨機(jī)插入某個(gè)工序之后.第三種鄰域結(jié)構(gòu)帶有一定導(dǎo)向性,是根據(jù)延遲量與提前量交換工序的鄰域結(jié)構(gòu):在這個(gè)方法中,將工件劃分為兩組.第一組為在到期時(shí)間窗之前完成的工件,第二組則是在到期時(shí)間窗之后完成的工件.對(duì)于各個(gè)加工機(jī)器上的所有加工工序,屬于第一組工件的操作移到完成時(shí)間窗右邊的位置,屬于第二組工件的則移到左遍的位置.更具體地說(shuō),如果同一臺(tái)機(jī)器包含兩個(gè)不同組的工件則被視為一對(duì),而此機(jī)器上這一對(duì)的加工工序的位置將被互換.例如圖1,機(jī)器M1 上有4 個(gè)加工操作,假設(shè)工件3 的完成時(shí)間在要求的完成時(shí)間窗之前,工件2 在完成時(shí)間窗之后,則將工序“22”和“33”的位置進(jìn)行交換.

圖1 鄰域結(jié)構(gòu)示例

原本“33”工序的完成使得工件3 產(chǎn)生提前量,“22”工序使得工件2 產(chǎn)生延遲量,導(dǎo)致工件完工的提前量和延遲量的總權(quán)重過(guò)大.經(jīng)過(guò)位置交換之后,可有效地將工件3 完成時(shí)間延后,使提前量減小,并且使工件2 的完成時(shí)間提前,減小延遲量.此鄰域結(jié)構(gòu)可以有效降低工件完工提前量和延遲量的總權(quán)重,并找到更優(yōu)的加工工序(即局部最優(yōu)解)達(dá)到優(yōu)化目標(biāo)的要求.

2.4 改進(jìn)的元啟發(fā)式算法

改進(jìn)的元啟發(fā)式算法的流程圖如圖2所示,基本步驟可描述如下.

圖2 算法流程圖

Step 1.讀入數(shù)據(jù),初始化解;

Step 2.建立并計(jì)算目標(biāo)函數(shù),初始化種群;

Step 3.進(jìn)入遺傳算法,進(jìn)行選擇、交叉、變異等操作進(jìn)行迭代;

Step 4.迭代完成后求出最優(yōu)個(gè)體進(jìn)入局部搜索;

Step 5.隨機(jī)選擇鄰域結(jié)構(gòu)進(jìn)行更新;

Step 6.判斷產(chǎn)生的新解是否大優(yōu)于原最有個(gè)體的解;是則輸出新個(gè)體,否則繼續(xù)選擇鄰域結(jié)構(gòu)進(jìn)行計(jì)算;

Step 7.輸出最優(yōu)個(gè)體.

3 實(shí)驗(yàn)結(jié)果分析

本文算法以Visual Studio 2017 為開(kāi)發(fā)工具,仿真實(shí)驗(yàn)具體過(guò)程通過(guò)C++語(yǔ)言進(jìn)行編程實(shí)現(xiàn).通過(guò)找到加工工序及機(jī)器人搬運(yùn)序列對(duì)目標(biāo)函數(shù)進(jìn)行計(jì)算,得到工件完工提前量和延遲量的總權(quán)重.再使用四中算法進(jìn)行優(yōu)化,找到最優(yōu)解.選取了16 組實(shí)例數(shù)據(jù)進(jìn)行實(shí)驗(yàn),其中實(shí)例1 至10 文獻(xiàn)[1]中的數(shù)據(jù),實(shí)例11 至16 隨機(jī)生成.每個(gè)實(shí)例包含不同數(shù)目的工件、機(jī)器與加工工序.參數(shù)aj和bj根據(jù)完工時(shí)間隨機(jī)產(chǎn)生.交叉概率為0.8,變異概率為0.2,種群規(guī)模為40.在局部搜索的運(yùn)行過(guò)程中,搜索更新次數(shù)不超過(guò)5 次.將所提出的算法與遺傳算法、傳統(tǒng)文化基因算法、及改進(jìn)文化基因算法進(jìn)行比較,每個(gè)實(shí)例數(shù)據(jù)測(cè)試10 次,并記錄每個(gè)實(shí)例提前量與延遲量總權(quán)重的最優(yōu)值和平均值.

最終結(jié)果如表1所示:J、M、S 分別代表各實(shí)例中的工件數(shù)、機(jī)器數(shù)與總工序數(shù).其中,“GA*”,“MA*”,“MA-VND*”和“MA-GVND*”代表對(duì)4 個(gè)算法運(yùn)行10 次后得到目標(biāo)函數(shù)的最優(yōu)值:工件完工提前量和延遲量的總權(quán)重越小說(shuō)明算法找到了更優(yōu)的工件加工序列及機(jī)器人搬運(yùn)序列.“MA-VND”算法為前期研究的一種啟發(fā)式算法[12].

例如,在例1 中,所得到的GA 和MA 算法的最優(yōu)值分別為9 和2,MA-VND 算法及MA-GVND 算法的最優(yōu)值為0,均小于“GA”和“MA”算法,表明MAVND 算法及MA-GVND 算法可以有效地找到更小的最優(yōu)值:即工件完工提前量和延遲量的總權(quán)重.“GA#”,“MA#”,“MA-VND#”和“MA-GVND#”代表對(duì)4 個(gè)算法運(yùn)行10 次后得到的目標(biāo)函數(shù)最優(yōu)值取平均.取得的平均值可以體現(xiàn)各算法在10 次運(yùn)行過(guò)程及結(jié)果中的穩(wěn)定性.GA 和MA 算法的平均值是18.1 和5.3,MA-VND算法為2.1,所提出算法為1.9,結(jié)果表明MA-GVND算法的穩(wěn)定性較其它3 種算法更優(yōu).綜合實(shí)驗(yàn)數(shù)據(jù)結(jié)果,說(shuō)明MA-GVND 算法優(yōu)于現(xiàn)有方法:比遺傳算法和傳統(tǒng)文化基因算法可以更有效地達(dá)到最優(yōu)目標(biāo)函數(shù)值,并且為帶有機(jī)器人制造單元的作業(yè)車(chē)間調(diào)度問(wèn)題提供更高質(zhì)量的解.

選擇實(shí)例1 的結(jié)果,使用Matlab2012 編程仿真繪制甘特圖(見(jiàn)圖3),甘特圖可以描述各工件在機(jī)器上的加工順序和機(jī)器人裝卸載的搬運(yùn)過(guò)程.圖中的縱坐標(biāo)表示各加工機(jī)器(起始點(diǎn)與終止點(diǎn)為裝卸載站),橫坐標(biāo)表示加工時(shí)間軸.例如,實(shí)例1 有3 個(gè)待加工工件,每個(gè)工件有4 道加工工序.考慮到裝卸載在同一機(jī)器上進(jìn)行,即裝卸/載站,總共有5 臺(tái)機(jī)器.其中“31”是第3 個(gè)加工工件的第1 道加工工序,在第3 個(gè)加工機(jī)器上進(jìn)行加工.矩形的長(zhǎng)度表示該工件此道加工工序的加工時(shí)間.實(shí)線代表搬運(yùn)機(jī)器人的帶載搬運(yùn)操作,虛線代表搬運(yùn)機(jī)器人的空載操作.

表1 各算法數(shù)據(jù)比較

圖3 實(shí)例1 甘特圖

4 結(jié)論與展望

針對(duì)時(shí)間窗口約束下的帶有機(jī)器人制造單元的作業(yè)車(chē)間調(diào)度問(wèn)題,提出了一種新的元啟發(fā)式算法,目的是最小化提前量和延遲量的總權(quán)重,該算法結(jié)合了文化基因算法和變鄰域下降搜索技術(shù).實(shí)驗(yàn)分析表明,該算法能有效地得到機(jī)器人搬運(yùn)的最佳近似序列解,并且優(yōu)于現(xiàn)有方法.進(jìn)一步的研究將會(huì)嘗試解決帶有機(jī)器人制造單元的多目標(biāo)作業(yè)車(chē)間調(diào)度問(wèn)題,同時(shí)最小化完工時(shí)間與提前量和延遲量的總權(quán)重.