可拒絕平行批平行機(jī)與在線平行批兩臺(tái)一致機(jī)排序.pdf

1、平行批排序是現(xiàn)代排序的一個(gè)重要模型.其優(yōu)點(diǎn)是多個(gè)工件可以放在同一批中同時(shí)進(jìn)行加工,從而提高工作效率.其中,一個(gè)工件批的加工時(shí)間定義為這批中所包含的最長(zhǎng)工件的加工時(shí)間.
　　 在這篇文章中,我們研究了兩類平行批排序問(wèn)題.首先我們研究了工件有到達(dá)時(shí)間并且可拒絕的m臺(tái)無(wú)界平行批平行處理機(jī)最小化最大完工時(shí)間的排序問(wèn)題.在該問(wèn)題中,如果拒絕-個(gè)工件,那么要花費(fèi)一定的懲罰費(fèi)用；如果接受這個(gè)工件,那么該工件被分配到m臺(tái)機(jī)器中的一臺(tái)上分批加工.

2、目標(biāo)函數(shù)是最小化接受工件的最大完工時(shí)間與拒絕工件的費(fèi)用之和.當(dāng)m是-個(gè)給定的常數(shù)時(shí),我們給出了這個(gè)問(wèn)題的一個(gè)擬多項(xiàng)式時(shí)間算法和一個(gè)完全多項(xiàng)式時(shí)間近似方案.
　　 其次我們研究了在線一致批處理機(jī)最小化最大完工時(shí)間的排序問(wèn)題.在該問(wèn)題中,我們有兩個(gè)批處理機(jī),一臺(tái)機(jī)器的速度是1,另一臺(tái)機(jī)器的速度為v,其中0

3、是方程β3+3β2+(3-1/v)β-1/v=0的正根.對(duì)該問(wèn)題,我們首先建立了其競(jìng)爭(zhēng)比下界:當(dāng)0