王 蕊，周光輝

(1. 西安建筑科技大學 理學院，西安 710055；2. 西安交通大學 機械制造系統(tǒng)工程國家重點實驗室，西安 710049；3. 西安交通大學 機械工程學院，西安 710049)

0 引言

制造車間任務批量調度問題需要在批次劃分基礎上進行工序排序。源于不同客戶的加工任務之間存在競爭關系，各客戶都希望自身利益最大化，同時縮小其他客戶任務利益[1,2]。

本文基于博弈論[3]，建立制造車間任務非合作博弈批量調度模型，將存在競爭任務批量調度問題求解就轉化為尋求非合作博弈模型Nash均衡點。為實現(xiàn)該模型Nash均衡點有效求解，制定批量調度策略，并設計相應遺傳算法進行解算。

1 存在競爭的任務批量調度問題描述

存在競爭的車間任務批量調度問題可描述為：在某車間中，有m臺設備，N種待加工任務，不同種類任務之間存在競爭關系，每種任務批量到來且包含多道工序，任務調度受設備資源限制與總成本影響。車間任務批量調度目標是確定該車間設備上的工序加工順序和開工時間，在滿足約束條件的同時，使得各任務滿足交貨期且成本最小。同時設定如下假設條件：1）工序處于加工狀態(tài)時不能被中斷；2）所有任務機會均等，工件之間無先后約束；3）各任務輔助加工、加工時間已知；4）任務在設備間運輸時間確定。

2 非合作博弈批量調度模型

2.1 批量調度策略與成本計算

1) 批量調度策略

將批量啟動輔助加工時間與加工時間分開考慮。同種任務不同工件的同一道工序在同一臺設備上連續(xù)加工，只計算一個輔助加工時間。采用同批次任務在加工部分后立即轉向下道工序加工設備處的多次運輸策略及無間隙等量分批策略。同子批任務加工連續(xù)，以保證在工作量增加不多的情況下提高生產率。

2) 批次劃分

依據(jù)等量分批策略，當某任務工件總數(shù)量小于任務最大運輸量二倍時，該任務不分批；反之，需要分批。

3)為方便問題描述，采用如下符號和定義：(1) N為任務種類數(shù)目，m為設備總數(shù)目；(2)JNi為任務 的總工件數(shù)，JOi為任務 的總工序數(shù)，JLi為任務的子批批數(shù)，為任務的第j道工序；(3)為任務 的第b個子批次，lib為任務的子批次的工件數(shù)量，為任務的最大運輸量；(4)為工序 在設備上加工時間，twk為設備與設備間運輸時間，為任務加工完畢總運輸時間，為工序在設備上準備時間， 為子批提前完工時間， 為子批次?拖期時間；(5)為任務 的子批次工序到達設備時刻， 為子批次工序在設備完工時刻，為子批次 完工時刻，為設備最早可用時刻，為任務完工時刻，?為任務交貨期；(6)為設備加工費率， 為任務單位時間運輸費率，為任務拖期一次性懲罰金額， 為任務單位拖期時間懲罰費率，為任務提前完工單位時間庫存費率?；谏鲜龆x，則：

2.2 任務非合作博弈批量調度模型

任務非合作博弈批量調度模型如下式所示：

如果對于每一參與任務 ， 是給定其他參與人選擇的策略組合為 的情況下的最優(yōu)策略，即滿足式（4）：

并受如下約束：

3 遺傳算法

3.1 編碼

染色體編碼方式如表1 所示，染色體前部分字符表示各種類任務所對應子批批數(shù)。染色體后部分表示所有子批工序排序，每一基因用“任務編號+*+批次序號”表示。同一批次同一工序在一臺設備上連續(xù)加工，看作一道子批大工序。任務某子批基因在染色體中出現(xiàn)的次序表示該基因所代表的任務子批的工序。

表1 染色體編碼示意

3.2 解碼

采用SPT調度規(guī)則，對染色體后部分p進行解碼：

1）設W為后部分染色體長度， 。

2）取出p未排工序中第一道工序，計算該工序在所有可選加工設備上的完工時刻。

該工序在可選設備 上完工時刻：

設備 最早可用時刻：

任務 第b個批次完工時刻：

任務 完工時刻：

3.3 適應度函數(shù)

為實現(xiàn)各任務利益最大化，達到利益均衡目標，設計適應度函數(shù)如下：

對于每種任務 當滿足式（17）時，認為達到工程意義上Nash均衡：

3.4 遺傳操作

選擇操作采用比例選擇法，染色體被選中的概率與適應都成正比。交叉操作對染色體前后兩部分分別進行：前部分采用兩點交叉法，對被交叉的染色體后部分進行修復；后部分采用文獻[4]集合交叉法。變異操作也分前后兩部分進行：前部分根據(jù)各任務批次劃分過程，在其可選子批批數(shù)中隨機選取一個子批數(shù)，并對染色體后部分進行修復；后部分采用反轉變異法。

4 實例仿真

4.1 初始條件

假定有6位客戶向車間提交了6種不同種類批量加工任務,每種任務包含30個工件，該車間包含6臺設備。每位客戶都希望自己所提交的任務利益最高并且盡量使得其它客戶利益最低。表2、表3列出了任務、設備相關信息。表2中圓括弧內數(shù)字為任務工序編號，方括弧為任務工序在相應可選加工設備上的加工時間。所有工序輔助加工時間均為1，設備間運輸時間均為2，6臺設備加工費率分別為13、12、14、14、11、15。

表2 任務基本工藝信息

表3 任務屬性信息

4.2 仿真結果與分析

仿真結果如圖1所示，上方甘特圖為不分批批量調度結果，下方甘特圖為分批批量調度結果。甘特圖中每一長方條代表某種任務某一批次某道工序排序，其上方數(shù)字自上而下分別表示該長方條所代表的任務、批次、工序編號。由圖1可見，不分批調度設備處于空閑等待狀態(tài)較多，各任務完工時間較晚，分批調度設備利用率高，任務完工時間明顯早于未分批任務。

圖1 不分批與分批批量調度甘特圖

“a/b” 表示同一種制造任務的未分批數(shù)據(jù)a和分批數(shù)據(jù)b。任務 - 完工時間分別為、、、、、，總成本分別為、、、、、。在未分批調度中，各任務均拖期，且總成本遠高于分批調度。在分批調度中各任務達到Nash均衡后，均滿足各任務交貨期，且收益相當。由此可見，基于非合作博弈任務分批批量調度方案優(yōu)于不分批批量調度。

5 結束語

本文以各任務總成本最低為調度目標，考慮到輔助加工時間、運輸時間，制定相應批量調度策略，建立任務非合作博弈批量調度模型，并設計遺傳算法實現(xiàn)對該模型的解算，最后對上述方法進行仿真。仿真結果表明任務非合作博弈批量調度方法的正確性和可行性，為此類調度問題解決提供了方案和實現(xiàn)途徑。

[1] 周光輝,江平宇,黃國全.客戶競爭驅動的任務調度非合作博弈[J].機械工程學報,2006,42(7):56-61.

[2] 周光輝,王蕊,江平宇,張國海.作業(yè)車間調度的非合作博弈模型與混合自適應遺傳算法[J].西安交通大學學報，2010,44 (5):36-39.

[3] 肖條軍.博弈論及其應用[M].上海:上海三聯(lián)書店,2004:2-12.

[4] 潘全科,朱劍英.多工藝路線的批量生產調度優(yōu)化[J].機械工程學報,2004,40(4):36-39.