Prior node selection for scheduling workflows in a heterogeneous system

Hidehiro Kanemitsu*, Masaki Hanada, Hidenori Nakazato

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)


Many workflow scheduling algorithms for heterogeneous systems have been developed to satisfy multiple requirements such as minimizing schedule length while maximizing throughput. In particular, in list-based scheduling approaches, the schedule length depends on the given nodes as well as the task allocation and ordering policies. This is because the scheduling priority is derived by averaging the execution time and communication time of the given nodes. If the set of nodes can be adjusted before the scheduling tasks, a small schedule length can be achieved. In this paper, we propose a prior node selection algorithm, called lower bound based candidate node selection (LBCNS) to select a subset of given nodes to minimize the schedule length while fairly scheduling each job. Our proposal has two approaches: (i) LBCNS_DEFAULT, which considers the job characteristics and each node's performance, and (ii) priority-based LBCNS, which additionally takes each scheduling priority into account for a dedicated task scheduling algorithm. The experimental results of extensive simulations show that LBCNS_DEFAULT has the best fairness for scheduling multiple workflow jobs, while priority-based LBCNS achieves the minimum schedule length with the highest efficiency for a single workflow job and multiple workflow jobs.

Original languageEnglish
Pages (from-to)155-177
Number of pages23
JournalJournal of Parallel and Distributed Computing
Publication statusPublished - 2017 Nov


  • DAG
  • Heterogeneous system
  • Node grouping
  • Processor grouping
  • Task scheduling
  • Workflow scheduling

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Artificial Intelligence


Dive into the research topics of 'Prior node selection for scheduling workflows in a heterogeneous system'. Together they form a unique fingerprint.

Cite this