部分機(jī)器分批的平行機(jī)在線排序.pdf

1、關(guān)于兩臺(tái)恒同機(jī)器的排序問題,在分批排序和經(jīng)典排序中,大多數(shù)文獻(xiàn)都是考慮或者兩臺(tái)機(jī)器都是批處理機(jī)(批容量無界)或者兩臺(tái)機(jī)器都是正常機(jī)器(任何時(shí)刻最多只能加工一個(gè)工件,即批容量為1)。
　　在本文中,我們考慮了兩臺(tái)恒同機(jī)器的在線排序問題,但是我們主要考慮第一臺(tái)機(jī)器M1是平行批處理機(jī),而第二臺(tái)機(jī)器M2是正常機(jī)器。
　　第二章我們研究的在線排序問題可以描述為:有兩臺(tái)恒同機(jī);工件信息(到達(dá)時(shí)間和加工時(shí)間)在排序之初未知,而是隨著時(shí)間的

2、推移而逐個(gè)到達(dá);目標(biāo)是最小化兩臺(tái)機(jī)器上工件的最大完工時(shí)間。采用Graham等人[21]提出的排序問題的一般記號(hào),這個(gè)問題記為我們首先利用對(duì)手法構(gòu)造一個(gè)實(shí)例證明了該問題競(jìng)爭(zhēng)比的下界為1+α。接著提供了一個(gè)競(jìng)爭(zhēng)比為2在線算法。
　　第三章我們研究的在線排序問題可以描述為:有兩臺(tái)恒同機(jī);工件之間的序約束關(guān)系是平行鏈;工件鏈一旦到達(dá),該鏈上所有工件的信息才可知;所有工件的長(zhǎng)度都相同(即為p);目標(biāo)是最小化兩臺(tái)機(jī)器上工件的最大完工時(shí)間。采用