（北京交通大學(xué) 機(jī)械與電子工程控制學(xué)院，北京 100044）

0 引言

生產(chǎn)調(diào)度研究的問題是將機(jī)器分配給一定時(shí)間內(nèi)的工作，它是一個(gè)決策過程，其目的是優(yōu)化一個(gè)或多個(gè)目標(biāo)。在過去50年里，生產(chǎn)調(diào)度問題已經(jīng)得到了深入研究和發(fā)展，形成了比較完備的理論體系[1]。但作為典型的NP難問題，生產(chǎn)調(diào)度問題即使規(guī)模很小，也很難得到最優(yōu)解，因此，對(duì)生產(chǎn)調(diào)度問題的研究，大多集中在具有求解速度快、容易得到滿意甚至近似調(diào)度最優(yōu)解的啟發(fā)式規(guī)則。Cheng TCE等[2]、Lee C Y等[3]、Mokotoff E等[4]對(duì)現(xiàn)有研究結(jié)果進(jìn)行了較為詳細(xì)的綜述。

并行機(jī)調(diào)度問題是一類重要的調(diào)度問題，在理論和實(shí)際應(yīng)用都有非常大的價(jià)值并一直受到廣泛的關(guān)注。Li K等[5]從建模方法、松弛技術(shù)和算法設(shè)計(jì)等方面對(duì)一類并行機(jī)調(diào)度問題進(jìn)行了綜述。李凱等[6]研究了目標(biāo)函數(shù)是完成時(shí)間和的同類機(jī)調(diào)度問題（Qm|∑C），為此問題建立數(shù)學(xué)模型，然后提出一種改進(jìn)的啟發(fā)式算法。史燁等[7]設(shè)計(jì)一個(gè)包含局部優(yōu)化的模擬退火算法，來研究調(diào)度目標(biāo)是最小化最大完成時(shí)間的并行機(jī)調(diào)度問題（Pm|Cmax)，以獲得問題的近優(yōu)解。楊斌鑫等[8]在傳統(tǒng)的解決P2|prmp|Cmax問題最優(yōu)調(diào)度規(guī)則的基礎(chǔ)上，考慮了被中斷任務(wù)恢復(fù)加工的延遲時(shí)間，給出改進(jìn)的算法。展勇[9]等研究了多并行機(jī)可中斷的開放車間調(diào)度問題（Om(P)|prmp,ri|Cmax），建立了以制造期最短為目標(biāo)的整數(shù)規(guī)劃模型，然后根據(jù)加工可中斷的特點(diǎn)將整數(shù)規(guī)劃模型的求解問題轉(zhuǎn)化為以機(jī)器滿負(fù)荷工作為目標(biāo)的資源分配和加工排序兩個(gè)子問題的求解，分別采用最大流算法和構(gòu)造加工時(shí)間矩陣的減量集合的方法，求得最優(yōu)調(diào)度結(jié)果基于網(wǎng)絡(luò)流的調(diào)度算法。黃竹君[10]分析啟發(fā)式調(diào)度規(guī)則的分類并總結(jié)已有的啟發(fā)式調(diào)度規(guī)則，對(duì)11種啟發(fā)式規(guī)則在各種仿真參數(shù)下的調(diào)度性能進(jìn)行了評(píng)價(jià)分析，總結(jié)了不同啟發(fā)式規(guī)則的調(diào)度性能，為啟發(fā)式規(guī)則的應(yīng)用提供了有價(jià)值的參考。但現(xiàn)有啟發(fā)式方法仍存在著求解結(jié)果不確定，也有可能求不到最優(yōu)解的問題，或存在其他缺陷，而本文所采用的整數(shù)規(guī)劃建模是一種精確求解的方法，可以求得問題的精確最優(yōu)解。

本文采用多目標(biāo)的混合整數(shù)規(guī)劃方法，針對(duì)現(xiàn)有LRPT和LRPT-FM算法中斷個(gè)數(shù)往往無限多的缺陷，對(duì)Pm|prmp|Cmax和Qm|prmp|Cmax兩類問題建立混合整數(shù)規(guī)劃模型。選用MLeap建模語言表達(dá)，使用CPLEX求解器進(jìn)行求解，當(dāng)問題的松弛最優(yōu)解與當(dāng)前整數(shù)解目標(biāo)值之間的差（gap）為零時(shí)，求得問題的精確最優(yōu)解。通過算例計(jì)算表明，對(duì)原文中的小規(guī)模算例，本方法能在瞬間求解出精確最優(yōu)解，之后通過隨機(jī)試驗(yàn)獲取算例數(shù)據(jù)，來驗(yàn)證該模型在解決較大規(guī)模算例時(shí)的有效性。

1 問題及傳統(tǒng)算法描述

并行機(jī)問題可以描述為：給定一組工作j調(diào)度分配到一組機(jī)器i中的任一機(jī)器加工。一臺(tái)機(jī)器在同一時(shí)刻只能加工一項(xiàng)工作，且一項(xiàng)工作在同一時(shí)刻只能被一臺(tái)機(jī)器加工。采用調(diào)度問題通用的α|β|γ表示方法，α描述機(jī)器環(huán)境，β描述加工特征，γ描述最小化的目標(biāo)。本文所討論的是Pm|prmp|Cmax和Qm|prmp|Cmax兩類問題，Pm表示m臺(tái)相同加工速度的同型機(jī)（Identical Machines），Qm表示m臺(tái)不同加工速度的同類機(jī)（Uniform Machines）。prmp表示工作的制造期可打斷，即允許在任何時(shí)間中斷一項(xiàng)工作的加工，而把另一項(xiàng)工作放到該機(jī)器上，一項(xiàng)中斷的工作重新返回到機(jī)器上時(shí)，它只需加工完剩下的工作即可。Cmax表示制造期（Makespan），和最后一項(xiàng)完成加工的時(shí)間相等，最小化制造期意味著機(jī)器的高利用率。

對(duì)于Pm|prmp|Cmax的調(diào)度算法是最長剩余加工時(shí)間優(yōu)先調(diào)度（Longest Remaining Processing Time，LRPT），這種算法是解決不可中斷問題的最長加工時(shí)間優(yōu)先（LPT）算法的改進(jìn)。LPT算法即在t=0將m個(gè)最長工作分配給m臺(tái)機(jī)器，此后任一臺(tái)機(jī)器空閑，剩下工作中加工時(shí)間最長的將分配給這臺(tái)空閑機(jī)器，此算法將較短工作放在調(diào)度的最后，被用于平衡負(fù)載。LRPT算法是LPT的中斷形式，對(duì)于Pm|prmp|Cmax問題能得到最優(yōu)調(diào)度，“但從實(shí)際角度，該算法存在嚴(yán)重的缺陷，因?yàn)樵诖_定情況下需要中斷個(gè)數(shù)往往是無限多的”[1]。

對(duì)于Qm|prmp|Cmax問題，即考慮機(jī)器的加工速度，通常采用一般化的LRPT算法被稱為最長剩余加工時(shí)間最快機(jī)器優(yōu)先（Longest Remaining Processing Time on the Fastest Machine，LRPR-FM）算法。根據(jù)該算法在任何時(shí)刻未完成工作中有最長剩余加工時(shí)間的工作被分配給加工速度最快的機(jī)器，有第二長剩余加工時(shí)間的工作被分配給第二快的機(jī)器，依次類推。該算法對(duì)于Qm|prmp|Cmax問題在離散時(shí)間和連續(xù)時(shí)間都是最優(yōu)調(diào)度。但如果在時(shí)刻t有兩項(xiàng)工作具有相同的剩余加工時(shí)間，并且這個(gè)加工時(shí)間是未完成工作中最長的，那么這兩項(xiàng)工作中一個(gè)被分給最快機(jī)器，另一項(xiàng)分給第二快機(jī)器，在t+ε（ε非常?。纸o第二快機(jī)器的工作將比最快機(jī)器上的工作的剩余加工時(shí)間長，這時(shí)它將被分到最快的機(jī)器上，反之亦然。因此這個(gè)算法同樣存在無窮數(shù)量的中斷。

2 多目標(biāo)混合整數(shù)規(guī)劃模型及MLeap表達(dá)

2.1 模型建立

為了改進(jìn)上述算法，減少中斷的次數(shù)，本文建立了多目標(biāo)的混合整數(shù)規(guī)劃模型，即最小化制造期和最小化工作段數(shù)兩個(gè)目標(biāo)。

在數(shù)學(xué)模型中，Cmax表示工作的最長加工時(shí)間，nSegment表示各工作的段數(shù)，xij表示工作j（j=1，…，n）在機(jī)器i（i=1，…，m）上的加工時(shí)間，pj表示工作j的加工時(shí)間，yij表示工作j是否被分配到機(jī)器i上（yij=1表示工作j被分配到機(jī)器i，反之yij=0則沒有分配），M表示一個(gè)極大值，spdi表示機(jī)器i的加工速度。

對(duì)于Pm|prmp|Cmax問題，建立整數(shù)規(guī)劃模型如下：

上述模型中的目標(biāo)要滿足最長加工時(shí)間Cmax和工作中斷次數(shù)nSegment最小，采用多目標(biāo)規(guī)劃的方法，為兩個(gè)目標(biāo)設(shè)置權(quán)重，Cmax的權(quán)重為1，nSegment的權(quán)重為0.1，表示先滿足第一個(gè)目標(biāo)之后再滿足第二個(gè)目標(biāo)。第一個(gè)約束保證每項(xiàng)工作必需的加工時(shí)間；第二個(gè)約束保證每項(xiàng)工作在各機(jī)器上加工之間之和不超過制造期；第三個(gè)約束保證每臺(tái)機(jī)器的工作時(shí)間不超過制造期；第四個(gè)約束表示當(dāng)存在把工作j分配到機(jī)器i上時(shí)（xij≠0），則yij=1；第五個(gè)約束表示將每個(gè)工作分成的段數(shù)進(jìn)行累加。

當(dāng)考慮在離散時(shí)間時(shí)，將所有的加工時(shí)間（xij、Cmax）設(shè)定為整數(shù)（integer），同時(shí)也只能在整數(shù)時(shí)間中斷工作。當(dāng)考慮在連續(xù)時(shí)間時(shí)，則將所有的加工時(shí)間（xij、Cmax）設(shè)定為常數(shù)（number），可在任意時(shí)間中斷工作。在下文通過MLeap建模語言進(jìn)行表達(dá)具有較強(qiáng)的便捷性。

對(duì)于Qm|prmp|Cmax問題，建立整數(shù)規(guī)劃模型如下：

該模型與上述模型大致相同，只是第一個(gè)約束中加入了機(jī)器速度spdi，不同機(jī)器有不同的加工速度。

2.2 MLeap建模表達(dá)

為求得數(shù)學(xué)模型的解，需要首先通過一種建模語言將其表達(dá)給機(jī)器，而后使用求解器得到所需要的結(jié)果。本文采用MLeap建模語言實(shí)現(xiàn)這一過程。MLeap語言是本文作者所設(shè)計(jì)一種數(shù)學(xué)規(guī)劃模型的描述型建模語言，具有很強(qiáng)的描述性，不需要任何模型展開和求解過程，基本上只需將數(shù)學(xué)模型寫成文本形式即可。

模型（2）的MLeap建模語言表達(dá)如圖1所示。在寫出MLeap語言后，使用MLeap語言解釋器將其解釋成內(nèi)碼模型直接求解，或者通過標(biāo)準(zhǔn)的數(shù)學(xué)規(guī)劃模型接口文件.mps格式或.lp格式將模型傳遞到求解器CPLEX中去求解。模型（1）的MLeap建模表達(dá)與之類似。

圖1 Qm |prmp|Cmax數(shù)學(xué)模型Mleap建模語言表達(dá)

如圖1所示，MLeap語言主要由目標(biāo)段、約束段、符號(hào)說明段、數(shù)據(jù)關(guān)系段、數(shù)據(jù)段組成。目標(biāo)段以Maximize/Minimize為標(biāo)識(shí)，用于描述目標(biāo)；約束段以Subject to為標(biāo)識(shí)，用于描述約束；符號(hào)說明段以Where為開始，用于描述語言中出現(xiàn)的符號(hào)；數(shù)據(jù)關(guān)系段以Data_relation為標(biāo)識(shí)，用于常數(shù)數(shù)據(jù)的計(jì)算；數(shù)據(jù)段以Data為起始標(biāo)識(shí)，用于為模型提供算例數(shù)據(jù)。MLeap中使用sum標(biāo)識(shí)表達(dá)累加，累和運(yùn)算的累計(jì)值寫在緊接其后的花括號(hào)內(nèi)；使用“|”分割約束式的聯(lián)立表達(dá)；使用“_$”表示獲取數(shù)組中元素的個(gè)數(shù)。

在MLeap模型被正確寫出之后，只需輸入問題的數(shù)據(jù)文件，讀入?yún)?shù)，便可選擇使用MLeap內(nèi)置求解器或者調(diào)用外部求解器CPLEX求解模型。此過程可以使用C++語言將整個(gè)過程封裝成一個(gè)不需要用戶干預(yù)的程序，進(jìn)而實(shí)現(xiàn)求解過程的自動(dòng)化。

3 算例

為驗(yàn)證本文方法的正確性和高效性，對(duì)兩類問題的模型進(jìn)行求解測試。先進(jìn)行小規(guī)模算例的計(jì)算，來源于文獻(xiàn)[1]中的簡單算例，對(duì)比原文中采用的傳統(tǒng)LRPT和LRPT-FM算法，測試結(jié)果表明，本文的方法要比文獻(xiàn)中的求解結(jié)果更加優(yōu)化。

3.1 Pm|prmp|Cmax問題算例

考慮2臺(tái)機(jī)器和3項(xiàng)工作，即工作1，2和3，加工時(shí)間為8，7和6。

整數(shù)時(shí)間下，LRPT算法調(diào)度結(jié)果如圖2所示，且制造期為11。

圖2 在整數(shù)時(shí)刻中斷，2臺(tái)機(jī)器和3項(xiàng)工作的LRPT算法

整數(shù)時(shí)間下，多目標(biāo)混合整數(shù)規(guī)劃建模求解結(jié)果如圖3所示，制造期也為11。

圖3 在整數(shù)時(shí)刻中斷，2臺(tái)機(jī)器和3項(xiàng)工作的多目標(biāo)混合整數(shù)規(guī)劃建模求解

連續(xù)時(shí)間下，LRPT算法調(diào)度結(jié)果如圖4所示，且制造期為10.5。

圖4 在任意時(shí)刻中斷，2臺(tái)機(jī)器和3項(xiàng)工作的LRPT算法

連續(xù)時(shí)間下，多目標(biāo)混合整數(shù)規(guī)劃建模求解結(jié)果如圖4所示，制造期也為10.5。

圖5 在任意時(shí)刻中斷，2臺(tái)機(jī)器和3項(xiàng)工作的多目標(biāo)混合整數(shù)規(guī)劃建模求解

通過對(duì)一個(gè)小規(guī)模算例分別在整數(shù)時(shí)間和連續(xù)時(shí)間下進(jìn)行求解，可以看出LRPT算法同混合整數(shù)規(guī)劃模型都可求出問題的精確最優(yōu)解，但LRPT算法求解結(jié)果存在制造期中斷次數(shù)較多的缺陷。在整數(shù)時(shí)間下，LRPT求解結(jié)果工作段數(shù)為9，而整數(shù)規(guī)劃結(jié)果為4；在連續(xù)時(shí)間下，LRPT求解結(jié)果工作段數(shù)為無窮多，而整數(shù)規(guī)劃結(jié)果為4。

3.2 Qm|prmp|Cmax問題算例

考慮3臺(tái)機(jī)器1，2和3，具有加工速度3，2和1。有3項(xiàng)工作1，2和3，其加工時(shí)間是36，34和12。

整數(shù)時(shí)間下，LRPT-FM算法調(diào)度結(jié)果如圖6所示，且制造期為14。

圖6 在整數(shù)時(shí)刻中斷，3臺(tái)不同速度的機(jī)器和3項(xiàng)工作的LRPT-FM算法

整數(shù)時(shí)間下，多目標(biāo)混合整數(shù)規(guī)劃建模求解結(jié)果如圖7所示，制造期也為14。

圖7 在整數(shù)時(shí)刻中斷，3臺(tái)不同速度的機(jī)器和3項(xiàng)工作的多目標(biāo)混合整數(shù)規(guī)劃建模求解

連續(xù)時(shí)間下，LRPT-FM算法調(diào)度結(jié)果如圖8所示，且制造期為14。

圖8 在任意時(shí)刻中斷，3臺(tái)不同速度的機(jī)器和3項(xiàng)工作的LRPT-FM算法

連續(xù)時(shí)間下，多目標(biāo)混合整數(shù)規(guī)劃建模求解結(jié)果如圖9所示，制造期也為14。

圖9 在任意時(shí)刻中斷，3臺(tái)不同速度的機(jī)器和3項(xiàng)工作的多目標(biāo)混合整數(shù)規(guī)劃建模求解

對(duì)于考慮機(jī)器加工速度的小規(guī)模算例，整數(shù)規(guī)劃結(jié)果同樣優(yōu)于LRPT-FM算法。在整數(shù)時(shí)間下，LRPTFM求解工作段數(shù)結(jié)果為15，而整數(shù)規(guī)劃結(jié)果5；在連續(xù)時(shí)間下，LRPT-FM算法求解制造期為14，工作段數(shù)為無窮多，而整數(shù)規(guī)劃求解，工作段數(shù)為5，得到精確最優(yōu)解。

3.3 較大規(guī)模算例測試

隨后，我們利用隨機(jī)數(shù)據(jù)來測試該多目標(biāo)混合整數(shù)規(guī)劃模型。取5臺(tái)機(jī)器的加工速度分別為1、2、3、4、5，工作數(shù)量分別為20、40、60、80、100，作業(yè)加工時(shí)間隨機(jī)生成，取值范圍為[10,40]。對(duì)任意相同規(guī)模的問題（相同作業(yè)數(shù)），分別采用5組不同的隨機(jī)算例進(jìn)行測試。表1給出了在不同工作數(shù)量規(guī)模下，各組數(shù)據(jù)的計(jì)算時(shí)間，最后兩列給出的是不同規(guī)模下模型展開后的變量數(shù)和約束數(shù)。從表1數(shù)據(jù)可以看出，本文提出的多目標(biāo)整數(shù)規(guī)劃模型對(duì)于較大規(guī)模算例同樣適用，且隨著問題規(guī)模的擴(kuò)大，計(jì)算時(shí)間基本呈遞增趨勢(shì)。

4 結(jié)論

本文對(duì)Pm|prmp|Cmax和Qm|prmp|Cmax兩類制造期可中斷的并行機(jī)調(diào)度問題，給出了多目標(biāo)的混合整數(shù)規(guī)劃模型解法。針對(duì)現(xiàn)有LRPT、LRPT-FM啟發(fā)式解法存在的中斷次數(shù)較多的缺陷，多目標(biāo)的混合整數(shù)規(guī)劃模型將制造期和工作段數(shù)通過加權(quán)同時(shí)最小化，實(shí)現(xiàn)了多目標(biāo)的需求。在求解過程中使用MLeap建模語言對(duì)模型進(jìn)行表達(dá)，之后調(diào)用外部求解器CPLEX進(jìn)行求解。通過算例驗(yàn)證表明，該方法能夠解決現(xiàn)有算法的缺陷，將工作段數(shù)最小化，能夠在較短時(shí)間內(nèi)求出問題的精確最優(yōu)解。

表1 較大規(guī)模算例測試結(jié)果