平行同型機(jī)半在線排序問(wèn)題的若干研究.pdf

1、該文主要研究?jī)深?lèi)同型(identical)機(jī)關(guān)在線排序問(wèn)題,分析確定性半在線算法的競(jìng)爭(zhēng)比(competitive ratio),一類(lèi)是帶機(jī)器費(fèi)用的半在線排序問(wèn)題,一類(lèi)是帶機(jī)器準(zhǔn)備時(shí)間的極大化機(jī)器負(fù)載的半在線排序問(wèn)題.全文共分三章.第一章是緒論部分,主要介紹排序問(wèn)題的背景內(nèi)容以及相應(yīng)的準(zhǔn)備知識(shí).第二章研究一類(lèi)新的帶機(jī)器費(fèi)用的同型機(jī)排序問(wèn)題(List model),在預(yù)先知道工件最大加工時(shí)間這種情況下,我們?cè)O(shè)計(jì)出了競(jìng)爭(zhēng)比至多為156(符號(hào)略

2、)/24≈1.5309的半在線算法,并證明問(wèn)題的下界為4/3.另外,在預(yù)先知道工件總加工時(shí)間這種情況下,我們?cè)O(shè)計(jì)出了競(jìng)爭(zhēng)比至多為2(符號(hào)略)的半在線算法,并證明問(wèn)題的下界為(37+1306(符號(hào)略)/63≈1.161).第三章研究以極大化最小機(jī)器負(fù)載為目標(biāo)的機(jī)器帶準(zhǔn)備時(shí)間的同型機(jī)排序問(wèn)題.我們LS算法是最好的在線算法,它的競(jìng)爭(zhēng)比為1/m.同時(shí),我們給出了求解兩臺(tái)機(jī)的預(yù)先知道工件最大加工時(shí)間、預(yù)先知道工件集的總加工時(shí)間以及工件從大到小到達(dá)