若干調(diào)度問題的算法研究.pdf

1、調(diào)度問題是組合最優(yōu)化領域和理論計算機科學領域中的一個重要分支，主要研究將稀缺資源分配給在一定時間內(nèi)不同任務的問題，分配過程也可以理解為一個決策過程。做決策目的是優(yōu)化一個或者多個目標，有單機調(diào)度，也有多機調(diào)度。從輸入信息的實時性來看，調(diào)度（排序）問題可以被分為離線、在線和半在線三類;從輸出結(jié)果的精確角度來看，調(diào)度問題的算法可被分為精確算法，近似算法（包含啟發(fā)式算法）。調(diào)度問題在實際生活中一直都有廣泛應用，比如計算機領域的節(jié)能調(diào)度，負載平衡

2、調(diào)度，作業(yè)調(diào)度，醫(yī)院中護士排班調(diào)度，運輸中的動態(tài)車輛調(diào)度，生產(chǎn)線上的流水調(diào)度，飛機的航班調(diào)度，鋼鐵生產(chǎn)過程中的批作業(yè)調(diào)度和流水調(diào)度等等，因此調(diào)度問題一直被人們所廣泛關注，并且是很多學者的研究課題。
　　本文分別研究了帶緩沖在線平行機調(diào)度、單機在線調(diào)度、帶運輸時間的流水調(diào)度和離線平行機調(diào)度等問題。
　　(1)帶緩沖在線平行機調(diào)度:文中給出了三個在線算法，并給出算法的競爭比分析，改進了已有的研究成果。文中提出了一個在線算法并證明

3、了在同型機的數(shù)量m＞51,緩沖區(qū)大小為「1.5m(])的情況，該算法競爭比為1.5;此外還提出在同型機數(shù)量為3的情況只需要6個緩沖區(qū)的最優(yōu)的在線算法，改進了之前需要9個緩沖區(qū)的最優(yōu)在線算法;文中還證明了在同類機的數(shù)量和緩沖區(qū)的均為m時，將競爭比從2+ε提升到2-1/m+ε，其中m是常數(shù)即機器的數(shù)量，ε＞0且足夠小。
　　(2)單機在線調(diào)度:文中研究了單機調(diào)度下帶有截至期限的搶占-重啟模型，在已知的WAL算法[16]中基礎上提出了一

4、個傳統(tǒng)啟發(fā)式算法D-WAL算法，其思想就是同時關注任務和作業(yè)的收益大小，分析實驗結(jié)果顯示D-WAL算法在性能上比只關注收益大小的WAL算法要好。
　　(3)帶運輸時間流水調(diào)度:文中考慮了一種特殊情況即所有的工件在機器B上加工時間都相同的時候，針對該種特殊情況可以發(fā)現(xiàn):存在一個最優(yōu)調(diào)度使得每個工件在機器A上的加工時間是非遞減的，而且工件執(zhí)行順序在機器A上的順序和在機器B和運輸機V是一樣的。利用這個性質(zhì)，文中給出了多項式時間的最優(yōu)調(diào)度