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

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

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

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

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

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

7、多個(gè)工件可以被同時(shí)加工的情況，目標(biāo)是要把工件分成多個(gè)批、再排列批的次序使得總費(fèi)用最?。渲械诙驴紤]批容量無(wú)限時(shí)，在交貨期窗口給定或其位置待定情況下，以最小化總的提前和延誤懲罰；并且如果交貨期窗口有待定參數(shù)時(shí)，總費(fèi)用包含該決策費(fèi)用． 性質(zhì)2存在一個(gè)最優(yōu)排序σ，使得準(zhǔn)時(shí)集合W(σ)包含加工時(shí)間最小的工件． 性質(zhì)3在任一個(gè)最優(yōu)排序σ中，要么W(σ)=φ，要么W(σ)只包含一個(gè)批而且這個(gè)批是所有批中加工時(shí)間最小的一個(gè)．

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

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

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

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

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

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

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

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

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

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