帶有拒絕、惡化效應和安裝時間的單機排序

趙玉芳, 梁 媛

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

0 引 言

在傳統的排序問題中,所有的工件都需要加工。然而,在實際問題中,機器的加工能力有限,若拒絕部分工件反而可能獲得更大的利潤。因而決策者需要將工件集進行劃分,一般分為接受工件集與拒絕工件集。接受工件在機器上加工,拒絕工件外包處理或直接擱置,外包需要支付代加工費,擱置工件也有倉庫費用,如此產生拒絕懲罰。惡化效應在現實生活中的很多地方都有體現,比如在鋼鐵的鍛造生產過程中[1]。安裝時間也稱為調整時間,即機器在處理不同的工件時都有一個調整時間,在實際生產中也是普遍存在的。

對于拒絕問題,Bartal等[2]研究了多處理機排序問題,目標函數是接受工件的最大完工時間與拒絕工件的總拒絕懲罰之和,并給出了近似算法。Gerstl和Mosheiov[3]研究了帶有拒絕、工期依賴于工件位置的單機排序問題,目標函數是最大延誤或總延誤與拒絕懲罰之和,證明了上述2個問題都是NP難的,并給出了偽多項式動態規劃算法和啟發式算法。Shabtay等[4]綜述了帶有拒絕的排序問題。Agnetis和Mosheiov[5]研究了帶有拒絕、加工時間依賴位置但不依賴于機器的流水作業問題,目標函數是最大完工時間,并證明了問題是多項式時間可解的。工件的惡化效應是由Browne和Yechiali[6]提出的,他們認為工件的加工時間是開始時間的函數,并在假設加工時間為線性惡化模型時,討論了極小化流水作業問題。Wang和Liang[7]研究了帶有成組技術與簡單線性惡化效應的單機資源分配問題。在2種特殊情況下,給出多項式時間算法;在一般情況下,由于極小化最大完工時間問題受到有限可用資源的約束,因而提出了一個啟發式算法與分枝定界算法。Zhao和Hsu[8]考慮了帶有惡化效應、工期指派和資源分配的極小化加權誤工任務數的單機排序問題,提出了一個偽多項式時間算法和完全多項式時間近似策略(fully polynomial time approximation scheme, FPTAS)。Liang等[9]研究了帶有簡單線性惡化效應與成組技術的單機資源分配問題,對于極小化加權最大完工時間與資源分配費用之和問題,給出了偽多項式與分枝定界算法。對于同時考慮惡化效應與拒絕懲罰的模型,Nian和Mao[10]研究了單機排序問題,通過將其轉化為指派問題及設計動態規劃算法,分別證明了在2種惡化加工時間模型下,總完工時間與總拒絕懲罰之和問題可以在多項式時間內求解;Li等[11]研究了平行機排序問題,目標函數為最大完工時間與總拒絕懲罰之和,給出了動態規劃算法和FPTAS。Koulamas和Kyparisis[12]研究了安裝時間與已完工工件的加工時間有關(p-s-d)且安裝時間帶有學習效應的單機排序問題,目標函數分別是最大完工時間、總完工時間、總完工時間絕對差以及后2個目標函數的線性組合,給出了多項式時間算法。Huang等[13]研究了帶有p-s-d安裝時間、惡化效應依賴于時間和學習效應依賴于位置的單機排序問題,對于最大完工時間、總完工時間等目標函數,分別給出了多項式時間算法。Biskup和Herrmann[14]研究了帶有p-s-d安裝時間的單機排序問題,目標函數是關于工期的函數。Soroush[15]研究了帶有p-s-d安裝時間和學習效應的單機排序問題,目標函數分別是最大完工時間、總完工時間、總延誤、總完工時間絕對差以及提前、延誤、相同工期懲罰的線性組合,給出了分枝定界法。Wang等[16]研究了帶有拒絕、惡化效應與p-s-d安裝時間的單機排序問題,目標函數分別是最大完工時間、總完工時間、總完工時間絕對差以及總等待時間絕對差與總拒絕懲罰之和,給出了多項式時間算法。

1 問題描述

2 理論推導

設C[j]表示排在第j個位置工件的完工時間,W[j]表示排在第j個位置工件的等待時間。

1)Cmax的推導公式:

因此

(1)

即

(2)

3) TADC的推導公式:

其中

(3)

4) TADW的推導公式:

那么

其中

(4)

證明 設接受工件的數量為na,下面證明4個目標函數對應的4個問題可以轉化為指派問題求解。

1) 當Y=Cmax時,由式(1),令

供給側結構性改革的五大重點任務是去產能、去庫存、去杠桿、降成本、補短板。具體來說就是從生產領域入手，減少無效供給，擴大有效供給，提高全要素生產率，使供給體系靈活適應需求結構變化。健身休閑產業供給側結構性改革的目標就是要從供給的角度，優化資源、人力、資本、技術、政策等要素資源配置，激發政策導向優勢，強化資源支撐地位，融入科技與“互聯網+”信息技術，推動體育健身休閑產業的可持續發展。結合自治區的《實施意見》，廣西健身休閑產業供給側結構性改革可從供給什么、誰來供給、如何供給、供給環境四個方面（如圖1）入手。

3) 當Y=TADC時,由式(3),令

4) 當Y=TADW時,由式(4),令

3 算法算例

算法:

證明 算法的第1步為計算O(n);當na給定時,求解指派問題的復雜度為O(n3),第2步共需解n-1個指派問題,復雜度為O(n4);第3步為O(n),故算法的復雜度為O(n4)。

求解:

當na=1時,依次將4個工件放到第1個位置,其余工件拒絕,分別計算目標函數值進行比較,得到接受工件為1或3最好,目標值Z(1)=39;

當na=2時,有

通過指派問題求解,得到接受工件為2和3,S=[3,2],目標值Z(2)=35;

當na=3時,由指派問題整理可得接受工件為2,3和4,S=[3,2,4],目標值Z(3)=48;

當na=4時,由指派問題整理可得S=[1,3,2,4]或S=[3,1,2,4],目標值Z(4)=120。

綜上,最優解是接受工件2,3,S=[3,2],最優目標函數值Z*=35。同理可以求得下面問題的最優解。

4 結 語

本文研究了帶有拒絕效應的單機排序問題,工件的加工時間同時受到2種惡化效應的影響,即依賴位置和開始加工時間的惡化效應,且工件在加工之前還帶有一個p-s-d安裝時間。對于4種目標函數,給出了復雜度為O(n4)的多項式時間算法。對于帶有惡化效應、安裝時間和拒絕的此類問題,今后可以考慮不同的處理機環境或其他類型的惡化效應和安裝時間模型。