Modeling and solving workflow scheduling problems on shared computing units with makespan and energy cost objectives

Abstract This research addresses the workflow scheduling problem on shared computing units. A set of interdependent tasks, originating from a workflow or project, requires processing by computing units such as virtual machines, while respecting precedence constraints and capacity restrictions, for example, in terms of virtual central processing units. The computing units may be heterogeneous or homogeneous in their capacities and cost rates. This problem arises in cloud environments that allow multiple tasks to share resources to improve utilization and reduce energy consumption in accordance with a race-to-idle strategy. We present different mathematical model formulations for this integrated model of workflow scheduling and vector bin packing: a mixed-integer program based on the pulse disaggregated discrete-time formulation, a mixed-integer quadratically constrained program, and a constraint programming satisfiability model, which can be further extended to related scheduling settings. The formulations are evaluated under a makespan objective and under a weighted-sum objective combining makespan and active-unit energy cost. Computational experiments with the Gurobi Optimizer and the CP-SAT solver show that the pulse-based formulation provides the strongest bounds and proves optimality most often, whereas the constraint programming formulation quickly finds high-quality incumbent solutions for the combined objective.

Authors

Institutions

Publication Details

Journal
Central European Journal of Operations Research
Published
2026-11-16
DOI
https://doi.org/10.1007/s10100-026-01048-4
Primary Topic
Scheduling and Optimization Algorithms
Type
article
Field-Weighted Citation Impact
0.00
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
article

Modeling and solving workflow scheduling problems on shared computing units with makespan and energy cost objectives

Andréas Fink, Anke Stieber
1 links
Central European Journal of Operations Research
Scheduling and Optimization Algorithms
article

Modeling and solving workflow scheduling problems on shared computing units with makespan and energy cost objectives

Andréas Fink, Anke Stieber
article en

Abstract

Abstract This research addresses the workflow scheduling problem on shared computing units. A set of interdependent tasks, originating from a workflow or project, requires processing by computing units such as virtual machines, while respecting precedence constraints and capacity restrictions, for example, in terms of virtual central processing units. The computing units may be heterogeneous or homogeneous in their capacities and cost rates. This problem arises in cloud environments that allow multiple tasks to share resources to improve utilization and reduce energy consumption in accordance with a race-to-idle strategy. We present different mathematical model formulations for this integrated model of workflow scheduling and vector bin packing: a mixed-integer program based on the pulse disaggregated discrete-time formulation, a mixed-integer quadratically constrained program, and a constraint programming satisfiability model, which can be further extended to related scheduling settings. The formulations are evaluated under a makespan objective and under a weighted-sum objective combining makespan and active-unit energy cost. Computational experiments with the Gurobi Optimizer and the CP-SAT solver show that the pulse-based formulation provides the strongest bounds and proves optimality most often, whereas the constraint programming formulation quickly finds high-quality incumbent solutions for the combined objective.

Central European Journal of Operations Research
Helmut Schmidt University (DE)
Scheduling and Optimization Algorithms
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon