版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
1、排序論是組合優(yōu)化的一個重要分支,對它的研究有著深刻的理論意義和重要的應用前景.在線排序和分批排序是近年來排序論研究中十分活躍的前沿課題.本文對兩個在線平行分批排序問題進行了研究.論文的主要內容如下:
第一章簡單介紹了排序問題的相關定義、記號及相關知識.
第二章考慮了兩臺機器在線分批排序問題,其中一臺是批處理機,一臺是標準機;目標函數為極小化工件的最大完工時間.利用Graham等人(1979)引入的三參數法,該
2、問題可表示為
P2|on-line,p-batch,B1=∞,B2=1|Cmax.
對上述一般問題,我們首先給出了一個改進的下界1+β,其中β=√2/2≈0.707.接著給出了兩個競爭比為2的簡單在線算法.最后設計了兩個有待進一步研究的在線算法.對限制問題
P2|on-line,p-batch,agreeable(rj,pj),B1=∞,B2=1|Cmax,
我們給出了一個競爭比為
3、(√5+1/2)的最好可能在線算法.
第三章考慮了單機在線分批排序問題,工件帶有運輸時間,目標函數為最小化工件的最大運輸完工時間.利用Graham等人(1979)引入的三參數法,該問題可表示為:
1|p-batch,on-line,B=∞|Lmax.對于限制問題
1|p-batch,on-line,Pj≥qj,B=∞|Lmax,
1|p-batch,on-line,agreeabl
4、e(pj,qj),B=∞|Lmax和
1|p-batch,on-line,Pj=P,B=∞|Lmax,
我們給出了一個競爭比為(√5+1/2)的最好可能的在線彈性算法.對于限制問題
1|p-batch,on-line,qmax\qmin≤1+α,B=∞|Lmax,我們證明了Poon和Yu(2005)的彈性算法的競爭比不超過(√5+1/2),也就是說,該彈性算法仍是最好的.
第四章總
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 兩類特殊的在線分批排序問題.pdf
- 兩類平行機分批排序問題.pdf
- 兩類加權冪和形式的分批排序問題.pdf
- 機器具有學習效應的兩類分批排序問題.pdf
- 兩類平行機并行分批排序問題的協(xié)調機制和算法研究.pdf
- 一類平行機在線分批排序問題.pdf
- 171.兩類平行機排序問題的在線算法
- 兩類新型排序問題的算法研究.pdf
- 幾類新型在線分批排序問題.pdf
- 兩類資源受限的排序問題研究.pdf
- 兩類供應鏈排序問題.pdf
- 單機在線分批排序和平行機半在線排序問題.pdf
- 單機分批排序和平行機在線排序問題.pdf
- 兩類可拒絕同類機排序問題.pdf
- 一類訂單排序及兩類平行機排序問題.pdf
- 兩類在線算法問題的研究
- 一類訂單排序及兩類平行機排序問題
- 兩類在線算法問題的研究.pdf
- 兩類半在線排序模型的算法性能分析.pdf
- 分批排序問題.pdf
評論
0/150
提交評論