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

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

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