羅成新, 李 石

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

排序理論是組合最優(yōu)化學(xué)科的重要組成部分之一,具有非常重要的理論意義,廣泛應(yīng)用于各個(gè)學(xué)科之中。大型復(fù)雜工作排序的好壞對(duì)工程費(fèi)用大小影響很大。在傳統(tǒng)調(diào)度模型之下,大多數(shù)假定任務(wù)的加工時(shí)間是一個(gè)給定的常數(shù)值,但隨著科學(xué)技術(shù)的迅速發(fā)展,人們發(fā)現(xiàn)這種假設(shè)并不能更好地貼近實(shí)際生活。影響工件加工時(shí)間的原因多種多樣,如因機(jī)器老化而造成的退化效應(yīng),或因工人反復(fù)操作提高技術(shù)而產(chǎn)生的學(xué)習(xí)效應(yīng),或資源分配等情況,任務(wù)的加工時(shí)間不再是固定不變的。Liu等[1]研究了帶有學(xué)習(xí)效應(yīng)且加工時(shí)間依賴于資源分配的最優(yōu)交貨期排序問(wèn)題,目標(biāo)是通過(guò)獲得最優(yōu)交貨期位置和最優(yōu)排序使目標(biāo)值最小;王吉波等[2]研究了同時(shí)具有學(xué)習(xí)和惡化效應(yīng)的不同工期的指派問(wèn)題;文獻(xiàn)[3-4]相繼研究了同時(shí)具有學(xué)習(xí)效應(yīng)和退化效應(yīng)的單機(jī)調(diào)度問(wèn)題。近年來(lái)帶有交貨期窗口的問(wèn)題逐漸走進(jìn)了人們的視野,相比于交貨期問(wèn)題[5-7],更加貼近實(shí)際生產(chǎn)的需要。Sidney[8]首先提出了帶有交貨期窗口指派的單機(jī)排序問(wèn)題,目標(biāo)是找到工件的最優(yōu)排序及提前、誤工的最小費(fèi)用。此類問(wèn)題中規(guī)定若一個(gè)工件在交貨期窗口起始時(shí)間之前完成,則需要承擔(dān)一部分提前懲罰費(fèi)用;若一個(gè)工件在交貨期結(jié)束之后完工,則需要接受一部分延誤懲罰費(fèi)用[9-11]。

此外,帶有資源分配的問(wèn)題也逐漸得到了人們的關(guān)注。Wang等[12]研究了帶有截?cái)嗫刂茀?shù)學(xué)習(xí)效應(yīng)、退化效應(yīng)、資源分配的單機(jī)調(diào)度問(wèn)題;Ji等[13]研究了帶有公共交貨期窗口且?guī)в匈Y源分配、退化效應(yīng)和維修活動(dòng)的單機(jī)排序問(wèn)題。本文在上述2篇論文的基礎(chǔ)上,假定所有工件有一個(gè)公共交貨期窗口,研究同時(shí)具有截?cái)嗫刂茀?shù)學(xué)習(xí)效應(yīng)和退化效應(yīng)且工件加工時(shí)間依賴于凸資源分配的單機(jī)調(diào)度問(wèn)題。進(jìn)一步推廣了目標(biāo)函數(shù),通過(guò)確定最優(yōu)交貨期窗口位置以及規(guī)模、最優(yōu)資源分配方案及最優(yōu)排序,求出目標(biāo)函數(shù)最優(yōu)值。分2種情況:限制資源總費(fèi)用的前提下,使提前、延誤、工期窗口開始時(shí)間、工期窗口大小、絕對(duì)完工差異、總完工時(shí)間和、總資源費(fèi)用最小;限制帶有提前、延誤等費(fèi)用,極小化總資源量,證明所研究的2種問(wèn)題是多項(xiàng)式時(shí)間可解的,并給出2個(gè)最優(yōu)算法。

1 問(wèn)題描述

研究下面問(wèn)題:有一臺(tái)機(jī)器,設(shè)n個(gè)獨(dú)立工件N={J1,J2,…,Jn}需在這臺(tái)機(jī)器上連續(xù)加工,即加工期間不允許中斷。其中,一臺(tái)機(jī)器同一時(shí)間最多只能加工一個(gè)工件,全部工件在0時(shí)刻到達(dá)并且為可用狀態(tài)。本文中,考慮帶有截?cái)嗫刂茀?shù)的學(xué)習(xí)效應(yīng)和退化效應(yīng)的凸資源分配模型,設(shè)工件Jj的實(shí)際加工時(shí)間表達(dá)式為

其中:m>0是一個(gè)給定的正常數(shù);pj為工件Jj的基礎(chǔ)加工時(shí)間;aj≤0是工件Jj的學(xué)習(xí)指數(shù);b(0

問(wèn)題1 目標(biāo)是在資源消耗總費(fèi)用不大于常數(shù)U的前提下,求出最優(yōu)資源分配方案和最優(yōu)工件排序、最優(yōu)交貨期窗口位置d,ω。極小化目標(biāo)函數(shù)Z1如下:

其中α>0,β>0,γ>0,δ≥0,μ1≥0,μ2≥0為給定常數(shù)。

使用文獻(xiàn)[14]的三參數(shù)表示法,可將上述問(wèn)題分別表示為

2 最優(yōu)算法

2.1 最優(yōu)解性質(zhì)

引理1 在最優(yōu)排序下,機(jī)器相鄰工件之間無(wú)空閑時(shí)間。

引理2 對(duì)于任一固定排序π=(J[1],J[2],…,J[n]),存在一個(gè)最優(yōu)公共交貨期窗口,其中交貨期窗口的開始時(shí)間d和結(jié)束時(shí)間ω與某些工件的完工時(shí)間一致。

證明 詳細(xì)證明類似于Mosheiov and Sarig(2009)中引理3,從略。

2.2 最優(yōu)算法

引理4 問(wèn)題1中對(duì)于給定的工件排序π=?J[1],J[2],…,J[n]」,可以得到最優(yōu)資源分配為

(3)

其中P[j]表示工件的正常加工時(shí)間。

證明

其中λ為拉格朗日乘子,分別對(duì)λ,u[j]求偏導(dǎo),令其為0,得

利用式(4)和式(5)得到

由式(6)和式(7)得到式(3)。證畢。

引理5 給定排序π(J[1],J[2],…,J[n]),問(wèn)題1和2中工件J[k](k=1,2,…,n)的實(shí)際加工時(shí)間為

(8)

證明 證明過(guò)程略。

由此可以得出

其中

將上述算式代入到Z1(π,u*)中,得到

(11)

為了求出最小值,考慮指派問(wèn)題如下,記

則問(wèn)題轉(zhuǎn)化為如下指派問(wèn)題

故針對(duì)問(wèn)題1可以得到下列最優(yōu)算法

算法1

第1步 依據(jù)引理3,求出k與l的數(shù)值;

第2步 依據(jù)(12)求出νjr的數(shù)值,j,r=1,2,…,n;

第3步 計(jì)算求解指派問(wèn)題(13)～(16),分析得到最優(yōu)排序π*=(J[1],J[2],…,J[n]);

第5步 賦值d=C[k],ω=C[j]。

定理1 對(duì)于問(wèn)題1可以通過(guò)求解指派問(wèn)題在O(n3)時(shí)間內(nèi)求得最優(yōu)解。

證明 定理結(jié)論的正確性由上述分析保證。第1、4、5步可以在O(1)時(shí)間內(nèi)完成,第2、3步需要O(n3)時(shí)間內(nèi)完成,所以算法的時(shí)間復(fù)雜性為O(n3)。

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

(17)

證明 對(duì)于給定排序π=(J[1],J[2],…,J[n]),拉格朗日函數(shù)如下:

其中λ為拉格朗日乘子。分別對(duì)λ,u[j]求偏導(dǎo),分別令其為0,有

由式(18)和式(19)得到

將式(17)代入到Z2中,得到

為了求出最小值,將其轉(zhuǎn)化為指派問(wèn)題,令

(22)

考慮指派問(wèn)題如下。令

(23)

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

(24)

(25)

(26)

xjr=0或1j,r=1,2,…,n

(27)

算法2

第1步 依據(jù)引理3,求得k與l:

第2步 依據(jù)式(22)求得τjr,j,r=1,2,…,n;

第3步 求解指派問(wèn)題式(24)～式(27),得出最優(yōu)排序π=(J[1],J[2],…,J[n]);

第5步 賦值d=C(k),ω=C(l)。

定理2 問(wèn)題2可通過(guò)利用求解指派問(wèn)題的方法在O(n3)時(shí)間之內(nèi)計(jì)算得到最優(yōu)解。

證明 證明過(guò)程略。

下面給出問(wèn)題1的一個(gè)實(shí)例,說(shuō)明算法的運(yùn)算過(guò)程。

例n=6,α=9,β=12,γ=5,δ=7,μ1=μ2=1,c=0.05,b=0.6,m=4,k=1,q=2,U=80,任務(wù)的基礎(chǔ)加工時(shí)間、學(xué)習(xí)指數(shù)、由于資源分配造成的單位費(fèi)用由表1給出。

表1 例1的數(shù)據(jù)Tab.1 Date of example 1

表2 例1中的υjr值Tab.2 υjr of example 1

3 結(jié) 論

本文研究帶有凸資源分配以及公共交貨期窗口的單機(jī)排序問(wèn)題,其中工件加工時(shí)間帶有截?cái)嗫刂茀?shù)學(xué)習(xí)效應(yīng)和退化效應(yīng).本文列舉2種問(wèn)題:1)限制資源總費(fèi)用情況下極小化提前懲罰、延誤懲罰等總費(fèi)用;2)帶有提前、延誤等費(fèi)用受限的情況下極小化總資源。分別給出目標(biāo)函數(shù)求得最小值的最優(yōu)算法,并證明問(wèn)題可在多項(xiàng)式時(shí)間內(nèi)解決,確定最優(yōu)排序及最優(yōu)資源分配,給出多項(xiàng)式時(shí)間算法。