基于實(shí)例空間壓縮的在線及半在線調(diào)度算法的競(jìng)爭(zhēng)分析.pdf

1、在線或半在線調(diào)度作為一種信息匱缺情況下的優(yōu)化決策問題，廣泛存在于生產(chǎn)制造、通信網(wǎng)絡(luò)、電力系統(tǒng)、交通運(yùn)輸及公共服務(wù)系統(tǒng)等領(lǐng)域。由于缺乏完整信息，一般不能建立基于問題完整描述的優(yōu)化算法，此外，在線調(diào)度在很多情況下還有實(shí)時(shí)性要求，這使得大部分在線調(diào)度都采用一些計(jì)算要求簡(jiǎn)單的分派規(guī)則，由于這些規(guī)則多為啟發(fā)式的，即使應(yīng)用到相同問題的不同實(shí)例也可能出現(xiàn)性能差異甚遠(yuǎn)的情況。因此，為了對(duì)規(guī)則的選擇和應(yīng)用提供理論支持，還需分析研究相應(yīng)調(diào)度算法的競(jìng)爭(zhēng)性能。

2、
　　 在競(jìng)爭(zhēng)分析的歷史研究中，采用的很多方法都具有很強(qiáng)的問題依賴性，證明分析都依賴于一些輔助調(diào)度的巧妙構(gòu)造，過程通常也顯得相當(dāng)繁瑣，精妙有余而規(guī)律性不強(qiáng)。本文首先嘗試進(jìn)行競(jìng)爭(zhēng)比分析方法的研究，提出了一種基于實(shí)例空間壓縮的較為一般的分析方法，然后將其應(yīng)用到多個(gè)在線及加工時(shí)間有界的半在線調(diào)度問題的算法設(shè)計(jì)與競(jìng)爭(zhēng)分析上，歸納起來，本論文的研究?jī)?nèi)容主要包括以下四個(gè)方面：
　　 ·提出了一種新穎的基于實(shí)例空間壓縮的競(jìng)爭(zhēng)比分析方法

3、，闡述了該方法的基本思想及常用的空間壓縮方法，并將該方法應(yīng)用于最小化總完工時(shí)間及總加權(quán)完工時(shí)間的單機(jī)調(diào)度，針對(duì)現(xiàn)有的兩個(gè)最優(yōu)在線算法，分別給出了替代的競(jìng)爭(zhēng)比證明。
　　 ·研究了最小化總加權(quán)完工時(shí)間的同速并行機(jī)在線調(diào)度Pm/rj/∑wjCj，通過擴(kuò)展相應(yīng)單機(jī)及非加權(quán)情況下的在線算法，提出了基于組合延時(shí)的CD-SWPT算法，并采用基于實(shí)例空間壓縮的分析方法，證明了該算法的競(jìng)爭(zhēng)比位于[2，2.5－1/2m]之間。
　　 ·研

4、究了加工時(shí)間有界的最小化總完工時(shí)間及總加權(quán)完工時(shí)間的單機(jī)半在線調(diào)度問題，針對(duì)1/rj,Pmax/Pmin≤γ/∑Cj，提出了αD-SPT算法，并應(yīng)用基于實(shí)例空間壓縮的方法證明其競(jìng)爭(zhēng)比為1+1+γ(γ-1)/γ；針對(duì)1/rj，Pmax/Pmin≤γ/∑wjCj，提出了αD-SWPT算法，并應(yīng)用基于實(shí)例空間壓縮的方法證明了其競(jìng)爭(zhēng)比為1+4γ2+1-1/2γ，同時(shí)證明了該競(jìng)爭(zhēng)比也是針對(duì)該問題的任何半在線算法所能取得的最好結(jié)果。