帶機器人制造單元的作業車間調度仿真①

李曉輝,楊 晰,趙 毅

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

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

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

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

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

1 問題描述

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

一般作業車間調度問題需要考慮如下約束條件:

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

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

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

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

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

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

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

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

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

時間窗約束的數學公式如下:

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

2 文化基因算法

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

2.1 解的表示

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

2.2 全局搜索

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

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

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

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

2.3 變鄰域下降搜索

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

圖1 鄰域結構示例

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

2.4 改進的元啟發式算法

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

圖2 算法流程圖

Step 1.讀入數據,初始化解;

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

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

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

Step 5.隨機選擇鄰域結構進行更新;

Step 6.判斷產生的新解是否大優于原最有個體的解;是則輸出新個體,否則繼續選擇鄰域結構進行計算;

Step 7.輸出最優個體.

3 實驗結果分析

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

最終結果如表1所示:J、M、S 分別代表各實例中的工件數、機器數與總工序數.其中,“GA*”,“MA*”,“MA-VND*”和“MA-GVND*”代表對4 個算法運行10 次后得到目標函數的最優值:工件完工提前量和延遲量的總權重越小說明算法找到了更優的工件加工序列及機器人搬運序列.“MA-VND”算法為前期研究的一種啟發式算法[12].

例如,在例1 中,所得到的GA 和MA 算法的最優值分別為9 和2,MA-VND 算法及MA-GVND 算法的最優值為0,均小于“GA”和“MA”算法,表明MAVND 算法及MA-GVND 算法可以有效地找到更小的最優值:即工件完工提前量和延遲量的總權重.“GA#”,“MA#”,“MA-VND#”和“MA-GVND#”代表對4 個算法運行10 次后得到的目標函數最優值取平均.取得的平均值可以體現各算法在10 次運行過程及結果中的穩定性.GA 和MA 算法的平均值是18.1 和5.3,MA-VND算法為2.1,所提出算法為1.9,結果表明MA-GVND算法的穩定性較其它3 種算法更優.綜合實驗數據結果,說明MA-GVND 算法優于現有方法:比遺傳算法和傳統文化基因算法可以更有效地達到最優目標函數值,并且為帶有機器人制造單元的作業車間調度問題提供更高質量的解.

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

表1 各算法數據比較

圖3 實例1 甘特圖

4 結論與展望

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