在線以及半在線排序調度問題研究.pdf

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

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

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

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