簡單線性退化工作於多虛擬機台之資料中心能源管理問題

Abstract

本研究探討不可分割的退化性工件於多部虛擬機台上的排程問題。研究目的為找出最佳工作排序，使總完工時間最小化。本研究問題可轉換成k-ways partitioning problem (KPP)，此問題已被證明是NP-Hard。同時，我們使用KPP於本研究問題，並提出數個於不同虛擬機台數下的最佳解性質。根據此性質使用貪婪演算法(Graham 1966)，設計了遞迴性的啟發式演算法。最後，本研究使用模擬測試方法隨機產生多種情境，並以此驗證所提出的演算法的效能。

We study the scheduling problem of simple linear deteriorating jobs on identical parallel virtual machines of a data center, where jobs are non-resumable. Each virtual machine requires takes a setup time to boot up, which is multiplication of the number of virtual machines. Our goal is to minimize the total makespan. Our problem is reduced to the k-ways partitioning problem, which is known to be NP-hard by Graham (1966). We then explore some optimality properties of our problem with different number of identical parallel virtual machines. A recursive heuristic is developed which is based on the properties and Graham’s heuristic (1966). Finally, numerical studies are implemented to validate the performance of our heuristics.