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

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

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

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