考慮成本的最大延遲時(shí)間同類機(jī)調(diào)度問題

李 凱, 楊 陽, 劉渤海

(1.合肥工業(yè)大學(xué) 管理學(xué)院,安徽 合肥 230009; 2.過程優(yōu)化與智能決策教育部重點(diǎn)實(shí)驗(yàn)室,安徽 合肥 230009)

0 引言

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

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

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

1 問題描述

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

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

minLmax

(1)

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

2 算法設(shè)計(jì)

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

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

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

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

Step5對于每一個(gè)作業(yè)j，計(jì)算Lij=Cij-dj，得到Lmax。

3 算法分析

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

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

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

=Cmax/Cmax(OPT)+1

(12)

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

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

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

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

因?yàn)長max=Lij=Cij-dij，可得Lmax≤Cmax-dmin，又因?yàn)長max(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

因?yàn)橛蠰ij=Cij-dij，所以此處存在Lmax(OPT)的計(jì)算結(jié)果有可能為負(fù)數(shù)的情況，但[Lmax(OPT)+dmin]/[Lmax(OPT)+dmax]不會為負(fù)，因?yàn)橐椎胐min對應(yīng)某一個(gè)已加工的作業(yè)j′的工期，有C′-dmin=L′，C′為j′的完工時(shí)間，L′為該作業(yè)加工的延遲時(shí)間，則有dmin=C′-L′，所以有Lmax(OPT)+dmin=Lmax(OPT)+C′-L′，又因?yàn)長′≤Lmax(OPT)，所以Lmax(OPT)+dmin>0，即[Lmax(OPT)+dmin]/[Lmax(OPT)+dmax]≥0。從而，有(Lmax+dmax)/[Lmax(OPT)+dmax]≤Cmax/Cmax(OPT)+1。

定理2在機(jī)器速度相同，即同型機(jī)時(shí)，按算法H進(jìn)行調(diào)度，可得式(13)。

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

(13)

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

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在機(jī)器速度不完全相同，即同類機(jī)時(shí)，按算法H進(jìn)行機(jī)器和作業(yè)的調(diào)度，可得式(14)。

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

(14)

證明在機(jī)器速度不完全相同時(shí)，顯然，在算法中的Step3和Step4中，每臺機(jī)器的最終完工時(shí)間在兩個(gè)步驟中沒有發(fā)生改變，即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設(shè)有四臺機(jī)器，它們的使用成本分別為S1=6,S2=5,S3=4,S4=3，加工速度分別為v1=6，v2=4，v3=3，v4=2，有一批作業(yè)需要加工，成本總預(yù)算為13，找到最優(yōu)調(diào)度方案，使得最大延遲時(shí)間最小化。參數(shù)如下：

表1 作業(yè)和工期參數(shù)

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

圖1 算例1的調(diào)度序列

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

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

表2 作業(yè)和工期參數(shù)

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

圖2 算例2的調(diào)度序列

計(jì)算可得Lmax=2.25，用Lingo得到的最優(yōu)解結(jié)果選擇M1、M3、M4三臺機(jī)器，最優(yōu)解的甘特圖如下

圖3 算例2的調(diào)度最優(yōu)序列

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

4 實(shí)驗(yàn)數(shù)據(jù)及分析

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

表3、表4和表5分別給出λ=0.3，λ=0.5，λ=0.7時(shí)，機(jī)器數(shù)為4，5，6，作業(yè)數(shù)為20，30，40的實(shí)驗(yàn)結(jié)果。

表3 λ=0.3時(shí)的實(shí)驗(yàn)結(jié)果

表4 λ=0.5時(shí)的實(shí)驗(yàn)結(jié)果

表5 λ=0.7時(shí)的實(shí)驗(yàn)結(jié)果

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

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

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

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

5 結(jié)論

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

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