基于Drools 規(guī)則引擎的柔性化鈑金產(chǎn)線優(yōu)化排程①

任 彬 王梓林

(上海大學(xué)機電工程與自動化學(xué)院上海市智能制造及機器人重點實驗室 上海 200444)

0 引言

柔性化產(chǎn)線作為新一代智能制造系統(tǒng)的基礎(chǔ),是智能生產(chǎn)的主要載體。柔性化產(chǎn)線自感知、自適應(yīng)、自學(xué)習(xí)、自決策的形成,是我國實現(xiàn)產(chǎn)品制造向現(xiàn)代化、數(shù)字化、智能化靠近的關(guān)鍵一步[1]。鈑金柔性生產(chǎn)線也向著自動化、智能化方向發(fā)展。由于鈑金加工具有多品種、小批量的離散制造典型特征,傳統(tǒng)的人工調(diào)度和排程方法不能滿足生產(chǎn)需求。通過應(yīng)用現(xiàn)代智能優(yōu)化算法對生產(chǎn)排程問題求解,可以有效提高排程效率并搜尋出復(fù)雜排程問題的最優(yōu)解,解決生產(chǎn)制造多目標、多任務(wù)、多工序的生產(chǎn)排程問題。

生產(chǎn)排程的求解尋優(yōu)問題一直是國內(nèi)外學(xué)者研究的熱點,研究方向主要集中在求解算法方面[2-4]。文獻[5]開發(fā)出一種雙目標隨機局部搜索啟發(fā)式算法,通過在搜索路徑上生成多個非支配解改善尋優(yōu)方式。文獻[6]提出用于實際的聚類算法以解決鈑金成型行業(yè)在單機系統(tǒng)中依賴于序列相關(guān)轉(zhuǎn)換時間的問題。文獻[7]結(jié)合整數(shù)編程方法和分解方法實現(xiàn)更短時間內(nèi)提供更高質(zhì)量的解決方案。國內(nèi)關(guān)于排程算法方面也有大量的研究[8-9]。文獻[10]提出優(yōu)先級策略改進非支配排序遺傳算法(NSGA2)解決煉鋼-連鑄調(diào)度中求解精度問題。文獻[11]針對智能車間復(fù)雜性程度高、動態(tài)不確定性明顯等問題提出一種將離散仿真與遺傳算法相結(jié)合的調(diào)度規(guī)則挖掘方法。文獻[12]針對大規(guī)模置換流水車間調(diào)度問題,提出一種改進的模擬退火算法求解調(diào)度問題。

隨著智能制造時代的到來,工業(yè)物聯(lián)網(wǎng)技術(shù)推動下的高級計劃與排程系統(tǒng)(advanced planning and scheduling,APS)發(fā)展呈現(xiàn)“協(xié)同社會化”,智能車間的APS 需能夠發(fā)揮出智能的優(yōu)勢[13]。車間生產(chǎn)過程中面對復(fù)雜的情況往往需要考慮多種目標建立規(guī)則約束條件以最大化利益,如在鈑金生產(chǎn)過程中,需考慮時間及諸多成本消耗等。由此尋優(yōu)過程中目標增多,現(xiàn)代智能優(yōu)化算法在判斷方案優(yōu)劣時,復(fù)雜程度增加,迭代尋優(yōu)過程消耗較多的時間。而小批量、離散化特征的鈑金加工訂單具有較多不可預(yù)估的臨時插單情況,要求能快速更新排程方案,傳統(tǒng)的方案優(yōu)劣判斷難以滿足要求。

針對上述柔性化鈑金產(chǎn)線生產(chǎn)排程問題,本文在訂單按時交貨的基礎(chǔ)上以最小化綜合成本及損耗為目標,引入Drools 規(guī)則約束引擎,通過約束匹配取代多目標尋優(yōu)中復(fù)雜的適應(yīng)度計算,研究適用于柔性化鈑金產(chǎn)線快速尋優(yōu)生產(chǎn)排程方法。最后通過柔性化鈑金產(chǎn)線的結(jié)果分析,驗證了排程方法的有效性。

1 柔性化鈑金產(chǎn)線的排程問題

1.1 柔性化鈑金產(chǎn)線的需求

鈑金加工生產(chǎn)多品種、小批量的離散制造特征使得人工排程變得困難。傳統(tǒng)離散制造業(yè)的生產(chǎn)計劃大多是用辦公軟件手工進行排程,計劃的優(yōu)劣程度主要由計劃員的經(jīng)驗決定,在訂單量較大的情況下難以短時間得出較好的生產(chǎn)計劃,緊急插單的情況更是難以快速更新計劃,且傳統(tǒng)生產(chǎn)計劃大多較為粗糙,對車間生產(chǎn)只具有簡單的指導(dǎo)意義。如此,傳統(tǒng)的排程方式不能滿足柔性化車間生產(chǎn)需求,它不僅需耗費大量的人力,難以保證計劃的時效性,且不能發(fā)揮出柔性化鈑金產(chǎn)線的信息化管理優(yōu)勢、產(chǎn)能優(yōu)勢[14]。

圖1 所示為柔性落料折彎鈑金產(chǎn)線。該柔性鈑金產(chǎn)線由數(shù)控設(shè)備和機器人組成,自動化程度高,可用來加工多種鈑金零件或產(chǎn)品。各加工單元任務(wù)相對獨立,互不干擾,由管理系統(tǒng)統(tǒng)一按照生產(chǎn)流程下發(fā)任務(wù)清單,不需嚴格工序銜接。

圖1 柔性落料折彎鈑金產(chǎn)線

柔性化鈑金產(chǎn)線加工訂單從下單到成品入庫的一般生產(chǎn)流程如圖2 所示。為保證訂單能按時完成加工,計劃排程是生產(chǎn)流程中不可缺少的一環(huán)。

圖2 鈑金加工生產(chǎn)流程

柔性化鈑金生產(chǎn)線相對于傳統(tǒng)的鈑金生產(chǎn)線產(chǎn)能提升很高,而由于鈑金訂單需求一般為小批量,且品種繁多,發(fā)揮產(chǎn)能優(yōu)勢代表訂單量巨大。將緊急插單的情況考慮在內(nèi),以保證訂單按時加工完成為基礎(chǔ),迅速形成或更新生產(chǎn)計劃成為生產(chǎn)排程的關(guān)鍵。此外,考慮最小成本、最小設(shè)備損耗,多目標尋優(yōu)成為迅速排程的難點。

1.2 柔性化鈑金生產(chǎn)的排程規(guī)劃

鈑金生產(chǎn)排程規(guī)劃問題的求解可以視為求解約束滿足問題(constraint satisfaction problem,CSP)[15]。CSP 由一個變量集合和一個約束集合組成,約束描述一個變量子集與子集內(nèi)各變量的相容賦值,所有約束的邏輯“與”構(gòu)成了問題的一個實例[16]。CSP的求解即找到滿足所有約束或能最大化滿足約束的變量賦值。實際情況中更多要求為在滿足約束的條件下得到CSP 優(yōu)化解。而當CSP 約束增加、目標變多時,解的優(yōu)劣性確定將變得復(fù)雜,為快速得到解的優(yōu)劣情況以便下一步迭代優(yōu)化,引入規(guī)則引擎對解進行評價函數(shù)計算。本文結(jié)合Drools 規(guī)則引擎建立生產(chǎn)規(guī)則約束,利用Java 的多線程優(yōu)勢,研究適用于柔性化鈑金產(chǎn)線的快速尋優(yōu)生產(chǎn)排程方法。

規(guī)劃問題包括規(guī)劃實體、規(guī)劃變量和問題事實。規(guī)劃實體是指被規(guī)劃的對象,如車間生產(chǎn)的生產(chǎn)線及其設(shè)備,生產(chǎn)排程的任務(wù)即對生產(chǎn)線上的設(shè)備進行時間及任務(wù)分配,從而優(yōu)化生產(chǎn)線產(chǎn)能;規(guī)劃變量是指對規(guī)劃實體的最終效益產(chǎn)生影響的可調(diào)整的量,即規(guī)劃過程中需要確定的變量,如確定生產(chǎn)任務(wù)的生產(chǎn)設(shè)備及生產(chǎn)時間;問題事實則為規(guī)劃問題中的業(yè)務(wù)情況,為問題提供資料,如生產(chǎn)排程問題中設(shè)備數(shù)量等。

為求解鈑金生產(chǎn)排程CSP 問題,結(jié)合規(guī)劃問題定義提出如圖3 所示的Drools 規(guī)劃問題求解方法。該方法包括生產(chǎn)實況了解、規(guī)則約束建立、Drools 規(guī)則引擎鄰域搜索法求解及結(jié)果表達4 個步驟。針對前述問題,該方法將算法迭代尋優(yōu)過程與Drools 規(guī)則引擎相結(jié)合,通過規(guī)則引擎表達并匹配約束與目標,以此對迭代過程中的解集進行優(yōu)劣性的判斷,并通過評分模型對優(yōu)劣性進行量化表示。采用Drools規(guī)則引擎表達匹配約束目標,清晰簡單表示生產(chǎn)過程中復(fù)雜的約束及多個目標,方便規(guī)則調(diào)整以適應(yīng)多變的車間生產(chǎn)狀況,并可逐條快速匹配約束情況。

圖3 規(guī)劃問題求解方法

在明確規(guī)劃實體、規(guī)劃變量、問題事實的關(guān)系并確定規(guī)劃問題的求解方法后,采用該方法求得柔性化鈑金產(chǎn)線優(yōu)化排程方案。優(yōu)化排程方案求解的核心為結(jié)合Drools 規(guī)則引擎的鄰域搜索法,包括求解器和評價器兩部分,求解器主要功能為迭代搜索解決方案,在實際生產(chǎn)問題事實(fact)基礎(chǔ)上,通過鄰域搜索迭代新的方案。評價器的核心為Drools 規(guī)則引擎,將生產(chǎn)實際約束及目標表達為規(guī)則(rules),結(jié)合三級評分模型對搜索方案進行得分計算,量化表示方案優(yōu)劣情況。最終得出優(yōu)化排程方案,結(jié)果表示為甘特圖。

2 規(guī)則約束建立

2.1 優(yōu)化目標表述

在制造行業(yè)中,按期交貨和降低成本是生產(chǎn)商重視的。由此建立以最小綜合成本及設(shè)備損耗為優(yōu)化目標約束模型,考慮到生產(chǎn)過程所有成本如用電成本、人工成本等,此外還考慮所有設(shè)備損耗,確立目標如下。

制定生產(chǎn)計劃,在實現(xiàn)按期交貨的前提下,以最小成本為指標,減小設(shè)備損耗。

式(1)和式(2)分別表示生產(chǎn)過程中的綜合成本和設(shè)備損耗。式中i 表示訂單任務(wù)的序號;j 為生產(chǎn)線序號;n、m 分別為生產(chǎn)訂單數(shù)量和生產(chǎn)線數(shù)量;fm1為最低成本消耗,主要考慮比重較大的人力資源成本fP和電力成本fQ;Qej、Qoi和Qss分別為空閑電耗、生產(chǎn)電耗和啟停電耗;fm2表示最低設(shè)備損耗;Loi、Lss分別表示生產(chǎn)損耗和啟停損耗;Sj為生產(chǎn)期間各生產(chǎn)線的啟停次數(shù)。

2.2 生產(chǎn)約束表述

綜合考慮生產(chǎn)過程中的約束,包括在交貨期前完成加工生產(chǎn)及加工生產(chǎn)固有約束等。此外,鈑金加工生產(chǎn)情況變化頻繁,生產(chǎn)商習(xí)慣對訂單設(shè)定加工緊急等級來附加額外的加工順序,并希望盡量按照緊急等級順序進行加工。為方便量化表示解的優(yōu)劣情況,將約束分為三級以配合評分模型量化表示,并將優(yōu)化目標作為中等約束以便通過Drools 規(guī)則引擎表達。由此建立如下約束。

(1)硬約束

1)按期交貨:訂單必須在訂單下達之后開始生產(chǎn)并在交期之前完成。

2)最大容量:每條生產(chǎn)線有一定加工容量,加工生產(chǎn)需占用一定加工容量,要求所排任務(wù)量占用容量不得超過對應(yīng)生產(chǎn)線的最大容量。

式(3)和式(4)分別表示按期交貨及生產(chǎn)線生產(chǎn)最大容量限制。式中To、Ts、Td分別為下單時間、訂單開始生產(chǎn)時間、收貨截止時間,Ni、Nj為某個時刻排入的生產(chǎn)訂單占用容量和生產(chǎn)線允許加工容量。

(2)中等約束

1)人力資源成本:生產(chǎn)期間需技術(shù)管理人員并消耗人力成本。

2)電力成本:生產(chǎn)線運行消耗電力成本。

3)設(shè)備損耗:生產(chǎn)線運行會造成一定設(shè)備損耗。

4)設(shè)備功耗:不同生產(chǎn)線加工和空閑都消耗不同電功。

5)任務(wù)功耗:不同產(chǎn)品生產(chǎn)消耗不同電功。

6)啟停消耗:設(shè)備啟動或關(guān)閉需額外的電功并造成一定損耗。

中等約束為優(yōu)化目標的前提,具體表現(xiàn)如式(1)、式(2)所示。

(3)軟約束

1)盡早生產(chǎn):訂單盡早開始生產(chǎn)。

2)緊急順序:加工生產(chǎn)順序盡量按照訂單緊急等級進行。

3)倉庫成本:原材料及成品的存儲需要倉庫成本。

式(5)～(7)為軟約束,表現(xiàn)為次要目標,相較主要目標而言比重較小,故僅作為軟約束考慮。其中fs1表示盡早生產(chǎn),fs2為按照緊急等級排序的量化分,fs3表示最低倉庫成本,St表示按照緊急加工等級順序的排序量化分,Cdm、Cdp分別為材料倉庫成本和成品倉庫成本。

2.3 目標函數(shù)

由圖3 規(guī)劃問題求解方法中,在建立約束后對調(diào)度問題進行迭代求解。在求解過程中智能優(yōu)化算法決定尋優(yōu)路徑,如遺傳算法通過染色體(解集編碼)的選擇、交叉、變異產(chǎn)生新族群(解集),粒子群算法通過粒子(解)的運動產(chǎn)生新粒子群等。本文針對鈑金排程問題擬采用局部搜索法對生產(chǎn)方案進行搜索尋優(yōu)。傳統(tǒng)解的優(yōu)劣情況通過適應(yīng)度(fitness)的計算確定。適應(yīng)度在實際情況中表現(xiàn)為對所提出的規(guī)則約束和目標要求的符合程度,根據(jù)鈑金實際加工生產(chǎn)狀況提出的目標及約束要求,適應(yīng)度的計算如下。

式中,Hs表示硬約束違反情況,Hs=0 時表明硬約束沒有被違反,為可行解;反之硬約束被違反,解不適用,適應(yīng)度為0。

當Hs=0 時,適應(yīng)度為兩部分之和,分別表示軟約束和中等約束的符合情況。分子中ws、wm分別為軟約束和中等約束的權(quán)重系數(shù),中等約束的權(quán)重大。分母中各項分別對應(yīng)相應(yīng)約束,見式(1)、(2)、(5)～(7),rsi、rmi(i=1,2,3)則表示約束的權(quán)重。

由式(9)可見,適應(yīng)度的計算非常復(fù)雜,這是由多目標尋優(yōu)的性質(zhì)決定的,當目標函數(shù)較多時,解優(yōu)劣的確定也隨之復(fù)雜起來。本文采用Drools 規(guī)則匹配代替適應(yīng)度計算,通過Drools 引擎表達規(guī)則極大地利用Java 多線程的優(yōu)勢[17],并可通過規(guī)則引擎的規(guī)則匹配功能,實現(xiàn)約束的快速匹配。Drools 作為主流的規(guī)則引擎之一,適合在復(fù)雜、變動頻繁的業(yè)務(wù)規(guī)則上應(yīng)用[18]。由此適應(yīng)度可以通過匹配結(jié)果量化簡單表示為

式中Ss和Ms分別為Drools 匹配軟約束和中等約束的量化得分。

3 評價與求解

3.1 Drools 規(guī)則引擎

Drools 規(guī)則引擎主要由規(guī)則庫、匹配引擎和工作空間三部分組成[19],如圖3 所示,規(guī)則庫加載被訪問的規(guī)則(rule),工作空間加載規(guī)劃問題的問題事實(fact),匹配引擎推動規(guī)則匹配器(pattern matcher)和執(zhí)行管理(agenda)的運行。Drools 采用的模式匹配算法有Rete 和Leaps 等,Rete-OO 算法是對Rete 算法的加強和優(yōu)化[20]。Drools 規(guī)則引擎推理步驟如下。

(1)分別將規(guī)則和問題事實加載到規(guī)則庫和工作空間中。

(2)通過規(guī)則匹配器比較規(guī)則和泛化問題事實,檢驗匹配性。

(3)若檢驗結(jié)果無規(guī)則沖突,將激活規(guī)則放入執(zhí)行管理器,若有沖突,將沖突規(guī)則放入沖突區(qū)。

(4)解決沖突規(guī)則區(qū)的問題,再將激活規(guī)則放入執(zhí)行管理器。

(5)運行執(zhí)行管理器中激活的規(guī)則。

(6)重復(fù)步驟(2)～(5)直到?jīng)]有規(guī)則與約束匹配。

具體規(guī)則約束匹配表現(xiàn)如圖4 所示。

圖4 Drools 約束匹配

其中RULE表示規(guī)則庫中的規(guī)則,包括硬約束、中等約束、軟約束在內(nèi)的7 個規(guī)則約束,見式(1)～(7)。為對問題事實的解進行規(guī)則匹配,即將搜索的解決方案按照上述的約束進行匹配。為觸發(fā)規(guī)則操作,若觸發(fā)硬約束則回收,該解為不可行解,若觸發(fā)中等約束或軟約束,則執(zhí)行對應(yīng)懲罰評分。由于中等約束、軟約束為成本、時間的計算,故所有方案都會觸發(fā)。

3.2 三級評分模型

問題事實的解決方案不可避免地違反所建立的約束,Drools 規(guī)則引擎需結(jié)合評分模型量化表示解的優(yōu)劣情況。通過計算解的評分,判斷解的優(yōu)劣。

評分模型一般為兩級評分模型,軟硬約束分別對應(yīng)軟硬分,硬分數(shù)表明方案是否可行,軟分數(shù)則表明方案的優(yōu)劣。本文中采用三級評分模型,引入中等約束的性質(zhì),中等約束與所求的目標函數(shù)相關(guān),見式(1)、(2)。軟約束為相對不重要的要求,見式(5)～(7)。硬約束為必須滿足的基本約束見式(3)、(4)。通過引入中等約束的性質(zhì)以區(qū)分約束的重要程度,并更加直觀地表示出目標函數(shù)的滿足情況。

各約束分別匹配解決方案時,觸發(fā)規(guī)則后,執(zhí)行操作即為計算對應(yīng)約束性質(zhì)的分數(shù),中等約束匹配結(jié)果通過中等分數(shù)Ms量化表示,軟約束匹配結(jié)果通過軟分數(shù)Ss量化表示,通過加權(quán)求和即可用來表示適應(yīng)度值,見式(10)。采用Drools 規(guī)則匹配器,結(jié)合三級評分模型,實現(xiàn)對方案優(yōu)劣性的量化表示。

3.3 鄰域搜索求解

適應(yīng)度計算方式確認后即可通過智能優(yōu)化算法搜索尋優(yōu)。本文針對鈑金排程問題擬采用局部搜索法進行求解,算法相關(guān)規(guī)則及步驟如下。

(1)隨機選擇初始可行解x0∈D,xb=x0,P=N(xb)。

(2)選擇鄰域P 的一個子集P′,計算子集各解的得分,xn為其中最優(yōu)解。

(3)如果xn得分較原有xb大,則有xb=xn,P=N(xn),否則P=P -P′。

(4)判斷是否滿足終止條件,滿足則尋優(yōu)結(jié)束,輸出最優(yōu)結(jié)果,否則執(zhí)行步驟(2)。

其中D 為鈑金排程問題中的可行解域,P 為當前最優(yōu)可行解的鄰域,所有可選擇的元素皆為可行解。用結(jié)合評分模型的Drools 規(guī)則引擎對所選解進行得分計算。由于快速形成生產(chǎn)計劃是需求,故算法中引入時間元素,以10 s 時間為終止條件。鄰域動作則為對某個任務(wù)進行生產(chǎn)設(shè)備或開始加工時間上的移動。最后通過該方法對鈑金排程問題進行搜索尋優(yōu)。

4 柔性化鈑金產(chǎn)線排程實例

以某安防門生產(chǎn)線為例,該生產(chǎn)線是柔性落料折彎鈑金產(chǎn)線,用于門板自動折彎成型,是集成料庫、單張取料、CCD 識別、激光切割、打碼、數(shù)控轉(zhuǎn)塔沖床、長邊折彎、短邊折邊、堆垛為一體的自動化加工生產(chǎn)線。在柔性化鈑金產(chǎn)線排程中,包括成本單價信息、生產(chǎn)線信息以及訂單信息。根據(jù)鈑金實際生產(chǎn)狀況,信息部分內(nèi)容擬定分別如表1、2、3 所示。

成本單價信息以人工成本為例,表示可選時間段內(nèi)所有時間的人工成本單價。本例中可選時間段為288 h,各時刻的單價如表1 所示。

表1 成本單價信息

擬定生產(chǎn)線由3 條相同的鈑金生產(chǎn)線組成,可加工5 種不同類型的產(chǎn)品,生產(chǎn)線信息包括工作功耗、啟動功耗、停止功耗及物種產(chǎn)品可生產(chǎn)容量等,部分參數(shù)如表2 所示,大小為功耗的量化表示。

表2 生產(chǎn)線信息

擬定任務(wù)有50 個訂單,訂單信息包括訂單序號、生產(chǎn)所需總時長、訂期、交期、任務(wù)功耗等,部分參數(shù)如表3 所示。

表3 訂單信息

根據(jù)上述問題事實采用所提出的優(yōu)化排程方法求解得出的最優(yōu)方案甘特圖如圖5 所示,其中橫、縱軸分別表示時間、訂單序號,不同圖標表示不同加工生產(chǎn)線。從生產(chǎn)排程的甘特圖結(jié)果可以看出,50 個訂單任務(wù)生產(chǎn)計劃全在對應(yīng)要求的定期和交期之間,滿足生產(chǎn)時間要求。排程優(yōu)化求解時間在6 s內(nèi)達到穩(wěn)定,滿足及時性要求。

圖5 排程結(jié)果甘特圖

約束匹配得分情況如表4、5 所示,從得分結(jié)果和得分明細中可以看出,硬分數(shù)為0,沒有生產(chǎn)線加工容量不足的情況,方案可行;盡早生產(chǎn)約束得分次數(shù)為50 次,50 個訂單均有開始時間,符合實際情況;中等分數(shù)中啟停次數(shù)為24,小于訂單數(shù)50,符合優(yōu)化方向。

表4 得分結(jié)果

鄰域搜索法的搜索尋優(yōu)過程如圖6 所示,分別表示中等分數(shù)和軟分數(shù)的優(yōu)化過程。由于本例中以中等約束作為優(yōu)化目標,故尋優(yōu)過程應(yīng)以中等分數(shù)的優(yōu)化為主,由圖6 可得,搜索路徑迅速收斂。

表5 得分明細

圖6 搜索優(yōu)化過程

5 結(jié)論

本文針對鈑金加工訂單呈現(xiàn)多品種、小批量離散化特征的問題,研究了柔性化鈑金產(chǎn)線的生產(chǎn)排程優(yōu)化方法。引入Drools 規(guī)則引擎,以在交貨日期前完成生產(chǎn)為基本約束,以最小化成本及設(shè)備損耗為主要目標,依據(jù)實際生產(chǎn)狀況建立了包括盡早生產(chǎn)的三級生產(chǎn)約束并進行了數(shù)學(xué)模型表達。研究規(guī)劃問題三要素,結(jié)合Drools 規(guī)則引擎和鄰域搜索法形成優(yōu)化排程方法。通過實例的運行對方法的有效性進行了驗證,結(jié)果表明,訂單按期交貨率達到100%,并且符合實際尋優(yōu)方向。

通過對優(yōu)化排程方法有效性的驗證表明,本文所提出的方法對現(xiàn)代柔性化鈑金產(chǎn)線的生產(chǎn)排程要求有較好的滿足情況,可發(fā)揮出柔性化產(chǎn)線的產(chǎn)能優(yōu)勢。本文所提出的基于Drools 規(guī)則引擎匹配約束的尋優(yōu)求解方式對于同類型的問題也提供了新的思路。

未來研究可以引入不同算法對比,還可通過在柔性化鈑金產(chǎn)線上的實際運行,考慮突發(fā)干擾事件的影響。