機(jī)器有兩種不同速度的平行工件在線排序.pdf

1、本文主要研究關(guān)于平行工件(parallel jobs)的排序(scheduling)問(wèn)題。有2m臺(tái)一致平行機(jī)，其中m臺(tái)速度為1，另外m臺(tái)速度為s(s>1)。每個(gè)平行工件J<,j>要求必須在m<,j>(m≥m<,j>≥1)臺(tái)機(jī)器上同時(shí)加工這個(gè)工件，但每個(gè)工件只能選取同一種速度的機(jī)器。工件在零時(shí)刻都已到達(dá)，但他們的加工時(shí)間是未知的，只有當(dāng)工件加工完成時(shí)才可知道。這種在線模型稱為無(wú)預(yù)見(jiàn)的(nonclairvoyant，簡(jiǎn)記為ncv)，目標(biāo)是極

2、小化最大完工時(shí)間(C<,max>)。用三參數(shù)表示法，我們的問(wèn)題可以表示為Q2m|r<,j>=O，m<,j>，on-line-ncu|C<,max>。我們對(duì)該排序問(wèn)題提出了相應(yīng)的在線算法，并采用國(guó)際上通用的算法評(píng)價(jià)標(biāo)準(zhǔn)競(jìng)爭(zhēng)比(competitive ratio)來(lái)衡量、分析給出的算法。通過(guò)構(gòu)造壞的實(shí)例，我們給出了問(wèn)題的下界(lowerbound)。同時(shí)研究了該模型在一定限制下的特殊情形，得到了更好的競(jìng)爭(zhēng)比。 本文的主要結(jié)果如下：