Resource selection for tasks with time requirements using spectral clustering

Nikolaos D. Doulamis, Panagiotis Kokkinos, Emmanouel Varvarigos

Research output: Contribution to journalArticleResearchpeer-review

21 Citations (Scopus)

Abstract

Resource selection and task assignment are basic operations in distributed computing environments, like the grid and the cloud, where tasks compete for resources. The decisions made by the corresponding algorithms should be judged based not only on metrics related to user satisfaction, such as the percentage of tasks served without violating their quality-of-service (QoS) requirements, but also based on resource-related performance metrics, such as the number of resources used to serve the tasks and their utilization efficiency. In our work, we focus on the case of tasks with fixed but not strict time requirements, given in the form of a requested start and finish time. We propose an algorithm for assigning tasks to resources that minimizes the violations of the tasks' time requirements while simultaneously maximizing the resources' utilization efficiency for a given number of resources. The exact time scheduling of the tasks on the resources is then decided by taking into account the time constraints. The proposed scheme exploits concepts derived from graph partitioning, and groups together tasks so as to 1) minimize the time overlapping of the tasks assigned to a given resource and 2) maximize the time overlapping among tasks assigned to different resources. The partitioning is performed using a spectral clustering methodology through normalized cuts. Experimental results show that the proposed algorithm outperforms other scheduling algorithms for different values of the granularity and the load of the task requests.

Original languageEnglish
Pages (from-to)461-474
Number of pages14
JournalIEEE Transactions on Computers
Volume63
Issue number2
DOIs
Publication statusPublished - Feb 2014
Externally publishedYes

Keywords

  • graph partitioning
  • interval scheduling
  • Resource assignment
  • soft time constraints
  • spectral clustering

Cite this