趙玉芳, 田 野, 富曉雙

(沈陽師范大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院, 沈陽 110034)

0 引 言

文獻(xiàn)[6-8]是近期國內(nèi)有關(guān)加工時間可控的單機(jī)排序問題的論文。近年帶有資源分配的排序問題也受到更多學(xué)者的關(guān)注,即通過給工件分配額外資源的方式減少工件加工的時間。SHABTAY和KASPI[9]提出凸資源消耗函數(shù):pj=(wj/uj)k,其中wj為基本加工時間,uj>0為分配給工件Jj的資源量,k是給定的整數(shù)。WEI等[10]研究了工件的實(shí)際加工時間為關(guān)于開始加工時間和資源分配線性函數(shù)的單機(jī)排序問題。文獻(xiàn)[11-16]是關(guān)于資源分配相關(guān)的文章。高潔等[8]分別研究了帶有與工件位置相關(guān)的學(xué)習(xí)效應(yīng)和與工件開始時間相關(guān)的惡化效應(yīng)的單機(jī)排序問題。并對帶有資源約束的情況討論了線性資源分配的單機(jī)工期排序問題。WANG等[16]研究了帶有資源分配的單機(jī)提前延誤排序問題。其中工件的加工時間是關(guān)于開始時間、資源分配的函數(shù)。并證明此問題是多項(xiàng)式可解的。

本文研究了帶有學(xué)習(xí)效應(yīng)、惡化效應(yīng)和資源分配的單機(jī)工期分配問題。文獻(xiàn)[16]從2種不同加工時間函數(shù)和3種不同的工期分配方法的角度分析了帶有資源分配的單機(jī)工期分配模型。本文的不同之處是提出凸性資源分配情況下工件的實(shí)際加工時間,表示為:pjr=(pjar-1/uj)c+bt,uj>0。并從CON、SLK及DIF這3種不同的工期分配問題的角度分析。找到最優(yōu)排序π*,使包含提前、延誤、工期、總資源消耗的目標(biāo)函數(shù)最小。并證明這些問題都是多項(xiàng)式時間可解的。

1 問題描述

本文研究帶有學(xué)習(xí)效應(yīng)、惡化效應(yīng)及資源分配的單機(jī)工期排序問題,模型描述如下:

設(shè)有n個工件且在0時刻全部到達(dá),n個工件的集合為J={J1,J2,…,Jn},其中pj表示工件Jj的基本加工時間,dj表示工件Jj的工期。對于任意給定的排序π,研究帶有凸性資源分配問題,工件的實(shí)際加工時間為

(1)

其中:b表示工件的惡化系數(shù),且b≥0;00,c是常數(shù),且c>0。

用[j]表示第j個位置的工件;Cj表示工件Jj的完工時間。Ej=max{0,dj-Cj}表示工件Jj提前時間;Tj=max{Cj-dj,0}表示工件Jj延誤時間;α、β、γ分別表示工件提前、延誤和工期的單位系數(shù),Gj表示單位懲罰加權(quán)系數(shù)。目標(biāo)是確定最優(yōu)排序π*,使目標(biāo)函數(shù)值最優(yōu)。其中目標(biāo)函數(shù)包含提前、延誤、工期、資源分配等,表示為

本文從3種常見的工期分配問題的角度進(jìn)行研究。3種工期分配問題分別為

1) 公共工期(CON):所有工件都有相同的工期dj=d(j=1,2,…,n),其中d≥0為決策變量;

2) 松弛工期(SLK):dj=pj+q,j=1,2,…,n,其中q≥0為決策變量;

3) 無限制工期(DIF):每個工件都有不同的工期,且工期的分配不受任何限制。

用三參數(shù)表示法,本文研究的問題可表示為

2 主要結(jié)論

關(guān)于CON、SLK及DIF三種工期分配問題,與文獻(xiàn)[16]類似,有如下結(jié)論:

圖1 排序π*的甘特圖Fig.1 The Gantt chart of sequence π*

1) 對于CON工期,最優(yōu)工期的值與某個工件的完工時間相同,即d=C[k];

2) 對于SLK工期,決策變量q=C[k-1];

3) 對于DIF工期,如果當(dāng)γ≥β有dj=0;當(dāng)γ<β有dj=Cj。

證明 對于CON工期,假設(shè)d在第k個工件加工過程中。即d-C[k-1]=δ>0。

此時目標(biāo)函數(shù)為

若記:A=α(k-1)-β(n-k+1)+γn

則f(d,π)=Aδ+B

其中k由下式得到

(2)

同理可證SLK及DIF工期。

對于不帶資源分配的問題有如下結(jié)論:

(3)

2.1 CON工期

在CON工期分配問題中,所有工件都有相同的工期dj=d(j=1,2,…,n),d≥0,最優(yōu)工期的值與某個工件的完工時間相同d=C[k],其中k值可由式(2)得到。則前k-1個工件提前;第k個工件恰好在工期時間完成;第k+1個到第n個工件延誤。對于任意排序π有

綜上,目標(biāo)函數(shù)為

設(shè)wj=min{nγ+α(j-1),β(n-j+1)},則

2.2 SLK工期

綜上,目標(biāo)函數(shù)為

設(shè)wj=min{αj+nγ,β(n-j)},與CON工期推導(dǎo)類似可得

2.3 DIF工期

由引理2可知,對于DIF工期分配問題,在最優(yōu)排序中,當(dāng)γ≥β時有dj=0。此時對于任意j,Ej=0,Tj=Cj;當(dāng)γ<β時有dj=Cj。此時對于任意j,Ej=Cj,Tj=0。綜上,目標(biāo)函數(shù)為

設(shè)wj=min{γ,β}(n-j+1)。與CON工期推導(dǎo)類似可得

綜上,CON、SLK及DIF這3種不同工期分配問題的目標(biāo)函數(shù)表達(dá)形式類似。則可以得到以下引理:

(4)

其中

引理5 對于任意排序π,CON、SLK及DIF這3種不同工期分配問題的最優(yōu)資源分配均可以寫為

(5)

證明 由式(5)知,對于任意排序π,為了使目標(biāo)函數(shù)最優(yōu),需對式(4)求導(dǎo):

令f′=0有

對于CON、SLK及DIF這3種不同工期分配問題,將式(5)代入式(4)中得到

(6)

其中

由式(7)和式(8)知,θ[j]只與工件相關(guān),φj只與位置相關(guān)。為了找到3種不同工期分配問題下凸性資源消耗函數(shù)的最優(yōu)排序,需要將位置懲罰φj與工件相關(guān)花費(fèi)θ[j]進(jìn)行最優(yōu)匹配:

引理6 3種不同工期分配方法下凸性資源消耗函數(shù)的最優(yōu)排序π*可以通過以下方法得到:位置懲罰φj的最小值與工件相關(guān)花費(fèi)θ[j]的最大值相匹配,位置懲罰φj的第2小的值與工件相關(guān)花費(fèi)θ[j]的第2大的值相匹配,以此類推。

證明 由文獻(xiàn)[18]知,2個向量相乘逆序排列時函數(shù)值最小

對于該問題可用如下算法求解:

算法

步驟2 由式(7)、式(8)計(jì)算φj與θ[j]的值,其中j=1,2,…,n;

步驟3 按位置懲罰φj的值從小到大,相關(guān)花費(fèi)θ[j]的值從大到小的順序進(jìn)行匹配。

定理1 算法能在O(nlogn)時間內(nèi)解決3種不同工期分配方法下凸性資源分配函數(shù)的排序問題。

證明 算法中步驟1、2可以在線性時間內(nèi)執(zhí)行,步驟3需要用O(nlogn)時間內(nèi)執(zhí)行,因此算法的總計(jì)算復(fù)雜度為O(nlogn)。

3 結(jié) 論

本文研究了帶有學(xué)習(xí)效應(yīng)、惡化效應(yīng)和資源分配相關(guān)的單機(jī)工期分配問題。確定了最優(yōu)排序,使包含提前、延誤、工期、總資源消耗的函數(shù)最小。證明該問題在O(nlogn)時間內(nèi)可解。本文僅研究了單機(jī)狀態(tài)下的排序問題,還可將該問題推廣至平行機(jī)或流水作業(yè)等其他復(fù)雜的排序問題;或者還可以增加影響工件加工時間的其他因素,比如帶有維修的情況。