若干批調(diào)度問題的算法研究.pdf

1、單機批調(diào)度問題是最近十幾年廣泛研究的一個領(lǐng)域。在本文之中，我們首先針對給定n個工件和一個容量為B的單機并行批處理機器問題展開研究。每個工件Jj(j∈(1，2…，n))具有一些給定屬性（rj，Pj，sizej，Wj），rj是工件Jj能夠被調(diào)度的最早時間，即到達時間；pj是工件Jj在不被打斷情況下，需要在機器上處理的時間，即處理時間；sizej是工件Jj的尺寸；Wj是工件Jj在被拒絕情況下需要在目標中付出的懲罰值。機器能夠把一定數(shù)量的工件作

2、為一批同時進行處理，只要這批工件的尺寸總和不超過B。一批的處理時間等于這批中工件的最大處理時間。同一批處理的工件具有相同的起始時間和相同的完成時間。我們的目標是調(diào)度這些工件，使得接受工件的最大完成時間與拒絕工件的懲罰總值之和最小。
　　 我們首先給出了此類問題無論到達時間是否相同均是Np-困難的，且不存在近似比小于3/2的近似算法；之后，我們給出了工件具有相同到達時間的情況的2-近似算法；最后我們給出了工件可能具有不同到達時間的

3、問題的2+e近似算法，其中e>O可以為任意小的常數(shù)。
　　 另外，受實時機器視覺系統(tǒng)啟發(fā)，我們對并行批混合流水車間最小化最大完成時間的調(diào)度問題進行遺傳算法的研究。此問題描述如下：工件集J，中的n個工件需要被k-階段的流水車間處理，其中每個階段i(ie{1，2…，，k})有mi個平行批處理器。設(shè)Bip口表示階段i（i∈{1，2…，k}）的處理器p(pe{1，2…，mi})的容量。也就是說，在階段i的處理器p至多同時處理Bip個工件

4、。一批的處理時間等于這批工件中的最大處理時間。我們可以把一個工件看成一個具有k個任務(wù)的序列，每個任務(wù)針對一個階段，且任何任務(wù)必須在其前序任務(wù)處理完成之后才能夠被處理。設(shè)PU為工件Jj（Jj∈J)在階段i（i∈{1，2…，，K}）需要的處理時間。我們對此問題有以下的假定：1.每個階段的處理器只能處理此階段的任務(wù)；2.同一處理器在一個時刻只能處理一批。設(shè)Cij(s)為調(diào)度S中工件Jj（Jj∈J的第f（f∈{1，2….，k}）個任務(wù)的完成時間