提前工作量指標下的單機排序研究.pdf

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

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

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