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

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

基于故障處理算法的動態(tài)多目標FJSP研究*

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

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

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

多目標柔性作業(yè)車間調(diào)度；動態(tài)調(diào)度；仿真求解模型；故障處理算法

0 引言

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

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

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

1 問題描述

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

本模型基于以下假設：

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

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

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

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

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

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

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

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

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

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

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

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

2 動態(tài)柔性作業(yè)車間調(diào)度建模

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

圖1 動態(tài)仿真求解模型

為保證求解的精度和系統(tǒng)運行的穩(wěn)定性，該仿真求解器能根據(jù)實際指標輸出與仿真指標輸出的差異來修正系統(tǒng)的參數(shù)與算法的選擇。

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

3 多目標FJSP數(shù)學模型建立

取設計變量：

(1)

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

(2)

FJSP優(yōu)化模型：

(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 故障處理算法設計

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

(1)初始化：

① 生成甘特圖數(shù)據(jù)結構G，方便重調(diào)度時刻的判斷與采用啟發(fā)算法的調(diào)整；

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

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

① 確定其對應工序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；

⑤ 執(zhí)行故障處理算法。

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

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

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

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

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

(3) 設備出現(xiàn)故障，執(zhí)行以下操作：

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

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 初始動態(tài)調(diào)度生成流程圖

5 算例仿真與企業(yè)實例驗證

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

表1 完全柔性作業(yè)車間調(diào)度加工時間表

圖3 “3×5”問題例靜態(tài)調(diào)度結果

圖3為靜態(tài)調(diào)度結果，工期指標為8。

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

圖4 “3×5”問題例動態(tài)調(diào)度結果的解碼

圖5 實時多目標調(diào)度參數(shù)設置界面

圖6 多目標優(yōu)化(成本+總負載)調(diào)度結果

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

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

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

6 結論

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

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

[2] 高俊宇，張平，余海峰.車間動態(tài)調(diào)度方法綜述[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調(diào)度問題[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

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

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

TH166;TG65

A