Scheduling Tasks towards Energy Autarky: Benefits and Computational Costs of Flexibility
2026-07-03 • Discrete Mathematics
Discrete Mathematics
AI summaryⓘ
The authors study how to schedule energy-using tasks so that a battery and energy forecast alone can power them, with no outside energy needed. They focus on how flexible tasks are in timing, showing the problem is hard (NP-hard) even when tasks can only be done in two time slots. However, they find cases where scheduling is easier and can be solved quickly, especially when considering multiple factors like task flexibility and number. They also create a math model (ILP) to find the minimum extra energy needed and test it with real data, finding that more flexible task timing can save a lot of energy without much extra computing effort.
autarky problemjob schedulingenergy forecastbattery storagejob flexibilityNP-hardpolynomial-time solvablefixed-parameter tractabilityinteger linear programming (ILP)W-hardness
Authors
Robert Bredereck, Till Fluschnik, Klaus Heeger
Abstract
We study the autarky problem: given an energy forecast, a battery, and a set of energy-consuming jobs with time windows, decide whether all jobs can be scheduled without requiring external energy. We analyze the problem through the lens of job flexibility, defined as the number of time steps at which a job may be scheduled. We show that the problem is NP-hard already for flexibility two, even in restricted settings. On the positive side, we identify settings in which the problem is polynomial-time solvable, even for large flexibilities. Moreover, we obtain fixed-parameter tractability for combined parameters involving flexibility, such as the number of jobs. In contrast, we establish W-hardness when parameterized by maximum flexibility alone, even in a restricted setting. To complement our theoretical results, we formulate an integer linear program (ILP) that computes the minimum required external energy and evaluate it experimentally on instances derived from real-world energy-consumption and radiation data. The experiments indicate that increased job flexibility substantially reduces the need for external energy at moderate computational cost.