可中斷制造期的并行機調度問題的多目標優(yōu)化研究

（北京交通大學 機械與電子工程控制學院，北京 100044）

0 引言

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

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

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

1 問題及傳統算法描述

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

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

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

2 多目標混合整數規(guī)劃模型及MLeap表達

2.1 模型建立

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

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

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

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

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

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

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

2.2 MLeap建模表達

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

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

圖1 Qm |prmp|Cmax數學模型Mleap建模語言表達

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

在MLeap模型被正確寫出之后，只需輸入問題的數據文件，讀入參數，便可選擇使用MLeap內置求解器或者調用外部求解器CPLEX求解模型。此過程可以使用C++語言將整個過程封裝成一個不需要用戶干預的程序，進而實現求解過程的自動化。

3 算例

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

3.1 Pm|prmp|Cmax問題算例

考慮2臺機器和3項工作，即工作1，2和3，加工時間為8，7和6。

整數時間下，LRPT算法調度結果如圖2所示，且制造期為11。

圖2 在整數時刻中斷，2臺機器和3項工作的LRPT算法

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

圖3 在整數時刻中斷，2臺機器和3項工作的多目標混合整數規(guī)劃建模求解

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

圖4 在任意時刻中斷，2臺機器和3項工作的LRPT算法

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

圖5 在任意時刻中斷，2臺機器和3項工作的多目標混合整數規(guī)劃建模求解

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

3.2 Qm|prmp|Cmax問題算例

考慮3臺機器1，2和3，具有加工速度3，2和1。有3項工作1，2和3，其加工時間是36，34和12。

整數時間下，LRPT-FM算法調度結果如圖6所示，且制造期為14。

圖6 在整數時刻中斷，3臺不同速度的機器和3項工作的LRPT-FM算法

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

圖7 在整數時刻中斷，3臺不同速度的機器和3項工作的多目標混合整數規(guī)劃建模求解

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

圖8 在任意時刻中斷，3臺不同速度的機器和3項工作的LRPT-FM算法

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

圖9 在任意時刻中斷，3臺不同速度的機器和3項工作的多目標混合整數規(guī)劃建模求解

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

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

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

4 結論

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

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