University of Twente Student Theses
As of Friday, 8 August 2025, the current Student Theses repository is no longer available for thesis uploads. A new Student Theses repository will be available starting Friday, 15 August 2025.
A Novel Heuristic for Directed Acyclic Graph Task Scheduling using Longest Betweenness Centrality
Damink, Niek P. (2025) A Novel Heuristic for Directed Acyclic Graph Task Scheduling using Longest Betweenness Centrality.
|
PDF
559kB |
| Abstract: | Task scheduling is a well-known NP-hard problem that involves efficiently allocating computational tasks across available resources. Existing heuristic approaches, such as HEFT and MinMin, typically rely on basic task properties and may fail to capture deeper structural dependencies in the task graph. In this work, we propose a novel list-scheduling heuristic based on Longest Betweenness Centrality (LBC), a metric designed to quantify a task's influence by evaluating its presence on long dependency paths. We introduce six LBC-based ranking methods, including variants that are source-based and successor-weighted. The most promising variant, LBC-SRL, estimates task criticality by analyzing each task's current critical dependencies. Experimental evaluations across five synthetic DAG generation models and multiple processor configurations demonstrated that LBC-SRL consistently outperforms classical heuristics such as MinMin, HCPT and PEFT. On DAGs with a high density, LBC-SRL achieves performance comparable to HEFT. Although HEFT remains the top performer overall, pairwise comparisons reveal that LBC-SRL frequently matches its performance and occasionally even surpasses it. These findings illustrate the potential of incorporating global graph-theoretical metrics into task scheduling. |
| Item Type: | Essay (Bachelor) |
| Faculty: | EEMCS: Electrical Engineering, Mathematics and Computer Science |
| Subject: | 54 computer science |
| Programme: | Computer Science BSc (56964) |
| Link to this item: | https://purl.utwente.nl/essays/107400 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page