在線以及半在線排序調(diào)度問(wèn)題研究.pdf

1、上海交通大學(xué)博士后研究報(bào)告題目：英文題目：姓名：研究方向：博士后編號(hào)：合作導(dǎo)師：提交日期：在線以及半在線排序調(diào)度問(wèn)題研究Onlineandsemi—onlineschedulingproblems曹茜專業(yè)：管理科學(xué)與工程生產(chǎn)計(jì)劃與排序調(diào)度85263萬(wàn)國(guó)華職稱：教授2012年5月上海交通大學(xué)(上海)一卜|海交通大學(xué)博七后研究報(bào)告第ii頁(yè)爭(zhēng)比也為：的最優(yōu)算法OM。第四章考慮了三個(gè)與緩沖區(qū)有關(guān)的兩臺(tái)同型機(jī)半在線排序調(diào)度問(wèn)題。第一個(gè)問(wèn)題考慮已知

2、最大工件尺寸且?guī)А珎€(gè)長(zhǎng)度為k(忌≥1)的緩沖區(qū)的問(wèn)題，我們給出了問(wèn)題的下界為g，同時(shí)設(shè)計(jì)了一個(gè)競(jìng)爭(zhēng)比為；的算法。第二個(gè)問(wèn)題考慮已知工件按照加工時(shí)間非增序到達(dá)且?guī)б粋€(gè)長(zhǎng)度為1的緩沖區(qū)的兩臺(tái)同型機(jī)半在線排序調(diào)度問(wèn)題，我們得到了問(wèn)題的下界為；。第三個(gè)問(wèn)題考慮已知工件加工時(shí)間有界且?guī)б粋€(gè)長(zhǎng)度為1的緩沖區(qū)的兩臺(tái)同型機(jī)半在線排序調(diào)度問(wèn)題，我們給出了問(wèn)題的一個(gè)下界max卜芻半)，m叫芻半)jm叫；半)，同時(shí)對(duì)1≤t≤；設(shè)計(jì)了～個(gè)競(jìng)爭(zhēng)比為maX警，；)

3、的算法BB，且該算法在半≤t≤墨2是最優(yōu)的。第五章考慮了所有工件加工時(shí)間是有界的兩臺(tái)同類機(jī)半在線排序調(diào)度問(wèn)題，，目標(biāo)同樣是最小化時(shí)間表長(zhǎng)。我們首先對(duì)問(wèn)題證明了一些下界，并研究TLS算法的競(jìng)爭(zhēng)比。首先我們?cè)趯?duì)任意s和亡得到上s算法的競(jìng)爭(zhēng)比為min料，了sl，￡)，結(jié)合我們給出的下界可知Ls算法在s≥盟世學(xué)業(yè)且亡≥壽時(shí)是最優(yōu)的，競(jìng)爭(zhēng)比為了sl；在N≤s≤NlJ|1≤t≤mins_與，壽)時(shí)是最優(yōu)的，競(jìng)爭(zhēng)比為t；在1≤s≤址2叢且t≥蠆ls時(shí)

4、是最優(yōu)的，競(jìng)爭(zhēng)比為百2sTl。然后我們又對(duì)LS算法進(jìn)行深入分析，得至IJLS算法在max鵒將，舞器㈦≤；2axt—麗耳Tj礦，兩了可百訂i口，∑‘∑；和maX坐鼉憋茜磐案署罟掣，丙sN，N一。Ⅳs，1≤t≤min。2s(2NⅣI，)一22。NⅣ1，芬等)是最優(yōu)的。進(jìn)一步，我們證明了其在s≤N1且t2未箬帚b時(shí)的競(jìng)爭(zhēng)比為半，并在盟塹乒巫≤s≤N1_Emax未箬器，由)≤￡≤壽時(shí)是最優(yōu)的。最后我們?cè)O(shè)計(jì)了兩個(gè)改進(jìn)的算法，在1325≤s≤生乎且