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

姜昆

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

0 引言

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

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

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

1 問題描述

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

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

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

2 模型分析與求解

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

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

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

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

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

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

算法1

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

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

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

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

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

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

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

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

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

由定理3和定理4，問題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)排序：計算（和（＝1，2，…，n，由定理4得到工件的最優(yōu)排序；

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

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

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

類似于算法1，算法2的總時間復雜度為O（nlogn），即問題能夠在多項式時間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），問題的最優(yōu)資源分配為：

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

4 結(jié)論

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