陳在德，陳慶新，毛 寧，劉建軍

（廣東工業(yè)大學(xué) 廣東省計(jì)算機(jī)集成制造重點(diǎn)實(shí)驗(yàn)室，廣東 廣州 510006）

0 引言

模具生產(chǎn)是典型的訂貨型（Make to Order，MTO）單件生產(chǎn)模式。模具項(xiàng)目生產(chǎn)過(guò)程存在很多不確定因素［1］：首先，模具生產(chǎn)過(guò)程中存在加工資源類選擇、加工工時(shí)、加工費(fèi)用等不確定因素，加大了項(xiàng)目進(jìn)度的預(yù)測(cè)難度；其次，大型模具生產(chǎn)中多采用單元化生產(chǎn)布局，每個(gè)生產(chǎn)單元之間的活動(dòng)會(huì)彼此干擾。

目前，國(guó)內(nèi)外有關(guān)不確定性環(huán)境下的多項(xiàng)目調(diào)度文獻(xiàn)還比較少。文獻(xiàn)［2－3］對(duì)不確定環(huán)境下的項(xiàng)目調(diào)度問(wèn)題進(jìn)行了總結(jié)分析，分別從反應(yīng)性調(diào)度、隨機(jī)性調(diào)度、模糊調(diào)度和魯棒性調(diào)度幾方面介紹了進(jìn)度計(jì)劃制定方法；文獻(xiàn)［4］運(yùn)用Q學(xué)習(xí)方法求解基于離散時(shí)間Markov鏈的動(dòng)態(tài)規(guī)劃模型；文獻(xiàn)［5］運(yùn)用活動(dòng)—模式兩步調(diào)度策略求解基于活動(dòng)成本目標(biāo)多模式資源受限的工程調(diào)度問(wèn)題；文獻(xiàn)［6－7］把Markov理論應(yīng)用在軟件項(xiàng)目計(jì)劃的隨機(jī)過(guò)程預(yù)測(cè)和決策上，得到了理想的效果。針對(duì)資源受限多項(xiàng)目 調(diào) 度 問(wèn) 題 （Resource－Constrained Multi－Project Scheduling Problem，RCMPSP），文獻(xiàn)［8］建議求解此類項(xiàng)目調(diào)度時(shí)采用多條優(yōu)先規(guī)則，并選擇不同優(yōu)先規(guī)則下求出的最優(yōu)解作為調(diào)度計(jì)劃，通過(guò)大量實(shí)驗(yàn)結(jié)果分析說(shuō)明該方法是非常可行的；文獻(xiàn)［9］建立了一種針對(duì)單模式PCMPSP的數(shù)學(xué)模型，提出一種啟發(fā)式算法解決該問(wèn)題，并給出具體的步驟與算例。針對(duì)模具項(xiàng)目調(diào)度問(wèn)題，文獻(xiàn)［10－11］研究隨機(jī)環(huán)境下的模具交貨期設(shè)置方法，文獻(xiàn)［12］分析了基于啟發(fā)式策略仿真的多項(xiàng)目模具制造過(guò)程隨機(jī)調(diào)度問(wèn)題，文獻(xiàn)［13］通過(guò)對(duì)建立多項(xiàng)目的交貨期隨機(jī)預(yù)測(cè)模型進(jìn)行演化，獲得項(xiàng)目交貨期的概率分布及最佳策略。

從已有研究看，國(guó)內(nèi)外學(xué)者主要對(duì)多項(xiàng)目調(diào)度模型進(jìn)行了一定擴(kuò)展，RCMPSP得到廣泛而深入的討論，如時(shí)間／費(fèi)用權(quán)衡問(wèn)題、資源水平問(wèn)題，并且得到許多成功應(yīng)用。但是針對(duì)不確定問(wèn)題、動(dòng)態(tài)問(wèn)題的研究還比較少，特別是模具項(xiàng)目這種不確定環(huán)境下工期與費(fèi)用的隨機(jī)調(diào)度研究，國(guó)內(nèi)外相關(guān)文獻(xiàn)還不多見。在實(shí)際生產(chǎn)中，多項(xiàng)目并行共享關(guān)鍵資源合作生產(chǎn)普遍存在。因此，進(jìn)行不確定環(huán)境下的多項(xiàng)目動(dòng)態(tài)協(xié)同調(diào)度研究，既考慮局部的利益，又考慮動(dòng)態(tài)的整體性，是非常有意義的。本文在以上研究的基礎(chǔ)上，以項(xiàng)目網(wǎng)絡(luò)圖確定的模具生產(chǎn)計(jì)劃為研究對(duì)象，考慮模具項(xiàng)目生產(chǎn)過(guò)程中加工任務(wù)存在多種加工資源類的完成方式和生產(chǎn)單元之間的進(jìn)度協(xié)同，建立以項(xiàng)目群的總懲罰值最小為優(yōu)化目標(biāo)的Markov決策過(guò)程模型，并且提出了一種分階段求優(yōu)的調(diào)度算法，有效地應(yīng)用于模具項(xiàng)目群的項(xiàng)目計(jì)劃制定。

1 問(wèn)題描述

目前，大中型模具企業(yè)生產(chǎn)趨于專業(yè)化，多采用模塊化單元布局的生產(chǎn)模式。在這種生產(chǎn)環(huán)境下，部件之間生產(chǎn)進(jìn)度的協(xié)調(diào)非常關(guān)鍵。制定項(xiàng)目計(jì)劃的目的在于給項(xiàng)目的執(zhí)行過(guò)程制定一個(gè)基準(zhǔn)，以利于各個(gè)部門以此為依據(jù)進(jìn)行項(xiàng)目協(xié)同。

模具項(xiàng)目中，每個(gè)任務(wù)可以在多個(gè)不同的加工資源類中完成，不同的加工資源對(duì)應(yīng)不同的完成時(shí)間，其差異決定了項(xiàng)目的交貨期。項(xiàng)目相鄰兩個(gè)任務(wù)之間的聯(lián)系用轉(zhuǎn)移概率矩陣描述，前續(xù)任務(wù)加工方式的選擇決定后續(xù)任務(wù)加工方式的概率分布。多個(gè)項(xiàng)目執(zhí)行狀態(tài)構(gòu)成了整個(gè)項(xiàng)目群的狀態(tài)。在項(xiàng)目群執(zhí)行的每個(gè)可能狀態(tài)，應(yīng)該采取合適的行動(dòng)，以構(gòu)造一個(gè)最優(yōu)決策，使得項(xiàng)目群的拖期懲罰與等待懲罰的總懲罰值最小化。

本文重點(diǎn)研究隨機(jī)環(huán)境下使用Markov決策過(guò)程模型進(jìn)行項(xiàng)目群演化，以獲得各項(xiàng)目任務(wù)在不同加工資源下的完成情況，得到模具項(xiàng)目群演化的最優(yōu)交貨期和拖期成本。

2 基于離散時(shí)間的Markov決策過(guò)程建模

隨機(jī)資源受限調(diào)度的問(wèn)題，即為對(duì)資源的多階段隨機(jī)優(yōu)化問(wèn)題，每一階段的決策依賴于當(dāng)前的系統(tǒng)狀態(tài)，而系統(tǒng)狀態(tài)是由多個(gè)不確定參數(shù)描述的。因此，采用離散時(shí)間 Markov鏈進(jìn)行系統(tǒng)建模［14］。作以下假設(shè)：①每個(gè)任務(wù)必須以一種模式開工；②每個(gè)任務(wù)的執(zhí)行順序是確定的，而且一個(gè)任務(wù)在同一時(shí)刻只占用一類資源；③任務(wù)一旦開工，必須以該模式執(zhí)行，直到任務(wù)完成；④不允許更改和取代執(zhí)行中的模式。

2．1 狀態(tài)定義

項(xiàng)目在每個(gè)決策時(shí)刻t，系統(tǒng)的所有可能狀態(tài)為S，也稱為狀態(tài)空間。企業(yè)承擔(dān)了L個(gè)模具制造項(xiàng)目，每個(gè)項(xiàng)目有M 個(gè)任務(wù)，共需要N類資源，每類資源提供的加工能力為T。

定義系統(tǒng)狀態(tài)

式中：Pi（i＝1，2，…，L），Pi∈ ［0，1］，表示項(xiàng)目i的當(dāng)前狀態(tài)是否完成。qi（i＝ 1，2，…，M），M 為正整數(shù)，表示項(xiàng)目i完成的任務(wù)數(shù)；qi∈ ［1，M］，項(xiàng)目的某個(gè)任務(wù)一旦完成，則更新qi；若qi＝M，則更新該項(xiàng)目狀態(tài)，表示該任務(wù)已經(jīng)完成。Ri∈ ［0，Ki］，Ki表示第i類資源在t時(shí)刻可提供的最大加工能力，Ri＝0表示在t時(shí)刻該類資源全部被占用；Ri＝Ki表示在t時(shí)刻該類資源的加工能力最大。Tpq，dpq和Fpq分別表示項(xiàng)目p的第q個(gè)任務(wù)以及該任務(wù)的工期和完工時(shí)間。π（t）＝ ｛Tpq∈Tp｜Fpq－dpq≤t≤Fpq｝為t時(shí)刻正在進(jìn)行的所有項(xiàng)目的任務(wù)集合。

其中：式（1）表示t時(shí)刻正在執(zhí)行的所有項(xiàng)目任務(wù)所占用的l類資源總數(shù)小于l類資源的最大可用數(shù)；式（2）表示t時(shí)刻正在執(zhí)行的任務(wù)所占用的l類資源數(shù)應(yīng)大于0；式（3）表示項(xiàng)目Tpq必須在其所有緊前任務(wù)均已完工的情況下才能開始；式（4）定義任務(wù)的完工約束。

2．2 目標(biāo)函數(shù)

項(xiàng)目在每個(gè)決策時(shí)刻t，系統(tǒng)處于狀態(tài)s，對(duì)應(yīng)一個(gè)行動(dòng)集At，定義系統(tǒng)為下一任務(wù)分配的加工資源的可用加工能力，采取對(duì)應(yīng)的行動(dòng)α∈At時(shí)可以得到：①項(xiàng)目演化完工期tf，每個(gè)項(xiàng)目都有一定的拖期懲罰系數(shù)Kp，懲罰值cp（s，a）＝kp×tf，拖期時(shí)間與懲罰值呈正相關(guān)關(guān)系；②每個(gè)項(xiàng)目?jī)?nèi)部各個(gè)生產(chǎn)單元的最早最遲完成時(shí)間分別為timax和timin，每個(gè)項(xiàng)目有一定的等待懲罰成本Kw，懲罰值cw（s，a）＝kw×（timax－timin），即懲罰值ct（s，a）＝kp×tf＋kw×（timax－timin）。模具企業(yè)的生產(chǎn)目標(biāo)是盡可能在滿足客戶交貨期的前提下，降低在制品的庫(kù)存量，將總的懲罰值降到最低，即Markov決策過(guò)程的目標(biāo)函數(shù)是

3 基于隨機(jī)動(dòng)態(tài)規(guī)劃的啟發(fā)式算法

Bellman迭代是求解Markov決策問(wèn)題的有效方法，但往往面臨“維數(shù)災(zāi)”的問(wèn)題。對(duì)于L個(gè)項(xiàng)目，每個(gè)項(xiàng)目有M個(gè)任務(wù)，每個(gè)任務(wù)有N種可選資源，其項(xiàng)目的狀態(tài)數(shù)量大于（NM）L，且隨著問(wèn)題規(guī)模的擴(kuò)大呈爆炸性增長(zhǎng)。

在本研究中，對(duì)于每一個(gè)任務(wù)階段，采用動(dòng)態(tài)規(guī)劃的方法計(jì)算最優(yōu)策略。將項(xiàng)目群從狀態(tài)到狀態(tài)的轉(zhuǎn)移函數(shù)定義為φ（γ，α；δ），轉(zhuǎn)移結(jié)果依賴于被選擇的計(jì)劃行動(dòng)a。對(duì)于一個(gè)確定的“狀態(tài)－行為”序列，

該序列轉(zhuǎn)移得到的時(shí)間

給定狀態(tài)γ和行動(dòng)決策α，轉(zhuǎn)移的期望時(shí)間為

項(xiàng)目群按照路徑ω繼續(xù)進(jìn)行下去的概率

因此，對(duì)于一個(gè)給定的策略π，經(jīng)過(guò)n個(gè)階段后的期望時(shí)間

每一狀態(tài)的最優(yōu)策略，只決定于當(dāng)前狀態(tài)到下一狀態(tài)的轉(zhuǎn)移概率和轉(zhuǎn)移時(shí)間，以及對(duì)應(yīng)下一狀態(tài)的最優(yōu)時(shí)間。因此，使用動(dòng)態(tài)規(guī)劃算法來(lái)計(jì)算項(xiàng)目群最優(yōu)期望時(shí)間和懲罰值。動(dòng)態(tài)規(guī)劃算法將項(xiàng)目群中零階段的時(shí)間定義為0。一直迭代，可以算出從而得出本階段的最優(yōu)期望時(shí)間。對(duì)于每一個(gè)階段，選擇取到最小期望時(shí)間的行為，從而構(gòu)造出本階段的最優(yōu)策略。每一階段結(jié)束后，更新初始化的向量，作為下一階段的輸入，直至項(xiàng)目終止。

尋求最優(yōu)迭代算法的具體步驟如下：

步驟1 為了有效協(xié)同項(xiàng)目?jī)?nèi)部各生產(chǎn)單元的進(jìn)度，縮短各單元到達(dá)裝配的時(shí)間差，減少庫(kù)存半成品，采用逆向進(jìn)度計(jì)劃排序。以項(xiàng)目任務(wù)的緊前緊后關(guān)系構(gòu)造項(xiàng)目任務(wù)表，按任務(wù)的執(zhí)行順序降序排列。

步驟2 以項(xiàng)目群的最大交貨期為問(wèn)題的初始上界，構(gòu)造逆向進(jìn)度計(jì)劃所需的任務(wù)優(yōu)先權(quán)列表：依據(jù)任務(wù)階段中項(xiàng)目群按照交貨期的時(shí)間降序排列，如果交貨期相同，則按照項(xiàng)目懲罰系數(shù)降序排列，任務(wù)所對(duì)應(yīng)的資源按照資源的加工效率降序排列。

步驟3 根據(jù)任務(wù)優(yōu)先權(quán)列表的任務(wù)，計(jì)算任務(wù)在每類可用資源類Rl中的期望開始時(shí)間，取最大的開始時(shí)間和對(duì)應(yīng)的資源類l，更新項(xiàng)目的上界和資源類的可用時(shí)間，將該任務(wù)從優(yōu)先權(quán)列表刪除。

步驟4 如果任務(wù)優(yōu)先權(quán)列表為空，則得到該任務(wù)的一個(gè)調(diào)度序列，以及項(xiàng)目群中的最早最遲開始結(jié)束時(shí)間，進(jìn)入步驟5；否則，轉(zhuǎn)步驟3。

步驟5 如果項(xiàng)目任務(wù)表為空，則得到項(xiàng)目群

有下面的遞推式的整個(gè)調(diào)度策略，以及整個(gè)項(xiàng)目群中每個(gè)項(xiàng)目的開始結(jié)束時(shí)間，進(jìn)入步驟6；否則，轉(zhuǎn)步驟1。

步驟6 根據(jù)得到的整個(gè)項(xiàng)目群中的最早開始時(shí)間TES與當(dāng)前時(shí)間對(duì)比TNow，如果TES＞TNow，則將整個(gè)項(xiàng)目群的所有任務(wù)計(jì)劃按照（TES－TNow）的差值順推，得到一個(gè)調(diào)整后的進(jìn)度計(jì)劃。

步驟7 根據(jù)調(diào)整后的項(xiàng)目計(jì)劃，計(jì)算項(xiàng)目群的懲罰值，終止程序。

4 算例

以國(guó)內(nèi)某大型輪胎模具企業(yè)為研究背景，選取企業(yè)部分?jǐn)?shù)據(jù)進(jìn)行方法驗(yàn)證。訂單的基本信息如表1所示，不同的產(chǎn)品類型表示需要不同的標(biāo)準(zhǔn)加工時(shí)間，訂單的工藝路徑及所需資源如表2所示，工序之間采用的不同加工資源類之間的狀態(tài)轉(zhuǎn)移矩陣如表3所示。

表1 訂單的基本信息

表2 工藝路徑與資源信息

表3 各項(xiàng)任務(wù)實(shí)現(xiàn)方式與概率轉(zhuǎn)移

4．1 算例數(shù)據(jù)

4．2 啟發(fā)式策略仿真和動(dòng)態(tài)規(guī)劃算法

EM－Plant是基于時(shí)間控制器觸發(fā)的面向?qū)ο蠓抡婀ぞ?，采用EM－Plant編寫動(dòng)態(tài)規(guī)劃算法（Dynamic Programming Algorithm，DPA）和三種啟發(fā)式策略，啟發(fā)式策略包括：①先到達(dá)的任務(wù)優(yōu)先執(zhí)行（First in first out，F(xiàn)IFO）；②交貨期急的任務(wù)優(yōu)先執(zhí)行（Earliest due date，EDD）；③加工效率高的加工資源優(yōu)先采用（Highest Efficiency Resource，HER）。在配置為Pentium（R）Dual－Core CPU T4200＠2．00GHz，4G內(nèi)存的機(jī)器上執(zhí)行。分別針對(duì)10，20，30個(gè)訂單進(jìn)行仿真，由于前兩種仿真策略在資源類選擇中存在不確定因素，各仿真10 000次，而第三種仿真策略與動(dòng)態(tài)規(guī)劃算法由定義的方法決策出資源類的選擇。三種仿真策略和動(dòng)態(tài)規(guī)劃算法得到的結(jié)果如表4所示，針對(duì)30個(gè)訂單的項(xiàng)目群進(jìn)度計(jì)劃甘特圖如圖1～圖4所示。

表4 4種策略值得到的項(xiàng)目群懲罰值

4．3 結(jié)果比較分析

分析表4和圖1～圖4可知，仿真結(jié)果中，F(xiàn)IFO所表現(xiàn)出的結(jié)果最差，EDD的結(jié)果略優(yōu)于FIFO，HER結(jié)果表現(xiàn)優(yōu)于前兩種。對(duì)比HER與DPA，由于HER側(cè)重于高效率資源的調(diào)配管理，而沒有注重各單元進(jìn)度之間的配合，在指標(biāo)E3中，HER取得的結(jié)果比DPA好，而E1和E2表現(xiàn)較差。從進(jìn)度甘特圖上看，黑色陰影部分表示訂單在各項(xiàng)目單元的完成情況，DPA表現(xiàn)的各單元項(xiàng)目進(jìn)度協(xié)調(diào)更為一致。因此，從總體上來(lái)說(shuō)，針對(duì)單元生產(chǎn)布局的多項(xiàng)目調(diào)度，應(yīng)用動(dòng)態(tài)規(guī)劃算法所得到的結(jié)果具有較好的性能，具有盡可能小的懲罰值和較高的發(fā)生概率，可為實(shí)際的生產(chǎn)管理提供決策支持。

5 結(jié)束語(yǔ)

本文針對(duì)模具項(xiàng)目群的項(xiàng)目計(jì)劃調(diào)度，進(jìn)行了如下工作：①將模具項(xiàng)目進(jìn)度計(jì)劃的制定抽象化為Markov決策過(guò)程；②介紹了一種基于資源受限模具群分階段最優(yōu)策略的項(xiàng)目計(jì)劃方法，在一定程度上解決了馬氏維數(shù)災(zāi)的問(wèn)題；③對(duì)項(xiàng)目狀態(tài)和項(xiàng)目階段進(jìn)行合理假設(shè)，建立啟發(fā)式策略仿真模型，通過(guò)求解最小化期望時(shí)間選取各個(gè)階段最優(yōu)策略，并與其他算法進(jìn)行對(duì)比分析，表明該方法更具優(yōu)越性，適應(yīng)了項(xiàng)目群的動(dòng)態(tài)變化；④開發(fā)了一套模具群項(xiàng)目仿真平臺(tái)，在統(tǒng)計(jì)數(shù)據(jù)充分的情況下，基于該平臺(tái)得到的最優(yōu)策略，對(duì)實(shí)際項(xiàng)目計(jì)劃和調(diào)度具有指導(dǎo)作用。

為進(jìn)一步增強(qiáng)可用性，今后的研究工作目標(biāo)為：①構(gòu)造性能更優(yōu)的啟發(fā)式算法；②分兩階段研究項(xiàng)目群及項(xiàng)目群內(nèi)部的進(jìn)度協(xié)同問(wèn)題。

［1］LIU Jianjun，CHEN Qingxin，MAO Ning，et al．Workload control approach for mould enterprise in stochastic production［J］．Computer Integrated Manufacturing Systems，2010，16（2）：263－270（in Chinese）．［劉建軍，陳慶新，毛 寧，等．隨機(jī)環(huán)境下模具企業(yè)車間負(fù)荷控制方法［J］．計(jì)算機(jī)集成制造系統(tǒng)，2010，16（2）：263－270．］

［2］HARTMANN S，BRISKORN D．A survey of variants and extensions of the resource－constrained project scheduling problem［J］．European Journal of Operational Research，2010，207（1）：1－14．

［3］HERROELEN W，LEUS R．Project scheduling under uncertainty：survey and research potentials［J］．European Journal of Operational Research，2005，165（2）：289－306．

［4］CHOI J，REALFF M J，LEE J H．Dynamic programming in a heuristically confined state space：a stochastic resource－constrained project scheduling application ［J］．Computers ＆Chemical Engineering，2004，28（6／7）：1039－1058．

［5］LIU Zhenyuan，WANG Hongwei．Two－step activity－mode scheduling schema on MMRCPSP with the objective of minimizing activities'cost［J］．Control and Decision，2007，22（10）：1160－1164（in Chinese）．［劉振元，王紅衛(wèi)．活動(dòng)成本目標(biāo)MMRCPSP的活動(dòng)－模式兩步調(diào)度策略［J］．控制與決策，2007，22（10）：1160－1164．］

［6］PADBERG F．A study on optimal scheduling for software projects［J］．Software Process：Improve Practice，2006，11（1）：77－91．

［7］PADBERG F．Scheduling software projects to minimize the development time and cost with a given staff［C］／／Proceedings of the 8th Asia－Pacific Software Engineering Conference．Washington，D．C．，USA：IEEE，2001：187－194．

［8］BOTOR F F．Heuristic for scheduling projects with resource restrictions and several resource－duration modes［J］．International Journal of Production Research，1993，31（11）：2547－2558．

［9］LIAO Ren，CHEN Qingxin，MAO Ning．Algorithm for resource－constrained project scheduling［J］．Computer Integrated Manufacturing Systems，2004，10（7）：815－819，857 （in Chinese）．［廖 仁，陳慶新，毛 寧．模具虛擬企業(yè)項(xiàng)目調(diào)度遺傳算法研究［J］．計(jì)算機(jī)集成制造系統(tǒng)，2004，10（7）：815－819，857．］

［10］LIU J J，CHEN Q X，MAO N．A multi－agent－based mould due date setting approach in stochastic production［J］．International Journal of Production Research，2011，49（5）：1353－1371．

［11］LIU Jianjun，CHEN Qingxin，MAO Ning．Approach to es－tablish reliable due dates of mould based on capacity check［J］．Computer Integrated Manufacturing Systems，2009，15（3）：617－624（in Chinese）．［劉建軍，陳慶新，毛 寧．基于能力驗(yàn)證的模具交貨期可行性分析方法［J］．計(jì)算機(jī)集成制造系統(tǒng)，2009，15（3）：617－624．］

［12］ZHANG Shaqing，CHEN Xindu，CHEN Qingxin，et al．Stochastic scheduling for multiple mould and die manufacturing projects under uncertainty［J］．Computer Integrated Manufacturing Systems，2009，15（7）：1389－1396 （in Chinese）．［張沙清，陳新度，陳慶新，等．不確定環(huán)境下模具制造項(xiàng)目群隨機(jī)調(diào)度［J］．計(jì)算機(jī)集成制造系統(tǒng)，2009，15（7）：1389－1396．］

［13］WANG Xiaoming，CHEN Qingxin，MAO Ning，et al．Mould projects due－date forecast methods research under random environment［J］．Computer Integrated Manufacturing Systems，2012，18（2）：405－414（in Chinese）．［王小明，陳慶新，毛 寧，等．隨機(jī)環(huán)境下的模具項(xiàng)目交貨期預(yù)測(cè)方法研究及應(yīng)用［J］．計(jì)算機(jī)集成制造系統(tǒng)，2012，18（2）：405－414．］

［14］PUTERMAN M．Markov decision processes：discrete stochastic dynamic programming ［M］．New York，N．Y．，USA：John Wiley ＆Sons，2005．