單機并行批調度問題的算法研究.pdf

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

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