具有退化維護和資源分配的單機排序問題

羅成新, 王亞男

(沈陽師范大學 數學與系統科學學院, 沈陽 110034)

0 引 言

排序作為一門應用科學,有著深刻的實際背景,它主要產生于機器制造,后來被廣泛應用于管理科學、運輸業、計算機科學和工程技術等眾多領域。排序對提高效率、資源的開發和配置、工程的進展安排及經濟運行方面都起到輔助科學決策作用。

在實際中,由于工人或機器的工作時間較長,其工作效率降低,也就產生了所謂的退化效應。Browne和Yechiali[1]首先對具有退化效應的排序問題進行了研究,其中工件的加工時間是與開始加工時間有關的線性不減函數;文獻[2-3]分別對具有簡單線性退化和線性遞減退化效應的單機排序問題進行了研究;Oron[4]在退化環境中排列具有可控加工時間的工件。

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

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

本文在上述文獻的基礎上,研究具有退化維護和資源分配的單機松弛交貨期指派排序問題。目標是在資源總量有限的條件下,確定最優公共松弛時間、最優維護位置、最優資源分配方案和最優工件排序,使得目標函數的總費用最小。根據凸優化相關知識,將問題轉化為指派問題,證明了該問題在多項式時間內是可解的,給出了多項式時間最優算法。

1 問題描述

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

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

(1)

其中β域中的ma表示維護。

2 初步分析

下面,就問題的最優排序提出了一些引理。一個重要的性質:最優排序中第一個工件從零時刻開始加工且2個相鄰的工件之間沒有空閑。為了簡便,假設在工件J[i]加工完成之后立即進行維護,即排在維護之前的工件數為i。

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

其中C[0]=0。

證明 用歸納法進行證明。此處省略,證畢。

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

證明 與引理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 對于任意指定的序列π,都存在一個最優的松弛交貨期,它的公共松弛時間q等于某工件的等待時間。

接下來,確定其等待時間等于公共松弛時間q的工件J[k]的k值。要證明工件J[k]的位置是費用參數的一個函數且與維護活動無關。

證明 考慮一個最優排序和最優公共松弛時間,使得對某工件J[k]有q=C[k-1]=W[k],利用經典擾動技術,研究當移動松弛時間時總費用的變化。當松弛時間左移ε個單位時間,總費用的改變值為

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

(2)

相反地,當松弛時間右移ε個單位時間,總費用的改變值為

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

(3)

3 問題的最優解

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

由上邊引理可得下述結論:

1) 如果在工件J[k]加工之前進行維護,即i

其中

2) 如果在工件J[k]完工之后進行維護,即i≥k,總費用為

其中

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

對于i

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

另外,對于i≥k的情況:

(9)

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

證明 下面只證i

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

由式(12)得

(13)

由式(11)和式(13)得

(14)

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

對于i

為了求出最優解,將問題化為指派問題。對于r=1,2,…,n,引入

考慮指派問題如下,令

則可轉化為如下指派問題:

對于i≥k的情況,將式(9)代入式(6),得到目標函數Z在最優資源分配下的一個新的統一表達式:

為了求出最優解,將問題化為指派問題。對于r=1,2,…,n,引入

考慮指派問題如下,令

則可轉化為如下指派問題:

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

算法

第2步 令維護位置j=1;

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

第4步j=j+1,如果j≤n,那么執行第三步;否則,執行第五步;

第5步 全局的最優排序是局部最優排序中總費用最小的排序;

定理對于問題(1),利用算法可以通過求解指派問題在O(n4)時間內得到最優解。

證明 定理的正確性由上述分析保證。第1步的時間復雜度為O(1),第3步的時間復雜度為O(n3)。因為任何一個工件完工之后都可以立即進行維護,所以必須對n個不同的維護位置進行評估進而得到全局最優解。因此求解問題(1)的時間復雜度為O(n4)。證畢。

4 結 論

本文研究了具有退化維護和資源分配的單機松弛交貨期指派排序問題。在資源總量有限的條件下確定最優公共松弛時間、最優維護位置、最優資源分配方案和最優工件排序,使得由工件的提前懲罰、延誤懲罰、交貨期公共松弛時間、最大完工時間、總完工時間構成的總費用最小。根據凸優化的相關知識,將問題轉化為指派問題,證明了該問題在多項式時間內是可解的,給出了多項式時間最優算法。