利用梯度逼近最佳等待時間的資源分配技巧

Abstract

本論文提出一個利用梯度的最佳化技巧，它藉由適當分配計算資源以降低使用者的平均等待時間。本研究主要動機是來自許多大型科學計畫(例如蛋白質結構比對)或商業應用(例如線上遊戲)，必須隨時保持較佳的等待時間才能維持客戶滿意度與繼續營運的需求。我們首先將此資源分配問題從原整數空間Z^n轉換到歐氏空間R^n，然後利用所提出梯度技巧在R^n空間中求出轉換問題的最佳解，最後再將此最佳解轉換回原空間Z^n得到原問題的近似最佳解。由理論分析得知此技巧能線性收斂以及能逼近最佳等待時間，此外我們也輔以實驗結果來印證此技巧的收斂速度與解答品質。利用此技巧，系統設計者僅花費些許執行時間即能完成資源部署，並提供近似最佳平均等待時間。以上結果顯示若將此技巧應用到其它類似最佳化問題(例如繞徑問題)，則大有可能得到同樣的近似最佳結果。

In this dissertation, we propose a gradient-based technique that properly partitions and allocates resources in order to minimize the average waiting time for users in several computing environments. It is motivated by that there are many large-scale scientific projects (e.g., protein structure matching) and commercial applications (e.g., online game) and their waiting time needs to be lowered down for sustaining customer satisfaction. First, such a partition/allocation problem is mapped from the integer space Z^n to the Euclidean space R^n. Then, the optimal solution to the mapped problem in R^n is discovered by the proposed technique which optimally divides the resources and distributes them to multiple sites/nodes/locations. Finally, a near-optimal solution to the original problem is obtained by mapping the optimal solution to the mapped problem from R^n back to Z^n. The theoretical analyses show that the proposed technique converges linearly and generates a near-optimal average waiting time. We also present experimental results that confirm the convergence speed and solution quality of the proposed technique. Using the proposed technique, a system designer spends only a little execution time for deploying his/her resources and provides users with a near-optimal average waiting time. Importantly, the proposed technique can be extended to other similar optimization problems (e.g., vehicle routing problem) and can promisingly achieve the same near-optimal results.