單機(jī)并行批調(diào)度問題的算法研究.pdf

1、隨著科學(xué)技術(shù)的發(fā)展,越來越多的單產(chǎn)品處理器被批處理器所取代。人們對批調(diào)度問題的研究達(dá)到了前所未有的高度,其中大多數(shù)工作是針對單機(jī)并行批調(diào)度問題的研究。
　　 論文研究如下單機(jī)并行批調(diào)度問題:給定一些工件{J1,J2,…,Jn},每個工件Jj有給定的處理時間Pj,以及懲罰值ej(可以拒絕處理某些工件,ej為拒絕處理工件Jj付出的代價)。給定一個批處理器,處理器可以將多個工件作為一批同時處理。同一批工件具有相同的開始時間和結(jié)束時間,

2、即開始時間加上這一個批中所有工件的最大給定處理時間。調(diào)度的目標(biāo)是判斷選擇處理哪些工件、給這些工件分批以及給批排序,使得目標(biāo)函數(shù)值達(dá)到最小。在本文中,考慮的目標(biāo)函數(shù)為被處理工件的完成時間之和加上被拒絕工件的懲罰值之和,并對批容量無界和批容量有界兩種情況分別進(jìn)行討論,其中,批容量無界是指一批中處理的工件個數(shù)沒有限制,批容量有界是指一批中處理的工件個數(shù)不超過某個常數(shù)b。
　　 對批容量無界的情況,使用后向動態(tài)規(guī)劃的技術(shù),并使用堆排序的