平行機台工作排程及運算資源獲取之規劃

Abstract

在過去十年內，雲端運算已經獲得越來越多的關注。雲端運算的架構可以被 視為是許多散佈在網際網路上的非等效平行機台。在本研究中，我們將探討非等 效平行機台排程以及資源獲取成本安排的問題。雲端服務經紀人接受客戶委託之 計算工作，並向雲端服務供應商購買運算資源以處理這些工作。我們的模型中， 不同的平行機台根據速度以及供應商的策略而被包裝成為許多套裝方案。而為了 提供更彈性化的購買選擇，這些組合依照一個新的機制來定價。為了將總成本(包含總加權延遲時間以及資源獲取成本)最小化，經紀人所要做的決定是選擇所需的套裝方案，並在其中的機台上安排工作。在本研究中，我們使用整數規劃模式描述此問題，並且提出許多演算法將總成本最小化。我們將十種文獻中對於平行機台排程問題所提出的啟發式演算法修改以適應此模型，並以此作為初始解，再將這些初始解用新的neighborhood structures所修改過的禁忌搜尋法和基因演算法做更進一步的改善。對於上述所提出的各種方法，我們以一系列的電腦模擬實驗來驗證各種演算法的效能，效率等表現。根據實驗結果，我們所使用的禁忌搜尋法以及基因演算法可以在短時間內獲得明顯的改善。並且禁忌搜尋法可在短時間內取得良好的近似解。

Cloud computing has been attracting considerable attention since the last decade. This study considers a decision problem formulated from the use of computing ser-vices over the Internet. An agent receives orders of computing tasks from clients and on the other hand acquires computing resources from computing service providers to fulfill the requirements of the clients. The processors are bundled as packages according to their speeds and the business strategies of the providers. The packages are rated at a certain pricing scheme to provide flexible purchasing options to the agent. The decision of the agent is to select the packages to acquire from the service providers and then schedule the tasks of the client onto the processors of the ac-quired packages such that the total cost, including acquisition cost and scheduling cost (weighted total tardiness), is minimum. In this study, we present an integer programming model to formulate the problem and propose several solution methods to minimize the total cost. Ten well-known heuristics of parallel-machine scheduling are adapted to fit into the studied problem so as to provide initial solutions. Tabu search (TS) and genetic algorithm (GA) are tailored to reflect the problem’s nature to improve upon the initial solutions. We conduct a series of computational exper-iment to evaluate the effectiveness and efficiency of all of the proposed algorithms. The results of the numerical experiments reveal that the proposed TS and GA can attain significant improvements. Moreover, TS outperforms GA in achieving im-pressive solution quality in a short time period.