馬麗萌，喬 非，馬玉敏，劉 鵑

(同濟(jì)大學(xué) 電子與信息工程學(xué)院，上海 201804)

0 引言

隨著信息科技的迅速發(fā)展，制造業(yè)已經(jīng)成為國民經(jīng)濟(jì)的支柱產(chǎn)業(yè)。生產(chǎn)調(diào)度問題是制造業(yè)管理的核心內(nèi)容，也是提高企業(yè)核心競爭力的關(guān)鍵，其研究主要包括基于智能搜索和基于調(diào)度規(guī)則兩種方法。智能搜索算法如禁忌搜索[1]、蟻群算法[2]、遺傳算法(Genetic Algorithm, GA)[3]、人工免疫系統(tǒng)[4]等，在解決經(jīng)典的作業(yè)車間和流水車間調(diào)度問題時(shí)可以找到良好的最優(yōu)近似解，然而當(dāng)問題規(guī)模較大時(shí)計(jì)算成本巨大，不能滿足智能車間實(shí)時(shí)調(diào)度的要求。相比之下，調(diào)度規(guī)則易于實(shí)現(xiàn)、求解的時(shí)間復(fù)雜度較低并能對(duì)動(dòng)態(tài)變化及時(shí)做出響應(yīng)[5-6]，比較適合求解智能車間這種高度復(fù)雜動(dòng)態(tài)環(huán)境下的調(diào)度問題。然而傳統(tǒng)的簡單調(diào)度規(guī)則只利用了有限的生產(chǎn)調(diào)度過程信息，其優(yōu)化性能一般較差[7]。一些研究人員針對(duì)經(jīng)典的作業(yè)車間問題研究了組合調(diào)度規(guī)則，這些規(guī)則是單一調(diào)度規(guī)則的啟發(fā)式組合，旨在繼承前者優(yōu)點(diǎn)，研究結(jié)果表明，組合調(diào)度規(guī)則在調(diào)度質(zhì)量方面好于單個(gè)調(diào)度規(guī)則[7-8]。

根據(jù)組合規(guī)則的結(jié)構(gòu)特征，可將其分為線性加權(quán)組合式調(diào)度規(guī)則和非線性組合調(diào)度規(guī)則。前者是根據(jù)具體的車間環(huán)境，以不同的權(quán)重對(duì)簡單規(guī)則進(jìn)行線性組合，這種方法的缺點(diǎn)是受限于所選調(diào)度規(guī)則的調(diào)度性能，而且無法解決規(guī)則之間關(guān)聯(lián)性問題；非線性組合規(guī)則對(duì)規(guī)則的組合不局限于簡單的線性加權(quán)，具有更靈活的形式，通過合適的組合可以改善線性加權(quán)規(guī)則的局限性。

組合規(guī)則的設(shè)計(jì)方法包括手工方法和智能方法。早期大多使用手工方法對(duì)已有規(guī)則進(jìn)行組合，所得到的規(guī)則形式簡潔，便于理解，但其需要根據(jù)領(lǐng)域知識(shí)進(jìn)行手工設(shè)計(jì)，過程十分耗時(shí)，而且所生成的規(guī)則一般不具普適性。用于調(diào)度規(guī)則設(shè)計(jì)的智能方法主要有進(jìn)化算法[9]、數(shù)據(jù)挖掘[10]、遺傳規(guī)劃(Genetic Programming, GP)[11]等，其中遺傳規(guī)劃的學(xué)習(xí)機(jī)制簡單且表現(xiàn)形式靈活，比較適合對(duì)調(diào)度規(guī)則進(jìn)行挖掘設(shè)計(jì)。Nguyen等[12]采用GP算法為單目標(biāo)作業(yè)車間調(diào)度問題生成新調(diào)度規(guī)則，并通過實(shí)驗(yàn)驗(yàn)證了集成系統(tǒng)和機(jī)器屬性的表示可以提高演化規(guī)則的質(zhì)量；Tay等[13]采用GP算法生成的調(diào)度規(guī)則解決多目標(biāo)柔性作業(yè)車間問題；Durasevi?等[14]采用GP算法為具有隨機(jī)性能指標(biāo)的無關(guān)機(jī)器環(huán)境的并行機(jī)調(diào)度問題自動(dòng)設(shè)計(jì)調(diào)度規(guī)則，實(shí)驗(yàn)結(jié)果表明，采用GP算法生成的調(diào)度規(guī)則的整體性能優(yōu)于傳統(tǒng)調(diào)度規(guī)則。

上述方法在解決以智能車間為代表的高復(fù)雜度生產(chǎn)系統(tǒng)的調(diào)度問題時(shí)具有局限性，主要表現(xiàn)在：①上述方法大多采用數(shù)學(xué)模型對(duì)生產(chǎn)環(huán)境建模，為了方便建模而對(duì)一些環(huán)境特性進(jìn)行簡化或忽略，使得約束條件相對(duì)實(shí)際環(huán)境有很大程度的松弛，例如將車間的初始狀態(tài)設(shè)為零初始狀態(tài)，導(dǎo)致對(duì)實(shí)際生產(chǎn)車間的建模不準(zhǔn)確，而且對(duì)不同的調(diào)度目標(biāo)往往需要重新設(shè)計(jì)測試用例；②由于智能車間具有結(jié)構(gòu)復(fù)雜、單/批量加工方式交錯(cuò)、隨機(jī)性等特點(diǎn)，導(dǎo)致其難以用數(shù)學(xué)模型描述。

針對(duì)上述問題，本文將智能車間離散仿真[15]與GP算法結(jié)合，以避免對(duì)智能車間調(diào)度問題進(jìn)行數(shù)學(xué)建模；并以簡單啟發(fā)式規(guī)則為基礎(chǔ)，提出一種組合式調(diào)度規(guī)則挖掘方法。該方法挖掘得到的規(guī)則在保留簡單啟發(fā)式規(guī)則復(fù)雜度低、易于實(shí)施的同時(shí)，優(yōu)化制造系統(tǒng)整體性能，滿足了智能車間生產(chǎn)調(diào)度規(guī)模大、復(fù)雜性高的特點(diǎn)。為了進(jìn)一步避免GP進(jìn)化過程產(chǎn)生的無意義調(diào)度規(guī)則所帶來的挖掘時(shí)間成本，本文對(duì)構(gòu)成GP算法的終止集進(jìn)行歸一化改進(jìn)。

1 基于SO-GP的調(diào)度規(guī)則挖掘框架

1.1 調(diào)度規(guī)則的表達(dá)

根據(jù)優(yōu)化的調(diào)度目標(biāo)分類，簡單啟發(fā)式規(guī)則一般包括基于工件的等待時(shí)間、基于工件的加工周期、基于工件的交貨期和基于生產(chǎn)線均衡負(fù)載等規(guī)則，這些簡單的啟發(fā)式規(guī)則利用有限的生產(chǎn)調(diào)度過程信息對(duì)工件的加工順序進(jìn)行排序，例如最早交貨期(Earliest Due Date，EDD)是通過對(duì)工件的交貨期進(jìn)行排序，優(yōu)先選擇具有最早交貨期的工件進(jìn)行加工。

本文組合規(guī)則由函數(shù)節(jié)點(diǎn)和終止符節(jié)點(diǎn)以樹的結(jié)構(gòu)構(gòu)成。其中終止符節(jié)點(diǎn)是構(gòu)成二叉樹的葉子節(jié)點(diǎn)，在文中表示為簡單啟發(fā)式調(diào)度規(guī)則；函數(shù)節(jié)點(diǎn)為構(gòu)成二叉樹的非葉子節(jié)點(diǎn)，用于將簡單規(guī)則組合起來，包括加、減、乘、除等操作函數(shù)。如圖1所示為樹形組合規(guī)則的例子，其中EDD、最短剩余加工時(shí)間(Smallest Remaining Processing Time, SRPT)是簡單啟發(fā)式規(guī)則，對(duì)該二叉樹進(jìn)行中序遍歷，得到組合規(guī)則的表達(dá)式為EDD+(EDD-SRPT)。

1.2 智能車間調(diào)度規(guī)則挖掘框架

基于仿真優(yōu)化與遺傳規(guī)劃(Simulation Optimization-Genetic Programming，SO-GP)的智能車間調(diào)度規(guī)則挖掘框架如圖2所示，可劃分為調(diào)度規(guī)則離線挖掘模塊和在線調(diào)度模塊兩部分，本文主要對(duì)調(diào)度規(guī)則離線挖掘模塊進(jìn)行研究，以優(yōu)化調(diào)度規(guī)則庫，支持后期的在線調(diào)度。離線挖掘過程包括基于GP算法的挖掘模塊和基于SO適應(yīng)度值的評(píng)價(jià)模塊。

GP算法挖掘模塊主要完成組合規(guī)則挖掘的進(jìn)化過程。首先確定用于生成調(diào)度規(guī)則(GP個(gè)體)的終止符集和函數(shù)集，對(duì)其編碼生成樹形結(jié)構(gòu)的組合調(diào)度規(guī)則；然后初始化種群并將生成的規(guī)則輸入SO適應(yīng)度值評(píng)價(jià)模塊得到對(duì)應(yīng)的性能指標(biāo)，將其作為GP算法個(gè)體的適應(yīng)度值來促進(jìn)種群進(jìn)化(包括個(gè)體的選擇和復(fù)制、交叉、變異等操作)，完成進(jìn)化后即得到優(yōu)異的組合調(diào)度規(guī)則。

基于SO適應(yīng)度值評(píng)價(jià)模塊對(duì)GP算法生成的組合規(guī)則適應(yīng)度進(jìn)行評(píng)價(jià)。根據(jù)智能車間的生產(chǎn)線數(shù)據(jù)生成智能車間生產(chǎn)線仿真模型，通過將模型的調(diào)度規(guī)則設(shè)置為GP算法挖掘模塊生成的組合調(diào)度規(guī)則，得到某一生產(chǎn)狀態(tài)下生成的各個(gè)調(diào)度規(guī)則對(duì)應(yīng)的性能指標(biāo)。

2 SO-GP算法設(shè)計(jì)

GP算法是Koza在1992年借鑒GA提出的一種進(jìn)化計(jì)算方法。在GP算法設(shè)計(jì)中，個(gè)體的構(gòu)造采用樹形結(jié)構(gòu)，由終止符節(jié)點(diǎn)和函數(shù)節(jié)點(diǎn)構(gòu)成，相比于GA固定長度的二進(jìn)制字符串，它是一種更為靈活的可變分層結(jié)構(gòu)，能夠獨(dú)立表示各個(gè)變量之間的算術(shù)或邏輯關(guān)系。GP算法設(shè)計(jì)包括函數(shù)集和終止符集的確定、種群進(jìn)化過程以及適應(yīng)度函數(shù)的確定。

2.1 組合規(guī)則的構(gòu)成

2.1.1 終止符集的確定

啟發(fā)式調(diào)度規(guī)則是車間調(diào)度問題中常用的調(diào)度方法，它是按照工件特征屬性集中的某個(gè)屬性或多個(gè)屬性的組合來計(jì)算得到工件的優(yōu)先級(jí)。本文對(duì)新的調(diào)度規(guī)則的挖掘是基于簡單的啟發(fā)式規(guī)則，將簡單啟發(fā)式規(guī)則作為終止符集，通過函數(shù)集中的函數(shù)操作產(chǎn)生新的調(diào)度規(guī)則。本文所用終止符集如表1所示。

表1 終止符集

然而，直接使用這些規(guī)則作為終止符集，在進(jìn)行函數(shù)操作時(shí)可能會(huì)生成沒有意義的規(guī)則。例如生成的規(guī)則為EDD+SRPT*EDD，加法操作符兩邊的量綱不統(tǒng)一，理論上無法進(jìn)行加法操作，雖然在進(jìn)化過程中這些無意義的規(guī)則必然會(huì)淘汰，但是會(huì)影響整個(gè)進(jìn)化的過程。為了避免這種情況，本文對(duì)這些簡單規(guī)則進(jìn)行了歸一化處理，如式(1)所示，將工件i在該規(guī)則下的優(yōu)先級(jí)作為該規(guī)則的屬性值參與計(jì)算。

(1)

式中：kmax，kmin分別為待排序工件中由簡單調(diào)度規(guī)則確定的工件屬性k的最大值和最小值；ki為工件i的屬性k的值。Rk,i為經(jīng)過歸一化處理后的簡單啟發(fā)式調(diào)度規(guī)則，即歸一化后，由屬性k確定的工件i的優(yōu)先級(jí)。

以SRPT規(guī)則為例，歸一化后的SRPT規(guī)則所確定的工件i的優(yōu)先級(jí)為

式中：RPTmax，RPTmin分別為待排序工件中剩余加工時(shí)間的最大值和最小值；RPTi為工件i的剩余加工時(shí)間；RRPT,i為歸一化后，由屬性RPT確定的工件i的優(yōu)先級(jí)。

2.1.2 函數(shù)集的確定

與GP算法解決其他的優(yōu)化問題類似，本文函數(shù)集選擇加減乘除4種基本操作符以及一些規(guī)則中常見的最大、最小函數(shù)，其中當(dāng)除法操作的除數(shù)為0時(shí)返回1，其他情況返回正常計(jì)算值。

2.2 種群的進(jìn)化過程

2.2.1 初始種群的生成

初始種群的生成方法有多種，常用的有完全法、生長法和混合法3種[16]。其中，完全法保證生成的個(gè)體擴(kuò)展到最大深度，生長法使生成的個(gè)體具有多樣的結(jié)構(gòu)，混合法則綜合了完全法和生長法的優(yōu)點(diǎn)。因此，本文采用混合法產(chǎn)生初始種群，即初始種群中的一半個(gè)體用完全法生成，另一半個(gè)體用生長法生成。

GP個(gè)體用二叉樹的結(jié)構(gòu)表示，個(gè)體生成過程：在函數(shù)集和終止符集中隨機(jī)產(chǎn)生根節(jié)點(diǎn)，然后隨機(jī)產(chǎn)生子樹作為根節(jié)點(diǎn)的子節(jié)點(diǎn)，子節(jié)點(diǎn)若為終止符，則終止該分支的生長；若為函數(shù)操作符，則繼續(xù)生長；以此類推，直至達(dá)到最大深度。

2.2.2 遺傳操作

GP算法進(jìn)化過程包括個(gè)體的選擇、復(fù)制、交叉、變異等操作。本文采用競爭選擇法對(duì)種群進(jìn)行選擇和復(fù)制，同時(shí)為了保證最優(yōu)的個(gè)體能夠生存到下一代，采用精英保留策略保留最優(yōu)個(gè)體。

(1)交叉操作 針對(duì)復(fù)制的每一對(duì)個(gè)體，若產(chǎn)生一個(gè)隨機(jī)數(shù)小于交叉概率，則執(zhí)行交叉操作，即在該對(duì)個(gè)體中隨機(jī)選取某節(jié)點(diǎn)作為交叉點(diǎn)，相互交換以交叉點(diǎn)為根節(jié)點(diǎn)的子樹，得到兩個(gè)子代。

(2)變異操作 針對(duì)每一個(gè)個(gè)體，若產(chǎn)生一個(gè)隨機(jī)數(shù)小于變異概率，則執(zhí)行變異操作，即在該個(gè)體中隨機(jī)選擇除根節(jié)點(diǎn)之外的節(jié)點(diǎn)作為變異點(diǎn)，刪掉以變異點(diǎn)為根節(jié)點(diǎn)的子樹，然后在變異點(diǎn)隨機(jī)生成新的子樹，新子樹的深度不能超過最大深度。

2.3 基于SO的適應(yīng)度函數(shù)設(shè)計(jì)

本文采用的SO方法是將仿真的輸出作為優(yōu)化算法中的評(píng)價(jià)值，其主體流程如圖2中基于SO的適應(yīng)度評(píng)價(jià)部分。將仿真的輸出輸入優(yōu)化模塊，在優(yōu)化算法中通過比較仿真運(yùn)行得到的輸出結(jié)果來判斷解的優(yōu)劣，從而做出進(jìn)一步優(yōu)化。由于離散事件建模方法在智能車間生產(chǎn)線建模方面有較大優(yōu)勢，本文通過對(duì)智能車間生產(chǎn)線建立離散事件仿真模型來配合GP算法挖掘調(diào)度規(guī)則。

2.3.1 智能車間離散事件仿真模型的設(shè)計(jì)

離散事件仿真模型的設(shè)計(jì)包括數(shù)據(jù)模塊設(shè)計(jì)和仿真模塊設(shè)計(jì)。數(shù)據(jù)模塊設(shè)計(jì)是將生產(chǎn)線車間模型數(shù)據(jù)經(jīng)過分類處理后整理成幾個(gè)基本數(shù)據(jù)表，如表2所示；仿真模塊主要通過對(duì)數(shù)據(jù)模塊提供的數(shù)據(jù)進(jìn)行建模，描述整個(gè)生產(chǎn)線加工的邏輯關(guān)系，并對(duì)事件進(jìn)行控制，包括數(shù)據(jù)導(dǎo)入模塊、初始化模塊、流程控制模塊、調(diào)度規(guī)則模塊、數(shù)據(jù)統(tǒng)計(jì)輸出模塊等。為了能與GP算法結(jié)合，除了上述模塊完成生產(chǎn)線的基本流程外，還需用函數(shù)運(yùn)算模塊對(duì)GP算法的個(gè)體進(jìn)行解碼。

表2 生產(chǎn)線車間模型基本數(shù)據(jù)表

2.3.2 適應(yīng)度函數(shù)

GP進(jìn)化過程中每代得到的表達(dá)為樹形的個(gè)體可以通過中序遍歷解碼成相應(yīng)的調(diào)度規(guī)則。本文將解碼得到的規(guī)則輸入智能車間離散事件仿真模型來計(jì)算個(gè)體適應(yīng)度值，具體過程為：每次計(jì)算前先對(duì)仿真模型進(jìn)行初始化；當(dāng)有機(jī)器空閑時(shí)，將該機(jī)器的工件等待隊(duì)列按照所輸入的規(guī)則計(jì)算優(yōu)先級(jí)并排序，對(duì)優(yōu)先級(jí)最高的工件進(jìn)行加工；經(jīng)過一個(gè)調(diào)度周期后，將得到的性能指標(biāo)作為個(gè)體適應(yīng)度值，個(gè)體的適應(yīng)度越好，被選擇并保存到下一代種群中的概率越大；照此規(guī)則不斷進(jìn)行優(yōu)勝劣汰。

本文智能車間生產(chǎn)線模型與GP算法之間通過數(shù)據(jù)庫進(jìn)行數(shù)據(jù)交互。每當(dāng)GP算法進(jìn)化得到一代個(gè)體，就觸發(fā)仿真模型從數(shù)據(jù)庫讀取生成的規(guī)則并計(jì)算適應(yīng)度值。對(duì)于GP種群個(gè)體適應(yīng)度值的計(jì)算，由于進(jìn)化過程中每一個(gè)GP個(gè)體都要輸入到仿真模型中計(jì)算適應(yīng)度值，而仿真模型一次只能計(jì)算一個(gè)個(gè)體的適應(yīng)度值，為了提高計(jì)算效率，本文采用并發(fā)計(jì)算方式，即同時(shí)啟動(dòng)多個(gè)仿真模型計(jì)算種群中不同個(gè)體的適應(yīng)度值。另外，因?yàn)槊恳淮鶪P種群規(guī)模均有限且確定，所以仿真可以計(jì)算出每一代個(gè)體的適應(yīng)度值。然后，將計(jì)算得到的每代個(gè)體適應(yīng)度值通過數(shù)據(jù)庫反饋給GP算法進(jìn)行優(yōu)勝劣汰，如此往復(fù)，直到滿足終止條件，最后生成優(yōu)異的規(guī)則。

從上述過程可以看出，雖然仿真優(yōu)化的方式較費(fèi)時(shí)，但是SO-GP算法的挖掘過程可以離線進(jìn)行，挖掘出的優(yōu)異規(guī)則在實(shí)際在線使用時(shí)與傳統(tǒng)簡單規(guī)則的時(shí)間成本相差不多，能夠滿足智能車間調(diào)度的實(shí)時(shí)性需求。GP算法設(shè)計(jì)流程圖如圖3所示。

3 實(shí)驗(yàn)設(shè)計(jì)和結(jié)果分析

3.1 仿真案例的設(shè)計(jì)

本文采用MiniFAB模型作為仿真模型進(jìn)行實(shí)驗(yàn)驗(yàn)證。MiniFAB模型是Kempf博士由Intel公司的半導(dǎo)體生產(chǎn)線提煉出的模型[17]，其由3個(gè)加工區(qū)、5臺(tái)設(shè)備組成，共有6個(gè)加工工序，工藝流程如圖4所示，其中Ma，Mb為多卡并行加工設(shè)備，最大加工批量為4卡。模型層運(yùn)行局部圖如圖5所示，解碼模塊的邏輯控制圖如圖6所示。

3.2 實(shí)驗(yàn)參數(shù)設(shè)置

(1)仿真模型參數(shù)的設(shè)置

MiniFAB模型每次的仿真時(shí)間為30天，設(shè)置生產(chǎn)線上生產(chǎn)3種產(chǎn)品，以固定間隔投料方式進(jìn)行投料，每種產(chǎn)品的投料數(shù)在[10,20]之間均勻分布。為了提高所挖掘規(guī)則的魯棒性，隨機(jī)生成5個(gè)不同的生產(chǎn)線初始狀態(tài)構(gòu)成訓(xùn)練集，對(duì)組合調(diào)度規(guī)則進(jìn)行挖掘。另外，為了提高種群的進(jìn)化速度，采用并發(fā)計(jì)算的方式，在仿真層同時(shí)運(yùn)行多個(gè)生產(chǎn)線仿真模型，每次訓(xùn)練向每個(gè)仿真模型輸入同一條生產(chǎn)線狀態(tài)數(shù)據(jù)來初始化仿真模型生產(chǎn)狀態(tài)。

(2)GP算法參數(shù)的設(shè)置

采用數(shù)據(jù)包絡(luò)分析效率評(píng)價(jià)[18]方法，對(duì)常見的簡單啟發(fā)式規(guī)則的效率(啟發(fā)式規(guī)則對(duì)多種生產(chǎn)性能的兼顧程度)進(jìn)行評(píng)價(jià)，根據(jù)評(píng)價(jià)結(jié)果選用EDD，SRPT，CR，F(xiàn)SVCT 4個(gè)啟發(fā)式規(guī)則構(gòu)成本案例的終止符集。經(jīng)過測試，GP算法的參數(shù)設(shè)置如表3所示。其中，為了避免所生成的規(guī)則過于復(fù)雜，控制初始種群中個(gè)體的最大深度不超過3。

表3 GP算法的參數(shù)設(shè)置

3.3 實(shí)驗(yàn)結(jié)果與分析

3.3.1 對(duì)終止符歸一化的分析

為了驗(yàn)證對(duì)終止符即簡單規(guī)則進(jìn)行歸一化處理的必要性，本文分別以平均加工周期(Mean Cycle Time, MCT)最小與準(zhǔn)時(shí)交貨率(On-time Delivery Rate, ODR)最大為調(diào)度目標(biāo)設(shè)計(jì)實(shí)驗(yàn)進(jìn)行分析。

(1)以平均加工周期最短為目標(biāo)

以MiniFAB為模型，MCT最短為目標(biāo)，分別對(duì)終止符進(jìn)行和不進(jìn)行歸一化處理，迭代相同次數(shù)后，每種情況下各挖掘3個(gè)GP規(guī)則，GP表示進(jìn)行歸一化處理后生成的規(guī)則，GP_N表示不進(jìn)行歸一化處理生成的規(guī)則，如表4所示。

表4 以MCT最短為目標(biāo)挖掘的調(diào)度規(guī)則

在MiniFAB仿真模型上遍歷這6種調(diào)度規(guī)則，記錄30天后采用不同調(diào)度規(guī)則產(chǎn)生的MCT的性能。繪制20條測試樣本(即20個(gè)不同的生產(chǎn)線初始狀態(tài))在不同調(diào)度規(guī)則下的生產(chǎn)性能對(duì)比圖，如圖7所示，其MCT指標(biāo)平均值如表5所示。

表5 不同調(diào)度規(guī)則下的MCT指標(biāo)平均值 h

(2)以準(zhǔn)時(shí)交貨率最大為目標(biāo)

以MiniFAB為實(shí)驗(yàn)?zāi)Ｐ?，ODR最大為目標(biāo)，分別通過對(duì)終止符集進(jìn)行和不進(jìn)行歸一化處理生成規(guī)則，如表6所示。

表6 以O(shè)DR最大為目標(biāo)挖掘的調(diào)度規(guī)則

在MiniFAB仿真模型上遍歷這6種調(diào)度規(guī)則，記錄30天后采用不同調(diào)度規(guī)則產(chǎn)生的ODR的性能。繪制20條測試樣本在不同調(diào)度規(guī)則下的ODR指標(biāo)，如圖8所示，其ODR指標(biāo)的平均值如表7所示。

表7 不同調(diào)度規(guī)則下的ODR指標(biāo)平均值 %

由圖7和圖8可以看出，在相同迭代次數(shù)下，對(duì)于不同的調(diào)度目標(biāo)，終止符集進(jìn)行歸一化處理后挖掘出的調(diào)度規(guī)則比不進(jìn)行歸一化處理挖掘出的調(diào)度規(guī)則整體性能都要好，而3個(gè)歸一化處理后挖掘的調(diào)度規(guī)則在性能方面均較接近，3個(gè)沒有歸一化處理挖掘出的調(diào)度規(guī)則的性能也較接近。從性能的平均值來看，對(duì)于MCT來說，歸一化處理后挖掘出的規(guī)則比不進(jìn)行歸一化挖掘出的規(guī)則性能提高23.6%；對(duì)于ODR，歸一化處理后挖掘出的規(guī)則比不進(jìn)行歸一化挖掘出的規(guī)則性能提高7.5%，以上結(jié)果說明對(duì)終止符集進(jìn)行歸一化處理能夠有效提高GP算法的挖掘效率。

3.3.2 對(duì)長期性能指標(biāo)的分析

由于對(duì)終止符集進(jìn)行歸一化處理的有效性，以下對(duì)不同調(diào)度目標(biāo)下的調(diào)度規(guī)則挖掘均采用歸一化的終止符集。為驗(yàn)證SO-GP算法挖掘的調(diào)度規(guī)則對(duì)提高長期指標(biāo)的有效性，本文分別以MCT最小和ODR最大為目標(biāo)設(shè)計(jì)實(shí)驗(yàn)進(jìn)行分析。

(1)以平均加工周期最短為目標(biāo)

以MiniFAB為實(shí)驗(yàn)?zāi)Ｐ?，以MCT最短為目標(biāo)進(jìn)行規(guī)則挖掘，選取表4中的3個(gè)生成規(guī)則GP1，GP2，GP3。

在MiniFAB仿真模型上遍歷8種調(diào)度規(guī)則，即3種GP生成的規(guī)則+4種候選基本規(guī)則+線性組合式調(diào)度規(guī)則，線性組合調(diào)度規(guī)則的參數(shù)權(quán)重為SRPT∶EDD∶CR∶FSVCT=0.64∶0.10∶0.22∶0.04，權(quán)重的確定方法參考文獻(xiàn)[19]，確定記錄30天后采用不同調(diào)度規(guī)則所產(chǎn)生的MCT的性能。20條測試樣本在不同調(diào)度規(guī)則下的MCT性能對(duì)比如圖9所示，其MCT指標(biāo)平均值如表8所示。

表8 不同調(diào)度規(guī)則下的MCT指標(biāo)平均值 h

由圖9可見，對(duì)于MCT，由GP算法挖掘出的3個(gè)調(diào)度規(guī)則在性能方面比較接近，而且性能比簡單啟發(fā)式規(guī)則和線性加權(quán)組合規(guī)則的性能整體好。由表8可見，對(duì)于MCT，GP1規(guī)則的性能比SRPT規(guī)則提高33%，比CR規(guī)則提高45%，比EDD規(guī)則提高54%，比FSVCT規(guī)則提高58%，比線性組合式提高30%。

(2)以準(zhǔn)時(shí)交貨率最大為目標(biāo)

以MiniFAB為實(shí)驗(yàn)?zāi)Ｐ?，以O(shè)DR最大為目標(biāo)進(jìn)行規(guī)則挖掘，選取表6中的3個(gè)生成規(guī)則GP1，GP2，GP3。

與本節(jié)實(shí)驗(yàn)(1)一樣，在MiniFAB仿真模型上遍歷這8種調(diào)度規(guī)則(其中線性組合調(diào)度規(guī)則的參數(shù)權(quán)重為SRPT∶EDD∶CR∶FSVCT=0.23∶0.56∶0.09∶0.12)，記錄30天后采用不同調(diào)度規(guī)則的ODR性能。20條測試樣本在不同調(diào)度規(guī)則下的ODR性能對(duì)比如圖10所示，其ODR平均值如表9所示。

表9 不同調(diào)度規(guī)則下的ODR指標(biāo)平均值 %

由圖10可見，對(duì)于ODR，由GP算法挖掘出的3個(gè)調(diào)度規(guī)則在性能方面比較接近，而且性能整體上比簡單啟發(fā)式規(guī)則和線性加權(quán)組合規(guī)則好。由表9可見，對(duì)于ODR，GP1規(guī)則性能比SRPT規(guī)則提高5.17%，比EDD規(guī)則提高5.76%，比CR規(guī)則提高8.62%，比FSVCT規(guī)則提高5.72%，比線性組合式規(guī)則提高3.43%。

從以上分析可以看出，GP算法挖掘出的調(diào)度規(guī)則對(duì)長期性能指標(biāo)優(yōu)化具有有效性。

3.3.3 對(duì)短期性能指標(biāo)的分析

為驗(yàn)證SO-GP算法挖掘的調(diào)度規(guī)則對(duì)短期性能指標(biāo)優(yōu)化的有效性，分別以日平均移動(dòng)步數(shù)(Mean Daily Movement, MDayMOV)和瓶頸設(shè)備利用率最大為目標(biāo)設(shè)計(jì)實(shí)驗(yàn)進(jìn)行分析。

(1)以日均移動(dòng)步數(shù)最大為目標(biāo)

以MDayMOV最大為目標(biāo)進(jìn)行規(guī)則的挖掘，最后選取所生成的3個(gè)優(yōu)異規(guī)則如表10所示。

表10 以MDayMOV最大為目標(biāo)挖掘的調(diào)度規(guī)則

在MiniFAB仿真模型上遍歷以下8種調(diào)度規(guī)則，即3種GP生成的規(guī)則+4種候選基本規(guī)則+線性組合調(diào)度規(guī)則，線性組合調(diào)度規(guī)則的參數(shù)權(quán)重為SRPT∶EDD∶CR∶FSVCT=0∶0∶0∶1，相當(dāng)于FSVCT規(guī)則，記錄8 h后采用不同調(diào)度規(guī)則產(chǎn)生的MDayMOV性能。20條測試樣本在不同調(diào)度規(guī)則下的MDayMOV性能對(duì)比如圖11所示，其MDayMOV指標(biāo)平均值如表11所示。

表11 不同調(diào)度規(guī)則下的MDayMov指標(biāo)的平均值

由圖11可以看出，對(duì)于MDayMOV，由GP算法挖掘出的3個(gè)調(diào)度規(guī)則在性能方面比較接近，而且整體上比簡單啟發(fā)式及線性加權(quán)規(guī)則的性能好。由表11可見，對(duì)于MDayMOV，GP1規(guī)則的性能比SRPT提高20.76%，比EDD規(guī)則提高11.67%，比CR規(guī)則提高19.97%，比FSVCT規(guī)則提高6.91%，比線性加權(quán)規(guī)則提高6.91%。

(2)以瓶頸設(shè)備利用率最大為目標(biāo)

以MiniFAB為實(shí)驗(yàn)?zāi)Ｐ?，瓶頸設(shè)備Me的利用率(OEE_Me)最大為目標(biāo)進(jìn)行規(guī)則挖掘，最后選取所生成的3個(gè)優(yōu)異規(guī)則如表12所示。

表12 以O(shè)EE_Me最大為目標(biāo)挖掘的調(diào)度規(guī)則

與本節(jié)實(shí)驗(yàn)(1)一樣，在MiniFAB仿真模型上遍歷這8種調(diào)度規(guī)則(其中線性組合調(diào)度規(guī)則的參數(shù)權(quán)重為SRPT∶EDD∶CR∶FSVCT=0.22∶0.33∶0.21∶0.24)，記錄8 h后采用不同調(diào)度規(guī)則產(chǎn)生的OEE_Me的性能。20條測試樣本在不同調(diào)度規(guī)則下的OEE_Me性能對(duì)比如圖12所示，其OEE_Me指標(biāo)平均值如表13所示。

表13 不同調(diào)度規(guī)則下的OEE_Me指標(biāo)的平均值 %

由圖12可以看出，對(duì)于瓶頸設(shè)備利用率，由GP算法挖掘出的3個(gè)調(diào)度規(guī)則在性能方面比較接近，雖然性能整體上比簡單啟發(fā)式規(guī)則和線性加權(quán)規(guī)則好，但是提高并不明顯。由表13可見，對(duì)于瓶頸設(shè)備利用率，GP1規(guī)則的性能比SRPT規(guī)則提高1.08%，比EDD規(guī)則提高0.33%，比CR規(guī)則提高1.19%，比FSVCT規(guī)則提高0.83%，比線性加權(quán)規(guī)則提高0.61%。從平均值來看，GP挖掘的規(guī)則對(duì)性能的提高也不明顯，這是因?yàn)槠款i設(shè)備的利用率在任何規(guī)則下的性能都很高，而GP在其性能已經(jīng)很高的情況下仍然能夠有所提升，不過這種性能提升空間不大的生產(chǎn)指標(biāo)在多數(shù)情況下沒有提升的必要。

從以上分析可以看出，SO-GP算法挖掘出的調(diào)度規(guī)則對(duì)短期性能指標(biāo)的提高具有有效性。

本文采用GP算法與仿真相結(jié)合的方法對(duì)調(diào)度規(guī)則進(jìn)行挖掘。GP算法計(jì)算量大，耗時(shí)長，而且使用仿真計(jì)算適應(yīng)度值的過程比較費(fèi)時(shí)，本文使用SO-GP算法的目的在于產(chǎn)生優(yōu)秀的新規(guī)則來補(bǔ)充在線調(diào)度規(guī)則庫，并通過離線計(jì)算獲取挖掘規(guī)則。由于挖掘出的優(yōu)異規(guī)則是有關(guān)各個(gè)屬性的多項(xiàng)式，其在在線實(shí)時(shí)調(diào)度中的時(shí)間開銷與傳統(tǒng)的簡單規(guī)則相當(dāng)，并不會(huì)明顯提升在線調(diào)度時(shí)間。

4 結(jié)束語

本文提出一種將離散仿真與遺傳規(guī)劃算法結(jié)合的調(diào)度規(guī)則挖掘方法，在挖掘過程中，為了提高GP算法的挖掘效率，對(duì)構(gòu)成GP個(gè)體的簡單規(guī)則進(jìn)行歸一化處理，并通過實(shí)驗(yàn)驗(yàn)證相同時(shí)間下，對(duì)終止符集歸一化處理后挖掘的組合規(guī)則性能優(yōu)于不作處理挖掘的規(guī)則性能。以MiniFAB為對(duì)象，分別使用MCT最短與ODR最大為調(diào)度目標(biāo)，分析SO-GP算法挖掘的規(guī)則與簡單啟發(fā)式調(diào)度規(guī)則和線性加權(quán)組合規(guī)則的性能，實(shí)驗(yàn)表明SO-GP算法能夠有效提高長期性能指標(biāo)。然后，分別以MDayMOV最大和瓶頸設(shè)備利用率最大為目標(biāo)驗(yàn)證SO-GP算法對(duì)提高短期性能指標(biāo)的有效性。由于采用SO-GP算法對(duì)調(diào)度規(guī)則的挖掘?yàn)殡x線進(jìn)行，實(shí)際中使用所挖掘的規(guī)則與傳統(tǒng)的簡單規(guī)則的時(shí)間成本相差不多，滿足智能車間實(shí)時(shí)調(diào)度的要求，為智能車間調(diào)度問題的求解提供了解決思路。

本文采用SO-GP方法挖掘調(diào)度規(guī)則時(shí)，候選規(guī)則只從常見的規(guī)則中通過效率分析得到，而實(shí)際有幾十種啟發(fā)式規(guī)則，今后可全面對(duì)其進(jìn)行分析并增加候選規(guī)則的數(shù)目。