窗時排序問題中的最優(yōu)化算法研究.pdf

1、為了避免儲存以及隱藏的額外運轉帶來的高費用，比如由于等待、傳遞、額外勞動力、重加工以及訂單改變等引起的效益損失，生產商不僅考慮延誤帶來的懲罰還必須顧及提前完工付出的費用；此乃準時排序問題．它限定工件的交貨期；如果工件在交貨期之前完工，會出現儲存費和保管費之類；而在交貨期之后完成，固然要課以罰款，則會產生延誤賠償甚至失去合作機會等損失．而準時排序的目的就是要最小化這些費用之和，所以，在“準時”概念中，盡可能使得工件的完工時間接近其交貨期或

2、者提前和延誤的工件個數盡量少．因此，提前和延誤應該盡可能地避免，這也使得以前討論的傳統(tǒng)性能函數已經無效．既然目標函數是關于工件完工時間的非正則函數，問題的研究相對比較困難． 實際上，大多數生產環(huán)境中的交貨期允許一定的寬容公差，所以‘咬貨期窗口”的概念顯得尤為重要．本文不考慮公共交貨期的情況，而代之以公共交貨期窗口．它是一個被最早交貨期e和最晚交貨期d定義的時間區(qū)間，其中窗口大小定義為K=d-e，最早交貨期e也被稱為交貨期窗口的位

3、置．工件在區(qū)間[e，d]中完工不必支付費用，若在e之前或d之后完成將受到提前或延誤懲罰．這就是窗時排序，它推廣了準時排序問題．并且，在有些生產場景中，交貨期窗口的位置和大小經常作為決策變量(假設單位時間費用分別是，γ和δ)，與工件的最優(yōu)序列一起確定． 粗略來講，有兩類相關的懲罰函數．一類是提前時間和延誤時間所帶來的懲罰，即與完工時間距離交貨期窗口的時間差成正比．此類目標函數既普遍又具備很強的競爭力，目前有以下幾個結果．Krame

4、r和Lee[52]分析并證明當交貨期窗口給定時，此問題是NP-完備的；當交貨期窗口的位置待定但沒有決策費用時，可以在多項式時間內找到最優(yōu)算法． [62，64，79]分別探討了交貨期窗口的位置或大小是給定還是待定的生產情形，以最小化提前和延誤懲罰及窗口的決策費用之和．在這幾篇文獻中，“位置權”對搜尋最優(yōu)排序起了關鍵作用．就這類目標函數，本文的第二章和第三章都討論了工件有公共交貨期窗口的同時加工排序問題，對批容量是有限的還是無限的兩種情況分

5、別研究；尤其當批的容量有限時，乃是以上經典排序的推廣．在尋找它們的最優(yōu)算法時，“位置權”已不再有效．另一類目標函數中，提前和延誤懲罰依賴于工件是否提前或延誤，而不是提前或延誤了多長時間．這類問題關注的是提前和延誤的賦權工件數．Yeung等[86]考慮交貨期窗口待定的情況，當懲罰系數是任意整數時，他們給出了NP-完備性證明和擬多項式時間算法；并對兩類特殊情況提出有效算法．本文的第四章就交貨期窗口的位置和大小是給定還是待定的其他三種情況進行

6、了討論并提出最優(yōu)算法；第五章至第七章把這些問題推廣到同時加工排序、成組分批排序及平行機加工． 本文共分為七章．第一章介紹窗時排序及其相關的組合優(yōu)化問題，常用術語與符號，準時排序和窗時排序的一些相關結果，本文的結構與主要內容． 在以前關于同時加工排序問題的研究中，最優(yōu)排序是要使得總完工時間或最大完工時間等正則函數最小；只有幾篇文獻涉及到交貨期的存在性，以最小化總延誤或最大延誤．這里，第二、三、五章中，首次把窗時排序推廣到了

7、多個工件可以被同時加工的情況，目標是要把工件分成多個批、再排列批的次序使得總費用最小．其中第二章考慮批容量無限時，在交貨期窗口給定或其位置待定情況下，以最小化總的提前和延誤懲罰；并且如果交貨期窗口有待定參數時，總費用包含該決策費用． 性質2存在一個最優(yōu)排序σ，使得準時集合W(σ)包含加工時間最小的工件． 性質3在任一個最優(yōu)排序σ中，要么W(σ)=φ，要么W(σ)只包含一個批而且這個批是所有批中加工時間最小的一個．

8、 性質6在一個最優(yōu)排序中，延誤集合中的批按加工時間非降的順序排列． 對給定的交貨期窗口，第一個被加工批的開工時間如性質5中所述；而且根據性質7，最優(yōu)排序符合SPT-批序．所以該問題就轉化為最小化延誤工件的總完工時間，從而可以用一個動態(tài)規(guī)劃得之．而當交貨期窗口的位置e待定時，第一個批的開工時間為零， e的取值如性質9．于是用枚舉法確定了集合W后，亦轉化為最小化延誤工件的總完工時間問題．根據以上分析，分別得到用時為O(N<'2> l

9、ogn)和O(n<'3> logn)的兩個多項式時間算法． 第三章討論了交貨期窗口給定且批容量有限的情況，但問題的復雜性是NP-完備的。實際上，最小化總完工時間的問題復雜性仍然沒有解決，只是一些文獻中給出了PTAS.何況本章的問題要比它難得多．文中提出了最優(yōu)排序的幾個性質，其中性質11、12說明了最優(yōu)排序是SPT一批序的并且準時集合包含那些最小的工件．性質10在最優(yōu)排序σ中，存在批B使得C(B)=e或G(B)=d，除非第一個批的

10、開工時間為零． 然后探討了以下兩種特殊情況．當提前集合為空集時，仍然可以用列舉法確定準時集合，問題就是要最小化延誤工件的總完工時間，于是可以得到其PTAS．另外，當所有工件的加工時間相等時，經分析得到了多項式時間算法． 以上兩章分別就批容量無限和有限兩種情況討論了同時加工排序，目標是最小化關于提前時間和延誤時間的懲罰．下面幾章研究第二類目標函數．第四章就交貨期窗口給定、窗口大小待定、窗口的位置和大小均待定三種情況進行探討

11、，以最小化提前和延誤工件的賦權個數及交貨期窗口的決策費用和；在提出最優(yōu)性質和參數分析的基礎上，給出了相應的多項式時間算法． 作為上一章的推廣，第五章研究有界的同時加工排序問題．當提前和延誤懲罰系數是任意整數且窗口位置待定時，把3-劃分的一個實例轉化到該問題，從而證明了它是強NP-完備的．進而提出幾個最優(yōu)性質，但最優(yōu)排序已不再滿足SPT-批序． 進一步，本章解決了三種特殊情況．首先，當所有的提前懲罰為零時，問題轉化為有待定

12、的公共交貨期問題，但它仍是NP一完備的，本文給出了擬多項式時間算法．如果交貨期窗口的定位費用為零，其位置可以取任意大的值．通過使得準時集合能避免最多懲罰以達到最優(yōu)，得到了擬多項式時間算法．這也說明以上兩個特例是一般NP一完備的．另外，當所有的提前懲罰相等、延誤懲罰也相等時，準時批包含那些最小的工件，算法5-3在O(max{b<'2>n，nlogn})時間內得到最優(yōu)排序．以上結果也推廣了[86]中的結論． 現實生產中有以下情形：具

13、有相似特征的一些工件需要相同的生產場景和設備，所有工件被分成多個組，于是從加工一個組的工件轉化到加工另一個組的工件時需要執(zhí)行安裝任務．正是由于安裝任務的介入使得問題更加困難． [78]討論當交貨期窗口給定時以最小化賦權提前時間和延誤時間總和的問題；即使當e=0時，問題的復雜性未知．但是此類生產環(huán)境普遍存在，于是第六章繼續(xù)討論，目標函數是關于提前和延誤的工件個數，其中交貨期窗口的位置待定或者位置和大小均待定． 顯然，第一個安裝任務

14、在零時刻開始，而且在整個工件與安裝任務的序列中沒有空閑時間．性質31～34描述了一個最優(yōu)排序的結構；算法6-1中綜合考慮工件對總懲罰的貢獻而確定其所在的集合． 而當交貨期窗口的位置和大小都是決策變量時，除了以上提到的性質，最優(yōu)算法又基于以下結論： 性質23如果δ<γ，則最優(yōu)排序中e=0． 性質25最優(yōu)排序σ中，如果δ>，γ+α且e≥1，則K=0． 推論4在最優(yōu)排序σ中，如果，γ<δ<γ+α且e≥1，則K等

15、于1加上W(σ)\{J<,e>}中工件和安裝任務的運行時間總和． 第七章把窗時排序推廣到了多臺平行機上，以最小化提前和延誤賦權工件數，乃是準時排序和單機排序的推廣．它是強NP-完備的．當交貨期窗口的定位費用為零時，根據多背包問題的算法得到PTAS．若定位費用不是零，在確定了各機器上的提前集合后也類似地得到PTAS． 概括地講，本文的創(chuàng)新點主要有： 1．多個工件可以同時被加工，并把同時加工的工件視為一個批，目標函數

16、是關于提前時間和延誤時間的總懲罰；本文首次把窗時排序和同時加工排序結合起來； (1)當批容量無界時，對于交貨期窗口給定及其位置待定兩種情況，分別給出了多項式時間算法； (2)當批容量有界且交貨期窗口給定時，問題是NP-完備的，并對兩個特殊情況分別給出了PTAS和多項式時間算法．從而推廣了[52]中的結果． 2．當目標函數關于提前和延誤的賦權工件個數時，(1)針對交貨期窗口的位置和大小是給定還是待定的生產場景，解決

17、了除[86]中所述之外的三種情況； (2)將[86]中的結果推廣到了同時加工排序，證明了當懲罰系數是任意整數時，問題是強NP-完備的；然后對三個特例得到擬多項式時間算法或者給出有效算法； (3)討論成組分批排序的情形． [78]曾對第一類目標函數進行了探討，但問題的復雜性并未解決．本文就第二類目標函數研究，在給出幾個結構化性質的基礎上得到多項式時間算法；亦是[86]的推廣； (4)在多臺平行機上加工且交貨期窗口的