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

(大連海洋大學(xué) 機(jī)械與動(dòng)力工程學(xué)院，遼寧 大連 116023)

基于故障處理算法的動(dòng)態(tài)多目標(biāo)FJSP研究*

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

(大連海洋大學(xué) 機(jī)械與動(dòng)力工程學(xué)院，遼寧 大連 116023)

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

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

0 引言

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

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

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

1 問題描述

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

本模型基于以下假設(shè)：

(1)每臺(tái)設(shè)備每一時(shí)刻只能加工一個(gè)零件的一個(gè)工序；

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

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

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

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

(6)設(shè)備在維護(hù)期間不能進(jìn)行加工；

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

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

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

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

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

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

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

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

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

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

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

3 多目標(biāo)FJSP數(shù)學(xué)模型建立

取設(shè)計(jì)變量：

(1)

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

(2)

FJSP優(yōu)化模型：

(3)

(4)

(5)

(6)

(7)

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

FJSP問題一定要保證某一時(shí)刻一臺(tái)加工設(shè)備最多有一道工序在進(jìn)行加工；并且要保證每個(gè)工件按工序的先后順序依次進(jìn)行。加工設(shè)備與工序的選擇關(guān)系由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)式保證各工序的開始加工時(shí)刻，或者為0，或者要在同一設(shè)備前一工序完工之后。

4 故障處理算法設(shè)計(jì)

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

(1)初始化：

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

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

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

① 確定其對(duì)應(yīng)工序Oij；

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

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

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

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

(3)計(jì)算按照目標(biāo)評(píng)價(jià)方案的適應(yīng)度；

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

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

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

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

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

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

Repair time=exp-rand(MTTR)

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

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

③ 重置FEL中對(duì)應(yīng)設(shè)備的變量，更新Mk的未來故障時(shí)間；

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

④ 將[Mk的使用時(shí)間歸零。

LIFE[[Mk]= 0

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

圖2 初始動(dòng)態(tài)調(diào)度生成流程圖

5 算例仿真與企業(yè)實(shí)例驗(yàn)證

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

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

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

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

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

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

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

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

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

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

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

6 結(jié)論

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

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

[2] 高俊宇，張平，余海峰.車間動(dòng)態(tài)調(diào)度方法綜述[J].機(jī)電工程技術(shù)，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] 潘穎，孫偉，張文孝. 基于適應(yīng)度分析的AGA求解柔性Job-shop調(diào)度問題[J].組合機(jī)床與自動(dòng)化加工技術(shù)，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

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

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

TH166;TG65

A