Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2507.08725 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916890958364672 |
|---|---|
| author | Schweisgut, Dominik Benoit, Anne Robert, Yves Meyerhenke, Henning |
| author_facet | Schweisgut, Dominik Benoit, Anne Robert, Yves Meyerhenke, Henning |
| contents | Large data and computing centers consume a significant share of the world's energy consumption. A prominent subset of the workloads in such centers are workflows with interdependent tasks, usually represented as directed acyclic graphs (DAGs). To reduce the carbon emissions resulting from executing such workflows in centers with a mixed (renewable and non-renewable) energy supply, it is advisable to move task executions to time intervals with sufficient green energy when possible. To this end, we formalize the above problem as a scheduling problem with a given mapping and ordering of the tasks. We show that this problem can be solved in polynomial time in the uniprocessor case. For at least two processors, however, the problem becomes NP-hard. Hence, we propose a heuristic framework called CaWoSched that combines several greedy approaches with local search. To assess the 16 heuristics resulting from different combinations, we also devise a simple baseline algorithm and an exact ILP-based solution. Our experimental results show that our heuristics provide significant savings in carbon emissions compared to the baseline. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_08725 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Carbon-Aware Workflow Scheduling with Fixed Mapping and Deadline Constraint Schweisgut, Dominik Benoit, Anne Robert, Yves Meyerhenke, Henning Distributed, Parallel, and Cluster Computing Large data and computing centers consume a significant share of the world's energy consumption. A prominent subset of the workloads in such centers are workflows with interdependent tasks, usually represented as directed acyclic graphs (DAGs). To reduce the carbon emissions resulting from executing such workflows in centers with a mixed (renewable and non-renewable) energy supply, it is advisable to move task executions to time intervals with sufficient green energy when possible. To this end, we formalize the above problem as a scheduling problem with a given mapping and ordering of the tasks. We show that this problem can be solved in polynomial time in the uniprocessor case. For at least two processors, however, the problem becomes NP-hard. Hence, we propose a heuristic framework called CaWoSched that combines several greedy approaches with local search. To assess the 16 heuristics resulting from different combinations, we also devise a simple baseline algorithm and an exact ILP-based solution. Our experimental results show that our heuristics provide significant savings in carbon emissions compared to the baseline. |
| title | Carbon-Aware Workflow Scheduling with Fixed Mapping and Deadline Constraint |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2507.08725 |