提前工作量指標(biāo)下的單機(jī)排序研究.pdf

1、排序論是運(yùn)籌學(xué)中非常重要的一個(gè)分支.在經(jīng)典的排序問(wèn)題中，人們對(duì)與時(shí)間限制有關(guān)的目標(biāo)函數(shù)的研究是非常廣泛的.在本學(xué)位論文中，我們主要研究目標(biāo)函數(shù)是關(guān)于提前工作量指標(biāo)的單機(jī)排序問(wèn)題.工件的提前工作量是不同于工件的提前量的一個(gè)指標(biāo)，它是工件在預(yù)開(kāi)工時(shí)間之前加工部分的大小.因此，在任一可行排序中，一個(gè)工件的提前工作量不會(huì)大于它的加工時(shí)間.在大數(shù)據(jù)的信息處理中，預(yù)開(kāi)工時(shí)間之前加工的工件（數(shù)據(jù))會(huì)產(chǎn)生額外的存儲(chǔ)費(fèi)用，并且該費(fèi)用通常是與工件的提前工作

2、量是成正比的.因此，如何合理安排工件的加工使得工件的提前工作量產(chǎn)生的費(fèi)用盡可能少就是一個(gè)具有理論研究?jī)r(jià)值和應(yīng)用前瞻性的研究課題.
　　本學(xué)位論文分成兩部分來(lái)研究關(guān)于提前工作量指標(biāo)下的排序問(wèn)題.第一部分研究的是單機(jī)上的最小化最大提前工作量的排序問(wèn)題，第二部分研究的是單機(jī)上最小化加權(quán)提前工作量的排序問(wèn)題.
　　我們用EWmax表示工件的最大提前工作量，用此處為公式表示工件的加權(quán)提前工作量總和.本文的主要結(jié)果如下：
　　?對(duì)

3、于排序問(wèn)題此處為公式,我們給出了一個(gè)運(yùn)行時(shí)間為O(n2)的最優(yōu)算法；我們進(jìn)一步猜測(cè)，引入適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)，該算法的運(yùn)行時(shí)間可以改進(jìn)到0(nlogn).
　　?對(duì)于排序問(wèn)題此處為公式,我們給出了一個(gè)運(yùn)行時(shí)間為O(n2)的最優(yōu)算法.并且指出了該算法對(duì)于在線的排序問(wèn)題此處為公式也是最優(yōu)的.
　　?對(duì)于NP-困難的排序問(wèn)題此處為公式,我們給出了一個(gè)運(yùn)行時(shí)間為此處為公式的動(dòng)態(tài)規(guī)劃算法.這就解決了Ben-Yehoshua和 Mosheio