李曉輝,楊 晰,趙 毅

(長安大學 電子與控制工程學院,西安 710064)

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

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

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

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

1 問題描述

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

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

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

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

3)某一時刻,一臺機器只能加工一個工件,每個工序在加工期間不能中途停止;

4)只有一個搬運機器人(同一時刻,機器人只能搬運一個工件);

5)一個工件在加工過程中采取平行移動方式,轉(zhuǎn)移時間忽略不計或計入加工時間;

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

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

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

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

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

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

2 文化基因算法

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

2.1 解的表示

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

2.2 全局搜索

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

選擇操作采用輪盤賭選擇法來選擇兩個個體作為雙親,這是遺傳算法和進化算法等算法中常用的一種選擇方法.

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

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

2.3 變鄰域下降搜索

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

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

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

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

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

圖2 算法流程圖

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

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

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

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

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

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

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

3 實驗結(jié)果分析

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

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

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

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

圖3 實例1 甘特圖

4 結(jié)論與展望

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