若干調度問題的算法研究.pdf

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

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

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

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