基于故障處理算法的動態多目標FJSP研究*

潘 穎，高天一，薛冬娟，謝忠東

(大連海洋大學 機械與動力工程學院，遼寧 大連 116023)

基于故障處理算法的動態多目標FJSP研究*

潘 穎，高天一，薛冬娟，謝忠東

(大連海洋大學 機械與動力工程學院，遼寧 大連 116023)

針對柔性作業車間調度(FJSP)過程的多目標、動態和信息不確定等特征，文章提出了一種實時調整的FJSP動態調度方法。首先，建立了FJSP動態仿真求解模型，該模型受自適應控制啟發，并結合魯棒調度和預見調度，求解效果穩定而高效；同時，該模型中設置了基于自適應遺傳算法的仿真求解器，并通過故障處理算法實現預見功能。最后，通過一企業實例驗證了文中所提算法的有效性和實用性。

多目標柔性作業車間調度；動態調度；仿真求解模型；故障處理算法

0 引言

生產調度是一系列生產活動的計劃，用于指導生產過程。但是，實際制造系統比如存在一些不可預期的現象或隨機擾動，會有各種實時動態事件發生，如到達緊急訂單、工件交貨期突化和加工設備突發故障等，可見實際生產系統具有本質上的不確定性與動態特征。而這些實時動態事件會使之前通過靜態調度已經制定好的生產加工計劃無法執行，需要車間調度人員根據這些新情況重新進行任務分配或工件調度。

柔性制造系統由于采用高度柔性的加工設備，零件的加工路線約束松弛使生產更靈活、高效，但相應的柔性調度更加復雜，調度算法所要搜索的解空間也急劇增大[1]。研究動態調度的主要方法有：最優化方法、系統仿真方法、啟發式方法、人工智能方法及計算智能方法等[2-8]。

本文針對柔性作業車間調度過程中多目標、信息不確定和動態的特征，提出了一種基于故障處理算法的FJSP動態調度方法。建立了FJSP動態仿真求解模型，提出了動態仿真求解模型框架，該框架受自適應控制啟發，結合了魯棒調度和預見調度，兼具兩者的優點，即穩定而高效；進而研究了基于預見動態調度的初步方案生成方法，采用動態仿真求解器的方法實現了預見功能，在隨機事件發生時減少系統的調整與優化指標波動；獲得了真正的優化效果。

1 問題描述

某生產車間，要在m臺設備上加工n個零件，每個零件有p個工序，所有工序都可以在任一設備上經指定的時間和花費指定的成本加工完成。

本模型基于以下假設：

(1)每臺設備每一時刻只能加工一個零件的一個工序；

(2)全部工序都必須加工也只需加工一次；

(3)每道工序必須一次加工完成，不能中斷；

(4)同一零件的工序必須按順序加工，即某道工序必須在其前道工序完成后開始；

(5)各零件的各工序在不違背要求(4)的條件下具有相同的優先級；

(6)設備在維護期間不能進行加工；

(7)設備在故障維修期間不能加工；

(8)隨機故障遵循期望為MTBF(Mean Time Between Failure，平均故障間隔時間)的指數分布；

(9)維修時間遵循期望為MTTR(Mean Time To Restoration，平均維修時間)的指數分布；

(10)所有機器的MTTR，MTBF均事先已知；

(11)假設某工序加工過程中出現故障，該工序可以重新開始，而且不會因此產生廢品。

多目標FJSP即滿足上述假設下將工序分配到各機床，確定加工次序，使得總工期、機器總負載、總成本和工序滯后度等指標最優。

2 動態柔性作業車間調度建模

受現代控制理論觀測器概念的啟發，本文設計了如圖1的動態仿真求解模型。其中仿真求解器共享實際生產系統的基礎信息，包括設備、人員、物料、訂單等方面信息，以及各工序在不同設備上加工的工時與成本等，還包括了設備新舊程度、維修周期等方面的信息。同時仿真求解器還接受實際生產系統運行過程中產生的信息更新，如設備無故障工作時間，已完成工序內容等。以上信息也作為考慮實時事件發生時生成初始動態決策的基礎。當發生設備故障或訂單變動等實時事件時仿真求解器的調度更新功能將作出快速反應，重新生成新的調度決策，或對原調度決策進行調整以適應情況的變化，并保證系統指標的優化。

圖1 動態仿真求解模型

為保證求解的精度和系統運行的穩定性，該仿真求解器能根據實際指標輸出與仿真指標輸出的差異來修正系統的參數與算法的選擇。

AGA(Adaptive Genetic Algorithm，自適應遺傳算法)求解器是保證動態調度優化能力的核心，該求解器是作者前續研究AGA算法基礎上修改得到的[9-10]。修改后的AGA求解器在模型中能動態更新其求解參數，具備了動態調度的能力。

3 多目標FJSP數學模型建立

取設計變量：

(1)

ORDij∈{1，2，...,pn}i∈N,j∈P

(2)

FJSP優化模型：

(3)

(4)

(5)

(6)

(7)

(3)-(6)式分別給出了最小總工期目標、單臺設備最大負載最小化目標、全部設備總負載最小化目標和最小總成本目標；(7)式保證每工序只在一臺設備上加工。

FJSP問題一定要保證某一時刻一臺加工設備最多有一道工序在進行加工；并且要保證每個工件按工序的先后順序依次進行。加工設備與工序的選擇關系由0-1變量可確定；工件的工序加工順序可由式(8)到(10)約束確定。

s.t.

STij+1≥ETiji∈N,j∈{1，2，...，p-1}

(8)

(9)

k∈M,i,i′∈N,j,j′∈P,且i≠i′,j≠j′

(10)

(8)式保證同一工件各工序的順序；(9)式保證ORDij取得1-pn的組合；(10)式保證各工序的開始加工時刻，或者為0，或者要在同一設備前一工序完工之后。

4 故障處理算法設計

在給定的目標下，如期望的工期或最小的滯后，仿真器能在隨機故障事件的情況下評價各方案的適應度。在仿真過程中，使用事件驅動策略決定何時進行重調度，當需要重調度時使用右移啟發算法進行調度方案修正。在以上兩個過程中都要使用到FEL變量與LIFE變量。將仿真器算法添加到AGA的解碼算法中，對每一個原靜態方案(染色體)施行以下步驟：

(1)初始化：

① 生成甘特圖數據結構G，方便重調度時刻的判斷與采用啟發算法的調整；

② 根據各設備的MTBF，按指數分布生成隨機變量FEL，對每臺設備Mk生成隨機數：FEL[Mk]= exp-rand(MTBF)，其中 exp-rand為指數分布隨機數生成器Mk；k= 1， 2，...，m。

(2)建立動態調度，對工序部分自左至右讀出其基因代碼執行以下操作：

① 確定其對應工序Oij；

② 參考設備指定部分基因，確定其加工設備Mk，以及該工序在該設備上的工時Pijk；

③ 取t1為工序Oij的同一工件緊前工序Oij-1的結束時間，t2為同一設備前一工序的結束時間。如果Oij為某工件的首道工序(j=1)，則t1=0。如果Oij為所在設備的第一個工序，則t2=0；

④ 如果t2小于或等于t1，也就是指定設備Mk在t1時刻空閑，將工序在Mk上加工。起始時間為t1。否則將Oij插入Mk上正在加工工序之后，即開始時間為t2；

⑤ 執行故障處理算法。

(3)計算按照目標評價方案的適應度；

(4)若滿足迭代終止準則，則輸出方案；否則，轉2。

仿真器通過故障處理算法實現對現實過程中隨機故障的模擬，其步驟如下：

(1) 將Oij在設備Mk上加工的工時Pijk累加到Mk的使用時間中，即LIFE的相應變量中 LIFE[Mk]=LIFE[Mk]+Pijk；

(2) 如果(LIFE[[Mk] > FEL[[Mk]) 轉步驟 3，否則，轉步驟4；

(3) 設備出現故障，執行以下操作：

① 生成以該設備MTTR為期望的指數分布隨機數，作為維修時間；

Repair time=exp-rand(MTTR)

② 將生成的維修時間添加到被中斷工序所在零件的結束時間中；

Complete[i]= Complete[i]+ Repair time

③ 重置FEL中對應設備的變量，更新Mk的未來故障時間；

FEL[[Mk]= exp-rand(MTBF)

④ 將[Mk的使用時間歸零。

LIFE[[Mk]= 0

(4) 返回修改后的AGA算法。

圖2 初始動態調度生成流程圖

5 算例仿真與企業實例驗證

以下以表1“3×5”問題為例，展示動態調度的特點。以及當發生故障時，基于故障處理算法的動態調度優越性。其中M1被設置成易于發生故障的設備。

表1 完全柔性作業車間調度加工時間表

圖3 “3×5”問題例靜態調度結果

圖3為靜態調度結果，工期指標為8。

圖4為采用本文提出的故障處理算法獲取的動態調度結果，工期指標為9。由于設備故障的隨機性以及該指標為多次動態解碼的算術平均，此圖只給出了一種解碼結果，工期為9。但這不影響在統計意義下方案的較優性。而且，由圖可見動態調度自動避開了傾向于故障的M1，使得初始調度方案具有更高的可靠性。

圖4 “3×5”問題例動態調度結果的解碼

圖5 實時多目標調度參數設置界面

圖6 多目標優化(成本+總負載)調度結果

該算法在某減速機分公司的生產管理軟件得以應用，該企業主要生產重型汽車的減速器、齒輪齒座、聯軸器和渦輪絲桿升降機等產品，屬于典型的面向柔性制造的離散制造業。

圖5為實時多目標調度參數設置界面，可選擇調度任務，并列有調度類型選項：預調度、訂單變動、設備故障及報廢工件等。在優化參數一欄，可人工修改遺傳算法參數，根據車間實際動態狀況在一定程度上控制算法運算時間和精度。如不修改就沿用系統默認的參數值。優化目標部分，在各優化目標后面方框中的數字代表不同權重，數值大小可調。優化參數和優化目標權重值的調整會影響調度時間和結果，可根據工廠車間實際要求做出調整。全部參數選擇設置好之后，可執行“開始”按鈕，并查看調度結果甘特圖。

圖6顯示的是由于車間出現設備故障，重新調度后以最小成本和最小全部設備負載為優化目標的甘特圖。

6 結論

本文建立了動態仿真求解模型框架，該框架受自適應控制啟發，結合了魯棒調度和預見調度，兼具兩者的優點，即穩定而高效；然后研究了故障處理算法，采用動態仿真求解器的方法實現了預見功能，使得生成的方案從統計的角度考慮了隨機事件的可能發生，因而既獲得了真正的優化效果，又能在隨機事件發生時減少系統的調整與優化指標波動；綜上所述，本文系統地給出了一種求解動態調度問題的模型與方法，并算例驗證了其可行性與先進性。

[1] 王世進.基于自治與協商機制的柔性制造車間智能調度技術研究[D].上海:上海交通大學,2010.

[2] 高俊宇，張平，余海峰.車間動態調度方法綜述[J].機電工程技術，2009,38(9)：13-16.

[3] Dong Liang-cai, XU Zi-qi, MI Wei-jian.The dynamic tugboat schedule based on particle swarm algorithm combined with genetic operators[J]. mathematics in practice and theory, 2012,42(6):122-133.

[4] W.J. Jiang, L.M. Zhang, P.Wang. Dynamic scheduling model of computing resource based on MAS cooperation mechanism[J]. Science in China Series F: Information Sciences, 2009 (l52):1302-1320.

[5] X.Wang, L. Gao, C. Zhang. A multi-objective genetic algorithm based on immune and entropy principle for flexible job-shop scheduling problem [J]. The International Journal of Advanced Manufacturing Technology, 2010 (51):757-767.

[6] Herroelen W. Discussion of “Probabilistic Estimation and Allocation of Project Time Contingency” by Gabriel A. Barraza[J]. Journal of Construction Engineering and Management 2013, 139(1):253-255.

[7] L. Nie, L. Gao, P. Li. A GEP-based reactive scheduling policies constructing approach for dynamic flexible job shop scheduling problem with job release dates[J]. Journal of Intelligent Manufacturing , 2012:12-21.

[8] M?nch L, Fowler J W, Dauzère-Pérès S. A survey of problems, solution techniques, and future challenges in scheduling semiconductor manufacturing operations[J]. Journal of Scheduling, 2011 (14):583-599.

[9] 潘穎，孫偉，張文孝. 基于適應度分析的AGA求解柔性Job-shop調度問題[J].組合機床與自動化加工技術，2010(6)：101-104.

[10] Ying Pan, Wei Sun, Xiao-Hong Lu, Qin-Yi Ma.An Adaptive Genetic Algorithm for the Flexible Job-shop Scheduling Problem[C]. Proceedings 2011 IEEE International Conference on Computer Science and Automation Engineering,2011: 405-409.

(編輯 趙蓉)

Research on Dynamic Multi-objective FJSP Based on Fault-handling Algorithm

PAN Ying，GAO Tian-yi，XUE Dong-juan，XIE Zhong-dong

(School of Mechanical and Power Engineering, Dalian Ocean University. Dalian Liaoning 116023, China)

Aiming at multi-objective, uncertain information and dynamic characteristic during flexible job-shop scheduling process, some kind of dynamic scheduling method for FJSP is put forward based on real-time adjustment. Firstly, a dynamic simulation solution mode framework is presented for FJSP. This framework is inspired by adaptive control, combined with the robust scheduling and foreseeing scheduling. It has both advantages of such two schedulings, and it’s stable and highly efficient; at the same time, foreseeing function is realized by fault-handling algorithm and dynamic simulation solver on the basis of Adaptive Genetic Algorithm. Finally, the effectiveness and practicality of the presented algorithm is proved through the enterprise instance.

multi-objective flexible job-shop scheduling problem(FJSP); dynamic scheduling; simulation solution mode; fault-handling algorithm

1001-2265(2014)04-0150-04

10.13462/j.cnki.mmtamt.2014.04.042

2013-09-04

國家科技支持計劃"大連市制造業信息化科技示范工程" (2013BAF02B03-2)；大連海洋大學博士啟動基金(SYBS201205)

潘穎(1977—)，女，哈爾濱人，大連海洋大學講師，博士，研究方向為車間調度，精益生產，(E-mail)panying@dlou.edu.cn。

TH166;TG65

A