發(fā)布時(shí)間：2020-06-28 00:14

【摘要】：隨著科學(xué)技術(shù)的發(fā)展,越來越多的單產(chǎn)品處理器被批處理器所取代。人們對(duì)批調(diào)度問題的研究達(dá)到了前所未有的高度,其中大多數(shù)工作是針對(duì)單機(jī)并行批調(diào)度問題的研究。 論文研究如下單機(jī)并行批調(diào)度問題：給定一些工件{J1,J2,…,Jn},每個(gè)工件J有給定的處理時(shí)間乃,以及懲罰值ej(可以拒絕處理某些工件,ej為拒絕處理工件J,付出的代價(jià))。給定一個(gè)批處理器,處理器可以將多個(gè)工件作為一批同時(shí)處理。同一批工件具有相同的開始時(shí)間和結(jié)束時(shí)間,即開始時(shí)間加上這一個(gè)批中所有工件的最大給定處理時(shí)間。調(diào)度的目標(biāo)是判斷選擇處理哪些工件、給這些工件分批以及給批排序,使得目標(biāo)函數(shù)值達(dá)到最小。在本文中,我們考慮的目標(biāo)函數(shù)為被處理工件的完成時(shí)間之和加上被拒絕工件的懲罰值之和,并對(duì)批容量無界和批容量有界兩種情況分別進(jìn)行討論,其中,批容量無界是指一批中處理的工件個(gè)數(shù)沒有限制,批容量有界是指一批中處理的工件個(gè)數(shù)不超過某個(gè)常數(shù)b。 對(duì)批容量無界的情況,我們使用后向動(dòng)態(tài)規(guī)劃的技術(shù),并使用堆排序的思想,提出時(shí)間復(fù)雜性為O(n4)的精確算法,然后使用幾何歸納的方法將算法的時(shí)間復(fù)雜性改進(jìn)到O(n3 log n)。 批容量有界的情況更加復(fù)雜,批不再滿足批容量無界時(shí)滿足的一些重要性質(zhì)。我們使用后向動(dòng)態(tài)規(guī)劃的方法合理枚舉所有可能的情況,以得到最優(yōu)的調(diào)度。我們給出了時(shí)間復(fù)雜性為O(n2b2-2b+2)的精確算法,從而證明當(dāng)批容量b為常量時(shí),該問題是多項(xiàng)式時(shí)間可解的。
【學(xué)位授予單位】：山東大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2011
【分類號(hào)】：TP332

【參考文獻(xiàn)】

相關(guān)期刊論文 前4條

1 王珍;曹志剛;張玉忠;;極小化最大完工時(shí)間及拒絕費(fèi)用的單機(jī)可拒絕分批排序[J];曲阜師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2007年02期

2 孫錦萍,李曙光,張少強(qiáng);一個(gè)求分批排序最小時(shí)間表長的多項(xiàng)式時(shí)間近似方案[J];山東大學(xué)學(xué)報(bào)(理學(xué)版);2004年02期

3 張玉忠;曹志剛;;并行分批排序問題綜述[J];數(shù)學(xué)進(jìn)展;2008年04期

4 李曙光,李國君,趙浩;無限批量調(diào)度中最小化加權(quán)完工時(shí)間和問題的一個(gè)線性時(shí)間近似方案(英文)[J];運(yùn)籌學(xué)學(xué)報(bào);2004年04期

本文編號(hào)：2732292