  Multi-server jobs are imperative in modern cloud computing systems. A
noteworthy feature of multi-server jobs is that, they usually request multiple
computing devices simultaneously for their execution. How to schedule
multi-server jobs online with a high system efficiency is a topic of great
concern. Firstly, the scheduling decisions have to satisfy the service locality
constraints. Secondly, the scheduling decisions needs to be made online without
the knowledge of future job arrivals. Thirdly, and most importantly, the actual
service rate experienced by a job is usually in fluctuation because of the
dynamic voltage and frequency scaling (DVFS) and power oversubscription
techniques when multiple types of jobs co-locate. A majority of online
algorithms with theoretical performance guarantees are proposed. However, most
of them require the processing speeds to be knowable, thereby the job
completion times can be exactly calculated. To present a theoretically
guaranteed online scheduling algorithm for multi-server jobs without knowing
actual processing speeds apriori, in this paper, we propose ESDP (Efficient
Sampling-based Dynamic Programming), which learns the distribution of the
fluctuated processing speeds over time and simultaneously seeks to maximize the
cumulative overall utility. The cumulative overall utility is formulated as the
sum of the utilities of successfully serving each multi-server job minus the
penalty on the operating, maintaining, and energy cost. ESDP is proved to have
a polynomial complexity and a logarithmic regret, which is a State-of-the-Art
result. We also validate it with extensive simulations and the results show
that the proposed algorithm outperforms several benchmark policies with
improvements by up to 73%, 36%, and 28%, respectively.
