考慮成本的最大延遲時間同類機調度問題

李 凱, 楊 陽, 劉渤海

(1.合肥工業大學 管理學院,安徽 合肥 230009; 2.過程優化與智能決策教育部重點實驗室,安徽 合肥 230009)

0 引言

機器調度問題一直是生產領域學者們關注的重點，單機和同型機里的多數問題已被研究，但在現實生活中，隨著科技的進步，新老機器共同使用，使得所有的加工機器未必速度都相同，研究在同類機上如何更好的安排作業加工顯得尤為重要。單機調度指將若干工件放在一臺機器上進行排序調度。同型機調度則指的是若干速度相同的機器對工件進行排序加工。本文研究的同類機調度問題是指在若干速度不完全相同的一組機器上共同調度完成所需加工的作業。在一些經典的同類機問題的基礎上，學者們不斷探索在新的問題條件下，如何更好的優化結果。Zou et al.[1]考慮了作業的處理時間是其開始時間的線性遞增函數的同類機調度問題，優化目標是盡量減少作業的總完工時間和以及機器的總負載，證明了該問題是多項式可解的，并給出了相關方案來解決這個問題。Kim[2]研究了同類機上調度作業具有優先約束條件來最小化加權總完工時間的問題，并提出了基于LP的列表調度啟發式算法，進行了數值實驗來驗證。Lin et al.[3]假定完工時間有限，研究了最小化總資源消耗的同類機調度問題，提出了一種數學啟發式算法，并比較結果發現明顯優于PSO元啟發式算法。Lee et al.[4]拓展到具有學習效應的同類機調度，其目標是尋找操作員對機器的最優分配和最小化完工時間的最佳時間表，提出了兩種啟發式算法，并進行計算實驗以評估其性能。馬英等人[5]研究了帶機器準備時間的同類機最大完工時間調度問題，提出一種啟發式算法，利用工件互換性質重復對最大完工時間最大和最大完工時間最小的兩臺機器上的工件進行交換，來提高解的質量。另外，同時考慮多個目標的同類機調度問題，也是學者們研究的方向。陳榮軍和唐國春[6]考慮了以生產排序費用和發送費用總和最少為目標函數的同類機供應鏈排序問題，其中生產排序費用中分別用最大送貨時間和平均送貨時間來反映制造商服務水平，研究了兩種生產排序費用情形下的目標函數，用動態規劃算法構造了多項式時間近似算法，并分析了算法的性能比。

在研究相關調度問題時，完工時間問題一直被大部分學者所考慮。在實際生產中，企業在安排生產時間的同時，還必須要使生產時間不能錯過客戶定好的工期，以更好的滿足客戶需求。本文在機器成本限制的條件下，研究了作業加工的最小化最大延遲時間問題。劉樂和周泓[15]設計了含兩階段的啟發式算法以及精確求解問題的分支定界算法，研究解決在一批新工件突然到達的干擾條件下，總序位干擾量受上限的單機最大延遲時間重調度問題。Lin和Jeng[16]考慮了作業在同型機上的批調度問題，目標是減少最大延遲時間和延遲作業數量，為此設計了動態規劃算法來尋找兩個目標的最優解，同時還設計了幾種啟發式算法，并進行計算實驗來研究他們的相對性能。針對同類機上最小化最大延遲時間問題，Li et al.[17]為使作業最大延遲時間最小，提出了一種名為LPDT-SA的模擬退火算法，并隨機生成大量數據以測試解決效果。張玉忠等人[18]揭示了分批排序問題和經典排序問題之間的聯系，討論了最小化最大完成時間以及最小化最大延遲兩類問題，提出了近似算法并用“轉換引理”分析了這些算法的最差性能。

本文在上述論文的基礎上考慮機器具有不同固定使用成本的同類機調度問題，目標函數是總成本預算范圍內最小化最大延遲時間。本文后面章節安排如下：第1節給出問題并進行分析，構建了問題模型；第2節給出設計的啟發式算法；第3節對算法性能進行理論分析并給出兩個算例的解答過程；第4節通過計算機軟件提供隨機數據進行實驗驗證算法的性能；第5節總結了全文并考慮了在本文基礎上的進一步工作。

1 問題描述

本文研究了考慮機器固定使用成本的同類機調度問題。在給定的機器集M={Mi|i=1,2,…,m}中，有m臺加工速度不同的機器，vi表示機器Mi(i=1,2,…,m)的加工速度，其中vi(vi>0)是正整數，用Si表示機器Mi(i=1,2,…,m)的固定使用成本，其中Si(Si>0)是正整數。在現實生活中，當機器的加工速度慢和使用成本高兩個結果并存時，必將為生產廠家淘汰，而新式的機器加工速度快的同時，使用成本也會略高，所以我們假設當vi≥vt(i,t=1,2,…,m;i≠t)時，vi/Si≥vt/St，即加工速度越快的機器，單位成本內加工速度越快。不失一般性，將機器集中的各個機器按加工速度不增排序，使v1≥v2≥…≥vi≥…≥vm。對于任意機器Mi(i=1,2,…,m)，若vi=vi+1，則令Si≤Si+1。

為了便于問題表示，引入下列符號。引入0-1變量xijk用于表示作業Jj是否在機器Mi的位置k上加工，若加工則為1，否則為0。0-1變量yi表示機器Mi是否被使用，若使用則為1，否則為0。整數規劃模型如下：

minLmax

(1)

其中，(1)表示規劃模型的目標函數；等式(2)表示每個作業只會被調度到一個機器的一個位置上；等式(3)保證對于每個機器上的每個位置只能有一個作業；不等式(4)表示第i臺機器的第k個位置作業的完成時間；等式(5)表示第i臺機器的第k個位置上作業的工期；等式(6)表示作業的延遲時間等于作業完工時間和作業工期之差；不等式(7)表示調度的最大延遲時間為作業的最大延遲時間；等式(8)表示確定機器是否被使用；不等式(9)表示調度總成本不能超過給定成本上限；(10)和(11)分別表示xijk和yi只能為0-1變量。

2 算法設計

本文的主要思路涉及到兩方面，一方面是機器選擇的問題，另一方面則考慮作業的排序問題。結合問題條件，在給定的總成本預算范圍內優先選擇使算法結果更優的機器，然后引申用LPT(Longest Processing Time First，最長加工時間優先)、ECT(Earliest Completion Time First，最早完工時間優先)、EDD(Earliest Due Date First，最早工期優先)規則對作業進行排序，設計一個啟發式算法，實現最大延遲時間最小化的目標。

Step2將集合A中的機器重新編號：M1,M2,…,Mf。

Step3將作業按pj非增排序，若有作業pj相等，則按dj非減排序。將作業J1放在機器M1上加工，之后的作業依次遍歷所有已選機器，選取完工時間Cij最小的機器Mi加工。

Step4所有作業均安排好機器加工后，將集合A中的機器上的作業，按dj非減的順序重新排列。若有作業dj相等，則按pj非減排序。

Step5對于每一個作業j，計算Lij=Cij-dj，得到Lmax。

3 算法分析

大部分文獻主要用[Lmax-Lmax(OPT)]/[Lmax(OPT)+dmax]證明算法的延遲時間的誤差界，本文擴展到證明(Lmax+dmax)/[Lmax(OPT)+dmax]的誤差界，并具體分析和證明了算法在機器加工速度相同和不同時的最大誤差界，然后通過實際算例來說明算法的執行情況。

定理1算法H的最大延遲時間的最大誤差界可以表示為式(12)。

(Lmax+dmax)/[Lmax(OPT)+dmax]

=Cmax/Cmax(OPT)+1

(12)

證明設dmax和dmin分別為作業中的最長工期和最短工期，dh為最優排序中最后完工作業的工期，Lmax(OPT)表示為問題最優排序中的最大延遲時間，Cmax表示通過該算法得出的排序中的最大完成時間，Cmax(OPT)為該問題最優排序中的最大完成時間，有

[Lmax-Lmax(OPT)]/[Lmax(OPT)+dmax]

=[Lmax-Lmax(OPT)+dmax-Lmax]/[Lmax(OPT)+dmax]

=(Lmax+dmax)/[Lmax(OPT)+dmax]-1

因為Lmax=Lij=Cij-dij，可得Lmax≤Cmax-dmin，又因為Lmax(OPT)≥Cmax(OPT)-dh≥Cmax(OPT)-dmax，可得Lmax(OPT)+dmax≥Cmax(OPT)，則

(Lmax+dmax)/[Lmax(OPT)+dmax]

=[Lmax-Lmax(OPT)]/[Lmax(OPT)+dmax]+1

≤[Cmax-dmin-Lmax(OPT)]/[Lmax(OPT)+dmax]+1

=Cmax/[Lmax(OPT)+dmax]-[Lmax(OPT)+dmin]/

[Lmax(OPT)+dmax]+1

≤Cmax/Cmax(OPT)-[Lmax(OPT)+dmin]/

[Lmax(OPT)+dmax]+1

因為有Lij=Cij-dij，所以此處存在Lmax(OPT)的計算結果有可能為負數的情況，但[Lmax(OPT)+dmin]/[Lmax(OPT)+dmax]不會為負，因為易得dmin對應某一個已加工的作業j′的工期，有C′-dmin=L′，C′為j′的完工時間，L′為該作業加工的延遲時間，則有dmin=C′-L′，所以有Lmax(OPT)+dmin=Lmax(OPT)+C′-L′，又因為L′≤Lmax(OPT)，所以Lmax(OPT)+dmin>0，即[Lmax(OPT)+dmin]/[Lmax(OPT)+dmax]≥0。從而，有(Lmax+dmax)/[Lmax(OPT)+dmax]≤Cmax/Cmax(OPT)+1。

定理2在機器速度相同，即同型機時，按算法H進行調度，可得式(13)。

(Lmax+dmax)/[Lmax(OPT)+dmax]≤7/3

(13)

證明在機器速度都相同的情況下，算法在Step3的步驟可以進行簡化，在遍歷機器選擇加工時間最小的機器加工時，當機器速度相同時，即為在同型機中最小化最大完工時間問題，由《排序引論》[19]可知，當用LPT算法安排作業，令f為選擇的機器數，則有

Cmax(LPT)/Cmax(OPT)≤4/3-1/(3f)

由定理1可知，

(Lmax+dmax)/[Lmax(OPT)+dmax]

=[Lmax-Lmax(OPT)]/[Lmax(OPT)+dmax]+1

≤Cmax/Cmax(OPT)+1≤7/3-1(3f)≤7/3

定理3在機器速度不完全相同，即同類機時，按算法H進行機器和作業的調度，可得式(14)。

(Lmax+dmax)/[Lmax(OPT)+dmax]≤3+2/(N-1)

(14)

證明在機器速度不完全相同時，顯然，在算法中的Step3和Step4中，每臺機器的最終完工時間在兩個步驟中沒有發生改變，即Cmax不變，由Li et al.[20]可知，Cmax/Cmax(OPT)≤2[1+1/(N-1)]，由定理1可得式

(Lmax+dmax)/[Lmax(OPT)+dmax]

=[Lmax-Lmax(OPT)]/[Lmax(OPT)+dmax]+1

≤Cmax/Cmax(OPT)+1≤3+2/(N-1)

算例1設有四臺機器，它們的使用成本分別為S1=6,S2=5,S3=4,S4=3，加工速度分別為v1=6，v2=4，v3=3，v4=2，有一批作業需要加工，成本總預算為13，找到最優調度方案，使得最大延遲時間最小化。參數如下：

表1 作業和工期參數

解：按照算法要求選擇機器，選擇機器M1和M2，總成本為11，未超過預算。按照算法的調度規則將作業放在選擇的兩臺機器上，給出算法解的甘特圖。

圖1 算例1的調度序列

計算可得Lmax=3，通過Lingo軟件求得此問題的最優解即為本算法求得的結果，所以，(Lmax+dmax)/[Lmax(OPT)+dmax]=1。

算例2設有四臺機器，它們的使用成本分別為S1=10,S2=9,S3=8,S4=7，加工速度分別為v1=5，v2=4，v3=3，v4=2，有一批作業需要加工，成本總預算為25，找到最優調度方案，使得最大延遲最小化。參數如下：

表2 作業和工期參數

解：按照算法要求選擇機器，選擇機器M1和M2，總成本為19，未超過預算。按照算法的調度規則將作業放在選擇的兩臺機器上，算法解的甘特圖如下：

圖2 算例2的調度序列

計算可得Lmax=2.25，用Lingo得到的最優解結果選擇M1、M3、M4三臺機器，最優解的甘特圖如下

圖3 算例2的調度最優序列

計算可知為Lmax(OPT)為1.8，所以(Lmax+dmax)/[Lmax(OPT)+dmax]=185/176。

4 實驗數據及分析

本節將通過隨機實驗來驗證算法的有效性。設計的算法在Java中用MyEclipse編輯器實現。實驗環境：CPU：Inter(R)Core(TM)i5-3470 3.20GHz，RAM：4.00GB，線性規劃模型通過Lingo軟件完成。利用計算機隨機生成一些數據，分別考慮作業數為20、30、40以及機器數為4、5、6時算法的效果。

表3、表4和表5分別給出λ=0.3，λ=0.5，λ=0.7時，機器數為4，5，6，作業數為20，30，40的實驗結果。

表3 λ=0.3時的實驗結果

表4 λ=0.5時的實驗結果

表5 λ=0.7時的實驗結果

綜合表3、4、5可以得出：

(1)當λ為0.3、0.5、0.7時，隨著所選機器的速度變大，延遲時間相應減少 ，且G(E)的值全部都在[1,1.2669]范圍內，則算法滿足定理3，即(Lmax+dmax)/[Lmax(OPT)+dmax]≤3+2/(N-1)，且算法的實際誤差可能更小。

(2)當m，n和dmax均相同時，Lmax的值隨著值的增大而減小，進一步說明了成本會對算法取得的解具有約束作用。

(3)觀察實驗所得的Gap值，算法獲得的最好偏差是0.0000，最差誤差是0.5971，平均誤差為0.1353，可見算法的求解結果與最優值之間的偏離程度不大，表明算法性能較好。

5 結論

本文研究了一類考慮機器成本的同類機調度問題，目標函數是在給定的成本預算里最小化最大延遲時間。為解決該問題，我們建立了混合整數規劃模型，設計了相關算法，并理論證明了(Lmax+dmax)/[Lmax(OPT)+dmax]≤3+2/(N-1)，且通過大量實驗檢驗了該算法解的有效性。

在以后的研究中，可進一步考慮機器成本與機器速度相關同類機情況下，問題的求解方法。在本文基礎上，引入亞啟發式算法，考慮成本與最小化最大延遲時間的多目標問題。除此之外，還可以拓展研究同類機其他目標函數的類似問題。