具有退化維護(hù)和資源分配的單機(jī)排序問題

羅成新, 王亞男

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

0 引 言

排序作為一門應(yīng)用科學(xué),有著深刻的實(shí)際背景,它主要產(chǎn)生于機(jī)器制造,后來被廣泛應(yīng)用于管理科學(xué)、運(yùn)輸業(yè)、計(jì)算機(jī)科學(xué)和工程技術(shù)等眾多領(lǐng)域。排序?qū)μ岣咝省①Y源的開發(fā)和配置、工程的進(jìn)展安排及經(jīng)濟(jì)運(yùn)行方面都起到輔助科學(xué)決策作用。

在實(shí)際中,由于工人或機(jī)器的工作時(shí)間較長(zhǎng),其工作效率降低,也就產(chǎn)生了所謂的退化效應(yīng)。Browne和Yechiali[1]首先對(duì)具有退化效應(yīng)的排序問題進(jìn)行了研究,其中工件的加工時(shí)間是與開始加工時(shí)間有關(guān)的線性不減函數(shù);文獻(xiàn)[2-3]分別對(duì)具有簡(jiǎn)單線性退化和線性遞減退化效應(yīng)的單機(jī)排序問題進(jìn)行了研究;Oron[4]在退化環(huán)境中排列具有可控加工時(shí)間的工件。

在實(shí)際情形中,交貨期的設(shè)定會(huì)對(duì)生產(chǎn)活動(dòng)產(chǎn)生一定的懲罰費(fèi)用,因而如何去設(shè)定交貨期,使得支付的費(fèi)用盡可能少成了需要探討的問題。Seidmann等[5]研究了單機(jī)排序問題中的最優(yōu)交貨期指派;Panwalker等[6]采用公共交貨期指派來極小化單機(jī)排序問題中的總懲罰;Cheng等[7]研究了具有退化效應(yīng)的交貨期指派問題,假設(shè)所有工件的退化率和交貨期都相同;Wang等[8]討論了帶有退化工件和依賴于資源的加工時(shí)間的單機(jī)交貨期指派問題;王吉波等[9]對(duì)同時(shí)具有學(xué)習(xí)和惡化效應(yīng)的不同工期指派問題進(jìn)行了研究;Li等[10]討論了帶有學(xué)習(xí)效應(yīng)和與資源有關(guān)的加工時(shí)間的最優(yōu)交貨期指派問題。

維護(hù)活動(dòng)主要可以提高生產(chǎn)加工的工作效率,避免由于加工時(shí)間過長(zhǎng)而多支付一些費(fèi)用。Mosheiov和Oron[11]研究交貨期指派和維護(hù)活動(dòng)排序問題;Mosheiov和Sidney[12]討論了在單機(jī)上排列一個(gè)退化的維護(hù)活動(dòng);Yang等[13]與Zhao和Tang[14]都研究了具有退化效應(yīng)和維護(hù)活動(dòng)的單機(jī)排序問題;在此基礎(chǔ)上,Yang等[15]討論了具有退化效應(yīng)和退化維護(hù)的單機(jī)排序問題與松弛交貨期指派問題,提出實(shí)際加工時(shí)間pjr=pjraj,j=1,2,…,n,但如果第r個(gè)位置的工件被排在了維護(hù)之后,它的實(shí)際加工時(shí)間就變?yōu)閜jr=pj(r-i)aj,目的是極小化總費(fèi)用函數(shù);Luo和Ji[16]探討在單機(jī)中排列一個(gè)可變的維護(hù)活動(dòng)和線性退化工件。

本文在上述文獻(xiàn)的基礎(chǔ)上,研究具有退化維護(hù)和資源分配的單機(jī)松弛交貨期指派排序問題。目標(biāo)是在資源總量有限的條件下,確定最優(yōu)公共松弛時(shí)間、最優(yōu)維護(hù)位置、最優(yōu)資源分配方案和最優(yōu)工件排序,使得目標(biāo)函數(shù)的總費(fèi)用最小。根據(jù)凸優(yōu)化相關(guān)知識(shí),將問題轉(zhuǎn)化為指派問題,證明了該問題在多項(xiàng)式時(shí)間內(nèi)是可解的,給出了多項(xiàng)式時(shí)間最優(yōu)算法。

1 問題描述

其中:l>0;pj為工件Jj的基本加工時(shí)間,即Jj排在第1個(gè)位置時(shí)的加工時(shí)間;aj≥0為工件Jj與位置有關(guān)的退化因子;c為退化速率;工件Jj的開始加工時(shí)間為t(t≥0);uj為分配給工件Jj的不可再生資源數(shù)量。

最小,其中α>0,β>0,γ>0,δ1>0,δ2>0為給定的常數(shù)。使用三參數(shù)表示法可將上述問題表示為

(1)

其中β域中的ma表示維護(hù)。

2 初步分析

下面,就問題的最優(yōu)排序提出了一些引理。一個(gè)重要的性質(zhì):最優(yōu)排序中第一個(gè)工件從零時(shí)刻開始加工且2個(gè)相鄰的工件之間沒有空閑。為了簡(jiǎn)便,假設(shè)在工件J[i]加工完成之后立即進(jìn)行維護(hù),即排在維護(hù)之前的工件數(shù)為i。

引理1 令J[j]表示在一個(gè)工件序列中,被排在第j個(gè)位置的工件。如果工件J[j]被排在維護(hù)之前,它的等待時(shí)間和完工時(shí)間分別為

其中C[0]=0。

證明 用歸納法進(jìn)行證明。此處省略,證畢。

引理2 令J[j]表示在一個(gè)工件序列中,被排在第j個(gè)位置的工件。如果工件J[j]被排在維護(hù)之后,它的等待時(shí)間和完工時(shí)間分別為

證明 與引理1證明類似

引理3 如果C[j]≤d[j],那么C[j-1]≤d[j-1],j=2,3,…,n;如果C[j]≥d[j],那么C[j+1]≥d[j+1],j=1,2,…,n-1。

引理4 對(duì)于任意指定的序列π,都存在一個(gè)最優(yōu)的松弛交貨期,它的公共松弛時(shí)間q等于某工件的等待時(shí)間。

接下來,確定其等待時(shí)間等于公共松弛時(shí)間q的工件J[k]的k值。要證明工件J[k]的位置是費(fèi)用參數(shù)的一個(gè)函數(shù)且與維護(hù)活動(dòng)無關(guān)。

證明 考慮一個(gè)最優(yōu)排序和最優(yōu)公共松弛時(shí)間,使得對(duì)某工件J[k]有q=C[k-1]=W[k],利用經(jīng)典擾動(dòng)技術(shù),研究當(dāng)移動(dòng)松弛時(shí)間時(shí)總費(fèi)用的變化。當(dāng)松弛時(shí)間左移ε個(gè)單位時(shí)間,總費(fèi)用的改變值為

-α(k-1)ε+β(n-k+1)ε-nγε

(2)

相反地,當(dāng)松弛時(shí)間右移ε個(gè)單位時(shí)間,總費(fèi)用的改變值為

αkε-β(n-k)ε+nγε

(3)

3 問題的最優(yōu)解

引理6 在問題(1)中,第k個(gè)工件的實(shí)際加工時(shí)間為

由上邊引理可得下述結(jié)論:

1) 如果在工件J[k]加工之前進(jìn)行維護(hù),即i

其中

2) 如果在工件J[k]完工之后進(jìn)行維護(hù),即i≥k,總費(fèi)用為

其中

引理7 對(duì)于問題(1),工件排序π=(J[1],J[2],…,J[n]可以得到最優(yōu)資源分配如下:

對(duì)于i

其中Ωj由式(5)給出。

另外,對(duì)于i≥k的情況:

(9)

其中Φj由式(7)給出。

證明 下面只證i

其中λ是拉格朗日乘數(shù)。式(10)分別對(duì)u[j]和λ求導(dǎo),并令導(dǎo)數(shù)為0,得

由式(12)得

(13)

由式(11)和式(13)得

(14)

由式(13)和式(14)得式(8)。證畢。

對(duì)于i

為了求出最優(yōu)解,將問題化為指派問題。對(duì)于r=1,2,…,n,引入

考慮指派問題如下,令

則可轉(zhuǎn)化為如下指派問題:

對(duì)于i≥k的情況,將式(9)代入式(6),得到目標(biāo)函數(shù)Z在最優(yōu)資源分配下的一個(gè)新的統(tǒng)一表達(dá)式:

為了求出最優(yōu)解,將問題化為指派問題。對(duì)于r=1,2,…,n,引入

考慮指派問題如下,令

則可轉(zhuǎn)化為如下指派問題:

因此,對(duì)于問題(1)可以給出如下最優(yōu)算法:

算法

第2步 令維護(hù)位置j=1;

第3步 求解指派問題式(15)～式(18)或式(19)～式(22),得到一個(gè)局部最優(yōu)排序和總費(fèi)用;

第4步j(luò)=j+1,如果j≤n,那么執(zhí)行第三步;否則,執(zhí)行第五步;

第5步 全局的最優(yōu)排序是局部最優(yōu)排序中總費(fèi)用最小的排序;

定理對(duì)于問題(1),利用算法可以通過求解指派問題在O(n4)時(shí)間內(nèi)得到最優(yōu)解。

證明 定理的正確性由上述分析保證。第1步的時(shí)間復(fù)雜度為O(1),第3步的時(shí)間復(fù)雜度為O(n3)。因?yàn)槿魏我粋€(gè)工件完工之后都可以立即進(jìn)行維護(hù),所以必須對(duì)n個(gè)不同的維護(hù)位置進(jìn)行評(píng)估進(jìn)而得到全局最優(yōu)解。因此求解問題(1)的時(shí)間復(fù)雜度為O(n4)。證畢。

4 結(jié) 論

本文研究了具有退化維護(hù)和資源分配的單機(jī)松弛交貨期指派排序問題。在資源總量有限的條件下確定最優(yōu)公共松弛時(shí)間、最優(yōu)維護(hù)位置、最優(yōu)資源分配方案和最優(yōu)工件排序,使得由工件的提前懲罰、延誤懲罰、交貨期公共松弛時(shí)間、最大完工時(shí)間、總完工時(shí)間構(gòu)成的總費(fèi)用最小。根據(jù)凸優(yōu)化的相關(guān)知識(shí),將問題轉(zhuǎn)化為指派問題,證明了該問題在多項(xiàng)式時(shí)間內(nèi)是可解的,給出了多項(xiàng)式時(shí)間最優(yōu)算法。