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

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

【參考文獻】

相關期刊論文 前4條

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

2 孫錦萍,李曙光,張少強;一個求分批排序最小時間表長的多項式時間近似方案[J];山東大學學報(理學版);2004年02期

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

4 李曙光,李國君,趙浩;無限批量調度中最小化加權完工時間和問題的一個線性時間近似方案(英文)[J];運籌學學報;2004年04期

本文編號：2732292