基于非合作博弈批量調(diào)度優(yōu)化

王 蕊，周光輝

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

0 引言

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

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

1 存在競爭的任務(wù)批量調(diào)度問題描述

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

2 非合作博弈批量調(diào)度模型

2.1 批量調(diào)度策略與成本計算

1) 批量調(diào)度策略

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

2) 批次劃分

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

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

2.2 任務(wù)非合作博弈批量調(diào)度模型

任務(wù)非合作博弈批量調(diào)度模型如下式所示：

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

并受如下約束：

3 遺傳算法

3.1 編碼

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

表1 染色體編碼示意

3.2 解碼

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

1）設(shè)W為后部分染色體長度， 。

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

該工序在可選設(shè)備 上完工時刻：

設(shè)備 最早可用時刻：

任務(wù) 第b個批次完工時刻：

任務(wù) 完工時刻：

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

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

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

3.4 遺傳操作

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

4 實例仿真

4.1 初始條件

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

表2 任務(wù)基本工藝信息

表3 任務(wù)屬性信息

4.2 仿真結(jié)果與分析

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

圖1 不分批與分批批量調(diào)度甘特圖

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

5 結(jié)束語

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

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

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

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

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