帶凸資源和惡化效應(yīng)的單機(jī)松弛窗口排序

姜昆

（汕頭職業(yè)技術(shù)學(xué)院 自然科學(xué)系，廣東 汕頭515078）

0 引言

排序是組合優(yōu)化問(wèn)題，具有重要的理論和現(xiàn)實(shí)意義。一直是國(guó)際上的研究熱點(diǎn)問(wèn)題之一。經(jīng)典的排序問(wèn)題假定工件（也叫任務(wù)）的加工時(shí)間為給定常數(shù)，但在實(shí)際的生產(chǎn)過(guò)程中，工件的實(shí)際加工時(shí)間可能與開(kāi)工時(shí)間（即惡化工件，參見(jiàn)文獻(xiàn)Ng等［1］，Wang和Wang［2］，王吉波等［3，4］，王吉波和趙伯來(lái)［5］，Gawiejnowicz［6］）和所用的資源（即資源約束或可控加工時(shí)間問(wèn)題，Shabtay和Steiner［7］，Lu等［8］，羅成新和翟雯瑾［9］）有關(guān)。比如，在鋼鐵制造企業(yè)的連鑄軋制生產(chǎn)過(guò)程中，煉鋼的基本單元是爐次，它是指同一座轉(zhuǎn)爐一次共同冶煉的鋼水。在煉鋼的連鑄階段，高溫熔融鋼水在連鑄機(jī)底部連續(xù)凝固成鋼坯。當(dāng)?shù)却龝r(shí)間增加時(shí)（即加工開(kāi)始時(shí)間延后），在連鑄機(jī)上加工的爐次的溫度將會(huì)降低，從而造成爐次加工時(shí)間的惡化（劉鵬等［10］）。在另一方面，在給爐次的加熱過(guò)程中需要資源（比如煤炭、電、天然氣等），顯然所用的資源越多，溫度達(dá)到期望的時(shí)間就越短，從而出現(xiàn)有關(guān)惡化效應(yīng)和資源約束典型的排序問(wèn)題。

Wei等［11］討論了工件具有惡化效應(yīng)和資源約束的單機(jī)排序問(wèn)題，其加工時(shí)間為開(kāi)始時(shí)間和資源分配量的線性函數(shù)pj＝aj+bSj-cuj，其中aj＞0為工件Jj的基本（正常）加工時(shí)間，uj＞0為分配給工件Jj的資源量，Sj≥0為工件Jj的開(kāi)始加工時(shí)間，b≥0是惡化率，c≥0是給定常數(shù)。用三參數(shù)表示法，Wei等［11］證明了問(wèn)題1｜pj＝aj+bSj-cuj｜F是多項(xiàng)式時(shí)間可解的，F(xiàn)∈｛δ1Cmax+δ2TC+δ3TADC+δ4gjujδ1Cmax+δ2TW+δ3TADW+，gj＞0為資源量uj的單位費(fèi)用，δ1≥0，δ2≥0，δ3≥0，δ4≥0是給定常數(shù)（由決策者給出），Cmax（TC，TW，TADC，TADW）為最大完工時(shí)間。Wang和Wang［12］研究了工件同時(shí)具有惡化效應(yīng)與凸資源約束的單機(jī)排序問(wèn)題，即加工時(shí)間為開(kāi)始時(shí)間和資源分配量的凸函數(shù)pj＝+bSj，其中wj為工件Jj的加工時(shí)間參數(shù)，k是給定的正數(shù)。Wang和Wang［12］證明了問(wèn)題1｜pj＝+bSj｜F，F(xiàn)∈｛δ1Cmax+δ2TC+δ3TADC+δ4gjuj，δ1Cmax+δ2TW+δ3TADW+｝是多項(xiàng)式時(shí)間可解的。Wang和Wang［13］研究了以文獻(xiàn)［11］和［12］為基礎(chǔ)的工期指派問(wèn)題，Wang和Wang［13］證明了問(wèn)題1｜A｜Ej+βTj+γdj+gjuj），A∈｛pj＝aj+bSj-cuj，pj＝+b S j｝對(duì)三種指派模型（即共同工期（dj＝d）指派，松弛工期（d j＝pj+q）指派，不同工期指派）是多項(xiàng)式時(shí)間可解的，其中dj為工件Jj的工期。在另一方面，Zhao等［14］研究了總資源消耗量有限的問(wèn)題1｜pj＝+bSj，∑uj≤U｜F（其中U是給定的總資源消耗量的上界，F(xiàn)∈｛Cmax，TC，TADC，TADW，Ej+βTj+γdj），（αEj+βTj+γd+δD）｝，d為窗口的開(kāi)始時(shí)間，D為窗口的長(zhǎng)度），他們證明了這些問(wèn)題都是多項(xiàng)式時(shí)間可解的。郭苗苗等［15］研究了Zhao等［14］的反問(wèn)題，即問(wèn)題1｜pj＝+bSj，F(xiàn)≤V｜（其中V是給定的排序費(fèi)用的上界，F(xiàn)∈｛Cmax，TCTW，TADC，TADW，（αEj+βTj+γd j）（αEj+βTj+γd+δD）｝，他們證明了這些問(wèn)題都是多項(xiàng)式時(shí)間可解的。

在準(zhǔn)時(shí)制（Just-In-Time）的生產(chǎn)過(guò)程中，一般考慮共同的窗口指派問(wèn)題，但為了更柔性的安排交貨期窗口，Wu等［16］和Li等［17］研究了工件具有松弛窗口指派（具體定義見(jiàn)下面的模型描述）的排序模型。受文獻(xiàn)Zhao等［14］、郭苗苗等［15］和松弛窗口的啟發(fā)，我們研究在松弛窗口下的工件同時(shí)具有惡化效應(yīng)和凸資源約束的排序問(wèn)題，目標(biāo)是確定工件的最優(yōu)排序、最優(yōu)的資源分配和松弛窗口的位置和長(zhǎng)度使總資源消耗費(fèi)用（排序費(fèi)用）小于或等于給定常數(shù)的條件下，最小化排序費(fèi)用（總資源消耗費(fèi)用），并且證明這兩個(gè)問(wèn)題是多項(xiàng)式時(shí)間可解的。

1 問(wèn)題描述

帶有凸資源和惡化效應(yīng)的松弛窗口排序問(wèn)題可描述為：設(shè)有零時(shí)刻到達(dá)的n個(gè)工件J1，J2，…，JN要在一臺(tái)機(jī)器上加工，所有工件加工過(guò)程中不能中斷。同Zhao等［14］和郭苗苗等［15］一樣，假設(shè)工件Jj的實(shí)際加工時(shí)間p為

其中wj為工件Jj的加工時(shí)間參數(shù)，uj為分配給工件Jj的不可更新資源的消耗量。每一個(gè)工件Jj都有一個(gè)交貨期窗口［］，，工件在這個(gè)交貨期窗口內(nèi)完工不受到懲罰。令Cj表示工件Jj的完工時(shí)間，Ej＝max｛0與Tj＝max｛0，Cj-｝分別代表工件Jj的提前時(shí)間與延誤時(shí)間。松弛窗口指的是＝pj+q1，＝pj+q2，其中q1和q2是松弛決策變量。本工作首先是研究所有工件的最優(yōu)排序、最優(yōu)資源分配和松弛決策變量q1和q2使得在總資源消耗費(fèi)用有上界限制的情況下使工件的提前時(shí)間、延誤時(shí)間、窗口的開(kāi)始時(shí)間和窗口長(zhǎng)度的線性組合最小，即問(wèn)題：

其中U表示總資源消耗費(fèi)用的上界，SLKW表示松弛窗口指派模型。本文的第二個(gè)問(wèn)題是研究第一個(gè)問(wèn)題的反問(wèn)題，即確定所有工件的最優(yōu)排序、最優(yōu)的資源分配和松弛決策變量q1和q2使得在工件的提前時(shí)間、延誤時(shí)間、窗口的開(kāi)始時(shí)間和窗口長(zhǎng)度的線性組合有上界限制的情況下極小化總資源消耗費(fèi)用，即問(wèn)題：其中V表示工件的提前時(shí)間、延誤時(shí)間、窗口的開(kāi)始時(shí)間和窗口長(zhǎng)度的線性組合的上界。

2 模型分析與求解

引理1存在一個(gè)最優(yōu)排序，其中第一個(gè)工件的加工時(shí)間為0，并且相鄰工件之間沒(méi)有空閑時(shí)間。

引理2（Wu等［16］）對(duì)任意指定排序，都存在一個(gè)最優(yōu)排序使得q1和q2分別等于第h和第l個(gè)工件的完工時(shí)間，q1＝C［h］，q2＝C［l］，其中l(wèi)≥h，

引理4（Wang和Wang［12］）對(duì)于實(shí)際加工時(shí)間為pj＝+bSj的模型，排在第j個(gè)位置的工件的實(shí)際加工時(shí)間為

引理5（Hardy等［18］）式子的最小值由xj的最大值與yj的最小值相乘，xj的次最大值與yj的次最小值相乘，依次類(lèi)推得到。

定理2問(wèn)題1｜pj＝+bSj，SLKW，≤（αEj+βTj++δDj）的最優(yōu)排序能夠在O（nlogn）時(shí)間內(nèi)得到。

由定理1和定理2，問(wèn)題1｜pj＝+bSj，≤（αEj+βTj++δDj）的最優(yōu)算法可以如下給出：

算法1

步驟1初始化參數(shù)：輸入數(shù)據(jù)wj，gj（j＝1，2，…，n），b，k，n，α，β，γ，δ，U；

步驟2計(jì)算最優(yōu)位置

步驟3最優(yōu)排序：計(jì)算（和（＝1，2，…，n，由定理2得到工件的最優(yōu)排序；

步驟4最優(yōu)分配資源：由式（7）計(jì)算出對(duì)應(yīng)最優(yōu)排序的最優(yōu)資源分配；

步驟5計(jì)算最優(yōu)位置完成時(shí)間：計(jì)算q1＝C［h］，q2＝C［l］；

步驟6計(jì)算最優(yōu)目標(biāo)函數(shù)值：計(jì)算出排序目標(biāo)（αEj+βTj++δDj）。

顯然，算法1的步驟1）需要常數(shù)時(shí)間，步驟2）需要O（nlogn）時(shí)間，步驟3），4）和5）分別需要O（n）時(shí)間，因此算法1總的時(shí)間復(fù)雜度為O（nlogn），即問(wèn)題能夠在多項(xiàng)式時(shí)間O（nlogn）內(nèi)解決。

定理3對(duì)于問(wèn)題1｜pj＝+bSj，SLKW，最優(yōu)的資源分配量為

定理4對(duì)于問(wèn)題1｜pj＝+bSj，SLKW，βTj++δDj）≤V｜ gj uj，最優(yōu)的排序能夠在O（nlogn）時(shí)間內(nèi)得到。

由定理3和定理4，問(wèn)題1｜pj＝+bSj，，（αEj+βTj++δDj）≤V｜ gjuj的最優(yōu)算法可以如下給出：

算法2

步驟1初始化參數(shù)：輸入數(shù)據(jù)wj，gj（j＝1，2，…，n），b，k，n，α，β，γ，δ，V；

步驟3最優(yōu)排序：計(jì)算（和（＝1，2，…，n，由定理4得到工件的最優(yōu)排序；

步驟4最優(yōu)分配資源：由式（8）計(jì)算出對(duì)應(yīng)最優(yōu)排序的最優(yōu)資源分配；

步驟5計(jì)算最優(yōu)位置完成時(shí)間：計(jì)算q1＝C［h］，q2＝C［l］；

步驟6計(jì)算最優(yōu)目標(biāo)函數(shù)值：根據(jù)式（14）計(jì)算出排序目標(biāo)gjuj。

類(lèi)似于算法1，算法2的總時(shí)間復(fù)雜度為O（nlogn），即問(wèn)題能夠在多項(xiàng)式時(shí)間O（nlogn）內(nèi)解決。

3 算例

例1令n＝6，b＝0.05，k＝2，α＝9，β＝12，γ＝5，δ＝7，U＝200，V＝300，w1＝12，w2＝13，w3＝10，w4＝8，w5＝22，w6＝11，g1＝6，g2＝7，g3＝3，g4＝4，g5＝2，g6＝5，所有數(shù)據(jù)保留7位有效數(shù)字。

解根據(jù)算法1和2，

步驟2h＝1，l＝2；

步驟4由式（7），問(wèn)題的最優(yōu)資源分配為：

步驟5q1＝C［1］＝C4＝1.064500，q2＝C［2］＝C3＝2.132008；

4 結(jié)論

考慮了工件帶有凸資源和惡化效應(yīng)的單機(jī)松弛窗口排序問(wèn)題。目標(biāo)是確定最優(yōu)排序，最優(yōu)的資源分配以及窗口的開(kāi)始時(shí)間與長(zhǎng)度，使總資源消耗費(fèi)用（與窗口有關(guān)的排序費(fèi)用）小于或等于給定常數(shù)的條件下，最小化與窗口有關(guān)的排序費(fèi)用，證明上述問(wèn)題都是多項(xiàng)式時(shí)間可解的。對(duì)其它機(jī)器環(huán)境（比如平行機(jī)或流水作業(yè)機(jī)）和其它目標(biāo)函數(shù)的相關(guān)問(wèn)題將繼續(xù)研究。